The Geometry of Statistical Machine Translation

Human Language Technologies: The 2015 Annual Conference of the North American Chapter of the ACL, pages 376–386, Denver, Colorado, May 31 – June 5, 2015. c⃝2015 Association for Computational Linguistics The Geometry of Statistical Machine Translation Aurelien Waite, William Byrne Department of Engineering, University of Cambridge, UK aaw35@cam.ac.uk, wjb31@cam.ac.uk Abstract Most modern statistical machine translation systems are based on linear statistical models. One extremely effective method for estimating the model parameters is minimum error rate training (MERT), which is an efficient form of line optimisation adapted to the highly non- linear objective functions used in machine translation. We describe a polynomial-time generalisation of line optimisation that com- putes the error surface over a plane embedded in parameter space. The description of this al- gorithm relies on convex geometry, which is the mathematics of polytopes and their faces. Using this geometric representation of MERT we investigate whether the optimisation of lin- ear models is tractable in general. Previous work on finding optimal solutions in MERT (Galley and Quirk, 2011) established a worst- case complexity that was exponential in the number of sentences, in contrast we show that exponential dependence in the worst-case complexity is mainly in the number of fea- tures. Although our work is framed with respect to MERT, the convex geometric description is also applicable to other error-based training methods for linear models. We believe our analysis has important ramifications because it suggests that the current trend in building sta- tistical machine translation systems by intro- ducing a very large number of sparse features is inherently not robust. 1 Introduction The linear model of Statistical Machine Translation (SMT) (Och and Ney, 2002) casts translation as a search for translation hypotheses under a linear com- bination of weighted features: a source language sentence f is translated as ˆe(f; w) = argmax e {wh(e, f)} (1) where translation scores are a linear combination of the D × 1 feature vector h(e, f) ∈ RD under the 1 × D model parameter vector w. Convex geometry (Ziegler, 1995) is the math- ematics of such linear equations presented as the study of convex polytopes. We use convex geom- etry to show that the behaviour of training methods such as MERT (Och, 2003; Macherey et al., 2008), MIRA (Crammer et al., 2006), PRO (Hopkins and May, 2011), and others converge with a high fea- ture dimension. In particular we analyse how robust- ness decreases in linear models as feature dimension increases. We believe that severe overtraining is a problem in many current linear model formulations due to this lack of robustness. In the process of building this geometric represen- tation of linear models we discuss algorithms such as the Minkowski sum algorithm (Fukuda, 2004) and projected MERT (Section 4.2) that could be use- ful for designing new and more robust training algo- rithms for SMT and other natural language process- ing problems. 2 Training Linear Models Let f1 . . . fS be a set of S source language sentences with reference translations r1 …

Content truncated to 500 words