Learning Beam Search Policies via Imitation Learning

Renato Negrinho, Matthew R. Gormley, Geoffrey J. Gordon

Abstract

Beam search is a cornerstone of approximate decoding in structured prediction, yet it is often treated as a post-hoc heuristic rather than a learned component. This paper presents a unifying meta-algorithm that integrates beam search into the training process using imitation learning. By treating the entire beam as the model's state, the authors provide the first no-regret theoretical guarantees for beam-aware policies. This framework not only captures existing algorithms like LaSO and BSO but also introduces a "continue" strategy that effectively mitigates exposure bias.

Introduction

In structured prediction tasks such as machine translation or speech recognition, the goal is to predict a sequence of labels. Due to the exponential size of the search space, beam search is typically employed at test time to maintain a set of $k$ promising partial hypotheses. However, a significant gap exists between training and inference: models are often trained via Maximum Likelihood Estimation (MLE) on "gold" prefixes, ignoring the beam. This leads to training-test mismatch and exposure bias, where the model fails to recover from its own errors during inference.

The Meta-Algorithm Framework

The authors propose framing beam search as a "Learning to Search" problem. In this view, the state is defined as the entire beam, and the policy is the scoring function that determines the next beam.

Algorithm 1: Formal definition of the Beam Search process.

This formulation allows for the application of imitation learning techniques, specifically inspired by the DAgger algorithm. The model learns to mimic an oracle by optimizing differentiable surrogate losses (e.g., cost-sensitive margins or log-losses) that penalize the exclusion of high-quality candidates from the beam.

Unifying Existing Methods

A key contribution of this work is the unification of various disparate "beam-aware" training techniques. By varying the data collection strategy (e.g., stop, reset, or continue) and the choice of surrogate loss, the meta-algorithm can replicate several well-known methods.

Comparison of existing algorithms as specific configurations of the proposed meta-algorithm.

The "continue" strategy is particularly noteworthy. Unlike "stop" or "reset" strategies used in methods like LaSO, "continue" allows the model to keep searching even after the oracle trajectory falls out of the beam. This forces the model to learn how to minimize future costs from sub-optimal states, directly addressing exposure bias.

Theoretical Guarantees and Results

The paper provides rigorous theoretical backing for this approach. The authors prove (Theorems 1 & 2) that if a no-regret online learning algorithm like SGD or Adam is used, the expected cost of the learned policy is bounded by the average surrogate loss plus a regret term that vanishes over time.

Furthermore, Theorem 4 provides a finite-sample analysis for "stop" and "reset" strategies, showing that while "continue" is theoretically superior, these common practices can still offer guarantees if the probability of the oracle falling out of the beam decreases sufficiently during training. The paper also includes a convexity analysis of various surrogate losses to guide practitioners in choosing optimizable objectives.

Limitations and Future Work

The primary drawback of this approach is computational: running beam search during every training step is significantly more expensive than standard MLE. Additionally, the guarantees assume the existence of a "good" policy within the chosen model class. Future research could explore more expressive policy classes or integrate sophisticated loss functions from the field of "learning to rank" to further enhance beam scoring.

Summary updated

Abstract

Beam search is widely used for approximate decoding in structured prediction problems. Models often use a beam at test time but ignore its existence at train time, and therefore do not explicitly learn how to use the beam. We develop an unifying meta-algorithm for learning beam search policies using imitation learning. In our setting, the beam is part of the model, and not just an artifact of approximate decoding. Our meta-algorithm captures existing learning algorithms and suggests new ones. It also lets us show novel no-regret guarantees for learning beam search policies.
BibTeX
@inproceedings{negrinho2018learning,
  author = {Renato Negrinho and Matthew R. Gormley and Geoffrey J. Gordon},
  title = {{Learning Beam Search Policies via Imitation Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2018},
  url = {https://openreview.net/forum?id=HkbjIwWdWH},
}
Figure