Search-based Structured Prediction

Abstract

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.

References in corpus (1)

• PEGASUS: A Policy Search Method for Large MDPs and POMDPs

Cited by in corpus (28)

• Can neural machine translation do simultaneous translation?
• Hinge-Loss Markov Random Fields and Probabilistic Soft Logic
• Reinforcement and Imitation Learning via Interactive No-Regret Learning
• Sequence-Level Knowledge Distillation
• Deeply AggreVaTeD: Differentiable Imitation Learning for Sequential Prediction
• Coordinated Multi-Agent Imitation Learning
• Learning Global Features for Coreference Resolution
• Training with Exploration Improves a Greedy Stack-LSTM Parser
• Online Trajectory Planning Through Combined Trajectory Optimization and Function Approximation: Application to the Exoskeleton Atalante
• SEARNN: Training RNNs with Global-Local Losses
• DropoutDAgger: A Bayesian Approach to Safe Imitation Learning
• End-to-end driving simulation via angle branched network
• Machine Learning with World Knowledge: The Position and Survey
• Discourse-Aware Neural Rewards for Coherent Text Generation
• Parser for Abstract Meaning Representation using Learning to Search
• Topo-boundary: A Benchmark Dataset on Topological Road-boundary Detection Using Aerial Images for Autonomous Driving
• Imitation Learning with Recurrent Neural Networks
• On the definition of a general learning system with user-defined operators
• On the Bayes-optimality of F-measure maximizers
• Co-training for Policy Learning
• Object-oriented Neural Programming (OONP) for Document Understanding
• Promising Accurate Prefix Boosting for sequence-to-sequence ASR
• Policy Gradient as a Proxy for Dynamic Oracles in Constituency Parsing
• Learning Reductions that Really Work
• Active Imitation Learning from Multiple Non-Deterministic Teachers: Formulation, Challenges, and Algorithms
• Tackling Error Propagation through Reinforcement Learning: A Case of Greedy Dependency Parsing
• Imitation Learning for Neural Morphological String Transduction
• Learning Neural Parsers with Deterministic Differentiable Imitation Learning