Abstract
Structured prediction is often approached by training a locally normalized model with maximum likelihood and decoding approximately with beam search. This approach leads to mismatches as, during training, the model is not exposed to its mistakes and does not use beam search. Beam-aware training aims to address these problems, but unfortunately, it is not yet widely used due to a lack of understanding about how it impacts performance, when it is most useful, and whether it is stable. Recently, Negrinho et al. (2018) proposed a meta-algorithm that captures beam-aware training algorithms and suggests new ones, but unfortunately did not provide empirical results. In this paper, we begin an empirical investigation: we train the supertagging model of Vaswani et al. (2016) and a simpler model with instantiations of the meta-algorithm. We explore the influence of various design choices and make recommendations for choosing them. We observe that beam-aware training improves performance for both models, with large improvements for the simpler model which must effectively manage uncertainty during decoding. Our results suggest that a model must be learned with search to maximize its effectiveness.
TL;DR
This paper provides the first comprehensive empirical study of "beam-aware" training—a method that teaches models how to perform search during the training phase itself. By testing various strategies on the task of supertagging, the authors demonstrate that training with a beam significantly improves performance, especially for simpler models that must manage high uncertainty during decoding.
What Problem Does This Paper Address?
Most structured prediction models (like those used for translation or parsing) are trained using Maximum Likelihood Estimation (MLE). During training, the model only sees "perfect" data (the gold standard). However, at test time, the model uses beam search to explore multiple hypotheses and often encounters its own previous mistakes—a phenomenon known as exposure bias.
Furthermore, there is a search mismatch: the model is trained to predict the next token in isolation, but at test time, it is expected to work effectively within a beam search framework. This paper investigates how to bridge this gap by using "beam-aware" training, where the model is exposed to the beam search process and its potential failures while it is still learning.
Methods
The authors implement a meta-algorithm that allows them to mix and match different training components. A key aspect of this approach is the accumulation of losses across the entire search sequence, ensuring the model receives a dense learning signal at every step.
- Data Collection Strategies: How do we choose which "beams" to show the model during training?
continue: The model keeps searching even if the correct answer falls out of the beam (exposing it to its mistakes).reset: If the correct answer is lost, the beam is reset to include the gold hypothesis.stop: Training on that sentence stops as soon as the gold hypothesis is lost.- Surrogate Losses: How do we penalize the model when the beam looks bad? They tested several, including Perceptron, Margin, and Log Loss. The goal is to ensure the "best" neighbor is scored high enough to stay in the beam.
- Dynamic Oracles: To train on "imperfect" beams where the gold label is already lost, the authors use a dynamic oracle to identify the best possible remaining path.
- Score Accumulation: They found that summing the scores of the sequence prefix (cumulative) performed better than just predicting the next step's score in isolation.
Datasets
The study focuses on Supertagging, a sequence labeling task that assigns complex syntactic tags (supertags) to words.
- Dataset: CCGBank (standard splits: ~40k training examples, ~2k development).
- Complexity: Supertagging is challenging because the label set is large (approximately 1,000 possible tags), making effective search crucial.
- Models: They compared a "Main Model" (a powerful Bi-LSTM + LM) and a "Simplified Model" (no Bi-LSTM, meaning it has less context and relies more heavily on the beam to resolve ambiguity).
Key Insights and Ideas
- Search is not just a post-processing step: Training a model with the search procedure in the loop yields better results than simply applying beam search to a traditionally trained model.
- The "Continue" strategy is king: Allowing the model to wander into "non-oracle" states (making mistakes and trying to recover) consistently outperformed strategies that reset or stopped upon error.
- Simpler models benefit most: The simplified model saw massive gains (over 10% accuracy) from beam-aware training. This suggests that beam-aware training can compensate for architectural weaknesses by teaching the model to manage uncertainty better.
- Update on every beam: The authors recommend calculating and applying a loss at every single step of the search, rather than only when the model makes a mistake. This provides a denser, more stable learning signal.
Key Results
- Simplified Model: Accuracy jumped from 82.41% (standard training + beam search) to 92.69% (beam-aware training).
- Main Model: Even the state-of-the-art model saw improvements, moving from 94.06% to 94.42%. While the gain is smaller, it shows that even high-capacity models have "search-related" performance left on the table.
Limitations and Future Work
- Task Specificity: The study is limited to supertagging. While supertagging is a great proxy for structured prediction, the benefits might vary for tasks like machine translation where the output space is even more fluid.
- Computational Cost: Training with beam search is naturally more expensive than standard MLE training, as it requires running a search for every training example.
- Future Directions: The authors suggest exploring these methods in "real-time" tasks where the full input isn't known upfront, as their simplified model results suggest beam-aware training is particularly potent when context is limited.
Summary updated