Paper: Efficient Search For Inversion Transduction Grammar

ACL ID W06-1627
Title Efficient Search For Inversion Transduction Grammar
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2006
Authors

We develop admissible A* search heuris- tics for synchronous parsing with Inver- sion Transduction Grammar, and present results both for bitext alignment and for machine translation decoding. We also combine the dynamic programming hook trick with A* search for decoding. These techniques make it possible to nd opti- mal alignments much more quickly, and make it possible to nd optimal transla- tions for the rst time. Even in the pres- ence of pruning, we are able to achieve higher BLEU scores with the same amount of computation.