Abstract

The talk will be composed of two parts. The first part will be an introduction to PAC learning. The second will be an introduction to PAC -Bayes.

Probably Approximately Correct learning (PAC learning) is a framework for the mathematical analysis of machine learning, proposed in 1984 by Leslie Valiant. The framework introduces computational complexity theory concepts to machine learning, expecting the learner to find efficient functions (polynomial time and space) using a polynomial learning procedure as well. PAC learning gave rise to the field of computational learning theory, whose primary goal is to compare the power of different learning models. This talk will introduce the basic concepts and present some of the results obtained using PAC learning and VC theory. Since this part of the talk is tutorial in nature no reading will be required.

PAC -Bayes is a PAC like framework where the generalization error bounds are derived using a reference distribution chosen before seeing the data. The bounds are often very tight relative to other types of PAC bound. There are intimate connections to the Bayesian view of learning though the two theories are not identical. In this talk we will give a tutorial on the basic concepts of PAC -Bayes before discussing the now classic application to Gaussian process classification. This part of the talk is tutorial in nature and relatively self contained apart from some knowledge of Gaussian processes which will be assumed. An idea of the content of the talk can be gained by looking at Seeger’s work:

http://www.jmlr.org/papers/volume3/seeger02a/seeger02a.pdf

but a detailed understanding of this paper is certainly not essential to learn from the talk.