Leveraging Sentence Similarity in Natural Language Generation: Improving Beam Search using Range Voting (2020)

Abstract: We propose a method for natural language generation, choosing the most representative output rather than the most likely output. By viewing the language generation process from the voting theory perspective, we define representativeness using range voting and a similarity measure. The proposed method can be applied when generating from any probabilistic language model, including n-gram models and neural network models. We evaluate different similarity measures on an image captioning task and a machine translation task, and show that our method generates longer and more diverse sentences, providing a solution to the common problem of short outputs being preferred over longer and more informative ones. The generated sentences obtain higher BLEU scores, particularly when the beam size is large. We also perform a human evaluation on both tasks and find that the outputs generated using our method are rated higher.

## introduction a language model specifies a probability distribution over sequences of words: given a sequence @xmath0, the model assigns a probability p (s) to the entire sequence. the probability distribution may be conditioned: for example in machine translation the distribution is conditioned on the source language sentence. in many applications, it is desirable to output a single sequence, rather than a distribution. a common approach is to choose the most likely sequence. however, this is problematic when the most likely sequence is not representative of the whole distribution. for example, in dialogue generation tasks, the most likely output can be "i don't know", even when most of the probability mass is assigned to long informative sequences. @xcite call this the "boring output problem". for a real-valued distribution, we can choose a representative output by taking the mean. however, for a discrete distribution (such as over sequences), the mean is not defined. in this paper, we choose a representative output using tools from voting theory, allowing us to avoid the boring output problem. the general idea is that, if the distribution assigns most of the probability mass to a group of similar sequences, we would like to generate one of them -even if they have low probability as individual sequences, they have high probability as a group. we can formulate this process as a range voting election, where the sentences vote for each other, with the strength of a vote being proportional to the similarity between the voter sequence and the candidate sequence. our approach can be used to mitigate problems commonly associated with language models. for example, a long-recognised problem is that shorter sequences are assigned higher probabilities and thus choosing the most likely sequence favours short sequences @xcite . indeed, @xcite show that the most likely output in machine translation is often the empty string. by designing the similarity function to be asymmetric such that more informative candidate sequences receive stronger votes, we can generate longer and more diverse outputs (see fig. 1 for an example). we focus on simple similarity metrics based on n-grams and generate the candidates and voters using beam search. we evaluate on two tasks: image captioning and machine translation. for both tasks, we find that our approach achieves higher bleu scores, and performs better in a human evaluation. our approach also generates longer and more diverse outputs, with the generated length and diversity more closely matching the length and diversity of the reference captions and reference translations. 0.00230: a couple of people that are sitting on a bench 0.00132: a man sitting on a bench next to a dog 0.00079: a black and white photo of a man sitting on a bench 0.00075: a couple of people sitting on a bench 0.00066: a man sitting on a bench with a dog 0.00064: a man and a woman sitting on a bench 0.00048: a man and a woman sitting on a park bench 0.00046: a black and white photo of a man and a horse 0.00033: a black and white photo of a man and a dog 0.00025: a black and white photo of a man on a horse ## related work much work has gone into analysing sources of errors in language generation, often focused on machine translation. @xcite raise 6 challenges for machine translation, including degrading performance for longer sentences, and degrading performance for larger beam sizes. @xcite distinguish model errors (high probabilities of bad sequences) and search errors (failing to find sequences preferred by the model). they show that the global optimal translations (according to likelihood) are considerably worse than translations found by beam search. this points to both serious model errors and serious search errors, which cancel out to some degree. this suggests there is much work to be done in improving both our models and our search objectives -the latter is the aim of this paper. @xcite find that beam search typically covers only a small proportion of the model's probability mass, foot_0 and they show that the degradation for large beams is at least partly due to the training data containing target sentences that are exact copies of source sentences. they also suggest that beam search is an effective search strategy, for the maximum-likelihood search objective, finding hypotheses with higher model probabilities than the reference translations. @xcite also find a performance degradation with larger beam sizes across different tasks (translation, image captioning and summarisation) and propose to add a search discrepancy heuristic to beam search. for image captioning, @xcite show that larger beams not only decrease performance but also reduce the diversity of the captions. they claim this is an overfitting effect and propose the use of small beam sizes as further regularization. in unconditional, open-ended language generation, @xcite find that using likelihood as the decoding objective leads to bland and repetitive text with unnaturally high probability and too little variance. they claim this is not due to a search error, but due to the maximum-likelihood decoding objective. they propose sampling, truncated the distribution to the top p percent of tokens. ## experiments we evaluate our method on two tasks: image captioning and machine translation. for mbr, we use bleu (bleu 4 ) and a smoothed version of bleu (smoothed bleu 4 ) which adds 1 to the n-gram counts for @xmath1. we consider two baselines: length normalisation and diverse decoding, described in §2.1. for machine translation, we also consider diverse beam search as a further baseline. other methods mentioned in §2 cannot be straightforwardly applied as they require modifying the model or the training objective. ## conclusion instead of generating the most likely sequence, we propose a method to generate the most representative sequence, formalising representativeness using a similarity measure and range voting. the evaluation on image captioning and machine translation shows that despite using simple similarity measures, we achieve an increase in bleu score, an increase in caption length and diversity, and statistically significantly better human evaluation performance on both tasks. for the image captioning task, performance of our method does not drop as beam size increases, removing the sensitivity of results to this hyperparameter. on the machine translation task, performance does drop for larger beam sizes, although by much less than with standard beam search or the baselines. furthermore, performance increases as the number of voters increases, for a fixed set of candidates. using better similarity measures that capture semantics could further improve results and is a promising direction for further research. finally, our approach can be applied to any probabilistic language model, without any need for additional training. this opens up many other tasks, including summarisation, dialogue systems, and question answering. if multiple outputs can be used (e.g. offering options to a user), our method can be extended to use reweighted range voting @xcite , a procedure that elects multiple candidates.