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

A∗ parsing makes 1-best search efficient by suppressing unlikely 1-best items. Existing kbest extraction methods can efficiently search for top derivations, but only after an exhaustive 1-best pass. We present a unified algorithm for k-best A∗ parsing which preserves the efficiency of k-best extraction while giving the speed-ups of A∗ methods. Our algorithm produces optimal k-best parses under the same conditions required for optimality in a 1-best A∗ parser. Empirically, optimal k-best lists can be extracted significantly faster than with other approaches, over a range of grammar types. . | K-Best A Parsing Adam Pauls and Dan Klein Computer Science Division University of California Berkeley adpauls klein @ Abstract A parsing makes 1-best search efficient by suppressing unlikely 1-best items. Existing k-best extraction methods can efficiently search for top derivations but only after an exhaustive 1-best pass. We present a unified algorithm for k-best A parsing which preserves the efficiency of k-best extraction while giving the speed-ups of A methods. Our algorithm produces optimal k-best parses under the same conditions required for optimality in a 1-best A parser. Empirically optimal k-best lists can be extracted significantly faster than with other approaches over a range of grammar types. 1 Introduction Many situations call for a parser to return the k-best parses rather than only the 1-best. Uses for k-best lists include minimum Bayes risk decoding Goodman 1998 Kumar and Byrne 2004 discriminative reranking Collins 2000 Char-niak and Johnson 2005 and discriminative training Och 2003 McClosky et al. 2006 . The most efficient known algorithm for k-best parsing Jimenez and Marzal 2000 Huang and Chiang 2005 performs an initial bottom-up dynamic programming pass before extracting the k-best parses. In that algorithm the initial pass is by far the bottleneck Huang and Chiang 2005 . In this paper we propose an extension of A parsing which integrates k-best search with an A -based exploration of the 1-best chart. A parsing can avoid significant amounts of computation by guiding 1-best search with heuristic estimates of parse completion costs and has been applied successfully in several domains Klein and Manning 2002 Klein and Manning 2003c Haghighi et al. 2007 . Our algorithm extends the speed-ups achieved in the 1-best case to the k-best case and is optimal under the same conditions as a stan dard A algorithm. The amount of work done in the k-best phase is no more than the amount of work done by the algorithm of Huang and Chiang 2005 . Our