A Fast Fertility Hidden Markov Model for Word Alignment Using MCMC

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 596–605, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics A Fast Fertility Hidden Markov Model for Word Alignment Using MCMC Shaojun Zhao and Daniel Gildea Department of Computer Science University of Rochester Abstract A word in one language can be translated to zero, one, or several words in other languages. Using word fertility features has been shown to be useful in building word alignment mod- els for statistical machine translation. We built a fertility hidden Markov model by adding fer- tility to the hidden Markov model. This model not only achieves lower alignment error rate than the hidden Markov model, but also runs faster. It is similar in some ways to IBM Model 4, but is much easier to understand. We use Gibbs sampling for parameter estimation, which is more principled than the neighbor- hood method used in IBM Model 4. 1 Introduction IBM models and the hidden Markov model (HMM) for word alignment are the most influential statistical word alignment models (Brown et al., 1993; Vogel et al., 1996; Och and Ney, 2003). There are three kinds of important information for word alignment mod- els: lexicality, locality and fertility. IBM Model 1 uses only lexical information; IBM Model 2 and the hidden Markov model take advantage of both lexi- cal and locality information; IBM Models 4 and 5 use all three kinds of information, and they remain the state of the art despite the fact that they were de- veloped almost two decades ago. Recent experiments on large datasets have shown that the performance of the hidden Markov model is very close to IBM Model 4. Nevertheless, we be- lieve that IBM Model 4 is essentially a better model because it exploits the fertility of words in the tar- get language. However, IBM Model 4 is so com- plex that most researches use the GIZA++ software package (Och and Ney, 2003), and IBM Model 4 it- self is treated as a black box. The complexity in IBM Model 4 makes it hard to understand and to improve. Our goal is to build a model that includes lexicality, locality, and fertility; and, at the same time, to make it easy to understand. We also want it to be accurate and computationally efficient. There have been many years of research on word alignment. Our work is different from others in essential ways. Most other researchers take either the HMM alignments (Liang et al., 2006) or IBM Model 4 alignments (Cherry and Lin, 2003) as in- put and perform post-processing, whereas our model is a potential replacement for the HMM and IBM Model 4. Directly modeling fertility makes our model fundamentally different from others. Most models have limited ability to model fertility. Liang et al. (2006) learn the alignment in both translation directions jointly, essentially pushing the fertility to- wards 1. ITG models (Wu, 1997) assume the fer- tility to be either zero or one. It …

Content truncated to 500 words