Generalisation Error Bounds in the PAC-Bayesian Framework

In the Bayesian framework learning is viewed as an update of prior belief in the target concept in light of the data. The learning algorithms considered in the PAC-Bayesian framework are the Gibbs classifier (or better classification strategy) and the Bayes classifiers. Thus, once a learning algorithm is expressed as an update of a probability distribution such that the Bayes classifier is equivalent to the classifier at hand, the whole (and powerful) machinery of PAC-Bayesian can be applied. We are particularly interested in the study of linear classifiers. A geometrical picture reveals that the margin is only an approximation to the real quantity controlling generalisation error: the volume of consistent classifiers to the whole volume of parameter space. Hence we are able to remove awkward constant as well as permanent complexity terms from known margin bounds. The resulting bound can considered as tight and practically useful for bound based model selection. Further research aims at revealing the limitation of bound based model selection and to extent the analysis to unbounded loss like in regression or unsupervised learning techniques such as clustering, PCA or ICA.

References

• Ralf Herbrich and Thore Graepel. A PAC-Bayesian Margin Bound for Linear Classifiers. , 2002. IEEE Transactions on Information Theory. (Gzipped PostScript)
• Thore Graepel and Ralf Herbrich. A PAC-Bayesian Margin Distribution Bound for Kernel Classifiers (extended abstract). , 2001. Poster at "New Directions in Kernel Based Learning Methods" NIPS*2001 workshop. (Gzipped PostScript)
• David McAllester. Some PAC Bayesian Theorems. Proceedings of the 11-th Annual Conference on Learning Theory. pages 230-234.  (Postscript)
• David McAllester. PAC-Bayesian Model Averaging. Proceedings of the 12-th Annual Conference on Learning Theory. (Postscript)