Structured Learning with Approximate Inference
Alex Kulesza, Fernando M. B. Pereira · 2007
Abstract In many structured prediction problems, the highest-scoring labeling is hard tocompute exactly, leading to the use of approximate inference methods. However, when inference is used in a learning algorithm, a good approximation of the scoremay not be sufficient. We show in particular that learning can fail even with an approximate inference method with rigorous approximation guarantees. There aretwo reasons for this. First, approximate methods can effectively reduce the expressivity of an underlying model by making it impossible to choose parameters thatreliably give good predictions. Second, approximations can respond to parameter changes in such a way that standard learning algorithms are misled. In contrast, wegive two positive results in the form of learning bounds for the use of LP-relaxed inference in structured perceptron and empirical risk minimization settings. Weargue that without understanding combinations of inference and learning, such as these, that are appropriately compatible, learning performance under approximateinference cannot be guaranteed.
Cited by 122 works.
Authors
References
- Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference
- Conditional Random Fields: Probabilistic Models for Segmenting and Labeling Sequence Data
- Discriminative training methods for hidden Markov models
- The computational complexity of probabilistic inference using bayesian belief networks
- Loopy Belief Propagation for Approximate Inference: An Empirical Study
- MAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming
- A Linear Programming Formulation for Global Inference in Natural Language Tasks
- Piecewise Training for Undirected Models
- Learning associative Markov networks
- Collective Segmentation and Labeling of Distant Entities in Information Extraction