Reordering Constraints for Phrase-Based Statistical Machine Translation

Reordering Constraints for Phrase-Based Statistical Machine Translation Richard Zens1, Hermann Ney1, Taro Watanabe2 and Eiichiro Sumita2 1Lehrstuhl f¨ur Informatik VI 2 Spoken Language Translation Research Laboratories Computer Science Department ATR RWTH Aachen University, Germany Kyoto, Japan {zens,ney}@cs.rwth-aachen.de {watanabe,sumita}@slt.atr.co.jp Abstract In statistical machine translation, the gen- eration of a translation hypothesis is com- putationally expensive. If arbitrary re- orderings are permitted, the search prob- lem is NP-hard. On the other hand, if we restrict the possible reorderings in an appropriate way, we obtain polynomial-time search algorithm. We in-a vestigate different reordering constraints for phrase-based statistical machine trans- lation, namely the IBM constraints and the ITG constraints. We present effi- cient dynamic programming algorithms for both constraints. We evaluate the con- straints with respect to translation quality on two Japanese–English tasks. We show that the reordering constraints improve translation quality compared to an un- constrained search that permits arbitrary phrase reorderings. The ITG constraints preform best on both tasks and yield sta- tistically significant improvements com- pared to the unconstrained search. 1 Introduction In statistical machine translation, we are given a source language (‘French’) sentence fJ 1 f1 . . . fj . . . fJ, which is to be translated into= a target language (‘English’) sentence eI 1 = e1 . . . ei . . . eI. Among all possible target lan- guage sentences, we will choose the sentence with the highest probability: ˆeI 1 = argmax eI 1 � Pr(eI 1|fJ 1 ) � = argmax eI 1 � Pr(eI 1) · Pr(fJ 1 |eI 1) � This decomposition into two knowledge sources is known as the source-channel ap- proach to statistical machine translation (Brown et al., 1990). It allows an independent modeling of target language model Pr(eI 1) and translation model Pr(fJ 1 |eI 1). The target lan- guage model describes the well-formedness of the target language sentence. The translation model links the source language sentence to the target language sentence. It can be fur- ther decomposed into alignment and lexicon model. The argmax operation denotes the search problem, i.e. the generation of the out- put sentence in the target language. We have to maximize over all possible target language sentences. An alternative to the classical source- channel approach is the direct modeling of the posterior probability Pr(eI 1|fJ 1 ). Using a log- linear model (Och and Ney, 2002), we obtain: Pr(eI 1|fJ 1 ) = exp � M � m=1 λmhm(eI 1, fJ 1 ) � · Z(fJ 1 ) Here, Z(fJ 1 ) denotes the appropriate normal- ization constant. As a decision rule, we obtain: ˆeI 1 = argmax eI 1 � M � m=1 λmhm(eI 1, fJ 1 ) � This approach is a generalization of the source-channel approach. It has the advan- tage that additional models or feature func- tions can be easily integrated into the over- all system. The model scaling factors λM 1 are trained according to the maximum entropy principle, e.g. using the GIS algorithm. Al- ternatively, one can train …

Content truncated to 500 words