Approximate Factoring for A* Search

Proceedings of NAACL HLT 2007, pages 412–419, Rochester, NY, April 2007. c⃝2007 Association for Computational Linguistics Approximate Factoring for A∗ Search Aria Haghighi, John DeNero, Dan Klein Computer Science Division University of California Berkeley {aria42, denero, klein}@cs.berkeley.edu Abstract We present a novel method for creating A∗ esti- mates for structured search problems. In our ap- proach, we project a complex model onto multiple simpler models for which exact inference is effi- cient. We use an optimization framework to es- timate parameters for these projections in a way which bounds the true costs. Similar to Klein and Manning (2003), we then combine completion es- timates from the simpler models to guide search in the original complex model. We apply our ap- proach to bitext parsing and lexicalized parsing, demonstrating its effectiveness in these domains. 1 Introduction Inference tasks in NLP often involve searching for an optimal output from a large set of structured out- puts. For many complex models, selecting the high- est scoring output for a given observation is slow or even intractable. One general technique to increase efficiency while preserving optimality is A∗ search (Hart et al., 1968); however, successfully using A∗ search is challenging in practice. The design of ad- missible (or nearly admissible) heuristics which are both effective (close to actual completion costs) and also efficient to compute is a difficult, open prob- lem in most domains. As a result, most work on search has focused on non-optimal methods, such as beam search or pruning based on approximate models (Collins, 1999), though in certain cases ad- missible heuristics are known (Och and Ney, 2000; Zhang and Gildea, 2006). For example, Klein and Manning (2003) show a class of projection-based A∗ estimates, but their application is limited to models which have a very restrictive kind of score decom- position. In this work, we broaden their projection- based technique to give A∗ estimates for models which do not factor in this restricted way. Like Klein and Manning (2003), we focus on search problems where there are multiple projec- tions or “views” of the structure, for example lexical parsing, in which trees can be projected onto either their CFG backbone or their lexical attachments. We use general optimization techniques (Boyd and Van- denberghe, 2005) to approximately factor a model over these projections. Solutions to the projected problems yield heuristics for the original model. This approach is flexible, providing either admissi- ble or nearly admissible heuristics, depending on the details of the optimization problem solved. Further- more, our approach allows a modeler explicit control over the trade-off between the tightness of a heuris- tic and its degree of inadmissibility (if any). We de- scribe our technique in general and then apply it to two concrete NLP search tasks: bitext parsing and lexicalized monolingual parsing. 2 General Approach Many inference problems in NLP can be solved with agenda-based methods, in which we incremen- tally build hypotheses for larger items by combining smaller ones with some local configurational struc- ture. We can formalize …

Content truncated to 500 words