PAC-Bayesian Generalisation Error Bounds for Gaussian Process Classification

By Matthias W. Seeger. 2003

376 citations recorded by the source corpus.

Approximate Bayesian Gaussian process (GP) classification techniques are powerful non-parametric learning methods, similar in appearance and performance to support vector machines. Based on simple probabilistic models, they render interpretable results and can be embedded in Bayesian frameworks for model selection, feature selection, etc. In this paper, by applying the PAC-Bayesian theorem of McAllester (1999a), we prove distribution-free generalisation error bounds for a wide range of approximate Bayesian GP classification techniques. We also provide a new and much simplified proof for this powerful theorem, making use of the concept of convex duality which is a backbone of many machine learning techniques. We instantiate and test our bounds for two particular GPC techniques, including a recent sparse method which circumvents the unfavourable scaling of standard GP algorithms. As is shown in experiments on a real-world task, the bounds can be very tight for moderate training sample sizes. To the best of our knowledge, these results provide the tightest known distribution-free error bounds for approximate Bayesian GPC methods, giving a strong learning-theoretical justification for the use of these techniques.

Subfields: Artificial Intelligence, 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

In Probabilistic & Bayesian Methods

In Statistical Learning Theory

Citations in the corpus

PAC-Bayesian Theory Meets Bayesian Inference (2016, neutral): “Seeger (2002, 2003) [42, 43] .”
Wireless Network Intelligence at the Edge (2018, background): “It is worth noting that the difference between L(q) and L̂(q) can be measured using their KL divergence, yielding the refined version by [126] as stated below.”
A PAC-Bayesian Tutorial with A Dropout Bound (2013, background): “PAC-Bayesian generalization bounds [11, 12, 10, 7, 4, 6] govern the performance (loss) when stochastically selecting rules from a “posterior” distribution.”
PAC-Bayes-Bernstein Inequality for Martingales and its Application to Multiarmed Bandits (2011, methodology): “The PAC-Bayesian analysis was introduced over a decade ago (Shawe-Taylor and Williamson, 1997; Shawe-Taylor et al., 1998; McAllester, 1998; Seeger, 2002) and has since made a significant contribution to the analysis and development of supervised learning methods.”
Bayesian Counterfactual Risk Minimization (2018, methodology): “We have presented a PAC-Bayesian analysis of counterfactual risk minimization, for learning Bayesian policies from logged bandit feedback.”
Information-theoretic upper and lower bounds for statistical estimation (2006, methodology): “The key ingredient in our proof of the information exponential inequality is a well-known convex duality, which employs KL-complexity, and has already been used in some recent machine learning papers to study sample complexity bounds [2], [4], [5], [11], [12].”
On Sparse Variational Methods and the Kullback-Leibler Divergence between Stochastic Processes (2015, methodology): “As will be evident, many of the required technical results were derived early on in the use of Gaussian processes for machine learning by Seeger (2003a; 2003b).”
Generalization Error Bounds for Bayesian Mixture Algorithms (2003, methodology): “We note that a similar use of convex duality was made in a related context by Seeger (2002) In general, it may be difficult to compute the expectation of g∗ with respect to σ.”
Inconsistency of Bayesian Inference for Misspecified Linear Models, and a Proposal for Repairing It (2014, background): “The original generalized posterior is a notion going back at least to [23] and has been developed mainly within the so-called (frequentist) PAC-Bayesian framework [17, 22, 4, 1, 26]; see also [3].”
PAC-Bayes-Empirical-Bernstein Inequality (2013, methodology): “We applied the bound to derive the PAC-Bayes-Empirical-Bernstein inequality which is a powerful Bernstein-type inequality outperforming the state-of-the-art PAC-Bayes-kl inequality of Seeger [7] in situations, where the empirical variance is smaller than the empirical loss and otherwise comparable t”
G-Learning: Taming the Noise in Reinforcement Learning via Soft Updates (2015, background): “For example, it is shown in [22] that for any prior distribution P over classifiers, with probability at least 1 − δ over the sample S of n instances i.”