Hierarchical Search for Parsing

Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the ACL, pages 557–565, Boulder, Colorado, June 2009. c⃝2009 Association for Computational Linguistics Hierarchical Search for Parsing Adam Pauls Dan Klein Computer Science Division University of California at Berkeley Berkeley, CA 94720, USA {adpauls,klein}@cs.berkeley.edu Abstract Both coarse-to-fine and A∗ parsing use simple grammars to guide search in complex ones. We compare the two approaches in a com- mon, agenda-based framework, demonstrat- ing the tradeoffs and relative strengths of each method. Overall, coarse-to-fine is much faster for moderate levels of search errors, but be- low a certain threshold A∗ is superior. In addi- tion, we present the first experiments on hier- archical A∗ parsing, in which computation of heuristics is itself guided by meta-heuristics. Multi-level hierarchies are helpful in both ap- proaches, but are more effective in the coarse- to-fine case because of accumulated slack in A∗ heuristics. 1 Introduction The grammars used by modern parsers are ex- tremely large, rendering exhaustive parsing imprac- tical. For example, the lexicalized grammars of Collins (1997) and Charniak (1997) and the state- split grammars of Petrov et al. (2006) are all too large to construct unpruned charts in memory. One effective approach is coarse-to-fine pruning, in which a small, coarse grammar is used to prune edges in a large, refined grammar (Charniak et al., 2006). Indeed, coarse-to-fine is even more effective when a hierarchy of successive approximations is used (Charniak et al., 2006; Petrov and Klein, 2007). In particular, Petrov and Klein (2007) generate a se- quence of approximations to a highly subcategorized grammar, parsing with each in turn. Despite its practical success, coarse-to-fine prun- ing is approximate, with no theoretical guarantees on optimality. Another line of work has explored A∗ search methods, in which simpler problems are used not for pruning, but for prioritizing work in the full search space (Klein and Manning, 2003a; Haghighi et al., 2007). In particular, Klein and Man- ning (2003a) investigated A∗ for lexicalized parsing in a factored model. In that case, A∗ vastly im- proved the search in the lexicalized grammar, with provable optimality. However, their bottleneck was clearly shown to be the exhaustive parsing used to compute the A∗ heuristic itself. It is not obvious, however, how A∗ can be stacked in a hierarchical or multi-pass way to speed up the computation of such complex heuristics. In this paper, we address three open questions regarding efficient hierarchical search. First, can a hierarchy of A∗ bounds be used, analogously to hierarchical coarse-to-fine pruning? We show that recent work in hierarchical A∗ (Felzenszwalb and McAllester, 2007) can naturally be applied to both the hierarchically refined grammars of Petrov and Klein (2007) as well as the lexicalized grammars of Klein and Manning (2003a). Second, what are the tradeoffs between coarse-to-fine pruning and A∗ methods? We show that coarse-to-fine is generally much faster, but at the cost of search errors.1 Below a certain search error rate, A∗ is faster and, of course, optimal. Finally, when and how, …

Content truncated to 500 words