Paper: Optimal Incremental Parsing via Best-First Dynamic Programming

ACL ID D13-1071
Title Optimal Incremental Parsing via Best-First Dynamic Programming
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2013
Authors

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.