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

Sebastian Borgeaud, Guy EmersonACL 2020

TL;DR

This paper introduces a novel approach to natural language generation (NLG) that prioritizes representative outputs over merely the most probable ones. By reframing NLG as a voting problem, they leverage range voting and similarity measures to select more informative and diverse sentences, effectively addressing the "boring output problem" common in NLG systems.

What Problem Does This Paper Address?

Generating natural language, whether it's translating text, captioning images, or creating dialogue, often involves selecting the "best" sequence of words from a vast number of possibilities. Language models assign probabilities to these sequences, and a common strategy is to pick the sequence with the highest probability (maximum likelihood decoding). However, this can lead to "boring" or uninformative outputs, especially in tasks like dialogue generation where the most likely response might be a simple "I don't know." This phenomenon, known as the "boring output problem," arises because the probability mass can be split across many similar, yet individually low-probability, sequences. Furthermore, standard beam search, a popular decoding algorithm, can suffer from performance degradation and reduced diversity as its search space (beam size) increases. This paper aims to tackle both the issue of generating bland outputs and the limitations of traditional beam search.

Methods

The core innovation of this paper is the application of range voting, a concept from voting theory, to the problem of selecting a sentence from a distribution of possibilities. Instead of simply picking the highest probability sequence, they treat each generated sequence as a candidate in an election. The probability of a sequence is interpreted as its proportion of votes. To address the "vote splitting" problem (where probability mass is spread thinly across many similar sequences), they introduce a similarity measure.

Here's how it works:

  1. Candidate and Voter Generation: Beam search is used to generate a set of candidate sequences and a set of "voter" sequences.
  2. Voting: Each voter sequence "votes" for candidate sequences. The strength of a vote is determined by a similarity measure between the voter and the candidate.
  3. Scoring: A candidate sequence's final score is the sum of its weighted votes, where the weights are the probabilities of the voter sequences. The formula is: score(c) = Σ P(v) * sim(v, c), where c is a candidate, v is a voter, P(v) is the probability of the voter, and sim(v, c) is the similarity.
  4. Selection: The candidate sequence with the highest score is selected as the final output.

The paper explores several similarity measures:

  • N-gram based: precision_n and overlap_n measures, which are asymmetric to favor more informative sequences.
  • Embedding based: Similarity based on the hidden states of LSTM or Transformer decoders (lstm_states, transformer_states).

This approach is designed to be general and applicable to any probabilistic language model without requiring additional training.

Datasets

  • MSCOCO: Used for image captioning.
  • WMT'14 English-German: Used for machine translation.

Key Insights and Ideas

  • Voting Theory for NLG: Applying voting theory, specifically range voting, provides a principled way to select a "representative" sentence from a distribution, effectively mitigating the "boring output problem."
  • Similarity as Votes: The strength of similarity between sequences directly translates to the strength of votes, allowing informative sequences to garner more support.
  • Asymmetric Similarity: Using asymmetric similarity measures (like precision_n and overlap_n) is crucial for encouraging longer and more informative outputs, as they give more weight to candidates that contain more information than the voter.
  • Robustness to Beam Size: The proposed range voting method shows improved robustness to increasing beam sizes, unlike standard beam search which can see performance degradation.
  • Decoupling Model and Search Errors: The method helps to separate issues with the language model itself from errors introduced by the search/decoding process.

Key Results

  • Improved BLEU Scores: The proposed method consistently achieved higher BLEU scores on both image captioning and machine translation tasks, especially at larger beam sizes. For image captioning, lstm_states at k=100 yielded the best result, significantly outperforming standard beam search. For machine translation, overlap2 with range voting achieved the best overall score.
  • Longer and More Diverse Outputs: The method generated significantly longer and more diverse sentences compared to standard beam search, with diversity metrics (distinct captions, unigrams, bigrams) showing marked improvements.
  • Human Evaluation: Human evaluations confirmed the superiority of the proposed method, with outputs rated higher for both tasks, indicating that the improvements are meaningful beyond automated metrics.
  • Reduced Performance Drop: For machine translation, the performance drop at larger beam sizes was significantly reduced when using range voting.

Limitations and Future Work

  • Similarity Measure Choice: While the paper explores several similarity measures, the performance can still depend on the choice of metric. The authors suggest that using better similarity measures that capture semantics more deeply could lead to further improvements.
  • Model Errors: The paper emphasizes that their method improves the selection from a distribution, not the distribution itself. If the underlying language model is flawed, the selected output might still contain errors, as noted in the human evaluation where sometimes the voted caption was worse.
  • Future Work:
    • Investigating more sophisticated semantic similarity measures.
  • Exploring the use of a larger and more diverse set of voters, potentially using sampling or stochastic beam search, to capture more knowledge from the distribution.
  • Extending the approach to other NLG tasks like summarization, dialogue systems, and question answering.
  • Adapting the method for scenarios where multiple outputs can be presented to a user, potentially using reweighted range voting.

Summary updated

BibTeX
@inproceedings{borgeaud2020leveraging,
  author = {Sebastian Borgeaud and Guy Emerson},
  title = {{Leveraging Sentence Similarity in Natural Language Generation: Improving Beam Search using Range Voting}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2020},
}
Figure