CoChat
Sign Up
PreprintCited by 14Natural Language Processing TechniquesAdvanced Bandit Algorithms ResearchMachine Learning and Algorithms

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

Open access
Sokolov, Artem, Riezler, Stefan, Urvoy, Tanguy·2016·arXiv
DOI 10.48550/arxiv.1601.04468arXiv 1601.04468
Open this paper in CoChat — free accountOpen PDF

Abstract

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. Our experiments show that our approach improves translation quality and is comparable to approaches that employ more informative feedback in learning.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1601.04468

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Sparse feedback is a constraint inherent to dealing with text and language.

    “Sparse feedback is a constraint inherent to dealing with text and language [175], as it is often unlikely for a human to provide feedback on incomplete sentences.”

    From RLHF Deciphered: A Critical Analysis of Reinforcement Learning from Human Feedback for LLMs (2026) · cites this paper as [175]

    The Introduction (p. 1) says feedback is limited in many NLP applications and identifies the cost and expertise required for post-editing as reasons. It does not say sparse feedback is inherent to text or language, or that people are unlikely to give feedback on incomplete sentences; the Discussion (p. 9) concerns feedback on predicted translations. (LLM, conf=0.85)

    Experimental — accuracy not yet measured

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

The citation lists haven’t been fetched yet

References 33 · Cited by 14

Research works printed but not linked: 42

  1. Abernethy, J. and Rakhlin, A. (2009). An efficient bandit algorithm for √ T regret in online multiclass prediction? In Conference on Learning Theory (COLT) , Montreal, Canada.
  2. Agarwal, A., Dekel, O., and Xiao, L. (2010). Optimal algorithms for online convex optimization with multi-point bandit feedback. In Conference on Learning Theory (COLT) , Haifa, Israel.
  3. Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E. (2002). The nonstochastic multiarmed bandit problem. SIAM Journal on Computing , 32(1):48-77.
  4. Auli, M., Galley, M., and Gao, J. (2014). Large-scale expected BLEU training of phrase-based reordering models. In Conference on Empirical Methods in Natural Language Processing (EMNLP) .
  5. Bach, F. and Moulines, E. (2011). Non-asymptotic analysis of stochastic approximation algorithms for machine learning. In Advances in Neural Information Processing Systems (NIPS) , Granada, Spain.
  6. Bach, F. and Moulines, E. (2013). Non-strongly-convex smooth stochastic approximation with convergence rate O (1 /n ) . In Advances in Neural Information Processing Systems (NIPS) , Lake Tahoe, CA, USA.
  7. Bottou, L. (2004). Stochastic learning. In Bousquet, O. and von Luxburg, U., editors, Advanced Lectures on Machine Learning , pages 146-168.
  8. Branavan, S., Chen, H., Zettlemoyer, L. S., and Barzilay, R. (2009). Reinforcement learning for mapping instructions to actions. In Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP , Suntec, Singapore.
  9. Chang, K.-W., Krishnamurthy, A., Agarwal, A., Daume, H., and Langford, J. (2015). Learning to search better than your teacher. In International Conference on Machine Learning (ICML) , Lille, France.
  10. Chapelle, O., Manavaglu, E., and Rosales, R. (2014). Simple and scalable response prediction for display advertising. ACM Transactions on Intelligent Systems and Technology , 5(4).
  11. Cho, E., F¨ ugen, C., Hermann, T., Kilgour, K., Mediani, M., M ohr, C., Niehues, J., Rottman, K., Saam, C., St¨ uker, S., and Waibel, A. (2013). A real-world sy stem for simultaneous translation of German lectures. In Interspeech , Lyon, France.
  12. Chu, W., Li, L., Reyzin, L., and Schapire, R. E. (2011). Contextual bandits with linear payoff functions. In International Conference on Artificial Intelligence and Statistics (AISTATS) , Fort Lauderdale, FL, USA.
  13. Clark, J., Dyer, C., Lavie, A., and Smith, N. (2011). Better hypothesis testing for statistical machine translation: Controlling for optimizer instability. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics (ACL'11) , Portland, OR.
  14. Daum´ e, H. and Jagarlamudi, J. (2011). Domain adaptation for machine translation by mining unseen words. In Meeting of the Association for Computational Linguistics: Human Language Technologies (ACL-HLT) , Portland, OR, USA.
  15. Denkowski, M., Dyer, C., and Lavie, A. (2014). Learning from post-editing: Online model adaptation for statistical machine translation. In Conference of the European Chapter of the Association for Computational Linguistics (EACL) , Gothenburg, Sweden.
  16. Dyer, C., Chahuneau, V., and Smith, N. A. (2013). A simple, fast, and effective reparameterization of IBM Model 2. In Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (NAACL-HLT) , Atlanta, GA, USA.
  17. Flaxman, A. D., Kalai, A. T., and McMahan, H. B. (2005). Online convex optimization in the bandit setting: gradient descent without a gradient. In ACM-SIAM Symposium on Discrete Algorithms (SODA) , Philadelphia, PA.
  18. Goldwasser, D. and Roth, D. (2013). Learning from natural instructions. Machine Learning , 94(2):205-232.
  19. Green, S., Wang, S. I., Chuang, J., Heer, J., Schuster, S., and Manning, C. D. (2014). Human effort and machine learnability in computer aided translation. In Conference on Empirical Methods in Natural Language Processing (EMNLP) , Doha, Qatar.
  20. He, X. and Deng, L. (2012). Maximum expected BLEU training of phrase and lexicon translation models. In Meeting of the Association for Computational Linguistics (ACL) , Jeju Island, Korea.
  21. Heafield, K., Pouzyrevsky, I., Clark, J. H., and Koehn, P. (2013). Scalable modified KneserNey language model estimation. In Meeting of the Association for Computational Linguistics (ACL) , Sofia, Bulgaria.
  22. 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). Moses: Open source toolkit for statistical machine translation. In ACL Demo and Poster Sessions , Prague, Czech Republic.
  23. Koehn, P. and Schroeder, J. (2007). Experiments in domain adaptation for statistical machine translation. In Workshop on Statistical Machine Translation , Prague, Czech Republic.
  24. Langford, J. and Zhang, T. (2007). The epoch-greedy algorithm for multi-armed bandits with side information. In Advances in Neural Information Processing Systems (NIPS) . Vancouver, Canada.
  25. Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. (2009). Robust stochastic approximation approach to stochastic programming. SIAM Journal on Optimization , 19(4):1574-1609.
  26. Och, F. J. (2003). Minimum error rate training in statistical machine translation. In Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (HLT-NAACL) , Edmonton, Canada.
  27. Papandreou, G. and Yuille, A. (2011). Perturb-and-map random fields: Using discrete optimization to learn and sample from energy models. In IEEE International Conference on Computer Vision (ICCV) , Barcelona, Spain.
  28. Polyak, B. T. and Juditsky, A. B. (1992). Acceleration of stochastic approximation by averaging. SIAM Journal on Control and Optimization , 30(4):838-855.
  29. Polyak, B. T. and Tsypkin, Y. Z. (1973). Pseudogradient adaptation and training algorithms. Automation and remote control: a translation of Avtomatika i Telemekhanika , 34(3):377-397.
  30. Riezler, S. and Maxwell, J. (2005). On some pitfalls in automatic evaluation and significance testing for MT. In Proceedings of the ACL-05 Workshop on Intrinsic and Extrinsic Evaluation Measures for MT and/or Summarization , Ann Arbor, MI.
  31. Riezler, S., Simianer, P., and Haas, C. (2014). Response-based learning for grounded machine translation. In Meeting of the Association for Computational Linguistics (ACL) , Baltimore, MD, USA.
  32. Robbins, H. (1952). Some aspects of the sequential design of experiments. Bulletin of the American Statistical Society , 55:527-535.
  33. Shalev-Shwartz, S. (2012). Online learning and online convex optimization. Foundations and Trends in Machine Learning , 4(2):107-194.
  34. Smith, D. A. and Eisner, J. (2006). Minimum risk annealing for training log-linear models. In International Committee on Computational Linguistics and the Association for Computational Linguistics (COLING-ACL) , Sydney, Australia.
  35. Snover, M., Dorr, B., Schwartz, R., Micciulla, L., and Makhoul, J. (2006). A study of translation edit rate with targeted human annotation. In Conference of the Association for Machine Translation in the Americas (AMTA) , Cambridge, MA, USA.
  36. Sokolov, A., Riezler, S., and Cohen, S. B. (2015). A coactive learning view of online structured prediction in statistical machine translation. In Proceedings of the Conference on Computational Natural Language Learning (CoNLL) , Beijing, China.
  37. Spall, J. C. (2003). Introduction to Stochastic Search and Optimization: Estimation, Simulation, and Control . Wiley.
  38. Sutton, R. S., McAllester, D., Singh, S., and Mansour, Y. (2000). Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processings Systems (NIPS) , Vancouver, Canada.
  39. Taskar, B., Klein, D., Collins, M., Koller, D., and Manning, C. (2004). Max-margin parsing. In Conference on Empirical Methods in Natural Language Processing (EMNLP) , Barcelona, Spain.
  40. Tsochantaridis, I., Joachims, T., Hofmann, T., and Altun, Y. (2005). Large margin methods for structured and interdependent output variables. Journal of Machine Learning Research , 5:1453-1484.
  41. Wuebker, J., Muehr, S., Lehnen, P., Peitz, S., and Ney, H. (2015). A comparison of update strategies for large-scale maximum expected bleu training. In Conference of the North American Chapter of the Association for Computational Linguistics Human Language Technologies (NAACL-HLT) , Denver, CO, USA.
  42. Yue, Y. and Joachims, T. (2009). Interactively optimizing information retrieval systems as a dueling bandits problem. In International Conference on Machine Learning (ICML) , Montreal, Canada.

Authors
Sokolov, A., Riezler, S., & Urvoy, T.
Affiliations
Heidelberg University (DE)
ORCID
Urvoy, Tanguy
Venue
arXiv
Publisher
arXiv
Published
2016
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1601.04468
arXiv
1601.04468
OpenAlex
W2278024189
Cited by
14
References
33
Citations by year
2022: 1 · 2021: 1 · 2019: 2 · 2018: 3 · 2017: 4 · 2016: 2 · 2015: 1
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Natural Language Processing Techniques
  • Social Sciences › Decision Sciences › Management Science and Operations Research › Advanced Bandit Algorithms Research
  • Physical Sciences › Computer Science › Artificial Intelligence › Machine Learning and Algorithms
Keywords
bandit feedback, structured prediction, statistical machine translation, partial feedback, interactive machine translation, reinforcement learning from human feedback

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review