Diverse Beam Search: Decoding Diverse Solutions from Neural Sequence Models

By Ashwin K. Vijayakumar, Michael Cogswell, Ramprasaath R. Selvaraju, Qing Sun, Stefan Lee, David J. Crandall, Dhruv Batra. 2016

657 citations recorded by the source corpus.

Neural sequence models are widely used to model time-series data. Equally ubiquitous is the usage of beam search (BS) as an approximate inference algorithm to decode output sequences from these models. BS explores the search space in a greedy left-right fashion retaining only the top-B candidates - resulting in sequences that differ only slightly from each other. Producing lists of nearly identical sequences is not only computationally wasteful but also typically fails to capture the inherent ambiguity of complex AI tasks. To overcome this problem, we propose Diverse Beam Search (DBS), an alternative to BS that decodes a list of diverse outputs by optimizing for a diversity-augmented objective. We observe that our method finds better top-1 solutions by controlling for the exploration and exploitation of the search space - implying that DBS is a better search algorithm. Moreover, these gains are achieved with minimal computational or memory over- head as compared to beam search. To demonstrate the broad applicability of our method, we present results on image captioning, machine translation and visual question generation using both standard quantitative metrics and qualitative human studies. Further, we study the role of diversity for image-grounded language generation tasks as the complexity of the image changes. We observe that our method consistently outperforms BS and previously proposed techniques for diverse decoding from neural sequence models.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Natural Language Processing

Citations in the corpus

fairseq: A Fast, Extensible Toolkit for Sequence Modeling (2019, background): “with user-supplied plug-ins (§2); (ii) efficient distributed and mixed precision training, enabling training over datasets with hundreds of millions of sentences on current hardware (§3); (iii) stateof-the-art implementations and pretrained models for machine translation, summarization, and language”
How Decoding Strategies Affect the Verifiability of Generated Text (2019, background): “To favor the diversity of the exploration, Vijayakumar et al. (2016) propose to divide the beam into groups.”
Wizard of Wikipedia: Knowledge-Powered Conversational agents (2018, background): “The generator without knowledge is particularly prone to many of the typical behaviors of seq2seq systems (Li et al., 2016; Vijayakumar et al., 2016), including local repetition (“cookies are made of ﬂour, oil, oil, and oil”), global repetition (producing the near same utterance for multiple…”
Hierarchical Neural Story Generation (2018, background): “We find this sampling strategy substantially more effective than beam search, which tends to produce common phrases and repetitive text from the training set (Vijayakumar et al., 2016; Shao et al., 2017).”
Learning to Write with Cooperative Discriminators (2018, background): “, 2016), or a diversityboosting objective function (Shao et al., 2017; Vijayakumar et al., 2016).”
Towards Empathetic Open-domain Conversation Models: A New Benchmark and Dataset (2018, methodology): “At inference time, we use diverse beam search from Vijayakumar et al. (2016).”
Accelerating Protein Design Using Autoregressive Generative Models (2019, neutral): “We also anticipate better strategies to explore diverse yet ﬁt regions of sequence space during generation, either by exploiting variance explained by latent variables (Greener et al., 2018) or diverse beam search strategies (Vijayakumar et al., 2016).”
Analyzing Uncertainty in Neural Machine Translation (2018, background): “in the data distribution, or decoding strategies which attempt to predict diverse outputs while leaving the model unchanged (Gimpel et al., 2013; Vijayakumar et al., 2016; Li & Jurafsky, 2016; Cho, 2016).”
Discrete Autoencoders for Sequence Models (2018, background): “On the practical side, sampling from the latent code and then running beam search allows to get valid but highly diverse samples, an important problem with beam search (Vijayakumar et al., 2016).”
Non-Parametric Adaptation for Neural Machine Translation (2019, background): “This strong trend towards combining neural generative models with non-parametric methods is an attempt to counter the weaknesses of neural networks, especially their failure to remember information from individual training instances and the diversity problem of seq2seq models (Vijayakumar et al., 20”
Mixture Models for Diverse Machine Translation: Tricks of the Trade (2019, methodology): “We demonstrate that mixture models, when successfully trained, consistently outperform variational NMT (Zhang et al., 2016) and diverse decoding algorithms such as diverse beam search (Vijayakumar et al., 2016; Li et al., 2017) and biased sampling (Graves, 2013; Fan et al., 2018).”
A Survey on Dialogue Systems: Recent Advances and New Frontiers (2017, background): “[86] augmented the beam-search objective with a dissimilarity term that measured the diversity between candidate sequences.”
Generating More Interesting Responses in Neural Conversation Models with Distributional Constraints (2018, methodology): “( Vijayakumar et al., 2016; Li and Jurafsky, 2016; Li et al., 2016b) Following previous work we evaluated our approach using a combination of automatic metrics and human judgments.”
ZeroGen: Efficient Zero-shot Learning via Dataset Generation (2022, result): “This finding is consistent with previous works (Li et al., 2016; Vijayakumar et al., 2016; Welleck et al., 2020; Holtzman et al., 2020).”
Improving Factual Consistency of Abstractive Summarization via Question Answering (2021, methodology): “To obtain good coverage and diverse q-a pairs, we use diverse beam search (Vijayakumar et al., 2016) to generate 60 q-a pairs for a given summary with 60 diverse beam groups and a diverse beam strength of 0.5.”
Translation between Molecules and Natural Language (2022, methodology): “To generate a variety of output molecules given a single input, we employ diverse beam search (Vijayakumar et al., 2016) with a beam width and beam group of 30 and a diversity penalty of 0.5.”
Context-Aware Captions from Context-Agnostic Supervision (2017, methodology): “3), which we describe next.”