Paper: A Comparative Study On Reordering Constraints In Statistical Machine Translation

ACL ID P03-1019
Title A Comparative Study On Reordering Constraints In Statistical Machine Translation
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2003
Authors

In statistical machine translation, the gen- eration of a translation hypothesis is com- putationally expensive. If arbitrary word- reorderings are permitted, the search prob- lem is NP-hard. On the other hand, if we restrict the possible word-reorderings in an appropriate way, we obtain a polynomial-time search algorithm. In this paper, we compare two different re- ordering constraints, namely the ITG con- straints and the IBM constraints. This comparison includes a theoretical dis- cussion on the permitted number of re- orderings for each of these constraints. We show a connection between the ITG constraints and the since 1870 known Schr¨oder numbers. We evaluate these constraints on two tasks: the Verbmobil task and the Cana- dian Hansards task. The evaluation con- sists of two parts: ...