Efficient Incremental Decoding for Tree-to-String Translation

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 273–283, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics Efficient Incremental Decoding for Tree-to-String Translation Liang Huang 1 1Information Sciences Institute University of Southern California 4676 Admiralty Way, Suite 1001 Marina del Rey, CA 90292, USA {lhuang,haitaomi}@isi.edu Haitao Mi 2,1 2Key Lab. of Intelligent Information Processing Institute of Computing Technology Chinese Academy of Sciences P.O. Box 2704, Beijing 100190, China htmi@ict.ac.cn Abstract Syntax-based translation models should in principle be efficient with polynomially-sized search space, but in practice they are often embarassingly slow, partly due to the cost of language model integration. In this paper we borrow from phrase-based decoding the idea to generate a translation incrementally left-to-right, and show that for tree-to-string models, with a clever encoding of deriva- tion history, this method runs in average- case polynomial-time in theory, and linear- time with beam search in practice (whereas phrase-based decoding is exponential-time in theory and quadratic-time in practice). Exper- iments show that, with comparable translation quality, our tree-to-string system (in Python) can run more than 30 times faster than the phrase-based system Moses (in C++). 1 Introduction Most efforts in statistical machine translation so far are variants of either phrase-based or syntax-based models. From a theoretical point of view, phrase- based models are neither expressive nor efficient: they typically allow arbitrary permutations and re- sort to language models to decide the best order. In theory, this process can be reduced to the Traveling Salesman Problem and thus requires an exponential- time algorithm (Knight, 1999). In practice, the de- coder has to employ beam search to make it tractable (Koehn, 2004). However, even beam search runs in quadratic-time in general (see Sec. 2), unless a small distortion limit (say, d=5) further restricts the possi- ble set of reorderings to those local ones by ruling out any long-distance reorderings that have a “jump” in theory in practice phrase-based exponential quadratic tree-to-string polynomial linear Table 1: [main result] Time complexity of our incremen- tal tree-to-string decoding compared with phrase-based. In practice means “approximate search with beams.” longer than d. This has been the standard prac- tice with phrase-based models (Koehn et al., 2007), which fails to capture important long-distance re- orderings like SVO-to-SOV. Syntax-based models, on the other hand, use asyntactic information to restrict reorderings to computationally-tractable and linguistically- motivated subset, for example those generated by synchronous context-free grammars (Wu, 1997; Chiang, 2007). In theory the advantage seems quite obvious: we can now express global reorderings (like SVO-to-VSO) in polynomial-time (as opposed to exponential in phrase-based). But unfortunately, this polynomial complexity is super-linear (being generally cubic-time or worse), which is slow in practice. Furthermore, language model integration becomes more expensive here since the decoder now has to maintain target-language boundary words at both ends of a subtranslation (Huang and Chiang, 2007), whereas a phrase-based decoder only needs to do this at one end since the translation is always growing left-to-right. As a result, syntax-based models are …

Content truncated to 500 words