On A Strictly Convex IBM Model 1

Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 221–226, Lisbon, Portugal, 17-21 September 2015. c⃝2015 Association for Computational Linguistics. On a Strictly Convex IBM Model 1 Andrei Simion Columbia University New York, NY, 10027 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 IBM Model 1 is a classical alignment model. Of the first generation word-based SMT models, it was the only such model with a concave objective function. For concave optimization problems like IBM Model 1, we have guarantees on the con- vergence of optimization algorithms such as Expectation Maximization (EM). How- ever, as was pointed out recently, the ob- jective of IBM Model 1 is not strictly con- cave and there is quite a bit of alignment quality variance within the optimal solu- tion set. In this work we detail a strictly concave version of IBM Model 1 whose EM algorithm is a simple modification of the original EM algorithm of Model 1 and does not require the tuning of a learning rate or the insertion of an l2 penalty. More- over, by addressing Model 1’s shortcom- ings, we achieve AER and F-Measure im- provements over the classical Model 1 by over 30%. 1 Introduction The IBM translation models were introduced in (Brown et al., 1993) and were the first-generation Statistical Machine Translation (SMT) systems. In the current pipeline, these word-based models are the seeds for more sophisticated models which need alignment tableaus to start their optimization procedure. Among the original IBM Models, only IBM Model 1 can be formulated as a concave opti- mization problem. Recently, there has been some research on IBM Model 2 which addresses either the model’s non-concavity (Simion et al., 2015) ∗Currently on leave at Google Inc. New York. or over parametrization (Dyer et al., 2013). We make the following contributions in this paper: • We utilize and expand the mechanism intro- duced in (Simion et al., 2015) to construct strictly concave versions of IBM Model 11. As was shown in (Toutanova and Galley, 2011), IBM Model 1 is not a strictly con- cave optimization problem. What this means in practice is that although we can initialize the model with random parameters and get to the same objective cost via the EM algorithm, there is quite a bit of alignment quality vari- ance within the model’s optimal solution set and ambiguity persists on which optimal so- lution truly is the best. Typically, the easiest way to make a concave model strictly con- cave is to append an l2 regularizer. However, this method does not allow for seamless EM training: we have to either use a learning-rate dependent gradient based algorithm directly or use a gradient method within the M step of EM training. In this paper we show how to get via a simple technique an infinite supply of models that still allows a straightforward application of the EM algorithm. • As a …

Content truncated to 500 words