Better k-best Parsing, Hypergraphs, and Dynamic Programming

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=kSlBxsNNOEw


Duration: 53:57
331 views
5

Joint work with David Chiang (University of Maryland) K-best parsing (and k-best processing in general) has become a popular technique in natural language processing. However, fast and exact k-best algorithms are largely unknown to the parsing community. In this work, we develop efficient algorithms for exact k-best derivation trees in the framework of directed monotonic hypergraphs. To demonstrate the efficiency, scalability  and accuracy of these algorithms, we present experiments on Bikel's implementation of Collins' lexicalized PCFG model, and on Chiang's CFG-based decoder for hierarchical phrase-based translation. We show in particular how the improved output of our algorithms has the potential to improve results from parse reranking systems and other applications. These algorithms have been re-implemented by other researchers in the field, including Eugene Charniak for his n-best parser, Ryan McDonald and Microsoft Research for dependency parsers, and the USC/ISI team for the CKY-based decoder in their syntax-based machine translation system. All of these experiments confirmed the findings in our work. Reference: Liang Huang and David Chiang (2005). Better k-best Parsing. Proceedings of the 9th International Workshop on Parsing Technologies (IWPT). http://www.cis.upenn.edu/~lhuang3/huang-iwpt.pdf



Other Videos By Microsoft Research


2016-09-0610 Rules for Strategic Innovators
2016-09-06Which Supervised Learning Method Works Best for What?  An Empirical Comparison
2016-09-06Using ACTIVboard In Interactive Presentations
2016-09-06Secure Trusted Overlay Networks for Robust Privacy-Protecting Communication
2016-09-06Dialogue Session: Worklife Balance and the Retention of Talent
2016-09-06From textons to parts: Local image features for texture and object recognition
2016-09-06Efficient Actions in Dynamic Auction Environment
2016-09-06Two Network Coding Talks for the price of one: Security, Low Complexity
2016-09-06Some recent results in camera calibration and shape reconstruction
2016-09-06Implicit Feedback: Techniques for Deployment and Evaluation
2016-09-06Better k-best Parsing, Hypergraphs, and Dynamic Programming
2016-09-06Rock 'n Roll : Earthquake & Disaster Preparedness
2016-09-06Understanding Customers: Shaping Our Future through Understanding Social Change
2016-09-06Fast Database and Data Streaming Operations using Graphics Processors
2016-09-06Hyperparameter and Kernel Learning for Graph Based Semi-Supervised Classification
2016-09-06Multi-Engine Machine Translation Guided by Explicit Word Matching
2016-09-06Using Compression Models to Filter Spam; Exploiting Structural Information for Categorization
2016-09-06The Man Who Knew Too Much: Alan Turing and the Invention of the Computer [1/4]
2016-09-06Estimation of intrinsic dimensionality using high-rate vector quantization
2016-09-06Abducted: How People Come to Believe They Were Kidnapped by Aliens [1/11]
2016-09-06Spontaneous Speech: Challenges and Opportunities for Parsing


Tags:
microsoft research