ICML-98 Submission #25

TITLE: Bayesian Classifiers are Large Margin Hyperplanes in a Hilbert Space

AUTHORS:
Nello Cristianini
Dept of Engineering Mathematics
University of Bristol
Bristol, UK

John Shawe-Taylor
Dept of Computer Science
Royal Holloway College
Egham, UK

Peter Sykacek
Austrian Research Institute
for Artificial Intelligence
Schottengasse 3, A-1010 Vienna, Austria

ABSTRACT Bayesian algorithms for Neural Networks are known to produce classifiers which are very resistent to overfitting. It is often claimed that one of their main distinctive features is that they don't simply output one hypothesis, but rather an entire distribution of probability over an hypothesis set: the Bayes posterior. An alternative perspective is that they output a linear combination of classifiers, whose coefficients are given by Bayes theorem. One of the concepts used to deal with thresholded convex combinations is the `margin' of the hyperplane with respect to the training sample, which is correlated to the predictive power of the hypothesis itself.

We provide a novel theoretical analysis of such classifiers, based on Data-Dependent VC theory, proving that they can be expected to be large margin hyperplanes in a Hilbert space. We then present experimental evidence that the predictions of our model are correct, i.e. that bayesian classifers really find hypotheses which have large margin on the training examples.

This not only explains the remarkable resistance to overfitting exhibited by such classifiers, but also co-locates them in the same class of other systems, like Support Vector machines and Adaboost, which have a similar performance.

Contact author email: nello.cristianini@bristol.ac.uk
Contact author phone: +44 117 928 9743
Contact author full address:

Nello Cristianini
Department of Engineering Mathematics
University Of Bristol,
Queen's Building, University Walk,
Bristol BS8 1TR,
United Kingdom