Dynamic Programming for Linear-Time Incremental Parsing

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1077–1086, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics Dynamic Programming for Linear-Time Incremental Parsing Liang Huang USC Information Sciences Institute 4676 Admiralty Way, Suite 1001 Marina del Rey, CA 90292 lhuang@isi.edu Kenji Sagae USC Institute for Creative Technologies 13274 Fiji Way Marina del Rey, CA 90292 sagae@ict.usc.edu Abstract 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. 1 Introduction In terms of search strategy, most parsing al- gorithms in current use for data-driven parsing can be divided into two broad categories: dy- namic programming which includes the domi- nant CKY algorithm, and greedy search which in- cludes most incremental parsing methods such as shift-reduce.1 Both have pros and cons: the for- mer performs an exact search (in cubic time) over an exponentially large space, while the latter is much faster (in linear-time) and is psycholinguis- tically motivated (Frazier and Rayner, 1982), but its greedy nature may suffer from severe search er- rors, as it only explores a tiny fraction of the whole space even with a beam. Can we combine the advantages of both ap- proaches, that is, construct an incremental parser 1McDonald et al. (2005b) is a notable exception: the MST algorithm is exact search but not dynamic programming. that runs in (almost) linear-time, yet searches over a huge space with dynamic programming? Theoretically, the answer is negative, as Lee (2002) shows that context-free parsing can be used to compute matrix multiplication, where sub-cubic algorithms are largely impractical. We instead propose a dynamic programming al- ogorithm for shift-reduce parsing which runs in polynomial time in theory, but linear-time (with beam search) in practice. The key idea is to merge equivalent stacks according to feature functions, inspired by Earley parsing (Earley, 1970; Stolcke, 1995) and generalized LR parsing (Tomita, 1991). However, our formalism is more flexible and our algorithm more practical. Specifically, we make the following contributions: • theoretically, we show that for a large class of modern shift-reduce parsers, dynamic pro- gramming is in fact possible and runs in poly- nomial time as long as the feature functions are bounded and monotonic (which almost al- ways holds in practice); • practically, dynamic programming is up to five times faster (with the same accuracy) as conventional beam-search on top of a state- of-the-art shift-reduce dependency parser; • as a by-product, dynamic …

Content truncated to 500 words