Elamur Research⌕
☰
home / papers / 2020 / If beam search is the answer, what was the question?

If beam search is the answer, what was the question?

Paper · 2020 · Clara Meister, Ryan Cotterell and Tim Vieira

Summary

In neural machine translation, exact MAP decoding often gives poor output. Prior work found it returns the empty string in over half of cases. Beam search makes many search errors yet produces better text. The authors ask which objective beam search actually solves. They add a regularizer to the MAP objective so that exactly decoding the regularized objective reproduces beam search's output. This regularizer favors hypotheses whose per-token surprisal is spread evenly. That links beam search's hidden inductive bias to the uniform information density (UID) hypothesis from cognitive science.

Building on this, they design several UID-promoting regularizers (greedy, squared, variance, local consistency, and a combination) and test them on NMT with both exact search and beam search. Sentences whose surprisals vary less tend to score higher BLEU. Regularized exact search gets close to beam-search quality, and UID regularization largely prevents the usual BLEU collapse at large beam sizes. The work explains why beam search succeeds and offers a principled alternative to ad hoc fixes such as length normalization.

Key points

  • Beam search is recast as exact search over a MAP objective with a UID-style penalty on uneven surprisal. Surprisal here means negative log-probability per token.
  • There is a strong inverse relationship between corpus BLEU and the average per-sentence standard deviation of surprisals. As the greedy-regularizer strength λ grows, exact-search BLEU approaches that of the best beam search.
  • On the first 1000 sentences of Newstest2014, unregularized beam search falls from 36.42 BLEU (k=5) to 14.66 (k=500).
    • With UID regularizers it stays near 36 at k=500: squared 35.96, greedy 36.15, combined 36.35.
    • Length normalization reaches 35.11 at k=500.
  • The best k=5 score is 36.92, from the squared regularizer.
    • Combining regularizers adds little, suggesting one UID constraint is enough.
    • The pure variance-based regularizers perform worst, possibly because they do not also penalize high surprisal.
  • Code is released at github.com/rycolab/uid-decoding.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Johns Hopkins UniversityBaltimore · United States187 works · 92,194 citations🎓University of CambridgeCambridge · United Kingdom155 works · 115,562 citations🎓ETH ZurichZurich · Switzerland36 works · 4,534 citations

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 works

Cite

Cite as Clara Meister, Ryan Cotterell and Tim Vieira. 2020. If beam search is the answer, what was the question?. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP).

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2020.emnlp-main.170

@inproceedings{meister2020if,
  title = {{If beam search is the answer, what was the question?}},
  author = {Clara Meister, Ryan Cotterell and Tim Vieira},
  booktitle = {Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)},
  year = {2020},
  doi = {10.18653/v1/2020.emnlp-main.170},
  url = {https://doi.org/10.18653/v1/2020.emnlp-main.170}
}

References

54 references, 21 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015. Neural machine translation by jointly learning to align and translate. In 3rd International Conference on Learning Representations.
  2. Samy Bengio, Oriol Vinyals, Navdeep Jaitly, and Noam Shazeer. 2015. Scheduled sampling for sequence prediction with recurrent neural networks. In Advances in Neural Information Processing Systems 28. find
  3. Ondřej Bojar, Christian Buck, Christian Federmann, Barry Haddow, Philipp Koehn, Johannes Leveling, Christof Monz, Pavel Pecina, Matt Post, Herve Saint-Amand, Radu Soricut, Lucia Specia, and Aleš Tamchyna. 2014. Findings of the 2014 workshop on statistical machine translation. In Proceedings of the…
  4. Mauro Cettolo, Christian Girardi, and Marcello Federico. 2012. Wit 3 : Web inventory of transcribed and translated talks. In Proceedings of the Conference of the European Association for Machine Translation (EAMT). find
  5. Yining Chen, Sorcha Gilroy, Andreas Maletti, Jonathan May, and Kevin Knight. 2018. Recurrent neural networks as weighted language recognizers. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (… find
  6. Kyunghyun Cho, Bart van Merriënboer, Dzmitry Bahdanau, and Yoshua Bengio. 2014. On the properties of neural machine translation: Encoder–decoder approaches. In Proceedings of SSST-8, Eighth Workshop on Syntax, Semantics and Structure in Statistical Translation, pages 103–111, Doha, Qatar. Associati…
  7. Eldan Cohen and Christopher Beck. 2019. Empirical analysis of beam search performance degradation in neural sequence models. In Proceedings of the International Conference on Machine Learning, volume 97, Long Beach, California, USA. PMLR. find
  8. Edsger W. Dijkstra. 1959. A note on two problems in connexion with graphs. Numerische Mathematik, 1(1). find
  9. Sergey Edunov, Myle Ott, Michael Auli, and David Grangier. 2018. Understanding back-translation at scale. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 489–500, Brussels, Belgium. Association for Computational Linguistics. find
  10. Angela Fan, Mike Lewis, and Yann Dauphin. 2018. Hierarchical neural story generation. CoRR, abs/1805.04833. find
  11. Jonas Gehring, Michael Auli, David Grangier, Denis Yarats, and Yann N. Dauphin. 2017. Convolutional sequence to sequence learning. In Proceedings of the International Conference on Machine Learning -Volume 70, ICML’17. JMLR.org.
  12. Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. 2017. On calibration of modern neural networks. In Proceedings of the International Conference on Machine Learning, ICML’17. JMLR.org. find
  13. Proceedings of the Tenth Workshop on Statistical Machine Translation, pages 134–140, Lisbon, Portugal. Association for Computational Linguistics. find
  14. Nal Kalchbrenner and Phil Blunsom. 2013. Recurrent convolutional neural networks for discourse compositionality. In Proceedings of the Workshop on Continuous Vector Space Models and their Compositionality, pages 119–126, Sofia, Bulgaria. Association for Computational Linguistics.
  15. Jon Kleinberg and Éva Tardos. 2005. Algorithm Design. Addison-Wesley Longman Publishing Co., Inc., USA. find
  16. Philipp Koehn. 2004. Pharaoh: A beam search decoder for phrase-based statistical machine translation models. In Machine Translation: From Real Users to Research, Berlin, Heidelberg. Springer Berlin Heidelberg. find
  17. John Hale. 2001. A probabilistic Earley parser as a psycholinguistic model. In Second Meeting of the North American Chapter of the Association for Computational Linguistics.
  18. Philipp Koehn and Rebecca Knowles. 2017. Six challenges for neural machine translation. In Proceedings of the First Workshop on Neural Machine Translation, pages 28–39, Vancouver. Association for Computational Linguistics. find
  19. Wei He, Zhongjun He, Hua Wu, and Haifeng Wang. 2016. Improved neural machine translation with smt features. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, AAAI’16. AAAI Press. find
  20. Philipp Koehn, Franz J. Och, and Daniel Marcu. 2003. Statistical phrase-based translation. In Proceedings of the 2003 Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics, pages 127–133. find
  21. Ari Holtzman, Jan Buys, Maxwell Forbes, and Yejin Choi. 2020. The curious case of neural text degeneration. International Conference on Learning Representations. find
  22. Aviral Kumar and Sunita Sarawagi. 2019. Calibration of encoder decoder models for neural machine translation. CoRR, abs/1903.00802. find
  23. Liang Huang, Kai Zhao, and Mingbo Ma. 2017. When to finish? optimal beam search for neural text generation (modulo beam size). In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 2134–2139, Copenhagen, Denmark. Association for Computational Linguistics. find
  24. T. Florian Jaeger. 2010. Redundancy and reduction: Speakers manage syntactic information density. Cognitive Psychology, 61(1). find
  25. T. Florian Jaeger and Harry Tily. 2011. On language ’utility’: Processing complexity and communicative efficiency. Wiley Interdisciplinary Reviews: Cognitive Science, 2. find
  26. Ayush Jain, Vishal Singh, Sidharth Ranjan, Rajakrishnan Rajkumar, and Sumeet Agarwal. 2018. Uniform information density effects on syntactic choice in Hindi. In Proceedings of the Workshop on Linguistic Complexity and Natural Language Processing, pages 38–48, Santa Fe, New-Mexico. Association for Co… find
  27. Sébastien Jean, Orhan Firat, Kyunghyun Cho, Roland Memisevic, and Yoshua Bengio. 2015. Montreal neural machine translation systems for WMT’15. In Roger Levy. 2005. Probabilistic Models of Word Order and Syntactic Discontinuity. Ph.D. thesis, Stanford, CA, USA. find
  28. Roger P. Levy and T. F. Jaeger. 2007. Speakers optimize information density through syntactic reduction. In B. Schölkopf, J. C. Platt, and T. Hoffman, editors, Advances in Neural Information Processing Systems 19. MIT Press. find
  29. Jiwei Li, Michel Galley, Chris Brockett, Jianfeng Gao, and Bill Dolan. 2016. A diversity-promoting objective function for neural conversation models. In Proceedings of the 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pag…
  30. Clara Meister, Tim Vieira, and Ryan Cotterell. 2020. Best-first beam search. Transactions of the Association for Computational Linguistics. find
  31. Kenton Murray and David Chiang. 2018. Correcting length bias in neural machine translation. In Proceedings of the Third Conference on Machine Translation: Research Papers, pages 212–223, Belgium, Brussels. Association for Computational Linguistics. find
  32. Nathan Ng, Kyra Yee, Alexei Baevski, Myle Ott, Michael Auli, and Sergey Edunov. 2019. Facebook FAIR’s WMT19 news translation task submission. In Proceedings of the Fourth Conference on Machine Translation (Volume 2: Shared Task Papers, Day 1), pages 314–319, Florence, Italy. Association for Computat…
  33. Felix Stahlberg and Bill Byrne. 2019. On NMT Search Errors and Model Errors: Cat Got Your Tongue? In Proceedings of the Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), Hong Kong, China. Associati…
  34. Franz Josef Och, Christoph Tillmann, and Hermann Ney. 1999. Improved alignment models for statistical machine translation. In 1999 Joint SIGDAT Conference on Empirical Methods in Natural Language Processing and Very Large Corpora.
  35. Felix Stahlberg, Eva Hasler, Danielle Saunders, and Bill Byrne. 2017. SGNMT – a flexible NMT decoding platform for quick prototyping of new models and search strategies. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 25–30, Cop… find
  36. Myle Ott, Michael Auli, David Grangier, and Marc’Aurelio Ranzato. 2018a. Analyzing uncertainty in neural machine translation. ICML.
  37. Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. 2019. fairseq: A fast, extensible toolkit for sequence modeling. In Proceedings of NAACL-HLT 2019: Demonstrations.
  38. Myle Ott, Sergey Edunov, David Grangier, and Michael Auli. 2018b. Scaling neural machine translation. In Proceedings of the Third Conference on Machine Translation: Research Papers, pages 1–9, Belgium, Brussels. Association for Computational Linguistics.
  39. Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002. BLEU: A method for automatic evaluation of machine translation. In Proceedings of the Annual Meeting on Association for Computational Linguistics.
  40. Matt Post. 2018. A call for clarity in reporting BLEU scores. In Proceedings of the Conference on Machine Translation: Research Papers.
  41. Raj Reddy. 1977. Speech understanding systems: A summary of results of the five-year research effort at carnegie mellon university. find
  42. Iulian Serban, Tim Klinger, Gerald Tesauro, Kartik Talamadupula, Bowen Zhou, Yoshua Bengio, and Aaron Courville. 2017. Multiresolution recurrent neural networks: An application to dialogue response generation. find
  43. Shiqi Shen, Yong Cheng, Zhongjun He, Wei He, Hua Wu, Maosong Sun, and Yang Liu. 2016. Minimum risk training for neural machine translation. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1683–1692, Berlin, Germany. Associatio…
  44. Pavel Sountsov and Sunita Sarawagi. 2016. Length bias in encoder decoder models and a case for global conditioning. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 1516–1525, Austin, Texas. Association for Computational Linguistics. find
  45. Ilya Sutskever, Oriol Vinyals, and Quoc V. Le. 2014. Sequence to sequence learning with neural networks. In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 27. Curran Associates, Inc. find
  46. Zhaopeng Tu, Zhengdong Lu, Yang Liu, Xiaohua Liu, and Hang Li. 2016. Modeling coverage for neural machine translation. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 76– 85, Berlin, Germany. Association for Computational Ling…
  47. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. In Advances in Neural Information Processing Systems, volume 30.
  48. Ashwin K. Vijayakumar, Michael Cogswell, Ramprasaath R. Selvaraju, Qing Sun, Stefan Lee, David J. Crandall, and Dhruv Batra. 2018. Diverse beam search for improved description of complex scenes. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence. AAAI Press. find
  49. Oriol Vinyals and Quoc V. Le. 2015. A neural conversational model. CoRR, abs/1506.05869.
  50. Oriol Vinyals, Alexander Toshev, Samy Bengio, and Dumitru Erhan. 2017. Show and tell: Lessons learned from the 2015 mscoco image captioning challenge. IEEE Transactions on Pattern Analysis and Machine Intelligence, 39(4):652–663. find
  51. Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V. Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, Jeff Klingner, Apurva Shah, Melvin Johnson, Xiaobing Liu, Lukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, Keith Stevens, George Kurian, N… find
  52. CoRR, Yilin Yang, Liang Huang, and Mingbo Ma. 2018. Breaking the beam search curse: A study of (re-)scoring methods and stopping criteria for neural machine translation. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pages 3054–3059, Brussels, Belgium. Ass…
  53. Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. 2019. Xlnet: Generalized autoregressive pretraining for language understanding. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information P…
  54. Jun Yin, Xin Jiang, Zhengdong Lu, Lifeng Shang, Hang Li, and Xiaoming Li. 2016. Neural generative question answering. In Proceedings of the Workshop on Human-Computer Question Answering, pages 36–42, San Diego, California. Association for Computational Linguistics. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/meister-2020-if-beam-search-is-answer/