Optimal Incremental Parsing via Best-First Dynamic Programming

Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 758–768, Seattle, Washington, USA, 18-21 October 2013. c⃝2013 Association for Computational Linguistics Optimal Incremental Parsing via Best-First Dynamic Programming∗ Kai Zhao1 James Cross1 1Graduate Center City University of New York 365 Fifth Avenue, New York, NY 10016 {kzhao,jcross}@gc.cuny.edu Liang Huang1,2 2Queens College City University of New York 6530 Kissena Blvd, Queens, NY 11367 huang@cs.qc.cuny.edu Abstract We present the first provably optimal polyno- mial time dynamic programming (DP) algo- rithm for best-first shift-reduce parsing, which applies the DP idea of Huang and Sagae (2010) to the best-first parser of Sagae and Lavie (2006) in a non-trivial way, reducing the complexity of the latter from exponential to polynomial. We prove the correctness of our algorithm rigorously. Experiments con- firm that DP leads to a significant speedup on a probablistic best-first shift-reduce parser, and makes exact search under such a model tractable for the first time. 1 Introduction Best-first parsing, such as A* parsing, makes con- stituent parsing efficient, especially for bottom-up CKY style parsing (Caraballo and Charniak, 1998; Klein and Manning, 2003; Pauls and Klein, 2009). Traditional CKY parsing performs cubic time exact search over an exponentially large space. Best-first parsing significantly speeds up by always preferring to explore states with higher probabilities. In terms of incremental parsing, Sagae and Lavie (2006) is the first work to extend best-first search to shift-reduce constituent parsing. Unlike other very fast greedy parsers that produce suboptimal results, this best-first parser still guarantees optimality but requires exponential time for very long sentences in the worst case, which is intractable in practice. Because it needs to explore an exponentially large space in the worst case, a bounded priority queue becomes necessary to ensure limited parsing time. ∗This work is mainly supported by DARPA FA8750-13-2- 0041 (DEFT), a Google Faculty Research Award, and a PSC- CUNY Award. In addition, we thank Kenji Sagae and the anonymous reviewers for their constructive comments. On the other hand, Huang and Sagae (2010) ex- plore the idea of dynamic programming, which is originated in bottom-up constituent parsing algo- rithms like Earley (1970), but in a beam-based non best-first parser. In each beam step, they enable state merging in a style similar to the dynamic pro- gramming in bottom-up constituent parsing, based on an equivalence relation defined upon feature val- ues. Although in theory they successfully reduced the underlying deductive system to polynomial time complexity, their merging method is limited in that the state merging is only between two states in the same beam step. This significantly reduces the num- ber of possible merges, because: 1) there are only a very limited number of states in the beam at the same time; 2) a lot of states in the beam with differ- ent steps cannot be merged. We instead propose to combine the idea of dy- namic programming with the best-first search frame- work, and apply it in shift-reduce dependency pars- ing. We merge states with the same features set …

Content truncated to 500 words