A Convex Alternative to IBM Model 2

Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1574–1583, Seattle, Washington, USA, 18-21 October 2013. c⃝2013 Association for Computational Linguistics A Convex Alternative to IBM Model 2 Andrei Simion Columbia University IEOR Department 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 The IBM translation models have been hugely influential in statistical machine translation; they are the basis of the alignment models used in modern translation systems. Exclud- ing IBM Model 1, the IBM translation mod- els, and practically all variants proposed in the literature, have relied on the optimization of likelihood functions or similar functions that are non-convex, and hence have multiple lo- cal optima. In this paper we introduce a con- vex relaxation of IBM Model 2, and describe an optimization algorithm for the relaxation based on a subgradient method combined with exponentiated-gradient updates. Our ap- proach gives the same level of alignment ac- curacy as IBM Model 2. 1 Introduction The IBM translation models (Brown et al., 1993) have been tremendously important in statistical ma- chine translation (SMT). The IBM models were the first generation of SMT systems; in recent work, they play a central role in deriving alignments used within many modern SMT approaches, for exam- ple phrase-based translation models (Koehn, 2008) and syntax-based translation systems (e.g., (Chi- ang, 2005; Marcu et al., 2006)). Since the origi- nal IBM paper, there has been a large amount of re- search exploring the original IBM models and mod- ern variants (e.g., (Moore, 2004; Liang et al., 2006; Toutanova and Galley, 2011; Riley and Gildea, 2012; Vogel et al., 1996)). Excluding IBM Model 1, the IBM translation models, and practically all variants proposed in the literature, have relied on the optimization of like- lihood functions or similar functions that are non- convex. Unfortunately, non-convex objective func- tions have multiple local optima, and finding a global optimum of a non-convex function is typi- cally a computationally intractible problem. Typi- cally, an EM algorithm is used, which often runs in a reasonable amount of time, but with no guarantees of finding a global optima (or for that matter, even a near-optimal solution). In this paper we make the following contributions: • We introduce a convex relaxation of IBM Model 2. At a very high level, the relaxation is derived by replacing the product t(fj|ei) × d(i|j) with a relaxation that is commonly used in the linear programming literature (e.g., see (Bertsimas, 1997; Bertsimas and Tsitsiklis, 1997; Martins et al., 2010)). (Here t(f|e) are the translation parameters of the model, and d(i|j) are the distortion parameters; the prod- uct is non-linear, effectively introducing non- convexity into the problem.) • We describe an optimization algorithm for the relaxed objective, based on a combina- tion of stochastic subgradient methods with the exponentiated-gradient (EG) algorithm (Kivi- nen and Warmuth, 1997; Beck and Teboulle, 2003). • We describe experiments with the method …

Content truncated to 500 words