Gappy Phrasal Alignment By Agreement

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 1308–1317, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Gappy Phrasal Alignment by Agreement Mohit Bansal∗ UC Berkeley, CS Division mbansal@cs.berkeley.edu Chris Quirk Microsoft Research chrisq@microsoft.com Robert C. Moore Google Research robert.carter.moore@gmail.com Abstract We propose a principled and efficient phrase- to-phrase alignment model, useful in machine translation as well as other related natural lan- guage processing problems. In a hidden semi- Markov model, word-to-phrase and phrase- to-word translations are modeled directly by the system. Agreement between two direc- tional models encourages the selection of par- simonious phrasal alignments, avoiding the overfitting commonly encountered in unsu- pervised training with multi-word units. Ex- panding the state space to include “gappy phrases” (such as French ne ⋆ pas) makes the alignment space more symmetric; thus, it al- lows agreement between discontinuous align- ments. The resulting system shows substantial improvements in both alignment quality and translation quality over word-based Hidden Markov Models, while maintaining asymptot- ically equivalent runtime. 1 Introduction Word alignment is an important part of statisti- cal machine translation (MT) pipelines. Phrase tables containing pairs of source and target lan- guage phrases are extracted from word alignments, forming the core of phrase-based statistical ma- chine translation systems (Koehn et al., 2003). Most syntactic machine translation systems extract synchronous context-free grammars (SCFGs) from aligned syntactic fragments (Galley et al., 2004; Zollmann et al., 2006), which in turn are de- rived from bilingual word alignments and syntactic ∗Author was a summer intern at Microsoft Research during this project. French English voudrais voyager par chemin de fer would like traveling by railroad ne pas not Figure 1: French-English pair with complex word alignment. parses. Alignment is also used in various other NLP problems such as entailment, paraphrasing, question answering, summarization and spelling correction. A limitation to word-based alignment is undesir- able. As seen in the French-English example in Fig- ure 1, many sentence pairs are naturally aligned with multi-word units in both languages (chemin de fer; would ⋆ like, where ⋆ indicates a gap). Much work has addressed this problem: generative models for direct phrasal alignment (Marcu and Wong, 2002), heuristic word-alignment combinations (Koehn et al., 2003; Och and Ney, 2003), models with pseudo- word collocations (Lambert and Banchs, 2006; Ma et al., 2007; Duan et al., 2010), synchronous gram- mar based approaches (Wu, 1997), etc. Most have a large state-space, using constraints and approxima- tions for efficient inference. We present a new phrasal alignment model based on the hidden Markov framework (Vogel et al., 1996). Our approach is semi-Markov: each state can generate multiple observations, representing word- to-phrase alignments. We also augment the state space to include contiguous sequences. This cor- responds to phrase-to-word and phrase-to-phrase alignments. We generalize alignment by agreement (Liang et al., 2006) to this space, and find that agree- ment discourages EM from overfitting. Finally, we make the alignment space more symmetric by in- cluding gappy (or non-contiguous) phrases. This al- lows agreement to reinforce …

Content truncated to 500 words