tailieunhanh - Báo cáo khoa học: "Top-Down K-Best A∗ Parsing"

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. | Top-Down K-Best A Parsing Adam Pauls and Dan Klein Computer Science Division University of California at Berkeley adpauls klein @ Chris Quirk Microsoft Research Redmond WA 98052 chrisq@ Abstract We propose a top-down algorithm for extracting k-best lists from a parser. Our algorithm TKA is a variant of the k-best 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. 1 Introduction Many situations call for a parser to return a k-best list of parses instead of a single best Currently there are two efficient approaches known in the literature. The k-best algorithm of Jimenez and Marzal 2000 and Huang and Chiang 2005 referred to hereafter as Lazy operates by first performing an exhaustive Viterbi inside pass and then lazily extracting k-best lists in top-down manner. The k-best A algorithm of Pauls and Klein 2009 hereafter KA computes Viterbi inside and outside scores before extracting k-best lists bottom up. Because these additional passes are only partial KA can be significantly faster than Lazy especially when a heuristic is used Pauls and Klein 2009 . In this paper we propose TKA a topdown variant of KA that like Lazy performs only an inside pass before extracting k-best lists top-down but maintains the same optimality and efficiency guarantees as KA . This algorithm can be seen as a generalization of the lattice k-best algorithm of Soong and Huang 1991 to parsing. Because TKA eliminates the outside pass from KA TKA is simpler both in implementation and specification. 1See Huang and Chiang 2005 for a review. 2 Review Because our algorithm is very similar to KA which is in turn an extension of the 1-best A parsing algorithm of Klein and Manning 2003