Liang Huang, Kenji Sagae: “Dynamic Programming for Linear-time Shift-Reduce Parsing”

July 14, 2010 | Uppsala, Sweden

Speaker: Liang Huang, Kenji Sagae
Host: ACL 2010: The 48th Annual Meeting of the Association for Computational Linguistics

Incremental parsing techniques such as shift-reduce have gained significant 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 in most cases dynamic programming is indeed possible for shift-reduce parsing, by merging “equivalent” stacks based on feature values. Empirically, our algorithm leads to up to 5-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 achieves the highest accuracy and the fastest speed among dependency parsers trained on the Treebank.