Fast Collocation-Based Bayesian HMM Word Alignment

Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers, pages 3146–3155, Osaka, Japan, December 11-17 2016. Fast Collocation-Based Bayesian HMM Word Alignment Philip Schulz ILLC University of Amsterdam P.Schulz@uva.nl Wilker Aziz ILLC University of Amsterdam W.Aziz@uva.nl Abstract We present a new Bayesian HMM word alignment model for statistical machine translation. The model is a mixture of an alignment model and a language model. The alignment component is a Bayesian extension of the standard HMM. The language model component is responsible for the generation of words needed for source fluency reasons from source language context. This allows for untranslatable source words to remain unaligned and at the same time avoids the introduction of artificial NULL words which introduces unusually long alignment jumps. Existing Bayesian word alignment models are unpractically slow because they consider each target position when resampling a given alignment link. The sampling complexity therefore grows linearly in the target sentence length. In order to make our model useful in practice, we devise an auxiliary variable Gibbs sampler that allows us to resample alignment links in constant time independently of the target sentence length. This leads to considerable speed improvements. Experimental results show that our model performs as well as existing word alignment toolkits in terms of resulting BLEU score. 1 Introduction Word alignment is one of the basic problems in statistical machine translation (SMT). The IBM models were originally devised for translation by Brown et al. (1993). Later, when SMT started to employ entire phrases instead of single words (Koehn et al., 2003), the IBM models were repurposed as word alignment models. The alignments they produce guide the phrase extraction heuristics that are used in many modern SMT systems. There are several extensions of the classical IBM models that try to weaken their independence as- sumptions. Notably, Vogel et al. (1996) introduced Markovian dependencies between individual align- ment links. Those links were treated as independent events in IBM models 1, 2 and 3. The model of Vogel et al. (1996) can be viewed as a Hidden Markov Model (HMM) in which the hidden Markov Chain induces a probability distribution over latent alignment links. Besides weakening the indepen- dence assumptions of the simpler IBM models, the HMM alignment model has the additional benefit of being tractable. This means that expectations under the HMM aligner can be computed exactly using the forward-backward algorithm. These expectations are then used in the Baum-Welch algorithm (Baum et al., 1970) to compute parameter updates for the model. Crucially, the Baum-Welch algorithm is a special case of the EM algorithm and thus guaranteed to never decrease the model’s likelihood at each parameter update (Dempster et al., 1977). Tractability and convergence (at least to a local optimum) are clear advantages of the HMM aligner over IBM models 3 to 5 which are all intractable. In practice, hill-climbing heuristics are employed to approximate expectations in these more complex models. Unfortunately, all convergence guarantees of the learning algorithm are lost this way. A major problem …

Content truncated to 500 words