emnlp emnlp2013 emnlp2013-146 emnlp2013-146-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Kai Zhao ; James Cross ; Liang Huang
Abstract: We present the first provably optimal polynomial time dynamic programming (DP) algorithm 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 confirm 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.
Alfred V. Aho and Jeffrey D. Ullman. 1972. The Theory of Parsing, Translation, and Compiling, volume I: Parsing of Series in Automatic Computation. Prentice Hall, Englewood Cliffs, New Jersey. Sharon A Caraballo and Eugene Charniak. 1998. New figures of merit for best-first probabilistic chart parsing. Computational Linguistics, 24(2):275–298. Jay Earley. 1970. An efficient context-free parsing algorithm. Communications of the ACM, 13(2):94–102. Jason Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proceedings of COLING. Liang Huang and Kenji Sagae. 2010. Dynamic programming for linear-time incremental parsing. In Proceedings of ACL 2010. Dan Klein and Christopher D Manning. 2003. A* parsing: Fast exact Viterbi parse selection. In Proceedings of HLT-NAACL. Dan Klein and Christopher D Manning. 2005. Parsing and hypergraphs. In New developments in parsing technology, pages 35 1–372. Springer. Donald Knuth. 1977. A generalization of Dijkstra’s algorithm. Information Processing Letters, 6(1). Marco Kuhlmann, Carlos G ´omez-Rodr ı´guez, and Giorgio Satta. 2011. Dynamic programming algorithms for transition-based dependency parsers. In Proceedings of ACL. Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005. Online large-margin training of dependency parsers. In Proceedings of the 43rd ACL. Mark-Jan Nederhof. 2003. Weighted deductive parsing and Knuth’s algorithm. Computational Linguistics, pages 135–143. Joakim Nivre. 2008. Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 34(4):513–553. Adam Pauls and Dan Klein. 2009. Hierarchical search for parsing. In Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 557–565. Association for Computational Linguistics. Kenji Sagae and Alon Lavie. 2006. A best-first probabilistic shift-reduce parser. In Proceedings of ACL. Andreas Stolcke. 1995. An efficient probabilistic context-free parsing algorithm that computes prefix probabilities. Computational Linguistics, 21(2): 165– 201. Yue Zhang and Stephen Clark. 2008. A tale of two parsers: investigating and combining graph-based and transition-based dependency parsing using beamsearch. In Proceedings of EMNLP. 768