An Empirical Investigation of Beam-Aware Training in Supertagging

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

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. (2018) 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.

Introduction

In structured prediction tasks such as translation, parsing, or supertagging, models are typically trained using Maximum Likelihood Estimation (MLE). While effective, this approach creates two significant discrepancies between training and inference: exposure bias and search mismatch. During training, the model only observes gold-standard trajectories; at test time, however, it must navigate its own potentially erroneous predictions using approximate search methods like beam search. This paper investigates "beam-aware" training, which integrates the search process into the training objective to mitigate these issues.

The Beam-Aware Meta-Algorithm

The authors implement a meta-algorithm that generalizes various beam-aware training strategies. This framework allows for the systematic evaluation of different components, including data collection strategies, surrogate loss functions, and scoring mechanisms.

Illustration of the beam transition and scoring mechanism within the meta-algorithm, showing how candidates are ranked and costs are assigned.

Key design choices explored include:

  • Data Collection: How the model explores the search space during training. The continue strategy, where the model keeps searching even after the gold sequence drops out of the beam, was found to be superior to stopping or resetting.
  • Surrogate Losses: The study compares the structured Perceptron, Margin loss, and Log Loss. Log Loss, which normalizes over the candidates currently in the beam, provided the most stable and high-performing results.
  • Scoring Function: The researchers found that Score Accumulation—summing scores along the entire search path—outperformed simple step-wise scoring by helping the model learn the long-term value of its decisions.

Experimental Setup and Models

The study focuses on Supertagging using the CCGBank dataset. Supertagging is a challenging sequence labeling task with a large label set (~1,000 tags), making it an ideal testbed for search-based training. The authors evaluate two distinct architectures:

  1. Main Model: A high-performance Bi-LSTM model with a look-ahead encoder.
  2. Simplified Model: A model that lacks the look-ahead encoder, forcing it to rely entirely on the beam to resolve syntactic ambiguity.
Architectural comparison between the Main Bi-LSTM model (left) and the Simplified model (right) which lacks look-ahead capabilities.

Key Results and Insights

The empirical results demonstrate that beam-aware training consistently improves performance, but its impact varies significantly by model architecture:

  • Search as a Crutch for Weak Models: The Simplified model saw a dramatic accuracy jump from 82.41% (MLE) to 92.69% with beam-aware training. This suggests that training with search allows the model to use the beam as a form of external memory and look-ahead, compensating for architectural limitations.
  • Consistent Gains for Strong Models: Even the high-performance Main model saw a boost, moving from 94.06% to 94.42%. While the gain is smaller, it indicates that even sophisticated models benefit from aligning their training objective with the inference-time search process.
  • The Importance of Error Recovery: Training with an oracle strategy (always showing the model the correct beam) actually degraded performance as beam size increased. This confirms that models must be exposed to "messy" beams during training to learn how to recover from inevitable mistakes.

Conclusion

This investigation confirms that beam-aware training is a powerful tool for structured prediction. By using the continue strategy combined with Log Loss and score accumulation, researchers can significantly improve model robustness. The results strongly suggest that for a model to maximize its effectiveness during inference, it must be learned in conjunction with the search algorithm it will use at test time.

Summary updated

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. (2018) 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.
BibTeX
@inproceedings{negrinho2020empirical,
  author = {Renato Negrinho and Matthew R. Gormley and Geoffrey J. Gordon},
  title = {{An Empirical Investigation of Beam-Aware Training in Supertagging}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2020},
  url = {https://openreview.net/forum?id=paXBNgmIPk},
}
Figure