Source-linked AI summary
Super-Samples from Kernel Herding
Yutian Chen, Max Welling, Alex Smola
TL;DR
The paper addresses the difficulty of extending herding from finite-dimensional discrete settings to continuous spaces. It introduces kernel herding as an infinite-memory deterministic sampling process, achieving O(1/T) Hilbert-space expectation-error convergence and compact super-sample sets for large sample collections. The method is illustrated for Bayesian predictive distributions and prediction averaging.
Problem
Finite-feature herding is difficult to extend to continuous spaces because infinitely many degrees of freedom can produce artifacts in pseudo-samples.
Method
Kernel herding reinterprets herding as an infinite-memory process and uses a kernel representation over potentially continuous state spaces.
Results
O(1/T) convergence is obtained for expectations of RKHS functions, faster than iid Monte Carlo, while herding can compress large sample collections into super-samples with the same empirical accuracy.
Takeaways & Limitations
Kernel herding supports compact sample sets for averaging predictions over many Bayesian or bootstrapped predictors and for reducing large MCMC collections.
Takeaways & Limitations
Kernel herding requires convolving the density with the chosen kernel, which is hard in general, and the paper uses only a Gaussian kernel without exploiting function-specific information.
Abstract
from arXiv · showhide
We extend the herding algorithm to continuous spaces by using the kernel trick. The resulting "kernel herding" algorithm is an infinite memory deterministic process that learns to approximate a PDF with a collection of samples. We show that kernel herding decreases the error of expectations of functions in the Hilbert space at a rate O(1/T) which is much faster than the usual O(1/pT) for iid random samples. We illustrate kernel herding by approximating Bayesian predictive distributions.
1 INTRODUCTION
Kernel herding extends herding to continuous spaces by using infinitely many kernel features, avoiding artifacts caused by finite-feature representations. It deterministically reduces Hilbert-space expectation error faster than iid sampling and can produce compact super-samples for prediction averaging.
- Motivation: Finite features cannot control continuous spaces’ infinitely many degrees of freedom, producing artifacts such as delta-peaks instead of a Gaussian.The paper motivates a kernel representation to address this limitation.
- Method: Kernel herding reinterprets herding as an infinite-memory process over past samples and applies the kernel trick to continuous state spaces.The formulation marginalizes parameters and maps the entire sample history to the next state.
- Convergence: O(1/T) error convergence for RKHS functions is faster than the standard iid Monte Carlo rate.The process achieves this through negative autocorrelations that steer sampling away from already oversampled regions.
- Scope and use: Kernel herding requires convolution of the target density with the chosen kernel, which is difficult in general.The method remains applicable for reducing large MCMC collections when that convolution is unavailable.
- Applications: Herding can select a small, ordered set of super-samples for averaging predictions over many predictors while reducing approximation error at each iteration.The paper validates this use through numerical experiments.
2 KERNEL HERDING
Kernel herding recasts herding in an RKHS and continuous state space as an infinite-memory process that greedily reduces empirical feature-distribution error. Under stated geometric conditions, it achieves O(T^-1) convergence for Hilbert-space expectations and supports compact super-sample representations.
- 2.1 Herding: Kernel herding extends herding to potentially continuous index spaces by representing states with a feature map into a Hilbert space.The formulation uses a dual view that removes the parameter vector in favor of the generated states.
- 2.1 Herding: The algorithm is an infinite-memory process: each new sample depends on the entire history and greedily minimizes the conditional squared error.It can be viewed as a state-space mapping after marginalizing the parameters.
- 2.2 Convergence in Hilbert Space: Negative autocorrelations explain the faster convergence by steering samples away from regions already oversampled, unlike iid sampling's O(T^-1/2) rate.The paper relates this behavior to Quasi Monte Carlo and Bayesian quadrature methods.
- 2.2 Convergence in Hilbert Space: O(T^-1) convergence holds when the target mean lies in the relative interior of the marginal polytope and feature norms are bounded.The same rate extends to function-expectation error uniformly over the unit ball of the Hilbert space.
- 2.2 Convergence in Hilbert Space: The paper's Gaussian-kernel choice leaves function-specific kernel design unexplored, although universal kernels suggest distributional convergence at O(T^-1).The authors identify kernels tailored to a known integration function or function distribution as future work.
- 2.1 Herding: For every n herding samples, O(n^2) iid samples are needed to achieve the same error reduction, motivating the term “super-samples.”Herding can also sub-select a small collection from a larger MCMC sample set, where negative autocorrelations may improve approximation beyond decorrelated subsampling.
3 Experiments
Experiments show that herding produces more accurate expectation estimates than random sampling and can compress empirical or posterior samples while preserving predictive accuracy.
- 3.1 Experiments: Herding samples represent a 2-D Gaussian mixture more evenly than iid samples, which can overrepresent or miss modes.The herding samples repel one another and are distributed to represent the density given earlier samples.
- 3.1 Experiments: Herding yields smaller expectation-estimation errors than random sampling for all four tested functions, with convergence rates close to O(T^-1).The functions include the first three moments and a nonlinear sine-of-norm function.
- 3.1 Experiments: For an empirical distribution of 10^5 iid samples, at most 2000 super-samples suffice for the first three functions and 10^4 for the fourth to achieve similar precision.Error on the empirical distribution continues decreasing, while error on the true distribution converges to the empirical-distribution error.
- 3.2 Approximating the Bayesian Posterior: In Bayesian logistic regression on Spambase, herding compresses posterior samples while retaining predictive performance.The experiment uses 10^5 posterior samples obtained by Metropolis-Hastings and applies herding to their empirical distribution.
- 3.2 Approximating the Bayesian Posterior: The predictive-probability error decreases roughly as O(T^-0.75) for herding versus O(T^-0.5) for random sampling.The comparison uses random subsets of the posterior sample set as the baseline.
- 3.2 Approximating the Bayesian Posterior: About 20 super-samples match the full-set classification accuracy, whereas random subsets require about 200 samples; posterior parameters can be compressed by 93% or 97%.The classification comparison is reported on the test set, and the compression result is reported for predictive distributions.
4 DISCUSSION
Kernel herding extends herding to continuous spaces and produces samples that can be more informative than IID samples. Its benefits include faster expectation approximation and compact super-sample sets, while practical use is constrained by kernel-convolution and kernel-design limitations.
- Kernel herding extends the original herding algorithm to continuous spaces and generates samples containing more information than IID samples.
- O(T^-1) convergence applies to expectations of Hilbert-space functions for distributions whose density-kernel convolution is computable.
- For other distributions, KH converts a larger sample collection into a more compact set of super-samples with the same empirical-distribution accuracy.
- The paper uses a Gaussian kernel without exploiting information about the function of interest, leaving better kernel design as future work.
- Negative autocorrelation lets herding use fewer samples than IID Monte Carlo for comparable error.
- Stochastic convolution approximations could make KH more practical for general distributions p.