Published on Sat Jul 04 2009

Learning as Search Optimization: Approximate Large Margin Methods for Structured Prediction

Daniel Marcu

Mappings to structured output spaces are typically learned using extensions of classification algorithms. We present a framework for learning as search optimization, and two parameter updates with convergence theorems and bounds. Empirical evidence shows that our integrated approach to learning and decoding can outperform exact models.

0
0
0
Abstract

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 theorems and bounds. Empirical evidence shows that our integrated approach to learning and decoding can outperform exact models at smaller computational cost.

Sat Jul 04 2009
Machine Learning
Search-based Structured Prediction
Searn is an algorithm for integrating search and learning to solve 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.
0
0
0
Sun Jun 28 2009
Machine Learning
Unsupervised Search-based Structured Prediction
We show that it is possible to reduce unsupervised learning to supervised learning. The key idea that enables this is an application of the predict-self idea. We demonstrate the efficacy of a semi-supervised extension of Searn.
0
0
0
Sun Jan 18 2009
Machine Learning
Maximum Entropy Discrimination Markov Networks
This work represents the first successful attempt to combine Bayesian-style learning with structured maximum margin learning. It outperforms a wide array of competing methods for structured learning on both synthetic and real data sets.
0
0
0
Wed Jun 27 2012
Machine Learning
Structured Learning from Partial Annotations
Structured learning is appropriate when predicting structured outputs such as trees, graphs, or sequences. Most prior work requires the training set to consist of complete trees or graphs. Our main contribution is a large margin formulation that makes structured learning from only partially annotated data possible.
0
0
0
Wed Aug 05 2015
Machine Learning
Structured Prediction: From Gaussian Perturbations to Linear-Time Principled Algorithms
Margin-based structured prediction commonly uses a maximum loss over all possible structured outputs. We show that this family of loss functions produces a tighter upper bound of the Gibbs decoder distortion than commonly used methods.
0
0
0
Fri Feb 08 2019
Machine Learning
A Smoother Way to Train Structured Prediction Models
Smoothing overcomes the non-smoothness inherent to the maximum margin structured prediction objective. Smoothing paves the way for the use of fast primal gradient-based optimization algorithms.
0
0
0