PAC-BAYESIAN SUPERVISED CLASSIFICATION: The Thermodynamics of Statistical Learning

By Olivier Catoni. 2007

542 citations recorded by the source corpus.

This monograph deals with adaptive supervised classification, using tools borrowed from statistical mechanics and information theory, stemming from the PACBayesian approach pioneered by David McAllester and applied to a conception of statistical learning theory forged by Vladimir Vapnik. Using convex analysis on the set of posterior probability measures, we show how to get local measures of the complexity of the classification model involving the relative entropy of posterior distributions with respect to Gibbs posterior measures. We then discuss relative bounds, comparing the generalization error of two classification rules, showing how the margin assumption of Mammen and Tsybakov can be replaced with some empirical measure of the covariance structure of the classification model.We show how to associate to any posterior distribution an effective temperature relating it to the Gibbs prior distribution with the same level of expected error rate, and how to estimate this effective temperature from data, resulting in an estimator whose expected error rate converges according to the best possible power of the sample size adaptively under any margin and parametric complexity assumptions. We describe and study an alternative selection scheme based on relative bounds between estimators, and present a two step localization technique which can handle the selection of a parametric model from a family of those. We show how to extend systematically all the results obtained in the inductive setting to transductive learning, and use this to improve Vapnik's generalization bounds, extending them to the case when the sample is made of independent non-identically distributed pairs of patterns and labels. Finally we review briefly the construction of Support Vector Machines and show how to derive generalization bounds for them, measuring the complexity either through the number of support vectors or through the value of the transductive or inductive margin.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics, Statistics and Probability, 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

In Statistical and Nonlinear Physics

In Statistics and Probability

In Statistical Learning Theory

Citations in the corpus

PAC-Bayesian Theory Meets Bayesian Inference (2016, positive): “The result of Corollary 2 (adapted from Catoni [9]) for bounded losses suffers from a similar gap, while having higher values than our sub-gamma result.”
A PAC-Bayesian bound for Lifelong Learning (2013, methodology): “For the convenience of readers who are not familiar with the PAC-Bayesian framework, we introduce the most relevant concepts from the literature here.”
Curriculum learning of multiple tasks (2014, background): “KL(Qπ(1)×· · ·×Qπ(n)||Q0×· · ·×Qπ(n−1))= n ∑”
A PAC-Bayesian Tutorial with A Dropout Bound (2013, methodology): “Tighter PACBayesian theorems have been given by various authors [12, 10, 7, 4, 6].”
Robust Forward Algorithms via PAC-Bayes and Laplace Distributions (2014, background): “1 [4]) For any distribution D, any set H of classifiers, any distributions P,Q of support H, any δ ∈ [0, 1], and any positive real scalar c, we have:”
Challenging the empirical mean and empirical variance: a deviation study (2010, methodology): “Our deviation study will use two kinds of tools: M-estimators to truncate observations and PAC-Bayesian theorems to combine estimates on the same sample without using a split scheme [13, 12, 14, 8, 2, 1].”
Tighter PAC-Bayes bounds through distribution-dependent priors (2013, methodology): “…version of exponential weights family of algorithm (Littlestone and Warmuth, 1989; Cesa-Bianchi et al., 1997; Vovk, 1990) such as Weighted Majority (which would predict with the weighted average of the hypotheses) and the stochastic version is studied in the PAC-Bayes setting in Catoni (2007).”
PAC-Bayesian learning of linear classifiers (2009, methodology): “The next corollary has also been found by Catoni (2007)[Th.1.2.1].”
Learning Efficient Random Maximum A-Posteriori Predictors with Non-Decomposable Loss Functions (2013, methodology): “Interestingly, when incorporating perturbmax models to Bayesian loss minimization one would ultimately like to use the PAC-Bayesian risk [11, 19, 3, 20, 5, 10].”
Chromatic PAC-Bayes Bounds for Non-IID Data (2009, background): “…introduced by McAllester (1999), and reﬁned in several occasions (Seeger, 2002a; Langford, 2005; Audibert and Bousquet, 2007), are some of the most appealing advances from the tightness and accuracy points of view (an excellent monograph on the Pac -Bayesian framework is that of Catoni (2007)).”
Risk bounds for the majority vote: from a PAC-Bayesian analysis to a learning algorithm (2015, background): “There have already been some attempts to develop PAC-Bayesian bounds that do not rely on the KL-divergence (see the localized Priors of Catoni (2007), or the distributiondependent priors of Lever et al. (2013)).”
Learning to share visual appearance for multiclass object detection (2011, methodology): “We now develop a connection between regret and risk bounds via a PAC-Bayesian analysis (McAllester, 2003; Audibert & Bousquet, 2007; Catoni, 2007). Such bounds also have the benefit of applying to any bounded loss (e.g., the 0-1 loss for binary classification), which may be more task-relevant than t”
A New PAC-Bayesian Perspective on Domain Adaptation (2015, background): “These results are presented as corollaries of Theorem 4 below, that generalizes a PAC-Bayesian theorem of Catoni (2007) to arbitrary loss functions.”
User-friendly introduction to PAC-Bayes bounds (2021, methodology): “I realize that most papers already assume some basic knowledge on these bounds, and that a monograph like [43] is quite technical to begin with.”
PAC-bayes bounds with data dependent priors (2012, background): “The tightest bounds for practical applications appear to be the PAC-Bayes bound (McAllester, 1999; Langford and Shawe-Taylor, 2002; Catoni, 2007) and in particular the form given in Seeger (2002), Langford (2005) and Germain et al. (2009).”
Entropy-SGD optimizes the prior of a PAC-Bayes bound: Data-dependent PAC-Bayes priors via differential privacy (2017, background): “Theorem 3.2 (Linear PAC-Bayes Bound (McAllester, 2013; Catoni, 2007)) .”