acl acl2010 acl2010-236 acl2010-236-reference knowledge-graph by maker-knowledge-mining

236 acl-2010-Top-Down K-Best A* Parsing


Source: pdf

Author: Adam Pauls ; Dan Klein ; Chris Quirk

Abstract: We propose a top-down algorithm for extracting k-best lists from a parser. Our algorithm, TKA∗ is a variant of the kbest A∗ (KA∗) algorithm of Pauls and Klein (2009). In contrast to KA∗, which performs an inside and outside pass before performing k-best extraction bottom up, TKA∗ performs only the inside pass before extracting k-best lists top down. TKA∗ maintains the same optimality and efficiency guarantees of KA∗, but is simpler to both specify and implement.


reference text

Liang Huang and David Chiang. 2005. Better k-best parsing. In Proceedings of the International Workshop on Parsing Technologies (IWPT), pages 53–64. V ´ıctor M. Jim e´nez and Andr e´s Marzal. 2000. Computation of the n best parse trees for weighted and stochastic context-free grammars. In Proceedings of the Joint IAPR International Workshops on Advances in Pattern Recognition, pages 183–192, London, UK. Springer-Verlag. Dan Klein and Christopher D. Manning. 2001. Parsing and hypergraphs. In Proceedings of the International Workshop on Parsing Technologies (IWPT), pages 123–134. Dan Klein and Christopher D. Manning. 2003. A* parsing: Fast exact Viterbi parse selection. In Proceedings of the Human Language Technology Conference and the North American Association for Computational Linguistics (HLT-NAACL), pages 119–126. Mark-Jan Nederhof. 2003. Weighted deductive parsing and Knuth’s algorithm. Computationl Linguistics, 29(1): 135–143. Adam Pauls and Dan Klein. 2009. K-best A* parsing. In Proccedings ofthe Associationfor Computational Linguistics (ACL). Slav Petrov, Leon Barrett, Romain Thibaux, and Dan Klein. 2006. Learning accurate, compact, and interpretable tree annotation. In Proccedings of the Association for Computational Linguistics (ACL). Stuart M. Shieber, Yves Schabes, and Fernando C. N. Pereira. 1995. Principles and implementation of deductive parsing. Journal of Logic Programming, 24:3–36. Frank K. Soong and Eng-Fong Huang. 1991. A treetrellis based fast search for finding the n best sentence hypotheses in continuous speech recognition. In Proceedings of the Workshop on Speech and Natural Language. 204