Learning via Gaussian Herding

Koby Crammer, Daniel D. LeeNeurIPS 2010

TL;DR

This paper introduces NHERD (Normal/Gaussian Herd), a novel family of online learning algorithms. By treating weight vectors as a distribution flowing through space and "herding" this Gaussian distribution using constrained velocity fields, NHERD creates a learning rule that is exceptionally robust to noisy data. It consistently outperforms state-of-the-art methods like Adaptive Regularization of Weights (AROW) as label noise increases.

The Stability-Plasticity Dilemma in Online Learning

Online learning algorithms are the workhorses of large-scale machine learning. Because they process data one example at a time, they are highly efficient in both memory and time. However, they face a fundamental challenge known as the "stability-plasticity" dilemma: how much should the model change to fit a new data point (plasticity) without forgetting the patterns it has already learned (stability)?

Previous approaches, such as Confidence-Weighted (CW) learning, were often too aggressive. They assumed the data was perfectly separable, which led to severe overfitting when encountering noisy data. Newer methods like AROW improved upon this by softening the margin, but they still relied on minimizing the divergence between static distributions. This paper addresses the need for a more intuitive and robust way to regularize these updates, particularly when training data contains "label noise" (incorrectly labeled examples).

The NHERD Approach: Velocity Flow and Herding

The authors shift the perspective of online learning from static, discrete updates to a continuous velocity flow. Instead of simply jumping from an old distribution to a new one, they model the weight vectors as flowing under a velocity field defined by each new data observation.

Conceptual illustration of herding a distribution of points.

The NHERD algorithm operates on a few core principles:

  1. The Velocity Field: The algorithm assumes a linear transformation where the distribution is rotated, stretched, and translated to accommodate new information.
  2. Herding: The algorithm "herds" the Gaussian distribution by solving an optimization problem. It trades off the cost of the velocity (how much the distribution is forced to move) against a loss function (how well it fits the new data).
  3. Analytical Solution: By employing a squared-hinge loss and finding a uniform bound for the expected loss, the authors derive a precise, analytical update rule.

To make the algorithm computationally efficient for high-dimensional data, the authors introduce three variants that handle diagonal covariance matrices:

  • NHERD-E (Exact): The mathematically precise update.
  • NHERD-P (Project): Projects the update onto a specific space, ensuring valid covariance properties.
  • NHERD-D (Drop): A simplified version that drops certain cross-terms for speed.

Key Insights: Aggressive yet Robust

Unlike traditional filters (such as Kalman filters) that reweight and diffuse individual points, herding actively guides the entire distribution. It provides a "microscopic" view of the learning process that yields a highly stable "macroscopic" result.

Interestingly, NHERD’s update is more "aggressive" than AROW in how it increases precision (the inverse of variance). The update rule effectively "shrinks" the uncertainty (covariance) of the model in the direction orthogonal to the data point. The model becomes very certain about the features it just saw, but only if they align with the overall "herd."

Comparison of covariance updates between NHERD variants and AROW.

This decisiveness actually makes NHERD less likely to be swayed by random noise, as the geometric shrinking tightly bounds the model's future updates.

Experimental Results

The authors evaluated NHERD across a massive battery of over 155 datasets, spanning document classification, OCR (USPS and MNIST), phoneme recognition (TIMIT), and action recognition in video. Crucially, they tested all algorithms at 0%, 10%, and 30% artificial label noise to measure robustness.

  • Superiority in Noise: NHERD-P (the "Projected" version) emerged as the clear winner. While it performed similarly to AROW on clean data, it significantly outperformed all baselines as noise increased. At 30% noise, NHERD-P beat AROW in nearly 80% of the tested datasets.
  • Video Performance: On complex, high-dimensional action recognition video data, NHERD-P outperformed all other algorithms by a wide margin.
  • Tournament Results: In a comprehensive comparison, the NHERD family consistently sat at the top of the performance hierarchy, with NHERD-P generally outperforming both the Exact and Drop versions.

Limitations and Future Directions

While highly effective, NHERD does have limitations. The more efficient diagonal versions of the algorithm cannot currently use Mercer kernels, restricting them from non-linear learning (though the full-matrix version can). Additionally, like many online algorithms, NHERD relies on a tradeoff parameter ($C$) that requires some tuning, despite the algorithm's overall robustness.

Future work may extend this velocity flow framework to other types of distributions beyond Gaussians, or explore different types of constraints on the flow field, opening new avenues for robust online learning.

Summary updated

BibTeX
@inproceedings{crammer2010learning,
  author = {Koby Crammer and Daniel D. Lee},
  title = {{Learning via Gaussian Herding}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
}
Figure