Structured Prediction Theory Based on Factor Graph Complexity

By Corinna Cortes, Vitaly Kuznetsov, Mehryar Mohri, Scott Yang. 2016

62 citations recorded by the source corpus.

We present a general theoretical analysis of structured prediction with a series of new results. We give new data-dependent margin guarantees for structured prediction for a very wide family of loss functions and a general family of hypotheses, with an arbitrary factor graph decomposition. These are the tightest margin bounds known for both standard multi-class and general structured prediction problems. Our guarantees are expressed in terms of a data-dependent complexity measure, factor graph complexity, which we show can be estimated from data and bounded in terms of familiar quantities. We further extend our theory by leveraging the principle of Voted Risk Minimization (VRM) and show that learning is possible even with complex factor graphs. We present new learning bounds for this advanced setting, which we use to design two new algorithms, Voted Conditional Random Field (VCRF) and Voted Structured Boosting (StructBoost). These algorithms can make use of complex features and factor graphs and yet benefit from favorable learning guarantees. We also report the results of experiments with VCRF on several datasets to validate our theory.

Subfields: Artificial Intelligence, Information Systems, Management Science and Operations Research, Probabilistic & Bayesian Methods, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Gauthier Gidel
2. Simon Lacoste-Julien
3. Pascal Vincent
4. Hugo Berard
5. Ahmed Touati
6. Gabriel Huang
7. Yoshua Bengio
8. Peter Richtárik

In Information Systems

1. Simon Lacoste-Julien
2. Pascal Vincent

In Management Science and Operations Research

1. Gauthier Gidel
2. Simon Lacoste-Julien
3. Ahmed Touati
4. Pascal Vincent
5. Hugo Berard

In Probabilistic & Bayesian Methods

1. Simon Lacoste-Julien
2. Gauthier Gidel
3. Ahmed Touati
4. Pascal Vincent
5. Hugo Berard
6. Yoshua Bengio
7. Yang Song
8. Stefano Ermon

In Statistical Learning Theory

1. Simon Lacoste-Julien
2. Ahmed Touati
3. Pascal Vincent

Citations in the corpus

• Parametric Adversarial Divergences are Good Task Losses for Generative Modeling (2017, background): “…understanding of learning in structured prediction, some recent papers are devoted to theoretical understanding of structured prediction such as Cortes et al. (2016) and London et al. (2016) which propose generalization error bounds in the same vein as Osokin et al. (2017) but with data…”