Large Scale Bayes Point Machines

Published 1 January 2000

Ralf Herbrich, Thore Graepel

Citations16

TL;DR

Experimental results on the MNIST data set of handwritten digits are presented which show that Bayes point machines (BPMs) are competitive with the current world champion, the support vector machine.

Abstract

The concept of averaging over classifiers is fundamental to the Bayesian analysis of learning. Based on this viewpoint, it has recently been demonstrated for linear classifiers that the centre of mass of version space (the set of all classifiers consistent with the training set) --- also known as the Bayes point --- exhibits excellent generalisation abilities. However, the billiard algorithm as presented in [4] is restricted to small sample size because it requires O \\Gamma m 2 \\Delta of memory and O \\Gamma N \\Delta m 2 \\Delta computational steps where m is the number of training patterns and N is the number of random draws from the posterior distribution. In this paper we present a method based on the simple perceptron learning algorithm which allows to overcome this algorithmic drawback. The method is algorithmically simple and is easily extended to the multi-class case. We present experimental results on the MNIST data set of handwritten digits which show that ...

Keywords

Computer Science

The Nature of Statistical Learning Theory

39,279 Citations1995Vladimir Vapnik

Machine LearningSupport-Vector Networks

33,035 Citations1995Corinna Cortes, Vladimir Vapnik

High generalization ability of support-vector networks utilizing polynomial input transformations is demonstrated and the performance of the support- vector network is compared to various classical learning algorithms that all took part in a benchmark study of Optical Character Recognition.

View PDF

The MIT Press eBooksProbabilities for SV Machines

1,015 Citations2000John C. Platt

This chapter contains sections titled: Introduction, Fitting a Sigmoid After the SVM, Empirical Tests, Conclusions, Appendix: Pseudo-code for the Sigmoids Training.

Prediction with Gaussian Processes: From Linear Regression to Linear Prediction and Beyond

639 Citations1998Christopher K. I. Williams

The main aim of this paper is to provide a tutorial on regression with Gaussian processes, starting from Bayesian linear regression, and showing how by a change of viewpoint one can see this method as a Gaussian process predictor based on priors over functions, rather than on prior over parameters.

IEEE Transactions on Information TheoryStructural risk minimization over data-dependent hierarchies

527 Citations1998John Shawe‐Taylor, Peter L. Bartlett +2 more

A result is presented that allows one to trade off errors on the training sample against improved generalization performance, and a more general result in terms of "luckiness" functions, which provides a quite general way for exploiting serendipitous simplicity in observed data to obtain better prediction accuracy from small training sets.

Some PAC-Bayesian theorems

489 Citations1998David McAllester

Neural ComputationGaussian Processes for Classification: Mean-Field Algorithms

215 Citations2000Manfred Opper, Ole Winther

A mean-field algorithm for binary classification with gaussian processes that is based on the TAP approach originally proposed in statistical physics of disordered systems is derived and an approximate leave-one-out estimator for the generalization error is computed.

Europhysics Letters (EPL)Optimal Learning with a Neural Network

60 Citations1993Timothy L. H. Watkin

It is found that the optimally-trained spherical perceptron may learn a linearly-separable rule as well as any possible network as well as any possible network in a neural network.

A PAC-Bayesian Margin Bound for Linear Classifiers: Why SVMs work

58 Citations2000Ralf Herbrich, Thore Graepel

A bound on the generalisation error of linear classifiers in terms of a refined margin quantity on the training set is presented in a PAC-Bayesian framework and is based on geometrical arguments in the space oflinear classifiers.

The Kernel Gibbs Sampler

21 Citations2000Thore Graepel, Ralf Herbrich

An algorithm that samples the hypothesis space of kernel classifiers with a uniform prior over normalised weight vectors and a likelihood based on a model of label noise leads to a piecewise constant posterior that can be sampled by the kernel Gibbs sampler (KGS).