Elamur Research
☰
home / papers / 2016 / Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models

Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models

Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "arXiv — non-exclusive license to distribute" does not allow redistributing the text itself. Original — arxiv.org/pdf/1610.02424

Summary

Beam search (BS), the standard approximate decoder for neural sequence models such as RNNs and LSTMs, tends to return candidates that are almost the same. Most beams branch from one strong prefix and differ only near the end. This wastes computation and fails to reflect the many valid outputs in ambiguous tasks such as describing an image.

The authors propose Diverse Beam Search (DBS). It splits the beam budget into groups and runs beam search within each group. Each later group's token scores are penalized by a dissimilarity term (weighted by a strength λ) that measures overlap with the groups already decoded. The search is therefore greedy in two directions, over time steps and over groups, and costs about as much time and memory as BS.

DBS was tested on three tasks (generating captions for images, translating between languages and producing questions about images), using automatic metrics and human preference studies. It beat BS and earlier diverse-decoding methods on oracle and diversity metrics, and it often also found better top-1 outputs. The gains were largest for complex images, which suggests DBS is simply a better search procedure.

Key points

  • Optimizing all B beams jointly is intractable: the solution space grows as |V|^B and can approach 10^60 in typical language settings. Grouping the beams avoids this joint search, and G = 1 reduces exactly to classical BS (the appendix illustrates B = 6 with G ∈ {1, 3, 6}).
  • Results on the PASCAL-50S validation split show that DBS is robust across a wide range of λ values. Of the dissimilarity functions tested, Hamming diversity scored best, and all variants outperformed BS.
  • In human studies on PASCAL-50S, a caption list counted as preferred when at least 3 of 5 turkers chose it. DBS was preferred for:
    • 50.51% of low-difficulty images (481 images),
    • 69.92% of mid-difficulty images (409 images),
    • 83.63% of high-difficulty images (110 images).
  • Even on simple, iconic images, DBS sometimes won because the statistics of the training and test data did not match.
  • Code is available at github.com/ashwinkalyan/dbs, and an image-captioning demo is hosted at dbs.cloudcv.org.

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: Other

Cited by

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

Cite

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1610.02424 · arXiv 1610.02424

@misc{vijayakumar2016diverse,
  title = {{Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models}},
  author = {Vijayakumar, Ashwin K and Cogswell, Michael and Selvaraju, Ramprasath R. and Sun, Qing and Lee, Stefan and Crandall, David and Batra, Dhruv},
  year = {2016},
  doi = {10.48550/arxiv.1610.02424},
  eprint = {1610.02424},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1610.02424}
}

References

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

  1. Stanislaw Antol, Aishwarya Agrawal, Jiasen Lu, Margaret Mitchell, Dhruv Batra, C Lawrence Zitnick, and Devi Parikh. VQA: Visual question answering. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2425–2433, 2015. find
  2. Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. Proceedings of the International Conference on Learning Repre-Oracle SPICE@k Distinct n-Grams @20 n=1 @5 @10 21.96 23.16 26.74 22.41 25.23 27.59 23.11 25.71 27.94 0.31 0.34 0.43… find our card
  3. Dhruv Batra, Payman Yadollahpour, Abner Guzman-Rivera, and Gregory Shakhnarovich. Diverse M-Best Solutions in Markov Random Fields. In Proceedings of European Conference on Computer Vision (ECCV), 2012. find
  4. Greg Corrado. Computer, respond to this email. Google Research Blog, November 2015. URL https://research.googleblog.com/. ↗
  5. Francis Ferraro, Ishan Mostafazadeh, Nasrinand Misra, Aishwarya Agrawal, Jacob Devlin, Ross Girshick, Xiadong He, Pushmeet Kohli, Dhruv Batra, and C Lawrence Zitnick. Visual storytelling. Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics – H… find
  6. Jenny Rose Finkel, Christopher D Manning, and Andrew Y Ng. Solving the problem of cascading errors: Approximate bayesian inference for linguistic annotation pipelines. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 618–626, 2006. find
  7. K. Gimpel, D. Batra, C. Dyer, and G. Shakhnarovich. A systematic exploration of diversity in machine translation. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), 2013. find
  8. Alex Graves, Abdel-rahman Mohamed, and Geoffrey E. Hinton. Speech recognition with deep recurrent neural networks. abs/1303.5778, 2013. — [arXiv:1303.5778](https://arxiv.org/abs/1303.5778) find
  9. Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 770–778, 2016. find
  10. Radu Tudor Ionescu, Bogdan Alexe, Marius Leordeanu, Marius Popescu, Dim Papadopoulos, and Vittorio Ferrari. How hard can it be? Estimating the difficulty of visual search in an image. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016. find
  11. Andrej Karpathy and Li Fei-Fei. Deep visual-semantic alignments for generating image descriptions. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015. find our card
  12. Alexander Kirillov, Bogdan Savchynskyy, Dmitrij Schlesinger, Dmitry Vetrov, and Carsten Rother. Inferring m-best diverse labelings in a single one. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015. find
  13. Jiwei Li and Dan Jurafsky. Mutual information and diverse decoding improve neural machine translation. arXiv preprint arXiv:1601.00372, 2016. — [arXiv:1601.00372](https://arxiv.org/abs/1601.00372) find
  14. Jiwei Li, Michel Galley, Chris Brockett, Jianfeng Gao, and Bill Dolan. A diversity-promoting objective function for neural conversation models. Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics – Human Language Technologies (NAACL HLT), 2015… find our card
  15. Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollar, and C. Lawrence Zitnick. Microsoft COCO: Common objects in context, 2014. find our card
  16. Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S. Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in Neural Information Processing Systems (NIPS), 2013. find
  17. Nasrin Mostafazadeh, Ishan Misra, Jacob Devlin, Margaret Mitchell, Xiaodong He, and Lucy Vanderwende. Generating natural questions about an image. Proceedings of the Annual Meeting on Association for Computational Linguistics (ACL), 2016. find
  18. Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. Bleu: a method for automatic evaluation of machine translation. In Proceedings of the Annual Meeting on Association for Computational Linguistics (ACL), 2002. find our card
  19. Dennis Park and Deva Ramanan. N-best maximal decoders for part models. In Proceedings of IEEE International Conference on Computer Vision (ICCV), 2011. find
  20. Adarsh Prasad, Stefanie Jegelka, and Dhruv Batra. Submodular meets structured: Finding diverse subsets in exponentially-large structured item sets. In Advances in Neural Information Processing Systems (NIPS), 2014. find
  21. Ramakrishna Vedantam, C Lawrence Zitnick, and Devi Parikh. Cider: Consensus-based image description evaluation. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015. find our card
  22. Subhashini Venugopalan, Marcus Rohrbach, Jeffrey Donahue, Raymond Mooney, Trevor Darrell, and Kate Saenko. Sequence to sequence-video to text. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 4534–4542, 2015. find
  23. Oriol Vinyals and Quoc Le. A neural conversational model. arXiv preprint arXiv:1506.05869, 2015. find our card
  24. Oriol Vinyals, Alexander Toshev, Samy Bengio, and Dumitru Erhan. Show and tell: A neural image caption generator. In Proceedings of IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015. find our card