Learning Linear Ordering Problems for Better Translation

Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing, pages 1007–1016, Singapore, 6-7 August 2009. c⃝2009 ACL and AFNLP Learning Linear Ordering Problems for Better Translation∗ Roy Tromble Google, Inc. 4720 Forbes Ave. Pittsburgh, PA 15213 royt@google.com Jason Eisner Department of Computer Science Johns Hopkins University Baltimore, MD 21218 jason@cs.jhu.edu Abstract We apply machine learning to the Lin- ear Ordering Problem in order to learn sentence-specific reordering models for machine translation. We demonstrate that even when these models are used as a mere preprocessing step for German-English translation, they significantly outperform Moses’ integrated lexicalized reordering model. Our models are trained on automatically aligned bitext. Their form is simple but novel. They assess, based on features of the input sentence, how strongly each pair of input word tokens wi, wj would like to reverse their relative order. Combining all these pairwise preferences to find the best global reordering is NP-hard. How- ever, we present a non-trivial O(n3) al- gorithm, based on chart parsing, that at least finds the best reordering within a cer- tain exponentially large neighborhood. We show how to iterate this reordering process within a local search algorithm, which we use in training. 1 Introduction Machine translation is an important but difficult problem. One of the properties that makes it dif- ficult is the fact that different languages express the same concepts in different orders. A ma- chine translation system must therefore rearrange the source language concepts to produce a fluent translation in the target language. 1This work is excerpted and adapted from the first au- thor’s Ph.D. thesis (Tromble, 2009). Some of the ideas here appeared in (Eisner and Tromble, 2006) without empirical validation. The material is based in part upon work sup- ported by the National Science Foundation under Grant No. 0347822. Phrase-based translation systems rely heavily on the target language model to ensure a fluent output order. However, a target n-gram language model alone is known to be inadequate. Thus, translation systems should also look at how the source sentence prefers to reorder. Yet past sys- tems have traditionally used rather weak models of the reordering process. They may look only at the distance between neighboring phrases, or depend only on phrase unigrams. The decoders also rely on search error, in the form of limited reordering windows, for both efficiency and translation qual- ity. Demonstrating the inadequacy of such ap- proaches, Al-Onaizan and Papineni (2006) showed that even given the words in the reference translation, and their alignment to the source words, a decoder of this sort charged with merely rearranging them into the correct target-language order could achieve a BLEU score (Papineni et al., 2002) of at best 69%—and that only when restricted to keep most words very close to their source positions. This paper introduces a more sophisticated model of reordering based on the Linear Order- ing Problem (LOP), itself an NP-hard permutation problem. We apply machine learning, in the form of a modified perceptron algorithm, to learn pa- rameters of …

Content truncated to 500 words