A Comparative Study on Reordering Constraints in Statistical Machine Translation

A Comparative Study on Reordering Constraints in Statistical Machine Translation Richard Zens and Hermann Ney Chair of Computer Science VI RWTH Aachen - University of Technology {zens,ney}@cs.rwth-aachen.de Abstract 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: First, we check how many of the Viterbi alignments of the training corpus satisfy each of these con- straints. Second, we restrict the search to each of these constraints and compare the resulting translation hypotheses. The experiments will show that the base- line ITG constraints are not sufficient on the Canadian Hansards task. There- fore, we present an extension to the ITG constraints. These extended ITG con- straints increase the alignment coverage from about 87% to 96%. 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 language sentences, we will choose the sentence with the highest probabil- ity: ˆeI 1 = argmax eI 1 {Pr(eI 1|fJ 1 )} (1) = argmax eI 1 {Pr(eI 1) · Pr(fJ 1 |eI 1)} (2) The decomposition into two knowledge sources in Eq. 2 is the so-called source-channel approach to statistical machine translation (Brown et al., 1990). It allows an independent modeling of tar- get language model Pr(eI 1) and translation model Pr(fJ 1 |eI 1). The target language model describes the well-formedness of the target language sentence. The translation model links the source language sen- tence 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 output sentence in the tar- get language. We have to maximize over all possible target language sentences. In this paper, we will focus on the alignment problem, i.e. the mapping between source sen- tence positions and target sentence positions. As the word order in source and target language may differ, the search algorithm has to allow certain word-reorderings. If arbitrary word-reorderings are allowed, the search problem is NP-hard (Knight, 1999). Therefore, we have to restrict the possible reorderings in some way to make the search prob- lem feasible. Here, we will discuss two such con- …

Content truncated to 500 words