K-Best A* Parsing

Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, pages 958–966, Suntec, Singapore, 2-7 August 2009. c⃝2009 ACL and AFNLP K-Best A∗ Parsing Adam Pauls and Dan Klein Computer Science Division University of California, Berkeley {adpauls,klein}@cs.berkeley.edu 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 exhaus- tive 1-best pass. We present a unified algo- rithm for k-best A∗ parsing which preserves the efficiency of k-best extraction while giv- ing the speed-ups of A∗ methods. Our algo- rithm 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 gram- mar 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 decod- ing (Goodman, 1998; Kumar and Byrne, 2004), discriminative reranking (Collins, 2000; Char- niak and Johnson, 2005), and discriminative train- ing (Och, 2003; McClosky et al., 2006). The most efficient known algorithm for k-best parsing (Jim´enez and Marzal, 2000; Huang and Chiang, 2005) performs an initial bottom-up dynamic pro- gramming pass before extracting the k-best parses. In that algorithm, the initial pass is, by far, the bot- tleneck (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∗ pars- ing 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 Man- ning, 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 algorithm is also equivalent to stan- dard A∗ parsing (up to ties) if it is terminated after the 1-best derivation is found. Finally, our algo- rithm can be written down in terms of deduction rules, and thus falls into the well-understood view of parsing as weighted deduction (Shieber et al., 1995; Goodman, 1998; Nederhof, 2003). In addition to presenting the algorithm, we show experiments in which we extract k-best lists for three different kinds of grammars: the lexi- calized grammars of Klein and Manning (2003b), the state-split grammars of Petrov et al. (2006), and the tree transducer grammars of Galley et al. (2006). We demonstrate that optimal k-best lists can be extracted significantly faster using our al- gorithm than with previous methods. 2 A k-Best A∗ Parsing Algorithm We build up to our full algorithm in several stages, beginning with standard 1-best A∗ parsing …

Content truncated to 500 words