A Coactive Learning View of Online Structured Prediction in Statistical Machine Translation

Proceedings of the 19th Conference on Computational Language Learning, pages 1–11, Beijing, China, July 30-31, 2015. c⃝2015 Association for Computational Linguistics A Coactive Learning View of Online Structured Prediction in Statistical Machine Translation Artem Sokolov and Stefan Riezler∗ Computational Linguistics & IWR∗ 69120 Heidelberg, Germany {sokolov,riezler}@cl.uni-heidelberg.de Shay B. Cohen University of Edinburgh Edinburgh EH8 9LE, UK scohen@inf.ed.ac.uk Abstract We present a theoretical analysis of online parameter tuning in statistical machine translation (SMT) from a coactive learn- ing view. This perspective allows us to give regret and generalization bounds for latent perceptron algorithms that are com- mon in SMT, but fall outside of the stan- dard convex optimization scenario. Coac- tive learning also introduces the concept of weak feedback, which we apply in a proof- of-concept experiment to SMT, showing that learning from feedback that consists of slight improvements over predictions leads to convergence in regret and transla- tion error rate. This suggests that coactive learning might be a viable framework for interactive machine translation. Further- more, we find that surrogate translations replacing references that are unreachable in the decoder search space can be inter- preted as weak feedback and lead to con- vergence in learning, if they admit an un- derlying linear model. 1 Introduction Online learning has become the tool of choice for large scale machine learning scenarios. Compared to batch learning, its advantages include memory efficiency, due to parameter updates being per- formed on the basis of single examples, and run- time efficiency, where a constant number of passes over the training sample is sufficient for conver- gence (Bottou and Bousquet, 2004). Statistical Machine Translation (SMT) has embraced the po- tential of online learning, both to handle millions of features and/or millions of data in parameter tuning via online structured prediction (see Liang et al. (2006) for seminal early work), and in in- teractive learning from user post-edits (see Cesa- Bianchi et al. (2008) for pioneering work on on- line computer-assisted translation). Online learn- ing algorithms can be given a theoretical analy- sis in the framework of online convex optimiza- tion (Shalev-Shwartz, 2012), however, the appli- cation of online learning techniques to SMT sac- rifices convexity because of latent derivation vari- ables, and because of surrogate translations replac- ing human references that are unreachable in the decoder search space. For example, the objective function actually optimized in Liang et al.’s (2006) application of Collins’ (2002) structure perceptron has been analyzed by Gimpel and Smith (2012) as a non-convex ramp loss function (McAllester and Keshet, 2011; Do et al., 2008; Collobert et al., 2006). Since online convex optimization does not provide convergence guarantees for the algorithm of Liang et al. (2006), Gimpel and Smith (2012) recommend CCCP (Yuille and Rangarajan, 2003) instead for optimization, but fail to provide a the- oretical analysis of Liang et al.’s (2006) actual al- gorithm under the new objective. The goal of this paper is to present an alternative theoretical analysis of online learning algorithms for SMT from the viewpoint of coactive learning (Shivaswamy …

Content truncated to 500 words