Parsing is a fundamental problem in Natural Language Processing, and has wide applications in other NLP problems such as Machine Translation and Summarization. Most statistical parsing algorithms can be divided into two broad categories: dynamic programming (e.g. CKY), and incremental parsing (e.g. shift-reduce). These two categories are largely disjoint, where the former provides principled (exact) search while the latter is faster, psycholinguistically motivated, but suffers from greedy search. This talk tries to bring together these two techniques, by injecting dynamic programming into incremental parsing, which provides fast and high quality search that also resembles human sentence processing.
More specifically, incremental parsing techniques such as shift-reduce have gained popularity thanks to their efficiency, but there remains a major problem: the search is greedy and only explores a tiny fraction of the whole space (even with beam search) as opposed to dynamic programming. We show that, surprisingly, dynamic programming is in fact possible and polynomial-time for many shift-reduce parsers, by merging ?equivalent? stacks based on feature values. Empirically, our algorithm yields up to a five-fold speedup over a state-of-the-art shift-reduce dependency parser with no loss in accuracy. Better search also leads to better learning, and our final parser outperforms all previously reported dependency parsers for English and Chinese, yet is much faster.
This is a joint work with Kenji Sagae (USC/ICT).
Biography
Liang Huang is a Research Assistant Professor at University of Southern California (USC), and a Research Scientist at USC Information Sciences Institute (ISI). He received his PhD from the University of Pennsylvania in 2008, and worked as a Research Scientist at Google before moving back to ISI where he did two internships. He is mainly interested in the theoretical aspects of computational linguistics, in particular, efficient algorithms in parsing and machine translation, generic dynamic programming, and formal properties of synchronous grammars. His work received a Best Paper Award at ACL 2008, and Best Paper Nominations at ACL 2007, EMNLP 2008, and ACL 2010.
http://www.isi.edu/~lhuang