Elamur Research
☰
home / papers / 2018 / Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation

Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation

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

Summary

Neural machine translation offers less direct control over output than older phrase-based systems. Lexically constrained decoding partly restores that control by changing beam search so that user-specified target words or phrases must appear in the translation. Earlier methods become more expensive as constraints are added. Grid beam search (GBS) grows linearly with the number of constraints, and constrained beam search (CBS) grows exponentially. GBS also changes the beam size for every sentence, which makes batching and fixed GPU computation graphs hard to use.

Post and Vilar propose dynamic beam allocation (DBA). It keeps one beam of fixed size k and, at each step, divides its slots among banks of hypotheses grouped by how many constraints they have satisfied. The added cost does not depend on the number of constraints. Experiments use English–German RNN models in SOCKEYE. DBA places constraints in sensible positions without any source-side or alignment information, and it runs much faster than GBS. Constrained decoding thus becomes practical even with many constraints, including those created by BPE splitting.

Key points

  • Decoding cost is O(Nk) for DBA, compared with O(NkC) for GBS and exponential growth in C for CBS (N = output length, k = beam size, C = number of constraints).
  • At each step, candidates come from three sources: the overall top-k tokens, every unmet constraint for each hypothesis, and each hypothesis's single best next token. The beam is then filled from these candidates according to a bank allocation policy.
  • Word constraints and phrasal constraints (including subwords from BPE) are counted per token. A phrase that is left incomplete is reset to unmet.
  • Constraint positions in the output correlate strongly with their positions in the reference (Pearson's r = 0.82), although no alignment information is used.
  • Using a 4-layer RNN running on a Volta GPU, decoding needs roughly 0.6 seconds per sentence, even when there are 10 or more constraints. Pruning is needed to avoid runaway runtimes; early stopping also prevents them but lowered BLEU. The implementation is released in SOCKEYE.

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

Topics: Machine translation

Cited by

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

Cite

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

@inproceedings{post2018fast,
  title = {{Fast Lexically Constrained Decoding with Dynamic Beam Allocation for Neural Machine Translation}},
  author = {Post, Matt and Vilar, David},
  booktitle = {Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers)},
  year = {2018},
  doi = {10.18653/v1/n18-1119},
  eprint = {1804.06609},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.18653/v1/n18-1119}
}

References

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

  1. Peter Anderson, Basura Fernando, Mark Johnson, and Stephen Gould. 2017. Guided open vocabulary image captioning with constrained beam search. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 936–945. Association for Computational Linguistics. find
  2. Philip Arthur, Graham Neubig, and Satoshi Nakamura. 2016. Incorporating discrete translation lexicons into neural machine translation. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 1557–1567. Association for Computational Linguistics. find
  3. Ondřej Bojar, Rajen Chatterjee, Christian Federmann, Yvette Graham, Barry Haddow, Shujian Huang, Matthias Huck, Philipp Koehn, Qun Liu, Varvara Logacheva, Christof Monz, Matteo Negri, Matt Post, Raphael Rubino, Lucia Specia, and Marco Turchi. 2017. Findings of the 2017 conference on machine transla… find our card
  4. Josep 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, Leidiana Martins, Dang-Chuan Nguy… find
  5. Felix Hieber, Tobias Domhan, Michael Denkowski, David Vilar, Artem Sokolov, Ann Clifton, and Matt Post. 2017. Sockeye: A toolkit for neural machine translation. Computing Research Repository, abs/1712.05690. — [arXiv:1712.05690](https://arxiv.org/abs/1712.05690) find
  6. Chris Hokamp and Qun Liu. 2017. Lexically constrained decoding for sequence generation using grid beam search. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1535– 1546. Association for Computational Linguistics. find our card
  7. Howard Johnson, Joel Martin, George Foster, and Roland Kuhn. 2007. Improving translation quality by discarding most of the phrasetable. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL). find
  8. Rebecca Knowles and Philipp Koehn. 2016. Neural interactive translation prediction. In Proceedings of the Association for Machine Translation in the Americas, pages 107–120. find
  9. 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. Association for Computational Linguistics. find
  10. 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. find
  11. Pierre Lison and Jörg Tiedemann. 2016. Opensubtitles2016: Extracting large parallel corpora from movie and tv subtitles. In Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC 2016), Paris, France. European Language Resources Association (ELRA). find our card
  12. Bruce T. Lowerre. 1976. The HARPY speech recognition system. Ph.D. thesis, Carnegie-Mellon University. find
  13. Christopher Manning, Mihai Surdeanu, John Bauer, Jenny Finkel, Steven Bethard, and David McClosky. 2014. The stanford corenlp natural language processing toolkit. In Proceedings of 52nd Annual Meeting of the Association for Computational Linguistics: System Demonstrations, pages 55–60. Association f… find our card
  14. Myle Ott, Michael Auli, David Grangier, and Marc’Aurelio Ranzato. 2018. Analyzing uncertainty in neural machine translation. CoRR, abs/1803.00047. find our card
  15. Matt Post. 2018. A call for clarity in reporting bleu scores. Computing Research Repository, abs/1804.08771. find our card
  16. Rico Sennrich. 2017. How grammatical is character-level neural machine translation? assessing mt quality with contrastive translation pairs. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 2, Short Papers, pages 376–382. Associat… find our card
  17. 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 (Volume 1: Long Papers), pages 1715– 1725. Association for Computational Linguistics. find
  18. 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, pages 3104–3112. Curran Associates, Inc. find
  19. Yaohua Tang, Fandong Meng, Zhengdong Lu, Hang Li, and Philip L. H. Yu. 2016. Neural machine translation with external phrase memory. CoRR. find
  20. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. 2017. Attention is all you need. CoRR. find
  21. 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, N… find
  22. 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), pages 66–75. Association for Computat… find