Investigating Label Bias in Beam Search for Open-ended Text Generation

Liang Wang, Jinlong Liu, Jingming LiuarXiv 2020 · OpenReview

TL;DR

This paper investigates why beam search, a popular decoding method for text generation, often produces repetitive and generic outputs in open-ended scenarios. They demonstrate that "label bias" – a phenomenon where locally normalized models favor states with fewer options – is a primary culprit. By introducing a sequence-level training approach that combines local and global normalization, they significantly reduce label bias, leading to more diverse and meaningful generated text with minimal impact on perplexity.

What Problem Does This Paper Address?

In many sequence-to-sequence (seq2seq) tasks like machine translation or summarization, the output is relatively constrained, and beam search, a greedy decoding algorithm, works well. However, in "open-ended" text generation, such as conversational AI or story writing, there are numerous plausible outputs for a given input. Here, beam search often falters, producing outputs that are repetitive, generic, and lack creativity. This contrasts with sampling-based methods like top-k or nucleus sampling, which are generally preferred for their ability to generate more diverse text. The paper aims to pinpoint the underlying cause of beam search's poor performance in these open-ended scenarios and propose a solution.

Methods

The core of the paper's contribution lies in identifying and mitigating "label bias." Label bias arises in models where probabilities are normalized locally at each step. This means that if a state has many possible next tokens, each token receives a small probability, while a state with fewer options will have higher probabilities for its limited choices. Beam search, by favoring higher local probabilities, inadvertently picks these "safer," less diverse options.

To combat this, the authors propose a sequence-level training approach. This method combines:

  • Locally normalized Maximum Likelihood Estimation (MLE): The standard training objective, which focuses on predicting the next token correctly.
  • Globally normalized sequence-level training: This objective aims to optimize the probability of the entire generated sequence, effectively considering the global context and reducing the impact of local normalization.

Crucially, they propose using unnormalized logits (raw scores before the softmax function) as the score for sequence-level training. This is more effective than using average log-probabilities because logits can vary over a larger range and can be calibrated without altering the local probabilities. They also introduce a novel method to estimate the partition function (a key component in global normalization) by using the top-k hypotheses generated by beam search itself, turning it into a (k+1)-class classification problem.

To quantify label bias, they devise a ranking-based metric: they rank the ground truth text against a set of "context-agnostic distractors" (low-perplexity sentences from a pre-trained language model). A model with less label bias should assign a higher score to the ground truth.

Datasets

  • Reddit dataset: Used for pre-training the seq2seq models. This dataset is large (over 10 million dialogue turns) but can be noisy.
  • ConvAI2 dataset: Used for fine-tuning and evaluation. This dataset is noted for its higher quality and is used for response generation tasks. The persona information was discarded to make the task more open-ended.

Key Insights and Ideas

  • Label bias is the primary culprit: The paper provides strong empirical evidence that label bias, not search errors (where beam search fails to find the optimal sequence), is the main reason for beam search's degenerate behavior in open-ended generation.
  • Global normalization is key: Shifting from purely local probability normalization to a globally normalized objective is crucial for reducing label bias.
  • Logits over log-probabilities: Using raw logits as scores in sequence-level training is more effective than using average log-probabilities, leading to better results with less perplexity increase.
  • A new metric for label bias: The proposed ranking-based metric offers a practical way to evaluate how well a model discriminates between ground truth and generic distractors, providing a quantitative measure of label bias.
  • Beam search can be improved: While sampling methods are popular, this work shows that by addressing label bias, beam search can be made to produce more diverse and meaningful outputs, potentially retaining some of its efficiency benefits.

Key Results

  • Reduced label bias: The proposed "Logits Avg" method (sequence-level training with logits) significantly reduces label bias, as evidenced by a lower mean rank on the context-agnostic distractors (35.1 compared to 44.7 for MLE).
  • Increased diversity: Sequence-level training methods ("LogProb Avg" and "Logits Avg") produced significantly more diverse texts, as measured by distinct-n metrics, compared to the baseline MLE method.
  • Minimal perplexity impact: The "Logits Avg" method only slightly increased perplexity (from 19.69 to 20.16) compared to the MLE baseline, indicating that reducing label bias doesn't necessarily come at a high cost to local prediction accuracy.
  • Improved human evaluation: Human evaluations showed that the proposed methods generated more specific and sensible responses, with the "Logits Avg" method achieving the highest Specificity, Sensibleness, and SSA scores.
  • Qualitative improvements: Examples show that the proposed method moves away from generic responses like "I'm doing well" towards more engaging and specific outputs.

Limitations and Future Work

  • Partition function estimation: The method for estimating the partition function using beam search hypotheses is an approximation and a source of bias. The authors suggest exploring more advanced techniques like Noise Contrastive Estimation (NCE) for unbiased estimation, though this might introduce high variance.
  • Incomplete elimination of bias: While label bias is reduced, it's not entirely eliminated. The paper acknowledges that their method only reduces it "to some degree."
  • Generalization to other tasks: The study focuses on response generation. Future work could investigate label bias in other open-ended tasks like conditional language modeling or story generation.
  • Efficiency of sequence-level training: Sequence-level training requires an extra decoding step, making it slower than standard MLE. Exploring more efficient methods for globally normalized training is a key future direction.
  • Semantic consistency: The paper notes that generating semantically consistent responses across dialogue turns remains an open challenge, as illustrated by an example where the model asks a question that was already answered.

Summary updated

Abstract

Beam search is an effective and widely used decoding algorithm in many sequence-to-sequence (seq2seq) text generation tasks. However, in open-ended text generation, beam search is often found to produce repetitive and generic texts, sampling-based decoding algorithms like top-k sampling and nucleus sampling are more preferred. Standard seq2seq models suffer from label bias due to its locally normalized probability formulation. This paper provides a series of empirical evidence that label bias is a major reason for such degenerate behaviors of beam search. By combining locally normalized maximum likelihood estimation and globally normalized sequence-level training, label bias can be reduced with almost no sacrifice in perplexity. To quantitatively measure label bias, we test the model's ability to discriminate the groundtruth text and a set of context-agnostic distractors. We conduct experiments on large-scale response generation datasets. Results show that beam search can produce more diverse and meaningful texts with our approach, in terms of both automatic and human evaluation metrics. Our analysis also suggests several future working directions towards the grand challenge of open-ended text generation.
BibTeX
@misc{wang2020investigating,
  author = {Liang Wang and Jinlong Liu and Jingming Liu},
  title = {{Investigating Label Bias in Beam Search for Open-ended Text Generation}},
  year = {2020},
  eprint = {2005.11009},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2005.11009},
}

Loading related content...

Figure