An Empirical Investigation of Beam-Aware Training in Supertagging (2020)

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 structured prediction often relies on models that train on maximum likelihood and use beam search for approximate decoding. this procedure leads to two significant mismatches between the training and testing settings: the model is trained on oracle trajectories and therefore does not learn about its own mistakes; the model is trained without beam search and therefore does not learn how to use the beam effectively for search. previous algorithms have addressed one or the other of these mismatches. for example, dagger @xcite and scheduled sampling @xcite use the learned model to visit non-oracle states at training time, but do not use beam search (i.e., they keep a single hypothesis). early update @xcite , laso @xcite , and bso (wiseman and rush, 2016) are trained with beam search, but do not expose the model to beams without a gold hypothesis (i.e., they either stop or reset to beams with a gold hypothesis). recently, @xcite proposed a meta-algorithm that instantiates beam-aware algorithms as a result of choices for the surrogate loss (i.e., which training loss to incur at each visited beam) and data collection strategy (i.e., which beams to visit during training). a specific instantiation of their meta-algorithm addresses both mismatches by relying on an insight on how to induce training losses for beams without the gold hypothesis: for any beam, its lowest cost neighbor should be scored sufficiently high to be kept in the successor beam. to induce these training losses it is sufficient to be able to compute the best neighbor of any state (often called a dynamic oracle @xcite ). unfortunately, @xcite do not provide empirical results, leaving open questions such as whether instances can be trained robustly, when is beam-aware training most useful, and what is the impact on performance of the design choices. contributions we empirically study beamaware algorithms instantiated through the metaalgorithm of @xcite . we tackle supertagging as it is a sequence labelling task with an easy-to-compute dynamic oracle and a moderatelysized label set (approximately 1000) which may require more effective search. we examine two supertagging models (one from @xcite and a simplified version designed to be heavily reliant on search) and train them with instantiations of the meta-algorithm. we explore how design choices influence performance, and give recommendations based on our empirical findings. for example, we find that perceptron losses perform consistently worse than margin and log losses. we observe that beam-aware training can have a large impact on performance, particularly when the model must use the beam to manage uncertainty during prediction. code for reproducing all results in this paper is available at https://github.com/ negrinho/beam_learn_supertagging . ## background on learning to search and beam-aware methods for convenience, we reuse notation introduced in @xcite to describe their metaalgorithm and its components (e.g., scoring function, surrogate loss, and data collection strategy). see figure 1 and figure 2 for an overview of the notation. when relevant, we instantiate notation for left-to-right sequence labelling under the hamming cost, which supertagging is a special case of. input and output spaces given an input structure x 2 x , the output structure y 2 y x , is generated through a sequence of incremental decisions. cost functions given a golden pair (x, y) 2 x ⇥ y, the cost function c x,y : y x ! r measures how bad the prediction ŷ 2 y x is relative to the target output structure y 2 y x . using c x,y : y x ! r, we define a cost function c ⇤ x,y : v x ! r for partial outputs by assigning to each node v 2 v x the cost of its best reachable complete output, i.e., c ⇤ ## meta-algorithm for learning beam search policies we refer the reader to @xcite for a discussion of how specific choices for the metaalgorithm recover algorithms from the literature. ## experiments we explore different configurations of the design choices of the meta-algorithm to understand their impact on training behavior and performance. ## related work related work uses either imitation learning (often called learning to search when applied to structured prediction) or beam-aware training. learning to search @xcite @xcite @xcite is a popular approach for structured prediction. this literature is closely related to imitation learning @xcite @xcite . @xcite addresses exposure bias by collecting data with the learned policy at training time. @xcite proposes a structured perceptron variant that trains with beam search, updating the model parameters when the correct hypothesis falls out of the beam. @xcite introduces a theoretical framework to analyze the convergence of early update. @xcite develops a beam-aware algorithm for dependency parsing that uses early update and dynamic oracles. @xcite introduce dynamic oracles for dependency parsing. @xcite observes that exposing the model to mistakes during training improves a dependency parser. @xcite makes a similar observation and present results on image captioning, constituency parsing, and speech recognition. beam-aware training has also been used for speech recognition @xcite . @xcite proposes an early update style algorithm for learning models with a beam, but use a log loss rather than a perceptron loss as in @xcite . parameters are updated when the golden hypothesis falls out of the beam or when the model terminates with the golden hypothesis in the beam. @xcite use a similar algorithm to @xcite but they use a margin-based loss and reset to a beam with the golden hypothesis when it falls out of the beam. @xcite use beam search to find a contrastive set to define sequence-level losses. @xcite propose a beam-aware training algorithm that relies on a continuous approximation of beam search. @xcite introduces a meta-algorithm that instantiates beam-aware algorithms based on choices for beam size, surrogate loss function, and data collection strategy. they propose a dagger-like algorithm for beam search. ## conclusions maximum likelihood training of locally normalized models with beam search decoding is the default approach for structured prediction. unfortunately, it suffers from exposure bias and does not learn to use the beam effectively. beam-aware training promises to address some of these issues, but is not yet widely used due to being poorly understood. in this work, we explored instantiations of the meta-algorithm of @xcite to understand how design choices affect performance. we show that beam-aware training is most useful when substantial uncertainty must be managed during prediction. we make recommendations for instantiating beam-aware algorithms based on the meta-algorithm, such as inducing losses at every beam, using log losses (rather than perceptron-style ones), and preferring the continue data collection strategy (or reset if necessary). we hope that this work provides evidence that beam-aware training can greatly impact performance and be trained stably, leading to their wider adoption. 1445606, at the pittsburgh supercomputing center (psc).