Learning Structured Predictors from Bandit Feedback for Interactive NLP

Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pages 1610–1620, Berlin, Germany, August 7-12, 2016. c⃝2016 Association for Computational Linguistics Learning Structured Predictors from Bandit Feedback for Interactive NLP Artem Sokolov⋄,∗and Julia Kreutzer∗ and Christopher Lo†,∗ and Stefan Riezler‡,∗ ∗Computational Linguistics & ‡IWR, Heidelberg University, Germany {sokolov,kreutzer,riezler}@cl.uni-heidelberg.de †Department of Mathematics, Tufts University, Boston, MA, USA chris.aa.lo@gmail.com ⋄Amazon Development Center, Berlin, Germany Abstract Structured prediction from bandit feed- back describes a learning scenario where instead of having access to a gold standard structure, a learner only receives partial feedback in form of the loss value of a pre- dicted structure. We present new learning objectives and algorithms for this inter- active scenario, focusing on convergence speed and ease of elicitability of feed- back. We present supervised-to-bandit simulation experiments for several NLP tasks (machine translation, sequence la- beling, text classification), showing that bandit learning from relative preferences eases feedback strength and yields im- proved empirical convergence. 1 Introduction Structured prediction from partial information can be described by the following learning protocol: On each of a sequence of rounds, the learning al- gorithm makes a prediction, and receives partial information in terms of feedback on the predicted point. This single-point feedback is used to con- struct a parameter update that is an unbiased esti- mate of the respective update rule for the full in- formation objective. In difference to the full infor- mation scenario, the learner does not know what the correct prediction looks like, nor what would have happened if it had predicted differently. This learning scenario has been investigated under the names of learning from bandit feedback1 or rein- ∗The work for this paper was done while the authors were at Heidelberg University. 1The name is inherited from a model where in each round a gambler pulls an arm of a different slot machine (“one- armed bandit”), with the goal of maximizing his reward rel- ative to the maximal possible reward, without apriori knowl- edge of the optimal slot machine. See Bubeck and Cesa- Bianchi (2012) for an overview. forcement learning2, and has (financially) impor- tant real world applications such as online adver- tising (Chapelle et al., 2014). In this application, the probability that an ad will be clicked (and the advertiser has to pay) is estimated by trading off exploration (a new ad needs to be displayed in or- der to learn its click-through rate) and exploitation (displaying the ad with the current best estimate is better in the short term) in displaying ads to users. Similar to the online advertising scenario, there are many potential applications to interac- tive learning in NLP. For example, in interactive statistical machine translation (SMT), user feed- back in form of post-edits of predicted transla- tions is used for model adaptation (Bertoldi et al., 2014; Denkowski et al., 2014; Green et al., 2014). Since post-editing feedback has a high cost and requires professional expertise of users, weaker forms of feedback are desirable. Sokolov et al. (2015) showed in a simulation …

Content truncated to 500 words