Learning Beam Search Policies via Imitation Learning

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

28 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research, Statistical and Nonlinear Physics, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Statistical and Nonlinear Physics

In Reinforcement Learning

Citations in the corpus

ColdGANs: Taming Language GANs with Cautious Sampling Strategies (2020, background): “In the generative architectures, the encoder part can reach such performances, supporting the hypothesis that generation failures are mostly due to the decoding step: under MLE training regimes, the decoding suffers from exposure bias [34, 2] and lacks a sequence-level loss to optimize [27].”
Stochastic Beams and Where to Find Them: The Gumbel-Top-k Trick for Sampling Sequences Without Replacement (2019, background): “Although typically a test-time procedure, there are works that include beam search in the training loop (Daumé et al., 2009; Wiseman & Rush, 2016; Edunov et al., 2018b; Negrinho et al., 2018; Edunov et al., 2018a) for training sequence models on the sequence level (Ranzato et al.”