Bayesian online learning in the perceptron

Ole Winther, Sara A. SollaESANN 1997 · OpenReview

Introduction

In the field of machine learning, a fundamental tension exists between batch learning and online learning. While batch learning offers statistical power by processing entire datasets simultaneously, it is often computationally prohibitive for large-scale or streaming data. Online learning, conversely, updates models incrementally, offering efficiency at the cost of statistical optimality. This paper, originally presented at ESANN 1997, proposes a framework to bridge this gap by applying Bayesian inference to online learning through recursive updates and parametric approximations.

Methodology: Recursive Bayesian Updates

The core challenge of Bayesian online learning is that the posterior distribution of weights—representing our updated belief after seeing data—becomes increasingly complex with every new example. To maintain tractability, the authors propose a recursive approach:

  1. Update Rule: The posterior $p(w|D_m)$ is updated using only the most recent training example $D_m$ and the previous posterior $p(w|D_{m-1})$.
  2. Parametric Approximation: The complex posterior is approximated by a simpler parametric distribution (e.g., a Gaussian). This effectively compresses the information from previous examples into a few parameters, such as the mean and variance.
  3. The Cavity Method: To handle the high-dimensional integration required for these updates, the authors employ the "cavity method" from statistical mechanics, allowing them to predict the interaction between new inputs and the current weight distribution.

Results for Spherical and Binary Weights

The authors evaluate their framework on two primary weight configurations using synthetic data generated by a "teacher" perceptron.

Spherical Weights

For continuous weights with a spherical Gaussian prior, the Bayesian framework naturally re-derives the "optimal Hebbian" learning rule. This result is significant as it provides a rigorous theoretical foundation for existing heuristic update rules, showing they are optimal under specific Bayesian assumptions.

Binary Weights

In the case of discrete weights ($\\pm 1$), the learning dynamics exhibit a distinct "phase transition." Unlike the smooth convergence seen in continuous models, binary perceptrons often experience a "snap" where the generalization error drops sharply after a critical number of examples (typically $m/N \approx 3-4$) is reached.

Generalization error as a function of the ratio of training examples to dimensions ($m/N$) for a binary perceptron. The curve demonstrates the algorithm's ability to reduce error over time, despite the challenges of discrete weight spaces.

As shown in Figure 1, the Bayesian online algorithm effectively reduces generalization error as the number of training examples increases. However, the authors note that in the binary case, the algorithm can occasionally become trapped in local optima, a common hurdle in discrete optimization problems.

Conclusion and Future Directions

This research demonstrates that Bayesian online learning can achieve generalization performance comparable to batch methods while maintaining the computational efficiency of online updates. By viewing online learning as a form of information compression, the authors provide a unifying framework for understanding various learning heuristics. Future work remains focused on extending these principles to multi-layer neural networks and refining the choice of parametric approximations to better capture the true posterior in complex architectures.

Summary updated

BibTeX
@inproceedings{winther1997bayesian,
  author = {Ole Winther and Sara A. Solla},
  title = {{Bayesian online learning in the perceptron}},
  booktitle = {ESANN},
  year = {1997},
  url = {https://openreview.net/forum?id=YrNKpPStJe7},
}
Figure