Search-based structured prediction

By Hal Daumé Iii, J. Langford, John Langford, Daniel Marcu, Daniel Marcu. 2009

602 citations recorded by the source corpus.

We present Searn, an algorithm for integrating search and learning to solve complex structured prediction problems such as those that occur in natural language, speech, computational biology, and vision. Searn is a meta-algorithm that transforms these complex problems into simple classification problems to which any binary classifier may be applied. Unlike current algorithms for structured learning that require decomposition of both the loss function and the feature functions over the predicted structure, Searn is able to learn prediction functions for any loss function and any class of features. Moreover, Searn comes with a strong, natural theoretical guarantee: good performance on the derived classification problems implies good performance on the structured prediction problem.

Subfields: Artificial Intelligence, Molecular Biology, Natural Language Processing

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 Molecular Biology

In Natural Language Processing

Citations in the corpus

Towards Coherent and Cohesive Long-form Text Generation (2018, background): “forcement learning (RL) problem (Daumé et al., 2009), in which the generator G is acting as a policy π, with parameters θπ, and each generated word at time t,wt, can be viewed as an action to be chosen by the policy from a large discrete space, or vocabulary, conditioned on state st−1 = w≤t−1.”
Thinking Fast and Slow with Deep Learning and Tree Search (2017, methodology): “Possible tree search algorithms include Monte Carlo Tree Search [7], α-β Search, and greedy search [6].”
Is Reinforcement Learning (Not) for Natural Language Processing?: Benchmarks, Baselines, and Building Blocks for Natural Language Policy Optimization (2022, methodology): “Imitation learning for NLP. Algorithms such as Schedule Sampling (SS) (Bengio et al., 2015), Parallel SS (Duckworth et al., 2019), SS for Transformers (Mihaylova & Martins, 2019), Diffential SS (Goyal et al., 2017), LOLS (Lampouras & Vlachos, 2016; Chang et al., 2015), TextGAIL (Wu et al., 2021b), a”
Neural Text Generation with Unlikelihood Training (2019, background): “The resulting distribution mismatch between training sequences and generated sequences is a known issue with maximum-likelihood training, motivating objectives that operate on model-generated sequences (Daum´e et al., 2009; Ross et al., 2011; Ranzato et al., 2015; Yu et al., 2016).”
A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning (2010, methodology): “Another approach called SMILe (Ross and Bagnell, 2010), similar to SEARN (Daumé III et al., 2009) and CPI (Kakade and Langford, 2002), trains a stationary stochastic policy (a ﬁnite mixture of policies) by adding a new policy to the mixture at each iteration of training.”
Learning Dependency-Based Compositional Semantics (2011, background): “The general approach is similar in spirit to Searn (Daume, Langford, andMarcu 2009), althoughwe do not have any formal guarantees at this point.”
Professor Forcing: A New Algorithm for Training Recurrent Networks (2016, methodology): “The scheduled sampling method Bengio et al. (2015), which is closely related to SEARN (Daumé et al. , 2009) and DAGGER Ross et al. (2010), involves randomly using the network’s predictions as its inputs (as in sampling mode) with some probability that increases over the course of training.”
Reinforcement learning in robotics: A survey (2013, methodology): “Structured prediction, a key technique used within computer vision and robotics, where many predictions are made in concert by leveraging inter-relations between them, may be seen as a simplified variant of imitation learning (Daumé et al., 2009; Ross et al., 2011a).”
Reward Augmented Maximum Likelihood for Neural Structured Prediction (2016, methodology): “We are not aware of successful large-margin methods for neural sequence prediction, but a related approach by [39] for neural machine translation builds on SEARN [8].”
Human Pose Estimation with Iterative Error Feedback (2015, background): “There is a rich literature on structured output learning [40, 7] (e.”