Cohesive Phrase-Based Decoding for Statistical Machine Translation

Proceedings of ACL-08: HLT, pages 72–80, Columbus, Ohio, USA, June 2008. c⃝2008 Association for Computational Linguistics Cohesive Phrase-based Decoding for Statistical Machine Translation Colin Cherry∗ Microsoft Research One Microsoft Way Redmond, WA, 98052 colinc@microsoft.com Abstract Phrase-based decoding produces state-of-the- art translations with no regard for syntax. We add syntax to this process with a cohesion constraint based on a dependency tree for the source sentence. The constraint allows the decoder to employ arbitrary, non-syntactic phrases, but ensures that those phrases are translated in an order that respects the source tree’s structure. In this way, we target the phrasal decoder’s weakness in order model- ing, without affecting its strengths. To fur- ther increase flexibility, we incorporate cohe- sion as a decoder feature, creating a soft con- straint. The resulting cohesive, phrase-based decoder is shown to produce translations that are preferred over non-cohesive output in both automatic and human evaluations. 1 Introduction Statistical machine translation (SMT) is complicated by the fact that words can move during translation. If one assumes arbitrary movement is possible, that alone is sufficient to show the problem to be NP- complete (Knight, 1999). Syntactic cohesion1 is the notion that all movement occurring during trans- lation can be explained by permuting children in a parse tree (Fox, 2002). Equivalently, one can say that phrases in the source, defined by subtrees in its parse, remain contiguous after translation. Early ∗Work conducted while at the University of Alberta. 1We use the term “syntactic cohesion” throughout this paper to mean what has previously been referred to as “phrasal cohe- sion”, because the non-linguistic sense of “phrase” has become so common in machine translation literature. methods for syntactic SMT held to this assump- tion in its entirety (Wu, 1997; Yamada and Knight, 2001). These approaches were eventually super- seded by tree transducers and tree substitution gram- mars, which allow translation events to span sub- tree units, providing several advantages, including the ability to selectively produce uncohesive transla- tions (Eisner, 2003; Graehl and Knight, 2004; Quirk et al., 2005). What may have been forgotten during this transition is that there is a reason it was once be- lieved that a cohesive translation model would work: for some language pairs, cohesion explains nearly all translation movement. Fox (2002) showed that cohesion is held in the vast majority of cases for English-French, while Cherry and Lin (2006) have shown it to be a strong feature for word alignment. We attempt to use this strong, but imperfect, char- acterization of movement to assist a non-syntactic translation method: phrase-based SMT. Phrase-based decoding (Koehn et al., 2003) is a dominant formalism in statistical machine transla- tion. Contiguous segments of the source are trans- lated and placed in the target, which is constructed from left to right. The process iterates within a beam search until each word from the source has been covered by exactly one phrasal translation. Candi- date translations are scored by a linear combination of models, weighted according to Minimum Error Rate Training or MERT (Och, …

Content truncated to 500 words