Title: DIVERSE BEAM SEARCH: DECODING DIVERSE SOLUTIONS FROM NEURAL SEQUENCE MODELS

Abstract: 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. This tends to result 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 a diversity-augmented objective. We observe that our method not only improved diversity but also finds better top 1 solutions by controlling for the exploration and exploitation of the search space. Moreover, these gains are achieved with minimal computational or memory overhead compared to beam search. To demonstrate the broad applicability of our method, we present results on image captioning, machine translation, conversation and visual question generation using both standard quantitative metrics and qualitative human studies. We find that our method consistently outperforms BS and previously proposed techniques for diverse decoding from neural sequence models.

1. INTRODUCTION:

In the last few years, Recurrent Neural Networks (RNNs), Long Short-Term Memory networks (LSTMs) or more generally, neural sequence models have become the standard choice for modeling time-series data for a wide range of applications including speech recognition (Graves et al., 2013) , machine translation (Bahdanau et al., 2014) , conversation modeling (Vinyals & Le, 2015) , image and video captioning (Vinyals et al., 2015; Venugopalan et al., 2015) , and visual question answering (Antol et al., 2015) . RNN based sequence generation architectures model the conditional probability, Pr(y|x) of an output sequence y = (y 1 , . . . , y T ) given an input x (possibly also a sequence); where the output tokens y t are from a finite vocabulary, V.

Inference in RNNs. Maximum a Posteriori (MAP) inference for RNNs is the task of finding the most likely output sequence given the input. Since the number of possible sequences grows as |V| T , exact inference is NP-hard -so, approximate inference algorithms like beam search (BS) are commonly employed. BS is a heuristic graph-search algorithm that maintains the B top-scoring partial sequences expanded in a greedy left-to-right fashion. Fig. 1 shows a sample BS search tree.

Lack of Diversity in BS. Despite the widespread usage of BS, it has long been understood that solutions decoded by BS are generic and lacking in diversity (Finkel et al., 2006; Gimpel et al., A steam engine train travelling through a lush green forest. A steam engine train travelling through a lush green countryside A train on a train track with a sky background.

A steam engine travelling down train tracks. A steam engine train travelling through a forest. An old steam engine train travelling down train tracks. An old steam engine train travelling through a forest. A black train is on the tracks in a wooded area. A black train is on the tracks in a rural area.

Single engine train rolling down the tracks.:

A steam locomotive is blowing steam.

A locomotive drives along the tracks amongst trees and bushes.

An old fashion train with steam coming out of its pipe.

A black and red train moving down a train track.

An engine is coming down the train track. 2013; Li et al., 2015; Li & Jurafsky, 2016) . Comparing the human (bottom) and BS (top) generated captions shown in Fig. 1 demonstrates this deficiency. While this behavior of BS is disadvantageous for many reasons, we highlight the three most crucial ones here:

Ground Truth Captions:

i) The production of near-identical beams make BS a computationally wasteful algorithm, with essentially the same computation being repeated for no significant gain in performance.

ii) Due to loss-evaluation mismatch (i.e. improvements in posterior-probabilities not necessarily corresponding to improvements in task-specific metrics), it is common practice to deliberately throttle BS to become a poorer optimization algorithm by using reduced beam widths (Vinyals et al., 2015; Karpathy & Fei-Fei, 2015; Ferraro et al., 2016) . This treatment of an optimization algorithm as a hyperparameter is not only intellectually dissatisfying but also has a significant practical side-effect -it leads to the decoding of largely bland, generic, and "safe" outputs, e.g. always saying "I don't know" in conversation models (Kannan et al., 2016) .

iii) Most importantly, lack of diversity in the decoded solutions is fundamentally crippling in AI problems with significant ambiguitye.g. there are multiple ways of describing an image or responding in a conversation that are "correct" and it is important to capture this ambiguity by finding several diverse plausible hypotheses.

Overview and Contributions. To address these shortcomings, we propose Diverse Beam Search (DBS) -a general framework to decode a set of diverse sequences that can be used as an alternative to BS. At a high level, DBS decodes diverse lists by dividing the given beam budget into groups and enforcing diversity between groups of beams. Drawing from recent work in the probabilistic graphical models literature on Diverse M-Best (DivMBest) MAP inference (Batra et al., 2012; Prasad et al., 2014; Kirillov et al., 2015) , we optimize an objective that consists of two terms -the sequence likelihood under the model and a dissimilarity term that encourages beams across groups to differ. This diversity-augmented model score is optimized in a doubly greedy manner -greedily optimizing along both time (like BS) and groups (like DivMBest).

Our primary technical contribution is Diverse Beam Search, a doubly greedy approximate inference algorithm to decode diverse sequences from neural sequence models. We report results on image captioning, machine translation, conversations and visual question generation to demonstrate the broad applicability of DBS. Results show that DBS produces consistent improvements on both task-specific oracle and other diversity-related metrics while maintaining run-time and memory requirements similar to BS. We also evaluate human preferences between image captions generated by BS or DBS. Further experiments show that DBS is robust over a wide range of its parameter values and is capable of encoding various notions of diversity through different forms of the diversty term.

Overall, our algorithm is simple to implement and consistently outperforms BS in a wide range of domains without sacrificing efficiency. Our implementation is publicly available at https: //github.com/ashwinkalyan/dbs. Additionally, we provide an interactive demonstration of DBS for image captioning at http://dbs.cloudcv.org.

2. PRELIMINARIES: DECODING RNNS WITH BEAM SEARCH:

We begin with a refresher on BS, before describing our generalization, Diverse Beam Search. For notational convenience, let [n] denote the set of natural numbers from 1 to n and let v

[n] = [v 1 , . . . , v n ] index the first n elements of a vector v ∈ R m .

The Decoding Problem. RNNs are trained to estimate the likelihood of sequences of tokens from a finite dictionary V given an input x. The RNN updates its internal state and estimates the conditional probability distribution over the next output given the input and all previous output tokens. We denote the logarithm of this conditional probability distribution over all tokens at time t as θ(y t ) = log Pr(y t |y t-1 , . . . , y 1 , x). To avoid notational clutter, we index θ(•) with a single variable y t , but it should be clear that it depends on all previous outputs, y [t-1] . We write the log probability of a partial solution (i.e. the sum of log probabilities of all tokens decoded so far) as Θ(y

[t] ) = τ ∈[t] θ(y τ ).

The decoding problem is then the task of finding a sequence y that maximizes Θ(y). As each output is conditioned on all the previous outputs, decoding the optimal length-T sequence in this setting can be viewed as MAP inference on a T -order Markov chain with nodes corresponding to output tokens at each time step. Not only does the size of the largest factor in such a graph grow as |V| T , but computing these factors also requires repetitively evaluating the sequence model. Thus, approximate algorithms are employed and the most prevalent method is beam search (BS).

Beam search is a heuristic search algorithm which stores the top B highest scoring partial candidates at each time step; where B is known as the beam width. Let us denote the set of B solutions held by BS at the start of time t as

Y [t-1] = {y 1,[t-1] , . . . , y B,[t-1] }.

At each time step, BS considers all possible single token extensions of these beams given by the set Y t = Y [t-1] × V and retains the B highest scoring extensions. More formally, at each step the beams are updated as

EQUATION

The above objective can be trivially maximized by sorting all B × |V| members of Y t by their log probabilities and selecting the top B. This process is repeated until time T and the most likely sequence is selected by ranking the B complete beams according to their log probabilities.

While this method allows for multiple sequences to be explored in parallel, most completions tend to stem from a single highly valued beam -resulting in outputs that are often only minor perturbations of a single sequence (and typically only towards the end of the sequences).

3. DIVERSE BEAM SEARCH: FORMULATION AND ALGORITHM:

To overcome this, we augment the objective in Eq. 1 with a dissimilarity term ∆(Y [t] ) that measures the diversity between candidate sequences, assigning a penalty ∆(Y [t] )[c] to each possible sequence completion c ∈ V. Jointly optimizing this augmented objective for all B candidates at each time step is intractable as the number of possible solutions grows with |V| B (easily 10 60 for typical language modeling settings). To avoid this, we opt for a greedy procedure that divides the beam budget B into G groups and promotes diversity between these groups. The approximation is doubly greedy -across both time and groups -so

∆(Y [t]

) is constant with respect to other groups and we can sequentially optimize each group using regular BS. We now explain the specifics of our approach.

Diverse Beam Search. As joint optimization is intractable, we form G smaller groups of beams and optimize them sequentially. Consider a partition of the set of beams

Y [t] into G smaller sets Y g [t] , g∈[G] of B = B/G beams each (we pick G to divide B).

In the example shown in Fig. 2 , B = 6 beams are divided into G = 3 differently colored groups containing B = 2 beams each.

Considering diversity only between groups, reduces the search space at each time step; however, inference remains intractable. To enforce diversity efficiently, we consider a greedy strategy that steps each group forward in time sequentially while considering the others fixed. Each group can then evaluate the diversity term with respect to the fixed extensions of previous groups, returning the search space to B × |V|. In the snapshot shown in Fig. 2 , the third group is being stepped forward at time step t = 4 and the previous groups have already been completed. With this staggered beamfront, the diversity term of the third group can be computed using these completions. Here we use hamming diversity, which adds diversity penalty -1 for each appearance of a possible extension word at the same time step in a previous group -'birds', 'the', and 'an' in the example -and 0 to all other possible completions. We discuss other forms for the diversity function in Section 5.1.

As we optimize each group with the previous groups fixed, extending group g at time t amounts to a standard BS using dissimilarity augmented log probabilities and can be written as:

EQUATION

s.t. λ ≥ 0, y g i,[t] = y g j,[t] ∀i = j

where λ is scalar controlling the strength of the diversity term. The full procedure to obtain diverse sequences using our method, Diverse Beam Search (DBS), is presented in Algorithm 1. It consists of two main steps for each group at each time step -1) augmenting the log probabilities of each possible extension with the diversity term computed from previously advanced groups (Algorithm 1, Line 5) and,

2) running one step of a smaller BS with B beams using the augmented log probabilities to extend the current group (Algorithm 1, Line 6).

Note that the first group (g = 1) is not 'conditioned' on other groups during optimization, so our method is guaranteed to perform at least as well as a beam search of size B .

Algorithm 1: Diverse Beam Search:

Perform a diverse beam search with G groups using a beam width of B for t = 1, . . . T do // perform one step of beam search for first group without diversity

Y 1 [t] ← argmax (y 1 1,[t] ,...,y 1 B ,[t] ) b∈[B ] Θ(y 1 b,[t] ) for g = 2, . . . G do // augment log probabilities with diversity penalty Θ(y g b,[t] ) ← Θ(y g b,[t] ) + λ∆( g-1 h=1 Y h [t] )[y g b,t ] b ∈ [B ], y g b,[t] ∈ Y g t and λ > 0 // perform one step of beam search for the group Y g [t] ← argmax y g 1,[t] ,...,y g B ,[t] b∈[B ] Θ(y g b,[t] ) s.t. y i,[t] = y j,[t] ∀i = j Return set of B solutions, Y [T ] = G g=1 Y g [T ]

4. RELATED WORK:

Diverse M-Best Lists. The task of generating diverse structured outputs from probabilistic models has been studied extensively (Park & Ramanan, 2011; Batra et al., 2012; Kirillov et al., 2015; Prasad et al., 2014) . Batra et al. (2012) formalized this task for Markov Random Fields as the DivMBest problem and presented a greedy approach which solves for outputs iteratively, conditioning on previous solutions to induce diversity. Kirillov et al. (2015) show how these solutions can be found jointly (non-greedily) for certain kinds of energy functions. The techniques developed by Kirillov are not directly applicable to decoding from RNNs, which do not satisfy the assumptions made.

Most related to our proposed approach is the work of Gimpel et al. (2013) , who applied DivMBest to machine translation using beam search as a black-box inference algorithm. Specifically, in this approach, DivMBest knows nothing about the inner-workings of BS and simply makes B sequential calls to BS to generate B diverse solutions. This approach is extremely wasteful because BS is called B times, run from scratch every time, and even though each call to BS produces B solutions, only one solution is kept by DivMBest. In contrast, DBS avoids these shortcomings by integrating diversity within BS such that no beams are discarded. By running multiple beam searches in parallel and at staggered time offsets, we obtain large time savings making our method comparable to a single run of classical BS. One potential disadvantage of our method w.r.t. Gimpel et al. (2013) is that sentence-level diversity metrics cannot be incorporated in DBS since no group is complete when diversity is encouraged. However, as observed empirically by us and Li et al. (2015) , initial words tend to disproportionally impact the diversity of the resultant sequences -suggesting that later words may not be important for diverse inference.

Diverse Decoding for RNNs. Efforts have been made by Li et al. (2015) and Li & Jurafsky (2016) to produce diverse decodings from recurrent models for conversation modeling and machine translation. Both of these works propose new heuristics for creating diverse M-Best lists and employ mutual information to re-rank lists of sequences. The latter achieves a goal separate from ours, which is simply to re-rank diverse lists.

Li & Jurafsky (2016) proposes a BS diversification heuristic that discourages beams from sharing common roots, implicitly resulting in diverse lists. Introducing diversity through a modified objective (as in DBS) rather than via a procedural heuristic provides easier generalization to incorporate different notions of diversity and control the exploration-exploitation trade-off as detailed in Section 5.1. Furthermore, we find that DBS outperforms the method of Li & Jurafsky (2016) . Li et al. (2015) introduced a novel decoding objective that maximizes mutual information between inputs and predicted outputs to penalize generic sequences. This operates on a principle orthogonal and complementary to DBS and Li & Jurafsky (2016) . It works by penalizing utterances that are generally more frequent (diversity independent of input) rather than penalizing utterances that are similar to other utterances produced for the same input (diversity conditioned on input). Furthermore, the input-independent approach requires training a new language model for the target language while DBS just requires a diversity function ∆. Combination of these complementary techniques is left as interesting future work.

In other recent work, Wu et al. (2016) modify the beam search objective by introducing lengthnormalization to favor longer sequences and a coverage penalty that favors sequences that account for the complete input sequence. While the coverage term does not generalize to all neural sequence models, the length-normalization term can be implemented by modifying the joint-log-probability of each sequence. Although the goal of this method is not to produce diverse lists and hence not directly comparable, it is a complementary technique that can be used in conjunction with our diverse decoding method.

5. EXPERIMENTS:

In this section, we evaluate our approach on image captioning, machine translation, conversation and visual question generation tasks to demonstrate both its effectiveness against baselines and its general applicability to any inference currently supported by beam search. We also analyze the effects of DBS parameters, explore human preferences for diversity, and discuss diversity's importance in explaining complex images. We first explain the baselines and evaluations used in this paper.

Baselines & Metrics. Apart from classical beam search, we compare DBS with the diverse decoding method proposed in Li & Jurafsky (2016) . We also compare against two other complementary decoding techniques proposed in Li et al. (2015) and Wu et al. (2016) . Note that these two techniques are not directly comparable with DBS since the goal is not to produce diverse lists. We now provide a brief description of the comparisons mentioned:

-Li & Jurafsky (2016): modify BS by introducing an intra-sibling rank. For each partial solution, the set of |V| beam extensions are sorted and assigned intra-sibling ranks k ∈ [|V|] in order of decreasing log probabilities, θ t (y t ). The log probability of an extension is then reduced in proportion to its rank, and continuations are re-sorted under these modified log probabilities to select the top B 'diverse' beam extensions.

- Li et al. (2015) : train an additional unconditioned target sequence model U (y) and perform BS decoding on an augmented objective P (y|x) -λU (y), penalizing input-independent decodings.

- Wu et al. (2016) modify the beam-search objective by introducing length-normalization that favors longer sequences. The joint log-probability of completed sequences is divided by a factor, (5 + |y|) α /(5 + 1) α , where α ∈ [0, 1].

We compare to our own implementations of these methods as none are publicly available. Both Li & Jurafsky (2016) and Li et al. (2015) develop and use re-rankers to pick a single solution from the generated lists. Since we are interested in evaluating the quality of the generated lists and in isolating the gains due to diverse decoding, we do not implement any re-rankers, simply sorting by log-probability.

We evaluate the performance of the generated lists using the following two metrics:

-Oracle Accuracy: Oracle or top k accuracy w.r.t. some task-specific metric, such as BLEU (Papineni et al., 2002) or SPICE (Anderson et al., 2016) , is the maximum value of the metric achieved over a list of k potential solutions. Oracle accuracy is an upper bound on the performance of any re-ranking strategy and thus measures the maximum potential of a set of outputs.

-Diversity Statistics: We count the number of distinct n-grams present in the list of generated outputs. Similar to Li et al. (2015) , we divide these counts by the total number of words generated to bias against long sentences.

Simultaneous improvements in both metrics indicate that output sequences have increased diversity without sacrificing fluency and correctness with respect to target tasks.

5.1. SENSITIVITY ANALYSIS AND EFFECT OF DIVERSITY FUNCTIONS:

Here we discuss the impact of the number of groups, strength of diversity , and various forms of diversity for language models. Note that the parameters of DBS (and other baselines) were tuned on a held-out validation set for each experiment. The supplement provides further discussion and experimental details.

Number of Groups (G).:

Setting G=B allows for the maximum exploration of the search space, while setting G=1 reduces DBS to BS, resulting in increased exploitation of the search-space around the 1-best decoding. Empirically, we find that maximum exploration correlates with improved oracle accuracy and hence use G=B to report results unless mentioned otherwise. See the supplement for a comparison and more details.

Diversity Strength (λ). The diversity strength λ specifies the trade-off between the model score and diversity terms. As expected, we find that a higher value of λ produces a more diverse list; however, very large values of λ can overpower model score and result in grammatically incorrect outputs. We set λ via grid search over a range of values to maximize oracle accuracies achieved on the validation set. We find a wide range of λ values (0.2 to 0.8) work well for most tasks and datasets.

Choice of Diversity Function (∆). In Section 3, we defined ∆(•) as a function over a set of partial solutions that outputs a vector of dissimilarity scores for all possible beam completions. Assuming that each of the previous groups influences the completion of the current group independently, we can simplify ∆(

g-1 h=1 Y h [t]

) as the sum of each group's contributions as

g-1 h=1 ∆(Y h [t]

). In Section 3, we illustrated a simple hamming diversity of this form that penalizes selection of tokens proportionally to the number of time it was used in previous groups. However, this factorized diversity term can take various forms in our model -with hamming diversity being the simplest. For language models, we study the effect of using cumulative (i.e. considering all past time steps), n-gram and neural embedding based diversity functions. Each of these forms encode differing notions of diversity and result in DBS outperforming BS. We find simple hamming distance to be effective and report results based on this diversity measure unless otherwise specified. More details about these forms of the diversity term are provided in the supplementary.

5.2. IMAGE CAPTIONING:

Dataset and Models. We evaluate on two datasets -COCO (Lin et al., 2014) and PASCAL-50S (Vedantam et al., 2015) . We use the public splits as in Karpathy & Fei-Fei (2015) for COCO. PASCAL-50S is used only for testing (with 200 held out images used to tune hyperparameters). We train a captioning model (Vinyals et al., 2015) using the neuraltalk21 code repository.

Results. Table 1 shows Oracle (top k) SPICE for different values of k. DBS consistently outperforms BS and Li & Jurafsky (2016) on both datasets. We observe that gains on PASCAL-50S are more pronounced (7.14% and 4.65% SPICE@20 improvements over BS and Li & Jurafsky (2016) ) than COCO. This suggests diverse predictions are especially advantageous when there is a mismatch between training and testing sets, implying DBS may be better suited for real-world applications.

Table 1 also shows the number of distinct n-grams produced by different techniques. Our method produces significantly more distinct n-grams (almost 300% increase in the number of 4-grams produced) as compared to BS. We also note that our method tends to produce slightly longer captions compared on average. Moreover, on the PASCAL-50S test split we observe that DBS finds more likely top-1 solutions on average -DBS obtains an average maximum log probability of -6.53 opposed to -6.91 found by BS of the same beam width. This empirical evidence suggests that using DBS as a replacement to BS may lead to lower inference approximation error. Human Studies. To evaluate human preference between captions generated by DBS and BS, we perform a human study via Amazon Mechanical Turk using all 1000 images of PASCAL-50S. For each image, both DBS and standard BS captions are shown to 5 different users. They are then asked -"Which of the two robots understands the image better?" In this forced-choice test, DBS captions were preferred over BS 60% of the time by human annotators.

Is diversity always needed? While these results show that diverse outputs are important for systems that interact with users, is diversity always beneficial? While images with many objects (e.g., a park or a living room) can be described in multiple ways, the same is not true when there are few objects (e.g., a close up of a cat or a selfie). This notion is studied by Ionescu et al. (2016) , which defines a "difficulty score": the human response time for solving a visual search task. On the PASCAL-50S dataset, we observe a positive correlation (ρ = 0.73) between difficulty scores and humans preferring DBS to BS. Moreover, while DBS is generally preferred by humans for 'difficult' images, both are about equally preferred on 'easier' images. Details are provided in the supplement.

5.3. MACHINE TRANSLATION:

We use the WMT'14 dataset containing 4.5M sentences to train our machine translation models.

We train stacking LSTM models as detailed in Luong et al. (2015) , consisting of 4 layers and 1024dimensional hidden states. While decoding sentences, we employ the same strategy to replace UNK tokens. We train our models using the publicly available seq2seq-attn 2 code repository. We report results on news-test-2013 and news-test-2014 and use the news-test-2012 to tune the parameters of DBS. We use sentence level BLEU scores to compute oracle metrics and report distinct n-grams similar to image captioning. Results are shown in Table 2 and we again find that DBS consistently outperforms all baselines. My mother used to hum that to me.

5.5. VISUAL QUESTION GENERATION:

We also report results on Visual Question Generation (VQG) (Mostafazadeh et al., 2016) , where a model is trained to produce questions about an image. Generating visually focused questions is interesting because it requires reasoning about multiple problems that are central to vision -e.g., object attributes, relationships between objects, and natural language. Furthermore, many questions could make sense for one image, so it is important that lists of generated questions be diverse.

We use the VQA dataset (Antol et al., 2015) to train a model similar to image captioning architectures. Instead of captions, the training set now consists of 3 questions per image. Similar to previous results, using beam search to sample outputs results in similarly worded questions (see Fig. 3 ) and DBS brings out new details captured by the model. Counting the number of types of questions generated (as defined by Antol et al. (2015) ) allows us to measure this diversity. We observe that the number of question types generated per image increases from 2.3 for BS to 3.7 for DBS (at B = 6).

6. CONCLUSION:

Beam search is widely a used approximate inference algorithm for decoding sequences from neural sequence models; however, it suffers from a lack of diversity. Producing multiple highly similar and generic outputs is not only wasteful in terms of computation but also detrimental for tasks with For image-captioning, we conduct a human preference study between BS and DBS captions as explained in Section 5. A screen shot of the interface used to collect human preferences for captions generated using DBS and BS is presented in Fig. 6 . The lists were shuffled to guard the task from being gamed by a turker. As mentioned in Section 5, we observe that difficulty score of an image and human preference for DBS captions are positively correlated. The dataset contains more images that are less difficulty and so, we analyze the correlation by dividing the data into three bins. For each bin, we report the % of images for which DBS captions were preferred after a majority vote (i.e. at least 3/5 turkers voted in favor of DBS) in Table 7 . At low difficulty scores consisting mostly of iconic images -one might expect that BS would be preferred more often than chance. However, mismatch between the statistics of the training and testing data results in a better performance of DBS. Some examples for this case are provided in Fig. 7 . More general qualitative examples are provided in Fig. 8 .

DISCUSSION:

Are longer sentences better? Many recent works propose a scoring or a ranking objective that depends on the sequence length. These favor longer sequences, reasoning that they tend to have more details and resulting in improved accuracies. We measure the correlation between length of a sequence and its accuracy (here, SPICE) and observe insignificant correlation between SPICE and sequence length. On the PASCAL-50S dataset, we find that BS and DBS have are negatively correlated (ρ = -0.003 and ρ = -0.015 respectively), while (Li & Jurafsky, 2016) is correlated positively (ρ = 0.002). Length is not correlated with performance in this case.

Efficient utilization of beam budget. In this experiment, we emperically show that DBS makes efficient use of the beam budget in exploring the search space for better solutions. Fig. 9 shows the variation of oracle SPICE (@B) with the beam size. At really high beam widths, all decoding techniques achieve similar oracle accuracies. However, diverse decoding techniques like DBS achieve the same oracle at much lower beam widths. Hence, DBS not only produces sequence lists that are significantly different but also efficiently utilizes the beam budget to decode better solutions. 

:

https://github.com/karpathy/neuraltalk2

https://github.com/harvardnlp/seq2seq-attn

https://github.com/macournoyer/neuralconvo

Figure 6: Screen-shot of the interface used to perform human studies

Figures and Tables:

train travelling down train tracks. A steam engine train travelling down tracks. A steam engine train travelling through a forest.

Figure 1: Comparing image captioning outputs decoded by BS (top) and our method, Diverse Beam Search (middle) -we notice that BS captions are near-duplicates with similar shared paths in the search tree and minor variations in the end. In contrast, DBS captions are significantly diverse and similar to the variability in human-generated ground truth captions (bottom).

Figure 2: Diverse beam search operates left-to-right through time and top to bottom through groups. Diversitybetween groups is combined with joint log probabilities, allowing continuations to be found efficiently. The resulting outputs are more diverse than for standard approaches.

Figure5: Fig.5ashows the results of a grid search of the diversity strength (λ) parameter of DBS on the validation split of PASCAL 50S dataset. We observe that it is robust for a wide range of values. Fig.5bcompares the performance of multiple forms for the diversity function (∆). While naïve diversity performs the best, other forms are comparable while being better than BS.

Figure 7: For images with low difficulty score, BS captions are preferred to DBS -as show in the first figure.However, we observe that DBS captions perform better when there is a mismatch between the statistics of the testing and training sets. Interesting captions are colored in blue for readability.

Figure 8: For images with a high difficulty score, captions produced by DBS are preferred to BS. Interesting captions are colored in blue for readability.

Oracle accuracy and distinct n-grams on COCO and PASCAL-50S datasets for image captioning at B = 20. While we report SPICE, we observe similar trends in other metrics (reported in supplement).

Table content: <table><tr><td>Dataset</td><td>Method</td><td colspan="4">Oracle Accuracy (SPICE)</td><td/><td colspan="2">Diversity Statistics</td><td/></tr><tr><td/><td/><td>@1</td><td>@5</td><td>@10</td><td>@20</td><td colspan="4">distinct-1 distinct-2 distinct-3 distinct-4</td></tr><tr><td/><td>Beam Search</td><td>4.933</td><td>7.046</td><td>7.949</td><td>8.747</td><td>0.12</td><td>0.57</td><td>1.35</td><td>2.50</td></tr><tr><td/><td colspan="2">Li &amp; Jurafsky (2016) 5.083</td><td>7.248</td><td>8.096</td><td>8.917</td><td>0.15</td><td>0.97</td><td>2.43</td><td>5.31</td></tr><tr><td>PASCAL-50S</td><td>DBS</td><td>5.357</td><td>7.357</td><td>8.269</td><td>9.293</td><td>0.18</td><td>1.26</td><td>3.67</td><td>7.33</td></tr><tr><td/><td>Wu et al. (2016)</td><td>5.301</td><td>7.322</td><td>8.236</td><td>8.832</td><td>0.16</td><td>1.10</td><td>3.16</td><td>6.45</td></tr><tr><td/><td>Li et al. (2015)</td><td>5.129</td><td>7.175</td><td>8.168</td><td>8.560</td><td>0.13</td><td>1.15</td><td>3.58</td><td>8.42</td></tr><tr><td/><td>Beam Search</td><td colspan="4">16.278 22.962 25.145 27.343</td><td>0.40</td><td>1.51</td><td>3.25</td><td>5.67</td></tr><tr><td/><td colspan="5">Li &amp; Jurafsky (2016) 16.351 22.715 25.234 27.591</td><td>0.54</td><td>2.40</td><td>5.69</td><td>8.94</td></tr><tr><td>COCO</td><td>DBS</td><td colspan="4">16.783 23.081 26.088 28.096</td><td>0.56</td><td>2.96</td><td>7.38</td><td>13.44</td></tr><tr><td/><td>Wu et al. (2016)</td><td colspan="4">16.642 22.643 25.437 27.783</td><td>0.54</td><td>2.42</td><td>6.01</td><td>7.08</td></tr><tr><td/><td>Li et al. (2015)</td><td colspan="4">16.749 23.271 26.104 27.946</td><td>0.42</td><td>1.37</td><td>3.46</td><td>6.10</td></tr></table>

Quantitative results on English-German translation on the newstest-2013 and newstest-2014 datasets combined (at B = 20).Dialog generation is a task that is inherently diverse as there are multiple valid ways to respond to a statement. We train a seq2seq model consisting of LSTMs as inVinyals & Le (2015) on the Cornell Movie Dialogs Corpus (Danescu-Niculescu-Mizil & Lee, 2011) using the neuralconvo 3 repository. The training dataset consists of 222,182 conversational exchanges between movie characters. Since automatic evaluation of dialog generation responses is an open research problem with existing metrics being poorly correlated with human judgement(Liu et al., 2016), we show qualitative results to demonstrate the effectiveness of DBS. Table3compares BS and DBS at B=3.

Table content: <table><tr><td>Method</td><td colspan="3">Oracle Accuracy (BLEU-4)</td><td/><td colspan="2">Diversity Statistics</td></tr><tr><td/><td>@1</td><td>@5 @10</td><td>@20</td><td colspan="4">distinct-1 distinct-2 distinct-3 distinct-4</td></tr><tr><td>Beam Search</td><td colspan="2">20.5 22.4 23.8</td><td>24.2</td><td>0.04</td><td>0.75</td><td>2.10</td><td>3.23</td></tr><tr><td colspan="3">Li &amp; Jurafsky (2016) 20.7 22.6 24.0</td><td>24.3</td><td>0.04</td><td>0.81</td><td>2.92</td><td>4.61</td></tr><tr><td>DBS</td><td colspan="2">20.8 22.9 24.4</td><td>24.8</td><td>0.06</td><td>0.95</td><td>3.67</td><td>5.54</td></tr><tr><td>Wu et al. (2016)</td><td colspan="2">20.6 22.6 24.3</td><td>24.6</td><td>0.05</td><td>0.88</td><td>2.83</td><td>4.50</td></tr><tr><td>Li et al. (2015)</td><td colspan="2">20.7 23.1 24.4</td><td>24.6</td><td>0.04</td><td>0.86</td><td>2.76</td><td>4.31</td></tr><tr><td colspan="2">5.4 DIALOG GENERATION</td><td/><td/><td/><td/><td/></tr></table>

Qualitative examples of dialog generation comparing best-first search, BS and DBS

Table content: <table><tr><td>Prompt</td><td>Beam Search</td><td>Diverse Beam Search</td></tr><tr><td/><td>I don't know.</td><td>I don't know.</td></tr><tr><td>Why do you want to be the president?</td><td>I don't know...</td><td>Because you know!</td></tr><tr><td/><td>I don't know, but I am the best</td><td>Because, I have another life.</td></tr><tr><td/><td>I know!</td><td>I know.</td></tr><tr><td>It's such a beautiful day!</td><td>It's true.</td><td>Well...</td></tr><tr><td/><td>Yeah.</td><td>That's not true, honey.</td></tr><tr><td/><td>Jacob.</td><td>Jacob.</td></tr><tr><td>What's your name?</td><td>Berger, my man.</td><td>Berger, darling</td></tr><tr><td/><td>Berger, Thomas.</td><td/></tr></table>

CIDEr Oracle accuracy on COCO and PASCAL-50S datasets for image captioning at B = 20.

Table content: <table><tr><td>Dataset</td><td>Method</td><td>Oracle Accuracy (CIDEr)</td></tr></table>

ROUGE Oracle accuracy on COCO and PASCAL-50S datasets for image captioning at B = 20.

Table content: <table><tr><td>Dataset</td><td>Method</td><td colspan="3">Oracle Accuracy (ROUGE-L)</td></tr><tr><td/><td/><td>@1</td><td>@5</td><td>@10</td><td>@20</td></tr><tr><td/><td>Beam Search</td><td colspan="3">45.23 56.12 59.61</td><td>62.04</td></tr><tr><td/><td colspan="4">Li &amp; Jurafsky (2016) 46.21 56.17 60.15</td><td>62.95</td></tr><tr><td>PASCAL-50S</td><td>DBS</td><td colspan="3">46.24 56.90 60.35</td><td>63.02</td></tr><tr><td/><td>Wu et al. (2016)</td><td colspan="3">43.73 52.29 56.49</td><td>61.65</td></tr><tr><td/><td>Li et al. (2015)</td><td colspan="3">44.12 54.67 57.34</td><td>60.11</td></tr><tr><td/><td>Beam Search</td><td colspan="3">52.46 58.43 62.56</td><td>65.14</td></tr><tr><td/><td colspan="4">Li &amp; Jurafsky (2016) 52.87 59.89 63.45</td><td>65.42</td></tr><tr><td>COCO</td><td>DBS</td><td colspan="3">53.04 60.89 64.24</td><td>67.72</td></tr><tr><td/><td>Wu et al. (2016)</td><td colspan="3">52.13 58.26 62.89</td><td>65.77</td></tr><tr><td/><td>Li et al. (2015)</td><td colspan="3">53.10 59.32 63.04</td><td>66.19</td></tr><tr><td>HUMAN STUDIES</td><td/><td/><td/></tr></table>

Frequency table for image difficulty and human preference for DBS captions on PASCAL50S dataset

Table content: <table><tr><td colspan="3">difficulty score # images % images DBS</td></tr><tr><td>bin range</td><td/><td>was preffered</td></tr><tr><td>≤ µ -σ</td><td>481</td><td>50.51%</td></tr><tr><td>[µ-σ, µ+σ]</td><td>409</td><td>69.92%</td></tr><tr><td>≥ µ + σ</td><td>110</td><td>83.63%</td></tr></table>

Peer review (iclr2017):
[ Summary ] This paper presents a new modified beam search algorithm that promotes diverse beam candidates. It is a well known problem —with both RNNs and also non-neural language models— that beam search tends to generate beam candidates that are very similar with each other, which can cause two separate but related problems: (1) search error: beam search may not be able to discover a globally optimal solution as they can easily fall out of the beam early on, (2) simple, common, non-diverse output: the resulting output text tends to be generic and common. This paper aims to address the second problem (2) by modifying the search objective function itself so that there is a distinct term that scores diversity among the beam candidates. In other words, the goal of the presented algorithm is not to reduce the search error of the original objective function. In contrast, stack decoding and future cost estimation, common practices in phrase-based SMT, aim to address the search error problem. [ Merits ] I think the Diverse Beam Search (DBS) algorithm proposed by the authors has some merits. It may be useful when we cannot rely on traditional beam search on the original objective function either because the trained model is not strong enough, or because of the search error, or because the objective itself does not align with the goal of the application. [ Weaknesses ] It is however not entirely clear how the proposed method compares against more traditional approaches like stack decoding and future cost estimation, on tasks like machine translation, as the authors compare their algorithm mainly against L&J’s diverse LM models and simple beam search. In fact, modification to the objective function has been applied even in the neural MT context. For example, see equation (14) in page 12 of the following paper: *Google*s Neural Machine Translation System: Bridging the Gap between Human and Machine Translation* (https://arxiv.org/pdf/1609.08144v2.pdf) where the attention coverage term serves a role similar to stack decoding (though unlike stack decoding, the objective term is entirely re-defined, more similarly to DBS proposed in this work), and the length penalty may have an effect that indirectly promotes more informative (thus more likely diverse) responses. Comparison against these existing algorithms would make the proposed work more complete. Also, I have a mixed feeling about computing and reporting only *oracle* BLUE, CIDEr, METEOR, etc. Especially given how these oracle scores are very close to each other, and that developing a high performing ranking has not been addressed in this work (and that doing so must be not all that trivial), I’m somewhat skeptical how much of DBS results make a practical difference. **** [Update after the author responses] **** The authors addressed some of my concerns by adding a new baseline comparison against Wu et al. 2016. Thus I will raise my score to 6.