Paper: Learning Linear Ordering Problems for Better Translation

ACL ID D09-1105
Title Learning Linear Ordering Problems for Better Translation
Venue Conference on Empirical Methods in Natural Language Processing
Session Main Conference
Year 2009

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 exponen...