Super-Samples from Kernel Herding

By Yutian Chen, Max Welling, Alex Smola. 2010

403 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Statistical Learning Theory

Citations in the corpus

GAIT: A Geometric Approach to Information Theory (2019, methodology): “…the approximation of the density of a mixture of Gaussians P by a uniform distribution Q = 1N ∑N i=1 δxi over N = 200 atoms with a polynomial kernel of degree 1.5, similar to the approximate super-samples (Chen et al., 2010) task presented by Claici et al. (2018) using the Wasserstein distance.”
Sequential Kernel Herding: Frank-Wolfe Optimization for Particle Filtering (2015, methodology): “We build on the optimization view from Bach et al. (2012) of kernel herding (Chen et al., 2010) to approximate the integrals appearing in the Bayesian ﬁltering recursions.”
On the Equivalence between Herding and Conditional Gradient Algorithms (2012, positive): “Note that the mapping Φ may be explicit (classically in low-dimensional settings) or implicit—where the kernel trick can be used, see Section 4.3 and Chen et al. (2010).”
Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, methodology): “In practice, πi and {mi, σi} are solved alternately until convergence (see, e.g., Song et al. (2008), Chen et al. (2010)).”
Consistent Kernel Mean Estimation for Functions of Random Variables (2016, methodology): “Various approaches, such as kernel herding (Chen et al., 2010; Lacoste-Julien et al., 2015), attempt to produce a better KME estimator by actively generating pseudo-samples that are not i.i.d. from the underlying distribution.”
On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions (2015, methodology): “We will not pursue this here as our theoretical results do not accommodate such constraints (see, e.g., Chen et al., 2010; Bach et al., 2012, and references therein).”
Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels (2014, methodology): “Thus, under certain , herding and (15) are equivalent Chen et al. [2010] also showed that under certain restrictions on the RKHS, herding will reduce the discrepancy in a ratio of O (1 /t ) .”
Characteristic Kernels and Infinitely Divisible Distributions (2014, background): “, 2013) and kernel herding algorithms (Chen et al., 2010) can also be extended to estimators f = ∑n i=1wimPθi with parametric kernel means {Pθi}.”
Optimally-Weighted Herding is Bayesian Quadrature (2012, methodology): “To ensure a comparison fair to herding, the target distribution, and the kernel used by both methods, correspond exactly to the one used in (Chen et al., 2010, Fig.”
Variational Prototype Replays for Continual Learning (2019, background): “There have been some attempts to select representative image examples to store based on different scoring functions (Chen et al., 2012; Koh & Liang, 2017; Brahma & Othon, 2018).”
Bayesian Inference and Learning in Gaussian Process State-Space Models with Particle MCMC (2013, neutral): “random sub-sampling or kernel herding [19].”
Dataset Condensation with Differentiable Siamese Augmentation (2021, background): “The coreset selection competitors are random , herding (Chen et al., 2010; Rebufﬁ et al., 2017; Castro et al., 2018; Belouadah & Popescu, 2020) and forgetting (Toneva et al., 2019).”
Black-box Importance Sampling (2016, background): “In the light of this, bound (7) is a form of the worse case bounds of the kernel-based quadrature rules (e.g., Chen et al., 2010; Bach, 2015; Huszár and Duve-naud, 2012; Niederreiter, 2010).”
Few-Shot Self Reminder to Overcome Catastrophic Forgetting (2018, methodology): “Other sophisticated methods such as influence function [15] and kernel herding [6] could potentially be used for point selection.”
Learning with Symmetric Label Noise: The Importance of Being Unhinged (2015, methodology): “Alternately, one can post hoc search for a sparse approximation to w ∗ unh ,λ , for example using kernel herding [Chen et al., 2012].”
On the Equivalence between Quadrature Rules and Random Features (2015, methodology): “If these constraints are required, kernel herding (Chen et al., 2010; Bach et al., 2012) provides a novel way to select a sequence of points based on the conditional gradient algorithm, but with currently no convergence guarantees improving over O (1 / √ n ) for inﬁnite-dimensional spaces.”