Coarse-to-Fine Syntactic Machine Translation using Language Projections

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 108–116, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics Coarse-to-Fine Syntactic Machine Translation using Language Projections Slav Petrov Aria Haghighi Dan Klein Computer Science Division, EECS Department University of California at Berkeley Berkeley, CA 94720 {petrov, aria42, klein}@eecs.berkeley.edu Abstract The intersection of tree transducer-based translation models with n-gram language models results in huge dynamic programs for machine translation decoding. We propose a multipass, coarse-to-fine approach in which the language model complexity is incremen- tally introduced. In contrast to previous order- based bigram-to-trigram approaches, we fo- cus on encoding-based methods, which use a clustered encoding of the target language. Across various encoding schemes, and for multiple language pairs, we show speed-ups of up to 50 times over single-pass decoding while improving BLEU score. Moreover, our entire decoding cascade for trigram language models is faster than the corresponding bigram pass alone of a bigram-to-trigram decoder. 1 Introduction In the absence of an n-gram language model, decod- ing a synchronous CFG translation model is very efficient, requiring only a variant of the CKY al- gorithm. As in monolingual parsing, dynamic pro- gramming items are simply indexed by a source lan- guage span and a syntactic label. Complexity arises when n-gram language model scoring is added, be- cause items must now be distinguished by their ini- tial and final few target language words for purposes of later combination. This lexically exploded search space is a root cause of inefficiency in decoding, and several methods have been suggested to combat it. The approach most relevant to the current work is Zhang and Gildea (2008), which begins with an ini- tial bigram pass and uses the resulting chart to guide a final trigram pass. Substantial speed-ups are ob- tained, but computation is still dominated by the ini- tial bigram pass. The key challenge is that unigram models are too poor to prune well, but bigram mod- els are already huge. In short, the problem is that there are too many words in the target language. In this paper, we propose a new, coarse-to-fine, mul- tipass approach which allows much greater speed- ups by translating into abstracted languages. That is, rather than beginning with a low-order model of a still-large language, we exploit language projec- tions, hierarchical clusterings of the target language, to effectively reduce the size of the target language. In this way, initial passes can be very quick, with complexity phased in gradually. Central to coarse-to-fine language projection is the construction of sequences of word clusterings (see Figure 1). The clusterings are deterministic mappings from words to clusters, with the property that each clustering refines the previous one. There are many choice points in this process, including how these clusterings are obtained and how much refinement is optimal for each pass. We demon- strate that likelihood-based hierarchical EM train- ing (Petrov et al., 2006) and cluster-based language modeling methods (Goodman, 2001) are superior to both rank-based and random-projection methods. In addition, we …

Content truncated to 500 words