Learning as search optimization
Hal Daumé, Daniel Marcu · International Conference on Machine Learning · 2005
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.
Cited by 157 works. doi:10.1145/1102351.1102373
Authors
References
- Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data
- The perceptron: A probabilistic model for information storage and organization in the brain.
- Discriminative training methods for hidden Markov models
- Maximum Entropy Markov Models for Information Extraction and Segmentation
- Large margin classification using the perceptron algorithm
- Shallow parsing with conditional random fields
- Max-Margin Markov Networks
- Simulation of self-organizing systems by digital computer
- Support vector machine learning for interdependent and structured output spaces
- Artificial Intelligence: A Modern Approach