Exact Decoding for Phrase-Based Statistical Machine Translation

The combinatorial space of translation derivations in phrase-based statistical ma-chine translation is given by the intersec-tion between a translation lattice and a tar-get language model. We replace this in-tractable intersection by a tractable relax-ation which incorporates a low-order up-perbound on the language model. Exact optimisation is achieved through a coarse-to-fine strategy with connections to adap-tive rejection sampling. We perform ex-act optimisation with unpruned language models of order 3 to 5 and show search-error curves for beam search and cube pruning on standard test sets. This is the first work to tractably tackle exact opti-misation with language models of orders higher than 3.