Some PAC-Bayesian theorems
David McAllester · 1998
This paper gives PAC guarantees for "Bayesian" algorithms --- algorithms that optimize risk minimization expressions involving a prior probability and a likelihood for the training data. PAC-Bayesian algorithms are motivated by a desire to provide an informative prior encoding information about the expected experimental setting but still having PAC performance guarantees over all IID settings. The PACBayesian theorems given here apply to an arbitrary prior measure on an arbitrary concept space. These theorems provide an alternative to the use of VC dimension in proving PAC bounds for parameterized concepts. 1 INTRODUCTION Much of modern learning theory can be divided into two seemingly separate areas --- Bayesian inference and PAC learning. Both areas study learning algorithms which take as input training data and produce as output a concept or model which can then be tested on test data. In both areas learning algorithms are associated with correctness theorems. PAC correct...
Cited by 464 works. doi:10.1145/279943.279989
Authors
References
- Minimum complexity density estimation
- An experimental and theoretical comparison of model selection methods
- A framework for structural risk minimisation
- Complexity Regularization with Application to Artificial Neural Networks
- Results on learnability and the Vapnik-Chervonenkis dimension
- A PAC analysis of a Bayesian estimator
- Concept learning using complexity regularization