A Simple, Fast Diverse Decoding Algorithm for Neural Generation

By Jiwei Li, Will Monroe, Dan Jurafsky. 2016

251 citations recorded by the source corpus.

In this paper, we propose a simple, fast decoding algorithm that fosters diversity in neural generation. The algorithm modifies the standard beam search algorithm by adding an inter-sibling ranking penalty, favoring choosing hypotheses from diverse parents. We evaluate the proposed model on the tasks of dialogue response generation, abstractive summarization and machine translation. We find that diverse decoding helps across all tasks, especially those for which reranking is needed. We further propose a variation that is capable of automatically adjusting its diversity decoding rates for different inputs using reinforcement learning (RL). We observe a further performance boost from this RL technique. This paper includes material from the unpublished script "Mutual Information and Diverse Decoding Improve Neural Machine Translation" (Li and Jurafsky, 2016).

Subfields: Artificial Intelligence, 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 Natural Language Processing

Citations in the corpus

The Curious Case of Neural Text Degeneration (2019, methodology): “(2) Computing the optimum argmax sequence from recurrent neural language models is not tractable, so consider two prominent decoding methods for approximating the argmax: Beam search is the most commonly used approximation in practice (Li et al., 2016c; Shen et al., 2017; Wiseman et al., 2017).”
Self-Consistency Improves Chain of Thought Reasoning in Language Models (2022, background): “Other work has sought to explicitly promote diversity in the decoding process (Batra et al., 2012; Li et al., 2016; Vijayakumar et al., 2018).”
How Decoding Strategies Affect the Verifiability of Generated Text (2019, background): “With the same aim of diversifying the exploration, Li et al. (2016) propose a variant of beam search which introduces a penalty proportional to the rank of a candidate token with respect to its source in the beam.”
Addressing Semantic Drift in Question Generation for Semi-Supervised Question Answering (2019, background): “different beam sizes and diverse beam search (Li et al., 2016), but all of them perform similarly.”
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 flour, oil, oil, and oil”), global repetition (producing the near same utterance for multiple…”
Neural Text Generation with Unlikelihood Training (2019, background): “Several forms of diverse beam search have been explored (Li et al., 2016; Vijayakumar et al., 2018; Kulikov et al., 2018; Holtzman et al., 2018) which can to some degree decrease the level of repetition of a model by selecting candidates unlike previously chosen ones, due to their variety.”
Adversarial Learning for Neural Dialogue Generation (2017, methodology): “Our work adapts the encoder-decoder model to RL training, and can thus be viewed as an extension of Li et al. (2016d), but with more general RL rewards.”
TransferTransfo: A Transfer Learning Approach for Neural Network Based Conversational Agents (2019, background): “I dont know) which are vague and not engaging for humans (Li, Monroe, and Jurafsky, 2016).”
Adversarial Example Generation with Syntactically Controlled Paraphrase Networks (2018, methodology): “For dialogue, Li et al. (2016a) affect the output using speaker identity, while Wang et al. (2017) develop models to inﬂuence topic and style of the output.”
Fast Abstractive Summarization with Reinforce-Selected Sentence Rewriting (2018, methodology): “We also apply the diverse decoding algorithm described in Li et al. (2016) (which has almost no computation overhead) so as to get the above approach to produce useful diverse reranking lists.”
Importance of Search and Evaluation Strategies in Neural Dialogue Modeling (2018, methodology): “…Cho et al. (2014) have become one of the most widely studied approaches to dialogue modeling (see, e.g., Serban et al., 2016, 2017; Zhao et al., 2017; Xu et al., 2017; Li et al., 2016, 2017a,b; Zemlyanskiy and Sha, 2018; Zhang et al., 2018; Miller et al., 2017; Shen et al., 2018; Gu et al., 2018).”
Ranking Generated Summaries by Correctness: An Interesting but Challenging Application for Natural Language Inference (2019, methodology): “Since the availability of at least one correct summary hypothesis is a prerequisite of the reranking approach, we rely on FAS which uses a variant of beam search yielding more diverse hypotheses (Li et al., 2016).”
Challenges in Building Intelligent Open-domain Dialog Systems (2019, background): “For example, Li et al. [39] penalized lower-ranked siblings extended from the same parents, so that the N-best hypotheses in the beam at each time step are more likely to expand from different parents, and thus more diverse.”
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): “[62] introduced a stochastic beam-search procedure, while [34] added an additional term for beam search scoring to penalize the siblings–expansions of the same parent node in the search.”
Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement (2019, background): “, 2018), diversity encouraging variants (Li et al., 2016; Shao et al., 2017; Vijayakumar et al., 2018) or using modifications such as length-normalization (Wu et al.”
Abstractive Document Summarization with a Graph-Based Attentional Neural Model (2017, background): “The reason is that the K -best sentences generated by a word decoder will mostly be similar to each other, which is also noticed by Li et al. (2016).”
Generating More Interesting Responses in Neural Conversation Models with Distributional Constraints (2018, methodology): “Combining both directions in this way has the effect of maximizing mutual information (Li et al., 2016a).”
Task-Oriented Dialog Systems that Consider Multiple Appropriate Responses under the Same Context (2019, methodology): “…and Ng 2006; Li, Monroe, and Jurafsky 2016), we address the issue by diversity promoting decoding techniques such as the diverse beam search (Li, Monroe, and Jurafsky 2016), top-k sampling (Fan, Lewis, and Dauphin 2018) and nucleus sampling (Holtzman et al. 2019) to further introduce dialog…”
A Stable and Effective Learning Strategy for Trainable Greedy Decoding (2018, methodology): “Various approaches have been explored recently to improve beam search by improving the method by which candidate sequences are scored (Li et al., 2016; Shu and Nakayama, 2017), the termination criterion (Huang et al.”