2016

Bandit Structured Prediction for Learning from Partial Feedback in Statistical Machine Translation

Sokolov, Artem, Riezler, Stefan, Urvoy, Tanguy

Understand

We present an approach to structured prediction from bandit feedback, called Bandit Structured Prediction, where only the value of a task loss function at a single predicted point, instead of a correct structure, is observed in learning.

We present an application to discriminative reranking in Statistical Machine Translation (SMT) where the learning algorithm only has access to a 1-BLEU loss evaluation of a predicted translation instead of obtaining a gold standard reference translation.
In our experiment bandit feedback is obtained by evaluating BLEU on reference translations without revealing them to the algorithm.
This can be thought of as a simulation of interactive machine translation where an SMT system is personalized by a user who provides single point feedback to predicted translations.

Built on

A technique for the measurement of attitudes
Likert, R. (1932) · 1932
Earlier work this paper cites.
Some aspects of the sequential design of experiments
Robbins, H. (1952) · 1952
Earlier work this paper cites.
Pseudogradient adaptation and training algorithms
Polyak, B. T. and Tsypkin, Y. Z. (1973) · 1973
Earlier work this paper cites.
Introduction to Optimization
Polyak, B. T. (1987) · 1987
Earlier work this paper cites.
Acceleration of stochastic approximation by averaging
Polyak, B. T. and Juditsky, A. B. (1992) · 1992
Earlier work this paper cites.
Neuro-Dynamic Programming
Bertsekas, D. P. and Tsitsiklis, J. N. (1996) · 1996
Earlier work this paper cites.
Policy gradient methods for reinforcement learning with function approximation
Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. (2000) · 2000
Earlier work this paper cites.
The nonstochastic multiarmed bandit problem
Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. (2002) · 2002
Earlier work this paper cites.
Minimum error rate training in statistical machine translation
Och, F. J. (2003) · 2003
Earlier work this paper cites.
Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control
Spall, J. C. (2003) · 2003
Earlier work this paper cites.
Stochastic learning
Bottou, L. (2004) · 2004
Earlier work this paper cites.
Max-margin parsing
Taskar, B., Klein, D., Collins, M., Koller, D., and Manning, C. (2004) · 2004
Earlier work this paper cites.
Online convex optimization in the bandit setting: gradient descent without a gradient
Flaxman, A. D., Kalai, A. T., and McMahan, H. B. (2005) · 2005
Earlier work this paper cites.
On some pitfalls in automatic evaluation and significance testing for MT
Riezler, S. and Maxwell, J. (2005) · 2005
Earlier work this paper cites.
Large margin methods for structured and interdependent output variables
Tsochantaridis, I., Joachims, T., Hofmann, T., and Altun, Y. (2005) · 2005
Earlier work this paper cites.
Minimum risk annealing for training log-linear models
Smith, D. A. and Eisner, J. (2006) · 2006
Earlier work this paper cites.
A study of translation edit rate with targeted human annotation
Snover, M., Dorr, B., Schwartz, R., Micciulla, L., and Makhoul, J. (2006) · 2006
Earlier work this paper cites.

Similar

Moses: Open source toolkit for statistical machine translation
Koehn, P., Hoang, H., Birch, A., Callison-Birch, C., Federico, M., Bertoldi, N., Cowan, B., Shen, W., Moran, C., Zens, R., Dyer, C., Bojar, O., Constantin, A., and Herbst, E. (2007) · 2007
Cited alongside, same era.
Experiments in domain adaptation for statistical machine translation
Koehn, P. and Schroeder, J. (2007) · 2007
Cited alongside, same era.
The epoch-greedy algorithm for multi-armed bandits with side information
Langford, J. and Zhang, T. (2007) · 2007
Cited alongside, same era.
An efficient bandit algorithm for T \sqrt{T} regret in online multiclass prediction?
Abernethy, J. and Rakhlin, A. (2009) · 2009
Cited alongside, same era.
Reinforcement learning for mapping instructions to actions
Branavan, S., Chen, H., Zettlemoyer, L. S., and Barzilay, R. (2009) · 2009
Cited alongside, same era.
Robust stochastic approximation approach to stochastic programming
Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. (2009) · 2009
Cited alongside, same era.
Interactively optimizing information retrieval systems as a dueling bandits problem
Yue, Y. and Joachims, T. (2009) · 2009
Cited alongside, same era.
Optimal algorithms for online convex optimization with multi-point bandit feedback
Agarwal, A., Dekel, O., and Xiao, L. (2010) · 2010
Cited alongside, same era.
Softmax-margin training for structured log-linear models
Gimpel, K. and Smith, N. A. (2010) · 2010
Cited alongside, same era.
Non-asymptotic analysis of stochastic approximation algorithms for machine learning
Bach, F. and Moulines, E. (2011) · 2011
Cited alongside, same era.
Contextual bandits with linear payoff functions
Chu, W., Li, L., Reyzin, L., and Schapire, R. E. (2011) · 2011
Cited alongside, same era.
Better hypothesis testing for statistical machine translation: Controlling for optimizer instability
Clark, J., Dyer, C., Lavie, A., and Smith, N. (2011) · 2011
Cited alongside, same era.

Then

Probabilistic models of vision and max-margin methods
Yuille, A. and He, X. (2012) · 2012
Later among the works it cites.
Non-strongly-convex smooth stochastic approximation with convergence rate 𝒪 ⁡ ( 1 / n ) \mathcal{O}(1/n)
Bach, F. and Moulines, E. (2013) · 2013
Later among the works it cites.
A real-world system for simultaneous translation of German lectures
Cho, E., Fügen, C., Hermann, T., Kilgour, K., Mediani, M., Mohr, C., Niehues, J., Rottman, K., Saam, C., Stüker, S., and Waibel, A. (2013) · 2013
Later among the works it cites.
A simple, fast, and effective reparameterization of IBM Model 2
Dyer, C., Chahuneau, V., and Smith, N. A. (2013) · 2013
Later among the works it cites.
Learning from natural instructions
Goldwasser, D. and Roth, D. (2013) · 2013
Later among the works it cites.
Scalable modified Kneser-Ney language model estimation
Heafield, K., Pouzyrevsky, I., Clark, J. H., and Koehn, P. (2013) · 2013
Later among the works it cites.
Large-scale expected BLEU training of phrase-based reordering models
Auli, M., Galley, M., and Gao, J. (2014) · 2014
Later among the works it cites.
Online adaptation to post-edits for phrase-based statistical machine translation
Bertoldi, N., Simianer, P., Cettolo, M., Wäschle, K., Federico, M., and Riezler, S. (2014) · 2014
Later among the works it cites.
Simple and scalable response prediction for display advertising
Chapelle, O., Manavaglu, E., and Rosales, R. (2014) · 2014
Later among the works it cites.
Learning from post-editing: Online model adaptation for statistical machine translation
Denkowski, M., Dyer, C., and Lavie, A. (2014) · 2014
Later among the works it cites.
Human effort and machine learnability in computer aided translation
Green, S., Wang, S. I., Chuang, J., Heer, J., Schuster, S., and Manning, C. D. (2014) · 2014
Later among the works it cites.
Response-based learning for grounded machine translation
Riezler, S., Simianer, P., and Haas, C. (2014) · 2014
Later among the works it cites.
Online discriminative learning for machine translation with binary-valued feedback
Saluja, A. and Zhang, Y. (2014) · 2014
Later among the works it cites.
Learning to search better than your teacher
Chang, K.-W., Krishnamurthy, A., Agarwal, A., Daume, H., and Langford, J. (2015) · 2015
Later among the works it cites.
A coactive learning view of online structured prediction in statistical machine translation
Sokolov, A., Riezler, S., and Cohen, S. B. (2015) · 2015
Later among the works it cites.
A comparison of update strategies for large-scale maximum expected bleu training
Wuebker, J., Muehr, S., Lehnen, P., Peitz, S., and Ney, H. (2015) · 2015
Later among the works it cites.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…