Efficient Search for Inversion Transduction Grammar

Proceedings of the 2006 Conference on Empirical Methods in Natural Language Processing (EMNLP 2006), pages 224–231, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Efficient Search for Inversion Transduction Grammar Hao Zhang and Daniel Gildea Computer Science Department University of Rochester Rochester, NY 14627 Abstract 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 find opti- mal alignments much more quickly, and make it possible to find optimal transla- tions for the first time. Even in the pres- ence of pruning, we are able to achieve higher BLEU scores with the same amount of computation. 1 Introduction The Inversion Transduction Grammar (ITG) of Wu (1997) is a syntactically motivated algorithm for producing word-level alignments of pairs of translationally equivalent sentences in two lan- guages. The algorithm builds a synchronous parse tree for both sentences, and assumes that the trees have the same underlying structure but that the or- dering of constituents may differ in the two lan- guages. ITG imposes constraints on which align- ments are possible, and these constraints have been shown to be a good match for real bitext data (Zens and Ney, 2003). A major motivation for the introduction of ITG was the existence of polynomial-time algorithms both for alignment and translation. Alignment, whether for training a translation model using EM or for finding the Viterbi alignment of test data, is O(n6) (Wu, 1997), while translation (decod- ing) is O(n7) using a bigram language model, and O(n11) with trigrams. While polynomial-time al- gorithms are a major improvement over the NP- complete problems posed by the alignment models of Brown et al. (1993), the degree of these polyno- mials is high, making both alignment and decod- ing infeasible for realistic sentences without very significant pruning. In this paper, we explore use of the “hook trick” (Eisner and Satta, 1999; Huang et al., 2005) to reduce the asymptotic complexity of decoding, and the use of heuristics to guide the search. Our search heuristics are a conservative esti- mate of the outside probability of a bitext cell in the complete synchronous parse. Some estimate of this outside probability is a common element of modern statistical (monolingual) parsers (Char- niak et al., 1998; Collins, 1999), and recent work has developed heuristics that are admissible for A* search, guaranteeing that the optimal parse will be found (Klein and Manning, 2003). We extend this type of outside probability estimate to include both word translation and n-gram language model probabilities. These measures have been used to guide search in word- or phrase-based MT sys- tems (Wang and Waibel, 1997; Och et al., 2001), but in such models optimal search is generally not practical even with good heuristics. In this paper, we show that the same assumptions that make ITG polynomial-time can be used to efficiently com- pute …

Content truncated to 500 words