Local Phrase Reordering Models for Statistical Machine Translation

Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 161–168, Vancouver, October 2005. c⃝2005 Association for Computational Linguistics Local Phrase Reordering Models for Statistical Machine Translation Shankar Kumar, William Byrne∗ Center for Language and Speech Processing, Johns Hopkins University, 3400 North Charles Street, Baltimore, MD 21218, U.S.A. Machine Intelligence Lab, Cambridge University Engineering Department, Trumpington Street, Cambridge CB2 1PZ, U.K. skumar@jhu.edu , wjb31@cam.ac.uk Abstract We describe stochastic models of local phrase movement that can be incorpo- rated into a Statistical Machine Transla- tion (SMT) system. These models pro- vide properly formulated, non-deficient, probability distributions over reordered phrase sequences. They are imple- mented by Weighted Finite State Trans- ducers. We describe EM-style parameter re-estimation procedures based on phrase alignment under the complete translation model incorporating reordering. Our ex- periments show that the reordering model yields substantial improvements in trans- lation performance on Arabic-to-English and Chinese-to-English MT tasks. We also show that the procedure scales as the bitext size is increased. 1 Introduction Word and Phrase Reordering is a crucial component of Statistical Machine Translation (SMT) systems. However allowing reordering in translation is com- putationally expensive and in some cases even prov- ably NP-complete (Knight, 1999). Therefore any translation scheme that incorporates reordering must necessarily balance model complexity against the ability to realize the model without approximation. In this paper our goal is to formulate models of lo- cal phrase reordering in such a way that they can be embedded inside a generative phrase-based model ∗ This work was supported by an ONR MURI Grant N00014-01-1-0685. of translation (Kumar et al., 2005). Although this model of reordering is somewhat limited and can- not capture all possible phrase movement, it forms a proper parameterized probability distribution over reorderings of phrase sequences. We show that with this model it is possible to perform Maximum A Posteriori (MAP) decoding (with pruning) and Ex- pectation Maximization (EM) style re-estimation of model parameters over large bitext collections. We now discuss prior work on word and phrase reordering in translation. We focus on SMT systems that do not require phrases to form syntactic con- stituents. The IBM translation models (Brown et al., 1993) describe word reordering via a distortion model de- fined over word positions within sentence pairs. The Alignment Template Model (Och et al., 1999) uses phrases rather than words as the basis for transla- tion, and defines movement at the level of phrases. Phrase reordering is modeled as a first order Markov process with a single parameter that controls the de- gree of movement. Our current work is inspired by the block (phrase-pair) orientation model introduced by Till- mann (2004) in which reordering allows neighbor- ing blocks to swap. This is described as a sequence of orientations (left, right, neutral) relative to the monotone block order. Model parameters are block- specific and estimated over word aligned trained bi- text using simple heuristics. Other researchers (Vogel, 2003; Zens and Ney, 2003; Zens et al., 2004) have reported performance gains …

Content truncated to 500 words