Towards a Convex HMM Surrogate for Word Alignment

Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 531–540, Austin, Texas, November 1-5, 2016. c⃝2016 Association for Computational Linguistics Towards a Convex HMM Surrogate for Word Alignment Andrei Arsene Simion Columbia University ∗ New York, NY, 10011 aas2148@columbia.edu Michael Collins Columbia University† Computer Science New York, NY, 10027 mc3354@columbia.edu Clifford Stein Columbia University IEOR Department New York, NY, 10027 cs2035@columbia.edu Abstract Among the alignment models used in statis- tical machine translation (SMT), the hidden Markov model (HMM) is arguably the most elegant: it performs consistently better than IBM Model 3 and is very close in perfor- mance to the much more complex IBM Model 4. In this paper we discuss a model which combines the structure of the HMM and IBM Model 2. Using this surrogate, our experi- ments show that we can attain a similar level of alignment quality as the HMM model im- plemented in GIZA++ (Och and Ney, 2003). For this model, we derive its convex relaxation and show that it too has strong performance despite not having the local optima problems of non-convex objectives. In particular, the word alignment quality of this new convex model is significantly above that of the stan- dard IBM Models 2 and 3, as well as the pop- ular (and still non-convex) IBM Model 2 vari- ant of (Dyer et al., 2013). 1 Introduction The IBM translation models are widely used in mod- ern statistical translation systems. Typically, one seeds more complex models with simpler models, and the parameters of each model are estimated through an Expectation Maximization (EM) proce- dure. Among the IBM Models, perhaps the most elegant is the HMM model (Vogel et al., 1996). The HMM is the last model whose expectation step is ∗Currently at Google. †Currently on leave at Google. both exact and simple, and it attains a level of ac- curacy that is very close to the results achieved by much more complex models. In particular, experi- ments have shown that IBM Models 1, 2, and 3 all perform worse than the HMM and Model 4 benefits greatly from being seeded by the HMM (Och and Ney, 2003). In this paper we make the following contributions: • We derive a new alignment model which com- bines the structure of the HMM and IBM Model 2 and show that its performance is very close to that of the HMM. There are several reasons why such a result would be of value (for more on this, see (Simion et al., 2013) and (Simion et al., 2015a), for example). • The main goal of this work is not to eliminate highly non-convex models such as the HMM entirely but, rather, to develop a new, power- ful, convex alignment model and thus push the boundary of these theoretically justified tech- niques further. Building on the work of (Simion et al., 2015a), we derive a convex relaxation for the new model and show that its performance is close to that of the HMM. Although it …

Content truncated to 500 words