Paper: Dynamic Programming for Linear-Time Incremental Parsing

ACL ID P10-1110
Title Dynamic Programming for Linear-Time Incremental Parsing
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2010

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 op- posed to dynamic programming. We show that, surprisingly, dynamic programming is in fact possible 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 depen- dency parser with no loss in accuracy. Bet- ter search also leads to better learning, and our final parser outperforms all previously reported dependency parsers for English and Chinese, yet is much faster.