On Hierarchical Re-ordering and Permutation Parsing for Phrase-based Decoding

Proceedings of the 7th Workshop on Statistical Machine Translation, pages 200–209, Montr´eal, Canada, June 7-8, 2012. c⃝2012 Association for Computational Linguistics On Hierarchical Re-ordering and Permutation Parsing for Phrase-based Decoding Colin Cherry National Research Council colin.cherry@nrc-cnrc.gc.ca Robert C. Moore Google bobmoore@google.com Chris Quirk Microsoft Research chrisq@microsoft.com Abstract The addition of a deterministic permutation parser can provide valuable hierarchical in- formation to a phrase-based statistical ma- chine translation (PBSMT) system. Permuta- tion parsers have been used to implement hier- archical re-ordering models (Galley and Man- ning, 2008) and to enforce inversion trans- duction grammar (ITG) constraints (Feng et al., 2010). We present a number of theoret- ical results regarding the use of permutation parsers in PBSMT. In particular, we show that an existing ITG constraint (Zens et al., 2004) does not prevent all non-ITG permutations, and we demonstrate that the hierarchical re- ordering model can produce analyses during decoding that are inconsistent with analyses made during training. Experimentally, we ver- ify the utility of hierarchical re-ordering, and compare several theoretically-motivated vari- ants in terms of both translation quality and the syntactic complexity of their output. 1 Introduction Despite the emergence of a number of syntax-based techniques, phrase-based statistical machine transla- tion remains a competitive and very efficient trans- lation paradigm (Galley and Manning, 2010). How- ever, it lacks the syntactically-informed movement models and constraints that are provided implicitly by working with synchronous grammars. There- fore, re-ordering must be modeled and constrained explicitly. Movement can be modeled with a dis- tortion penalty or lexicalized re-ordering probabili- ties (Koehn et al., 2003; Koehn et al., 2007), while decoding can be constrained by distortion limits or by mimicking the restrictions of inversion transduc- tion grammars (Wu, 1997; Zens et al., 2004). Recently, we have begun to see deterministic per- mutation parsers incorporated into phrase-based de- coders. These efficient parsers analyze the sequence of phrases used to produce the target, and assem- ble them into a hierarchical translation history that can be used to inform re-ordering decisions. Thus far, they have been used to enable a hierarchical re-ordering model, or HRM (Galley and Manning, 2008), as well as an ITG constraint (Feng et al., 2010). We discuss each of these techniques in turn, and then explore the implications of ITG violations on hierarchical re-ordering. We present one experimental and four theoreti- cal contributions. Examining the HRM alone, we present an improved algorithm for extracting HRM statistics, reducing the complexity of Galley and Manning’s solution from O(n4) to O(n2). Examin- ing ITG constraints alone, we demonstrate that the three-stack constraint of Feng et al. can be reduced to one augmented stack, and we show that another phrase-based ITG constraint (Zens et al., 2004) ac- tually allows some ITG violations to pass. Finally, we show that in the presence of ITG violations, the original HRM can fail to produce orientations that are consistent with the orientations collected during training. We propose three HRM variants to address this situation, including an approximate HRM that requires no permutation parser, …

Content truncated to 500 words