Elamur Research
☰
home / papers / 2017 / Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search

Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search

Written for the Research library (claude-opus-5-5) from the paper text. Original — aclanthology.org/P17-1141.pdf

Summary

Neural text generators usually decode with beam search, which cannot guarantee that particular words or phrases appear in the output. Such knowledge is often available at inference time, for example translator corrections, domain terminology, or confident predictions from other classifiers. Hokamp and Liu propose Grid Beam Search (GBS), a decoder that arranges beams in a two-dimensional grid. One axis tracks output timesteps, and the other counts how many constraint tokens a hypothesis already covers. At each step, a hypothesis either generates freely from the model or starts or extends a constraint. Only hypotheses that cover every constraint and emit EOS can be returned. GBS works with any token-by-token sequence model. It requires no changes to model parameters or training data, and it does not depend on source–target alignments or input-coverage search. The authors test it on neural MT in two settings: simulated interactive correction cycles and terminology-driven domain adaptation. Simulated user corrections give large quality gains at each iteration. Even automatically built terminologies yield significant improvements without retraining a general-domain model.

Key points

  • Grid structure: Beams are indexed by timestep t and covered-constraint-token count c. A model plugs into GBS through three operations: generate, start and continue. The scoring function can remain unaware of constraints.
  • Constraint types: A constraint can be either an individual token or a phrase spanning several words, and any number can be given at once. A per-hypothesis coverage vector prevents a constraint from being used twice. Discontinuous constraints, such as phrasal verbs, are handled by adding ordering and gap filters.
  • Experiments: NMT tests cover English→German, English→French and English→Portuguese, with models working on subword segments. The evaluated scenarios are Neural Interactive-Predictive Translation and domain adaptation.
  • Relation to prior work: Prefix-based interactive MT is a special case of GBS with a single constraint fixed at the start of the output. Unlike PRIMT (Cheng et al., 2016) or Moses "XML input" approaches, GBS works at the token level and does not need phrase boundaries.
  • Code: The implementation is released at github.com/chrishokamp/constrained_decoding. Applying GBS to summarization, captioning and dialog is left for future work.

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

Fields: Natural language processing

Cited by

217 papers of our library cite it (of the 140673 whose bibliographies we read); 6 of them have a page here, 211 not yet.

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/p17-1141 · arXiv 1704.07138

@inproceedings{hokamp2017lexically,
  title = {{Lexically Constrained Decoding for Sequence Generation Using Grid Beam Search}},
  author = {Hokamp, Chris and Liu, Qun},
  booktitle = {Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)},
  year = {2017},
  doi = {10.18653/v1/p17-1141},
  eprint = {1704.07138},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.18653/v1/p17-1141}
}

References

35 references, 7 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. 2014. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv:1409.0473 . find our card
  2. Sergio Barrachina, Oliver Bender, Francisco Casacuberta, Jorge Civera, Elsa Cubel, Shahram Khadivi, Antonio Lagarda, Hermann Ney, Jesús Tomás, Enrique Vidal, and Juan-Miguel Vilar. 2009. Statistical approaches to computer-assisted translation. Computational Linguistics 35(1):3–28. https://doi.org/… find
  3. Ondřej Bojar, Rajen Chatterjee, Christian Federmann, Barry Haddow, Matthias Huck, Chris Hokamp, Philipp Koehn, Varvara Logacheva, Christof Monz, Matteo Negri, Matt Post, Carolina Scarton, Lucia Specia, and Marco Turchi. 2015. Findings of the 2015 workshop on statistical machine translation. In Proc… find our card
  4. Shanbo Cheng, Shujian Huang, Huadong Chen, Xinyu Dai, and Jiajun Chen. 2016. PRIMT: A pick-revise framework for interactive machine translation. In NAACL HLT 2016, The 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, San Die… find
  5. David Chiang. 2007. Hierarchical phrase-based translation. Comput. Linguist. 33(2):201–228. https://doi.org/10.1162/coli.2007.33.2.201. ↗ our card
  6. Kyunghyun Cho, Bart van Merriënboer, Çalar Gülçehre, Dzmitry Bahdanau, Fethi Bougares, Holger Schwenk, and Yoshua Bengio. 2014. Learning phrase representations using rnn encoder–decoder for statistical machine translation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Lan… find
  7. Kenneth Ward Church and Patrick Hanks. 1990. Word association norms, mutual information, and lexicography. Comput. Linguist. 16(1):22–29. http://dl.acm.org/citation.cfm?id=89086.89095. ↗ our card
  8. Josep Maria Crego, Jungi Kim, Guillaume Klein, Anabel Rebollo, Kathy Yang, Jean Senellart, Egor Akhanov, Patrice Brunelle, Aurelien Coquard, Yongchao Deng, Satoshi Enoue, Chiyo Geiss, Joshua Johanson, Ardas Khalsa, Raoum Khiari, Byeongil Ko, Catherine Kobus, Jean Lorieux, Leid-iana Martins, Dang-Chu… — [arXiv:1610.05540](https://arxiv.org/abs/1610.05540) find
  9. Miguel Domingo, Alvaro Peris, and Francisco Casacuberta. 2016. Interactive-predictive translation based on multiple word-segments. Baltic J. Modern Computing 4(2):282–291. find
  10. George F. Foster. 2002. Text Prediction for Translators. Ph.D. thesis, Montreal, P.Q., Canada, Canada. AAINQ72434. find
  11. Spence Green. 2014. Mixed-Initiative Natural Language Translation. Ph.D. thesis, Stanford, CA, United States. find
  12. Chloé Kiddon, Luke Zettlemoyer, and Yejin Choi. 2016. Globally coherent text generation with neural checklist models. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, EMNLP 2016, Austin, Texas, USA, November 1-4, 2016. pages 329–339. http://aclweb.org/antho… ↗
  13. Rebecca Knowles and Philipp Koehn. 2016. Neural interactive translation prediction. find
  14. Philipp Koehn. 2009. A process study of computer-aided translation. Machine Translation 23(4):241– 263. https://doi.org/10.1007/s10590-010-9076-3. — [doi:10.1007/s10590-010-9076-3](https://doi.org/10.1007/s10590-010-9076-3) ↗
  15. Philipp Koehn. 2010. Statistical Machine Translation. Cambridge University Press, New York, NY, USA, 1st edition. find
  16. Philipp Koehn, Hieu Hoang, Alexandra Birch, Chris Callison-Burch, Marcello Federico, Nicola Bertoldi, Brooke Cowan, Wade Shen, Christine Moran, Richard Zens, Chris Dyer, Ondřej Bojar, Alexandra Constantin, and Evan Herbst. 2007. Moses: Open source toolkit for statistical machine translation. In Pro… find
  17. Stroudsburg, PA, USA, ACL ’07, pages 177–180. http://dl.acm.org/citation.cfm?id=1557769.1557821. ↗
  18. Franz Josef Och and Hermann Ney. 2004. The alignment template approach to statistical machine translation. Comput. Linguist. 30(4):417–449. https://doi.org/10.1162/0891201042544884. ↗
  19. Judea Pearl. 1984. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA. find
  20. Alexander Rush, Yin-Wen Chang, and Michael Collins. 2013. Optimal beam search for machine translation. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, Seattle, Washington, USA, pages 210–221. http://www.aclweb.org/… ↗
  21. Alexander M. Rush, Sumit Chopra, and Jason Weston. 2015. A neural attention model for abstractive sentence summarization. In Llus Mrquez, Chris Callison-Burch, Jian Su, Daniele Pighin, and Yuval Marton, editors, EMNLP. The Association for Computational Linguistics, pages 379–389. find
  22. Rico Sennrich, Barry Haddow, and Alexandra Birch. 2016. Neural machine translation of rare words with subword units. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016, August 7-12, 2016, Berlin, Germany, Volume 1: Long Papers. http://aclweb.org/anth… ↗
  23. Iulian V. Serban, Alessandro Sordoni, Yoshua Bengio, Aaron Courville, and Joelle Pineau. 2016. Building end-to-end dialogue systems using generative hierarchical neural network models. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence. AAAI Press, AAAI’16, pages 3776–3783. h… find our card
  24. Jason R. Smith, Herve Saint-amand, Chris Callison-burch, Magdalena Plamada, and Adam Lopez. 2013. Dirt cheap web-scale parallel text from the common crawl. In In Proceedings of the Conference of the Association for Computational Linguistics (ACL. find
  25. Lucia Specia. 2011. Exploiting objective annotations for measuring translation post-editing effort. In Proceedings of the European Association for Machine Translation. May. find
  26. Ralf Steinberger, Bruno Pouliquen, Anna Widiger, Camelia Ignat, Toma Erjavec, and Dan Tufi. 2006. The jrc-acquis: A multilingual aligned parallel corpus with 20+ languages. In In Proceedings of the 5th International Conference on Language Resources and Evaluation (LREC’2006. pages 2142–2147. find
  27. Ilya Sutskever, Oriol Vinyals, and Quoc V. Le. 2014. Sequence to sequence learning with neural networks. In Proceedings of the 27th Zhaopeng Tu, Yang Liu, Lifeng Shang, Xiaohua Liu, and Hang Li. 2016. Neural machine translation with reconstruction. arXiv preprint arXiv:1611.01874 . find
  28. Bart van Merrinboer, Dzmitry Bahdanau, Vincent Dumoulin, Dmitriy Serdyuk, David Warde-Farley, Jan Chorowski, and Yoshua Bengio. 2015. Blocks and fuel: Frameworks for deep learning. CoRR abs/1506.00619. find
  29. Tsung-Hsien Wen, Milica Gašić, Nikola Mrkšić, Pei-Hao Su, David Vandyke, and Steve Young. 2015. Semantically conditioned lstm-based natural language generation for spoken dialogue systems. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing (EMNLP). Associat… find
  30. 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, ukasz Kaiser, Stephan Gouws, Yoshikiyo Kato, Taku Kudo, Hideto Kazawa, Keith Stevens, George Kurian, Ni… find
  31. Joern Wuebker, Spence Green, John DeNero, Sasa Hasan, and Minh-Thang Luong. 2016. Models and inference for prefix-constrained machine translation. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Association for Computational Linguis… find
  32. Kelvin Xu, Jimmy Ba, Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio. 2015. Show, attend and tell: Neural image caption generation with visual attention. In David Blei and Francis Bach, editors, Proceedings of the 32nd International Conference on Machin… find our card
  33. Matthew D. Zeiler. 2012. ADADELTA: an adaptive learning rate method. CoRR abs/1212.5701. http://arxiv.org/abs/1212.5701. ↗ our card
  34. Ventsislav Zhechev. 2012. Machine Translation Infrastructure and Post-editing Performance at Autodesk. find
  35. In AMTA 2012 Workshop on Post-Editing Technology and Practice (WPTP 2012). Association for Machine Translation in the Americas (AMTA), San Diego, USA, pages 87–96. find