Paper: Efficient Incremental Decoding for Tree-to-String Translation

ACL ID D10-1027
Title Efficient Incremental Decoding for Tree-to-String Translation
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2010

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++).