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.
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.
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