Elamur Research⌕
☰
home / papers / 2017 / Beam Search Strategies for Neural Machine Translation

Beam Search Strategies for Neural Machine Translation

Summary

Standard NMT decoding uses a fixed-width beam: at every step it keeps a constant number of hypotheses, even those scoring far below the leader. Larger beams can improve output, but decoding becomes slower and quality eventually stops improving. Freitag and Al-Onaizan (IBM) make the beam adaptive by adding four pruning rules after the usual top-k selection:

  • relative pruning against the best total score,
  • absolute pruning against the best total score,
  • relative pruning on the last word's local score,
  • a cap on candidates sharing the same history, intended to increase diversity.

They test these rules on an in-house attention-based GRU NMT system for two directions:

  • German→English: WMT 2016 data with byte pair encoding.
  • Chinese→English: BOLT data.

For each rule, they pick the largest threshold that leaves translation quality unchanged on a selection set. Used together, the rules shrink the average fan-out and speed up decoding by up to 43% with no loss in BLEU or TER. The history cap brought no quality gain. The paper shows that cheap, SMT-style score pruning makes beam search notably faster.

Key points

  • Training data: German→English used WMT 2016 (3.9M sentence pairs, 40k BPE sub-word vocabulary). Chinese→English used 11M BOLT sentence pairs with 300K-word vocabularies. Both systems use 620-dimensional embeddings and 1000-cell GRU layers.
  • German→English (newstest2014/2015): combining all four rules gave 13% speed-up at beam 5 and 43% at beam 14. BLEU stayed at 27.3 and 27.6 respectively on newstest2014.
  • Chinese→English (MT08 nw/wb): combined pruning gave 10% speed-up at beam 5 and 24% at beam 14. BLEU held at about 35.3 (nw) for beam 14.
  • Search errors: pruning changed 5%/9% of German→English outputs and 4%/22% of Chinese→English outputs (beam 5/14).
  • Other findings:
    • Relative thresholds above 0.6 at beam 5 hurt quality.
    • Pruning makes decoding without any fixed beam possible, but this is slower.
    • The candidates-per-node cap (mc=3) produced almost no speed-up.

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: Machine translation · Natural language processing

Topics: Machine translation

Cited by

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

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/w17-3207

@inproceedings{freitag2017beam,
  title = {{Beam Search Strategies for Neural Machine Translation}},
  author = {Freitag, Markus and Al-Onaizan, Yaser},
  booktitle = {Proceedings of the First Workshop on Neural Machine Translation},
  year = {2017},
  doi = {10.18653/v1/w17-3207},
  url = {https://doi.org/10.18653/v1/w17-3207}
}

References

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

  1. 2016 conference on machine translation (wmt16). Proceedings of WMT . find
  2. D. Bahdanau, K. Cho, and Y. Bengio. 2014. Neural machine translation by jointly learning to align and translate. ArXiv e-prints . find our card
  3. Nicolas Boulanger-Lewandowski, Yoshua Bengio, and Pascal Vincent. 2013. Audio chord recognition with recurrent neural networks. In ISMIR. Citeseer, pages 335–340. find
  4. Christopher M Bishop. 1995. Neural networks for pattern recognition. Oxford university press. find
  5. Alex Graves. 2012. Sequence transduction with recurrent neural networks. arXiv preprint arXiv:1211.3711 . find our card
  6. Ondrej Bojar, Rajen Chatterjee, Christian Federmann, Yvette Graham, Barry Haddow, Matthias Huck, Antonio Jimeno Yepes, Philipp Koehn, Varvara Logacheva, Christof Monz, et al. 2016. Findings of the Xiaoguang Hu, Wei Li, Xiang Lan, Hua Wu, and Haifeng Wang. 2015. Improved beam search with constrained… find
  7. Sébastien Jean, Kyunghyun Cho, Roland Memisevic, and Yoshua Bengio. 2015. On using very large target vocabulary for neural machine translation. In Proceedings of ACL. Beijing, China, pages 1–10. find our card
  8. Nal Kalchbrenner and Phil Blunsom. 2013. Recurrent continuous translation models. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, Seattle. find
  9. Thang Luong, Ilya Sutskever, Quoc Le, Oriol Vinyals, and Wojciech Zaremba. 2015. Addressing the rare word problem in neural machine translation. In Proceedings of ACL. Beijing, China, pages 11–19. find our card
  10. Haitao Mi, Zhiguo Wang, and Abe Ittycheriah. 2016. Vocabulary manipulation for neural machine translation. arXiv preprint arXiv:1605.03209 . find
  11. Rico Sennrich, Barry Haddow, and Alexandra Birch. 2015. Neural machine translation of rare words with subword units. arXiv preprint arXiv:1508.07909 . find
  12. Ilya Sutskever, Oriol Vinyals, and Quoc V. Le. 2014. Sequence to sequence learning with neural networks. In Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada. pages 3104– 3112. http://pa… find
  13. Yonghui Wu, Mike Schuster, Zhifeng Chen, Quoc V Le, Mohammad Norouzi, Wolfgang Macherey, Maxim Krikun, Yuan Cao, Qin Gao, Klaus Macherey, et al. 2016. Google’s neural machine translation system: Bridging the gap between human and machine translation. arXiv preprint arXiv:1609.08144 . find
  14. Richard Zens, Daisy Stanton, and Peng Xu. 2012. A systematic comparison of phrase table pruning techniques. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. Association for Computational Linguistics, pages 97… find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/papers/freitag-2017-beam-search-strategies-neural-machine/