Learning as search optimization: approximate large margin methods for structured prediction

Mappings to structured output spaces (strings, trees, partitions, etc.) are typically learned using extensions of classification algorithms to simple graphical structures (eg., linear chains) in which search and parameter estimation can be performed exactly. Unfortunately, in many complex problems, it is rare that exact search or parameter estimation is tractable. Instead of learning exact models and searching via heuristic means, we embrace this difficulty and treat the structured output problem in terms of approximate search. We present a framework for learning as search optimization, and two parameter updates with convergence the-orems and bounds. Empirical evidence shows that our integrated approach to learning and decoding can outperform exact models at smaller computational cost.

• Publication year

  2005

• Venue

  International Conference on Machine Learning

• Publication date

  2005-08-07

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/1102351.1102373arXiv 0907.0809
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Loss Functions for Discriminative Training of Energy-Based Models

  2005cited by this paper
• Exponentiated Gradient Algorithms for Large-margin Structured Classification

  2004cited by this paper
• Support vector machine learning for interdependent and structured output spaces

  2004cited by this paper
• Incremental Parsing with the Perceptron Algorithm

  2004cited by this paper
• Semi-Markov Conditional Random Fields for Information Extraction

  2004cited by this paper
• Dynamic conditional random fields: factorized probabilistic models for labeling and segmenting sequence data

  2004cited by this paper
• Gaussian process classification for segmenting and annotating sequences

  2004cited by this paper
• Conditional Models of Identity Uncertainty with Application to Noun Coreference

  2004cited by this paper
• Max-Margin Markov Networks

  2003cited by this paper
• A Family of Additive Online Algorithms for Category Ranking

  2003cited by this paper
• Shallow Parsing with Conditional Random Fields

  2003cited by this paper
• Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms

  2002cited by this paper
• Kernel Dependency Estimation

  2002cited by this paper
• A New Approximate Maximal Margin Classification Algorithm

  2002cited by this paper
• Text Chunking based on a Generalization of Winnow

  2002cited by this paper
• Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data

  2001cited by this paper
• The Use of Classifiers in Sequential Inference

  2001cited by this paper
• Maximum Entropy Markov Models for Information Extraction and Segmentation

  2000cited by this paper
• Nash Convergence of Gradient Dynamics in General-Sum Games

  2000cited by this paper
• Large Margin Classification Using the Perceptron Algorithm

  1998cited by this paper
• Learning Evaluation Functions for Large Acyclic Domains

  1996cited by this paper
• Pattern-recognizing stochastic learning automata

  1985cited by this paper
• Associative search network: A reinforcement learning associative memory

  1981cited by this paper
• Polynomial approximation—a new computational technique in dynamic programming: Allocation processes

  1963cited by this paper
• The perceptron: a probabilistic model for information storage and organization in the brain.

  1958cited by this paper
• Simulation of self-organizing systems by digital computer

  1954cited by this paper

• Reuse your FLOPs: Scaling RL on Hard Problems by Conditioning on Very Off-Policy Prefixes

  2026cites this paper
• Dataset Reset Policy Optimization for RLHF

  2024cites this paper
• Filtered Semi-Markov CRF

  2023cites this paper
• A Policy-Based Learning Beam Search for Combinatorial Optimization

  2023cites this paper
• Individual mobility prediction review: Data, problem, method and application

  2022cites this paper
• Domain Adaptation for POS Tagging with Contrastive Monotonic Chunk-wise Attention

  2022cites this paper
• A Globally Normalized Neural Model for Semantic Parsing

  2021cites this paper
• Deep Policy Dynamic Programming for Vehicle Routing Problems

  2021cites this paper
• Domain Adaptation of Parts of Speech Annotators in Hindi Biomedical Corpus: An NLP Approach

  2021cites this paper
• Survey of Low-Resource Machine Translation

  2021cites this paper
• Towards Data-Efficient Machine Learning

  2021cites this paper
• An Empirical Investigation of Beam-Aware Training in Supertagging

  2020cites this paper
• Unsupervised Text Generation by Learning from Search

  2020cites this paper
• Max-Margin Incremental CCG Parsing

  2020cites this paper
• Neural Language Modeling for Named Entity Recognition

  2020cites this paper
• Learning Optimal Tree Models Under Beam Search

  2020cites this paper
• Stochasticity and Non-Autoregressive Modeling in Deep Generative Models of Text

  2020cites this paper
• MLE-guided parameter search for task loss minimization in neural sequence modeling

  2020cites this paper
• Automatic inference of causal reasoning chains from student essays

  2019cites this paper
• Randomized Greedy Search for Structured Prediction: Amortized Inference and Learning

  2019cites this paper
• Worst-Case Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies

  2019cites this paper
• AN ABSTRACT OF THE THESIS OF Chao Ma for the degree of Doctor of Philosophy in Computer Science presented on July 15, 2019. Title: New Directions in Search-based Structured Prediction: Multi-Task Learning and Integration of Deep Models Abstract approved:

  2019influential citation
• Learning and Inference for Structured Prediction: A Unifying Perspective

  2019cites this paper
• Constraint Learning: An Appetizer

  2019cites this paper
• A Fully Differentiable Beam Search Decoder

  2019cites this paper
• A Smoother Way to Train Structured Prediction Models

  2019cites this paper
• Rewarding Smatch: Transition-Based AMR Parsing with Reinforcement Learning

  2019cites this paper
• How Bad are PoS Tagger in Cross-Corpora Settings? Evaluating Annotation Divergence in the UD Project.

  2019cites this paper
• Visual-Textual Video Synopsis Generation

  2019cites this paper
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies

  2019cites this paper
• Asynchronous optimization for machine learning

  2018cites this paper
• Online Markov Decoding: Lower Bounds and Near-Optimal Approximation Algorithms

  2018cites this paper
• Automatically Selecting the Best Dependency Annotation Design with Dynamic Oracles

  2018cites this paper
• Collective Entity Disambiguation with Structured Gradient Tree Boosting

  2018cites this paper
• RNN S WITH GLOBAL-LOCAL LOSSES

  2018cites this paper
• Les méthodes « apprendre à chercher » en traitement automatique des langues : un état de l’art [A survey of learning-to-search techniques in Natural Language Processing]

  2018cites this paper
• Learning Beam Search Policies via Imitation Learning

  2018influential citation
• ENTROPY-GUIDED FEATURE GENERATION FOR LARGE MARGIN STRUCTURED LEARNING

  2018cites this paper
• Part of Speech Tagging: Shallow or Deep Learning?

  2018cites this paper
• Optimal Completion Distillation for Sequence Learning

  2018cites this paper
• Apprendre par imitation : applications à quelques problèmes d'apprentissage structuré en traitement des langues. (Imitation learning : application to several structured learning tasks in natural language processing)

  2018cites this paper
• Span-based Neural Structured Prediction

  2018cites this paper
• From Credit Assignment to Entropy Regularization: Two New Algorithms for Neural Sequence Prediction

  2018cites this paper
• Segmenting and Tagging Text with Neural Networks

  2018cites this paper
• Extracting Clinical Event Timelines: Temporal Information Extraction and Coreference Resolution in Electronic Health Records. (Création de Chronologies d'Événements Médicaux: Extraction d'Informations Temporelles et Résolution de la Coréférence dans les Dossiers Patients Électroniques)

  2018cites this paper
• Learning to Speed Up Structured Output Prediction

  2018cites this paper
• Theoretical and methodological advances in semi-supervised learning and the class-imbalance problem.

  2018cites this paper
• Peek Search: Near-Optimal Online Markov Decoding

  2018cites this paper
• Policy Shaping and Generalized Update Equations for Semantic Parsing from Denotations

  2018cites this paper
• Online learning of latent linguistic structure with approximate search

  2018cites this paper
• Training RNNs with global-local losses

  2017cites this paper
• Maximum Margin Reward Networks for Learning from Explicit and Implicit Supervision

  2017cites this paper
• The Conference on Empirical Methods in Natural Language Processing Proceedings of the 2nd Workshop on Structured Prediction for Natural Language Processing

  2017cites this paper
• Structured Set Matching Networks for One-Shot Part Labeling

  2017influential citation
• Differentiable Scheduled Sampling for Credit Assignment

  2017cites this paper
• Machine Learning for Entity Coreference Resolution: A Retrospective Look at Two Decades of Research

  2017cites this paper
• Clinically Significant Information Extraction from Radiology Reports

  2017cites this paper
• Greedy Transition-Based Dependency Parsing with Stack LSTMs

  2017influential citation
• Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning

  2017cites this paper
• A Neural Probabilistic Structured-Prediction Method for Transition-Based Natural Language Processing

  2017cites this paper
• Snake classification from images

  2017cites this paper
• SEARNN: Training RNNs with Global-Local Losses

  2017cites this paper
• Deep Energy-Based Models for Structured Prediction

  2017cites this paper
• Structured Prediction via Learning to Search under Bandit Feedback

  2017cites this paper
• Variance Reduction for Structured Prediction with Bandit Feedback

  2017cites this paper
• Structured Representations for Coreference Resolution

  2017cites this paper
• Multi-Task Structured Prediction for Entity Analysis: Search-Based Learning Algorithms

  2017cites this paper
• A Continuous Relaxation of Beam Search for End-to-end Training of Neural Sequence Models

  2017cites this paper
• Neural-Symbolic Learning for Semantic Parsing

  2017cites this paper
• Neural Network Based Named Entity Recognition

  2017cites this paper
• Fast and Accurate Neural Word Segmentation for Chinese

  2017cites this paper
• Combining Speaker Turn Embedding and Incremental Structure Prediction for Low-Latency Speaker Diarization

  2017cites this paper
• How to Train Dependency Parsers with Inexact Search for Joint Sentence Boundary Detection and Parsing of Entire Documents

  2016cites this paper
• Imitation Learning with Recurrent Neural Networks

  2016cites this paper
• Modèles exponentiels et contraintes sur les espaces de recherche en traduction automatique et pour le transfert cross-lingue. (Log-linear Models and Search Space Constraints in Statistical Machine Translation and Cross-lingual Transfer)

  2016cites this paper
• Reassessing the value of resources for cross-lingual transfer of POS tagging models

  2016cites this paper
• Improved Joint Kazakh POS Tagging and Chunking

  2016cites this paper
• Training with Exploration Improves a Greedy Stack LSTM Parser

  2016cites this paper
• Sequence-to-Sequence Learning as Beam-Search Optimization

  2016cites this paper
• Methods in Large Scale Inverse Optimal Control

  2016cites this paper
• An Actor-Critic Algorithm for Sequence Prediction

  2016cites this paper
• A Study of Imitation Learning Methods for Semantic Role Labeling

  2016cites this paper
• Multimodal Data Mining in a Multimedia Database Based on Structured Max Margin Learning

  2016cites this paper
• Improved Coreference Resolution Using Cognitive Insights

  2016cites this paper
• Robust Large Margin Approaches for Machine Learning in Adversarial Settings

  2016cites this paper
• Advanced Machine Learning Models for Coreference Resolution

  2016cites this paper
• Learning Reductions That Really Work This paper summarizes the mathematical and computational techniques that have enabled learning reductions to effectively address a wide class of tasks.

  2016cites this paper
• The Structured Weighted Violations Perceptron Algorithm

  2016cites this paper
• Global Neural CCG Parsing with Optimality Guarantees

  2016cites this paper
• CLIP@UMD at SemEval-2016 Task 8: Parser for Abstract Meaning Representation using Learning to Search

  2015cites this paper
• Incremental Recurrent Neural Network Dependency Parser with Search-based Discriminative Training

  2015cites this paper
• Apprentissage par imitation pour l’étiquetage de séquences : vers une formalisation des méthodes d’étiquetage easy-first

  2015cites this paper
• Towards structured representation of academic search results

  2015influential citation
• Approaches to Automatic Text Structuring

  2015cites this paper
• An Improved Classifier Chain Ensemble for Multi-DimensionalClassification with Conditional Dependence

  2015cites this paper
• Learning to Search Better than Your Teacher

  2015cites this paper
• Approaches to Automatic Text Structuring

  2015cites this paper
• Learning a sequential search for landmarks

  2015cites this paper
• Learning to Search for Dependencies

  2015cites this paper
• Learning Greedy Policies for the Easy-First Framework

  2015cites this paper