Model-Based Aligner Combination Using Dual Decomposition

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 420–429, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Model-Based Aligner Combination Using Dual Decomposition John DeNero Google Research denero@google.com Klaus Macherey Google Research kmach@google.com Abstract Unsupervised word alignment is most often modeled as a Markov process that generates a sentence f conditioned on its translation e. A similar model generating e from f will make different alignment predictions. Statistical machine translation systems combine the pre- dictions of two directional models, typically using heuristic combination procedures like grow-diag-final. This paper presents a graph- ical model that embeds two directional align- ers into a single model. Inference can be per- formed via dual decomposition, which reuses the efficient inference algorithms of the direc- tional models. Our bidirectional model en- forces a one-to-one phrase constraint while ac- counting for the uncertainty in the underlying directional models. The resulting alignments improve upon baseline combination heuristics in word-level and phrase-level evaluations. 1 Introduction Word alignment is the task of identifying corre- sponding words in sentence pairs. The standard approach to word alignment employs directional Markov models that align the words of a sentence f to those of its translation e, such as IBM Model 4 (Brown et al., 1993) or the HMM-based alignment model (Vogel et al., 1996). Machine translation systems typically combine the predictions of two directional models, one which aligns f to e and the other e to f (Och et al., 1999). Combination can reduce errors and relax the one-to-many structural restriction of directional models. Common combination methods include the union or intersection of directional alignments, as well as heuristic interpolations between the union and intersection like grow-diag-final (Koehn et al., 2003). This paper presents a model-based alterna- tive to aligner combination. Inference in a prob- abilistic model resolves the conflicting predictions of two directional models, while taking into account each model’s uncertainty over its output. This result is achieved by embedding two direc- tional HMM-based alignment models into a larger bidirectional graphical model. The full model struc- ture and potentials allow the two embedded direc- tional models to disagree to some extent, but reward agreement. Moreover, the bidirectional model en- forces a one-to-one phrase alignment structure, sim- ilar to the output of phrase alignment models (Marcu and Wong, 2002; DeNero et al., 2008), unsuper- vised inversion transduction grammar (ITG) models (Blunsom et al., 2009), and supervised ITG models (Haghighi et al., 2009; DeNero and Klein, 2010). Inference in our combined model is not tractable because of numerous edge cycles in the model graph. However, we can employ dual decomposi- tion as an approximate inference technique (Rush et al., 2010). In this approach, we iteratively apply the same efficient sequence algorithms for the underly- ing directional models, and thereby optimize a dual bound on the model objective. In cases where our algorithm converges, we have a certificate of opti- mality under the full model. Early stopping before convergence still yields useful outputs. Our model-based approach to …

Content truncated to 500 words