Bayes Point Machines

Ralf Herbrich, Thore Graepel, Colin CampbellJMLR 2001

TL;DR

This paper introduces the Bayes Point Machine (BPM), a novel kernel classifier that approximates the Bayes-optimal decision by estimating the center of mass of the "version space" (the set of all consistent classifiers). BPMs offer improved generalization performance over Support Vector Machines (SVMs) on various datasets, particularly in scenarios with elongated version spaces.

What Problem Does This Paper Address?

The paper addresses the fundamental challenge in machine learning of finding a classifier that generalizes well to unseen data. It highlights the divergence between two major schools of thought in machine learning: the frequentist approach, exemplified by Support Vector Machines (SVMs) which focus on finding a single "best" classifier (e.g., maximum margin), and the Bayesian approach, which considers the entire posterior distribution of possible classifiers. While SVMs are computationally efficient and often perform well, they can be suboptimal from a Bayesian perspective. The authors aim to bridge this gap by proposing a method that leverages the strengths of both approaches, offering a more principled Bayesian inference while remaining computationally tractable.

Methods

The core contribution is the Bayes Point Machine (BPM). Instead of finding a single optimal classifier like SVMs, BPMs aim to approximate the Bayes-optimal decision, which is the expected prediction over the entire posterior distribution of classifiers. This is achieved by estimating the center of mass of the version space. The version space is defined as the set of all classifiers consistent with the training data.

Two key algorithms are proposed for estimating this center of mass:

  1. Kernel Billiard Algorithm: This method treats the version space as a geometric region and simulates a "billiard ball" bouncing within it. By averaging the positions of the ball over time, it approximates the center of mass. This approach is exact in theory but computationally intensive.
  2. Permuted Perceptron Algorithm: This algorithm leverages the fact that the solution to linear classifiers can be represented as a linear combination of training points. By training a standard perceptron on different permutations of the training data and averaging the resulting classifiers, it provides an efficient approximation to the Bayes point, especially for large datasets.

The paper also discusses the connection between BPMs and SVMs, showing that SVMs can be viewed as a spherical approximation to the Bayes point, particularly in the hard margin case. Furthermore, it extends the BPM framework to handle "soft boundaries" (allowing training errors), which brings its performance closer to that of soft-margin SVMs.

Datasets

The paper evaluates its methods on a variety of datasets:

  • Artificial Data: A toy dataset in R³ generated with a linear decision rule was used to illustrate the benefits of BPMs in elongated version spaces.
  • UCI Benchmark Datasets: Five standard datasets from the UCI Repository (Heart, Thyroid, Diabetes, Waveform, Banana, Sonar, Ionosphere) were used for comparison.
  • Handwritten Digit Recognition: The USPS and MNIST datasets were used for large-scale experiments.

Key Insights and Ideas

  • Bayes Point as Center of Mass: The central idea is that the Bayes-optimal classifier can be approximated by the center of mass of the version space. This provides a principled way to combine information from all consistent hypotheses.
  • SVM as Spherical Approximation: SVMs are shown to be a spherical approximation to the Bayes point, particularly in the hard margin case. This explains why SVMs often perform well but can be suboptimal from a Bayesian perspective.
  • Kernel Billiard for Geometric Sampling: The billiard analogy offers an intuitive geometric interpretation of sampling from the version space.
  • Permuted Perceptron for Scalability: Using permutations of the training data with a perceptron is a clever way to obtain approximate Bayes points efficiently, making the method scalable to large datasets.
  • Soft Boundaries Bridge the Gap: Extending BPMs to allow training errors (soft boundaries) significantly improves their performance and brings them closer to the performance of soft-margin SVMs.
  • Real-valued Output as Confidence Measure: The real-valued output of BPMs on test points serves as a useful confidence measure, enabling effective rejection criteria and reducing generalization error.

Key Results

  • Superior Generalization (Hard Margin): For the zero training error case (hard margin/boundary), Bayes Point Machines consistently outperformed Support Vector Machines on both artificial and real-world benchmark datasets. For example, on the Sonar dataset, BPM achieved 15.9% error compared to SVM's 15.4% (though the paper notes this difference is not statistically significant for Sonar). On the Heart dataset, BPM achieved 22.8% error versus SVM's 25.4%.
  • Reduced Performance Gap (Soft Margin): When allowing for training errors (soft boundaries), the performance advantage of BPMs over SVMs was reduced, indicating that soft-margin SVMs also approximate the Bayes point behavior.
  • MNIST/USPS Performance: On large-scale handwritten digit recognition tasks (MNIST and USPS), BPMs achieved competitive generalization errors. For MNIST, SVM achieved 1.4% without rejection, while BPM achieved 1.46%. However, with rejection based on the real-valued output, BPM's error was reduced to an impressive 0.1%.
  • Confidence Measure: The real-valued output of BPMs was shown to be a valid confidence measure, leading to a steady decrease in generalization error when used as a rejection criterion.

Limitations and Future Work

  • Computational Cost of Billiard Algorithm: The kernel billiard algorithm, while theoretically exact, is computationally expensive, especially for large datasets.
  • Approximation Nature: The permuted perceptron algorithm provides an approximation to the Bayes point, and its accuracy depends on the number of permutations used.
  • Bias Dimension: Incorporating a bias dimension into the BPM framework is noted as conceptually challenging due to the normalization of the weight vector.
  • Ergodicity of Billiard: Further investigation into the ergodicity of the billiard sampling method is suggested.
  • Properties of Single Classifiers: An interesting open question is identifying which specific properties of single classifiers in version space are responsible for good generalization.
  • Dense Classifiers: The paper notes that while sparsity is often believed to indicate good generalization, their algorithms show that dense classifiers can also exhibit good performance, raising further questions about generalization.

Summary updated

BibTeX
@article{herbrich2001bayes,
  author = {Ralf Herbrich and Thore Graepel and Colin Campbell},
  title = {{Bayes Point Machines}},
  journal = {J. Mach. Learn. Res.},
  year = {2001},
}

Loading related content...

Figure