A* Search via Approximate Factoring

Aria Haghighi, John DeNero, Dan Klein

We present a novel method for creating A* estimates for structured search problems originally described in Haghighi, DeNero, and Klein (2007). In our approach, we project a complex model onto multiple simpler models for which exact inference is efficient. We use an optimization framework to estimate parameters for these projections in a way which bounds the true costs. Similar to Klein and Manning (2003), we then combine completion estimates from the simpler models to guide search in the original complex model. We apply our approach to bitext parsing and demonstrate its effectiveness.

Subjects: 15.7 Search; 13. Natural Language Processing

Submitted: Apr 23, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.