PaperlayerView exact revision on arXiv

Source-linked AI summary

Kernel Mean Embedding of Distributions: A Review and Beyond

Krikamol Muandet, Kenji Fukumizu, Bharath Sriperumbudur, Bernhard Schölkopf

arXiv:1605.09522v4stat.MLcs.LG

TL;DR

Kernel mean embeddings address how to represent probability distributions for kernel-based learning and inference. This survey reviews their RKHS foundations, theoretical guarantees, applications, conditional extensions, and open problems, including dimensionality-related limitations.

  • Problem

    Machine learning and statistics need reliable distributional representations, while many applications involve probability measures rather than individual data points.

  • Method

    The survey studies mappings of distributions into RKHSs and conditional mean embeddings that represent conditional distributions as operators or feature-space objects.

  • Results

    Characteristic-kernel embeddings capture all information about a distribution, while the framework supports statistical inference and applications to complex objects and conditional probability rules.

  • Takeaways & Limitations

    Kernel mean embeddings extend RKHS methods to probability measures across two-sample and independence testing, distributional learning, probabilistic inference, and related applications.

  • Takeaways & Limitations

    MMD-based methods can suffer from the curse of dimensionality, with test power potentially decreasing as dimension grows.

Abstract

from arXiv · show

A Hilbert space embedding of a distribution---in short, a kernel mean embedding---has recently emerged as a powerful tool for machine learning and inference. The basic idea behind this framework is to map distributions into a reproducing kernel Hilbert space (RKHS) in which the whole arsenal of kernel methods can be extended to probability measures. It can be viewed as a generalization of the original "feature map" common to support vector machines (SVMs) and other kernel methods. While initially closely associated with the latter, it has meanwhile found application in fields ranging from kernel machines and probabilistic modeling to statistical inference, causal discovery, and deep learning. The goal of this survey is to give a comprehensive review of existing work and recent advances in this research area, and to discuss the most challenging issues and open problems that could lead to new research directions. The survey begins with a brief introduction to the RKHS and positive definite kernels which forms the backbone of this survey, followed by a thorough discussion of the Hilbert space embedding of marginal distributions, theoretical guarantees, and a review of its applications. The embedding of distributions enables us to apply RKHS methods to probability measures which prompts a wide range of applications such as kernel two-sample testing, independent testing, and learning on distributional data. Next, we discuss the Hilbert space embedding for conditional distributions, give theoretical insights, and review some applications. The conditional mean embedding enables us to perform sum, product, and Bayes' rules---which are ubiquitous in graphical model, probabilistic inference, and reinforcement learning---in a non-parametric way. We then discuss relationships between this framework and other related areas. Lastly, we give some suggestions on future research directions.

Introduction

This survey develops kernel mean embeddings as a framework for mapping distributions into RKHSs, reviewing theoretical properties, applications, conditional extensions, and open research directions.

  • Scope and contribution: The survey provides a comprehensive review of kernel mean embeddings, including theoretical results, practical applications, related areas, and challenging open problems.It positions the review as filling a gap in the existing literature.
  • Marginal embeddings: Kernel functions extend feature maps from data points to probability distributions by representing each distribution as a mean function in an RKHS.The embedding is formed through an expectation operation, interpreted as a Bochner integral when needed.
  • Theoretical properties: For characteristic kernels, the mean map is injective, so the RKHS representation uniquely characterizes distributions and supports distributional metrics and two-sample tests.The embedding distance is zero exactly when the represented distributions are identical.
  • Conditional embeddings: Conditional mean embeddings represent conditional distributions through operators between RKHSs, enabling non-parametric analogues of sum, product, and Bayes’ rules.They also provide a way to compute conditional expectations through RKHS inner products.
  • Applications: Kernel mean embeddings support statistical inference and learning with distributions, including two-sample and independence testing, causal inference, and distributional-data learning.These extensions also accommodate non-vectorial objects such as graphs, strings, and semigroups through suitable kernels.
  • Survey organization: The survey organizes marginal embeddings, conditional embeddings, their applications, and future directions into a unified review of the framework.Sections cover MMD, dependence measures, learning on distributional data, probabilistic inference, reinforcement learning, and causal discovery.

Background

Kernel methods replace explicit inner products with positive definite kernels, enabling nonlinear learning in RKHSs without constructing high-dimensional feature maps. This framework supports diverse data types and motivates extending feature maps from points to distributions.

  • Kernel methods: Kernel methods obtain nonlinear algorithms by replacing the original inner product with an inner product in a feature space.The learning algorithm remains structurally unchanged while the representation space changes.
  • Kernel methods: The kernel trick avoids explicitly constructing potentially high-dimensional feature maps when evaluating similarities.This is especially useful for polynomial kernels with large degree.
  • Kernel methods: Positive definite kernels represent inner products in feature spaces and define corresponding reproducing kernel Hilbert spaces.The feature map need not be computed explicitly.
  • Kernel methods: Positive definite kernels apply beyond Euclidean vectors to structured, functional, and non-Euclidean data.Examples include graphs, text documents, and semigroups.
  • RKHS foundations: Mercer’s theorem characterizes continuous positive definite kernels on compact spaces through nonnegative eigenvalues and eigenfunction expansions.The expansion can provide an explicit feature-map representation.
  • Spectral characterization: Bochner’s theorem links translation-invariant kernels to spectral measures that determine which characteristic-function frequencies enter the embedding.Full spectral support yields uniquely identifying embeddings.

Distributions

Kernel mean embeddings generalize feature maps from individual data points and Dirac measures to arbitrary probability measures in an RKHS. They represent expectations, can preserve distributions under characteristic kernels, and admit consistent empirical estimation.

  • From points to measures: Kernel mean embedding extends the feature-map viewpoint from data points and Dirac measures to general probability measures.Figure 3.1 presents this progression from points to probability measures.
  • Finite-support measures: Finite-support measures include empirical measures, signed measures, and point processes, extending the framework beyond individual Dirac measures.Equal weights ai = 1/n produce the empirical measure associated with a sample.
  • Mean embedding: A probability measure is represented in an RKHS by integrating the kernel feature function with respect to that measure.The integral is interpreted as a Bochner integral.
  • Mean embedding: For any RKHS function f, its expectation under P equals the inner product between f and the embedding µP.This reproducing property supports expectation evaluation in probabilistic inference.
  • Estimation and representation: The empirical mean embedding is unbiased, converges to the population embedding, and captures more information as the kernel representation includes higher moments.The survey also notes explicit inner-product representations for translation-invariant kernels.

3.2 Covariance Operators

Covariance and cross-covariance operators generalize Euclidean covariance matrices to RKHSs. They encode joint and marginal feature relationships, support conditional mean embeddings, and can be estimated from samples.

  • Operator definitions: Covariance and cross-covariance operators generalize covariance matrices to infinite-dimensional RKHS elements.They are central to modern distribution-embedding applications.
  • Operator definitions: The cross-covariance operator maps functions in one RKHS to another using tensor products of canonical feature maps.Its definition is based on the joint distribution of (X,Y).
  • Centering: The centered cross-covariance operator subtracts the tensor product of the marginal mean embeddings from the joint mean embedding.This removes the uncentered marginal contribution.
  • Operator properties: Under stated moment assumptions, cross-covariance operators are well-defined Hilbert-Schmidt operators.The existence argument bounds expected tensor-product norms using kernel diagonal expectations.
  • Operator properties: The cross-covariance operator has an equivalent bounded-operator characterization through bilinear inner products of functions from the two RKHSs.This equivalence follows from Hilbert-Schmidt theory under the stated assumptions.
  • Conditional embeddings: A basic theorem relating conditional expectations to covariance operators underpins the later definition of conditional mean embeddings.The result assumes E[g(Y)|X=·] belongs to the input RKHS.

3.2. Covariance Operators

The survey develops operator decompositions, empirical convergence results, and kernel conditions governing whether mean embeddings retain complete distributional information. Characteristic kernels provide injectivity, while empirical embeddings achieve optimal n^-1/2 convergence under boundedness assumptions.

  • Dependence operators: The normalized cross-covariance operator captures dependence with less influence from marginal distributions than the unnormalized operator.It is also related to canonical correlation.
  • Applications: Covariance operators support kernel PCA, kernel discriminant analysis, kernel CCA, kernel ICA, and dependence measures.These applications extend across classical and modern kernel methods.
  • Empirical convergence: Under bounded continuous kernels on separable spaces, empirical mean embeddings converge in RKHS norm at rate n^-1/2.The survey reports this rate as minimax optimal and notes Gaussian-process asymptotics.
  • Characteristic kernels: A characteristic kernel is one whose mean map from distributions to RKHS elements is injective.This ensures that zero embedding distance occurs exactly for identical distributions.
  • Characteristic kernels: Gaussian and Laplacian kernels are characteristic on Rd, and translation-invariant kernels are characteristic when their Fourier-transform support is all of Rd.These conditions ensure that the embedding retains enough information to identify the distribution.
  • Characteristic kernels: Characteristic-kernel guarantees depend on kernel richness, including density conditions that allow representation of higher-order distributional information.Universal kernels on compact domains provide a related sufficient setting.

3.3. Properties of the Mean Embedding

This section reviews kernel properties that determine when mean embeddings distinguish distributions and how kernel mean estimators can be computed and improved. It also discusses shrinkage methods and approximations for reducing estimation error and computational cost.

  • Kernel classes: Universal kernels have RKHSs dense in bounded continuous functions on compact metric spaces, supporting arbitrarily accurate approximation in principle.The survey also relates characteristic and universal kernels in non-Euclidean settings, including groups, semigroups, and translation-invariant kernels.
  • Characteristic kernels: Characteristic kernels make the mean map injective, so equal embeddings imply identical distributions and the RKHS distance defines a distribution metric.For non-characteristic kernels, embeddings may identify only equivalence classes, although uniqueness can hold for restricted distribution classes.
  • Kernel mean estimation: The empirical kernel mean averages k(x_i, ·) over an i.i.d. sample and converges to the population embedding at rate O_p(n^-1/2).The estimator is described as minimax, motivating investigation of alternatives despite its optimality under limited distributional knowledge.
  • Kernel mean shrinkage estimators: Shrinkage estimators pull the empirical embedding toward a fixed function or shrink spectral components, trading increased bias for reduced variance.Spectral methods project data onto the KPCA basis, shrink components according to a filter, and reconstruct the estimate.
  • Approximating the kernel mean: Kernel methods can become computationally prohibitive because many algorithms scale at least quadratically with sample size, motivating compact mean approximations.Randomized feature maps represent the empirical mean in R^m and accelerate downstream algorithms, but apply only to certain kernel classes.

3.5 Maximum Mean Discrepancy

Maximum Mean Discrepancy (MMD) measures the distance between kernel mean embeddings and provides a distributional metric for two-sample testing. Its characteristic-kernel guarantees, convergence properties, and applications offer broad utility, while high-dimensional test power remains a limitation.

  • MMD is the distance in an RKHS between the mean embeddings of two probability distributions.It is obtained by taking the integral probability metric over the unit ball of an RKHS.
  • MMD admits bounds in terms of Wasserstein and total variation distances, so closeness under those metrics implies closeness in MMD.The total variation bound requires a bounded kernel diagonal, with sup_x k(x,x) ≤ C.
  • For characteristic kernels, MMD is zero if and only if the two distributions are identical.This follows from injectivity of the kernel mean embedding.
  • Empirical MMD estimators are constructed using U-statistics or V-statistics from independent samples drawn from the compared distributions.The U-statistic is unbiased, whereas the corresponding V-statistic is generally biased.
  • MMD has rapid empirical convergence of order 1/√n that is generally independent of dimension, although dimension-dependent constants can become large.The resulting curse of dimensionality can reduce the power of linear-time and kernel-based tests as dimension grows.
  • MMD tests are distribution free, support structured domains through positive definite kernels, and can replace GAN discriminators with a closed-form, computationally efficient objective.MMD nets avoid the hard minimax objective used in traditional GANs.

3.6. Kernel Dependency Measures

Kernel dependency measures use RKHS operators to detect relationships between random variables. HSIC provides a nonparametric independence criterion with theoretical and practical applications across statistics and machine learning.

  • HSIC measures dependence as the squared Hilbert–Schmidt norm of the cross-covariance operator between two RKHSs.The construction uses kernels k and l on the respective domains.
  • With a characteristic product kernel, HSIC is zero if and only if the two random variables are independent.The result follows by identifying the joint embedding with the product of marginal embeddings.
  • HSIC supports applications including supervised feature selection by maximizing dependence between selected covariates and targets.The targets may be binary, multiclass, or real-valued regression outputs.

3.6. Kernel Dependency Measures

Kernel dependency methods extend beyond ordinary independence testing to permutation-based, multivariable, structured, and time-series settings. These extensions require care because approximations and non-i.i.d. dependence can affect validity or convergence.

  • Independence can be tested by comparing the joint distribution PXY with the product distribution PX ⊗ PY using MMD.The product-distribution sample is approximated by randomly permuting the Y observations.
  • A learned permutation that preserves similarity in a conditioning variable enables a conditional independence test.The construction extends the permutation-based MMD formulation.
  • Extensions of HSIC address conditional dependence, three-variable interaction, and relative dependency.Lancaster interaction and relative-dependency tests are cited as examples.
  • Random permutations only approximate samples from PX ⊗ PY because they remove one pairing dependence while introducing another, which vanishes asymptotically.The introduced dependence becomes negligible as n tends to infinity.
  • As the number of random variables grows, estimator convergence for some dependency measures may be arbitrarily slow.The discussion defers conditional dependence measures to a later section.
  • For non-i.i.d. data, kernel dependence measures require assumptions such as graphical-model structure or mixing conditions.Structured-HSIC is described for dependencies specified by undirected graphical models.

3.7 Learning on Distributional Data

Learning on distributional data represents each probability distribution by its kernel mean embedding and applies kernel methods to those representations. The framework supports nonparametric learning and generalization, while computational and information-loss trade-offs remain important.

  • Learning on Distributional Data: Distributional learning treats kernel mean embeddings as feature representations for probability measures.A positive definite kernel on distributions can be formed by integrating the base kernel over both distributions.
  • Learning on Distributional Data: Empirical distribution kernels replace integrals with finite sums, and finite approximations of embeddings can make learning more efficient.These approximations permit use of off-the-shelf learning algorithms.
  • Learning on Distributional Data: Kernel mean representations can be consistently estimated without parametric assumptions and are less prone to the curse of dimensionality than density-estimation approaches.The passage also notes fast computation as an advantage.
  • Learning on Distributional Data: The embedding map is linear in the distribution, so kernels based directly on mean embeddings induce only linear functions over probability space.This motivates studying richer nonlinear kernels on the space of probability measures.
  • Learning on Distributional Data: For compact input spaces, universal base kernels yield density of the induced RKHS in the relevant class of bounded continuous functionals.Injective embeddings can additionally yield density in all bounded continuous functions on the space of probability measures.
  • Distributional Risk Minimization: Distributional risk minimization has a representer theorem in terms of the kernel mean embeddings of the training distributions.Restricting distributions to Dirac measures recovers the classical representer theorem.
  • Distributional Risk Minimization: Optimizing empirical risk directly over distributions is computationally expensive, whereas optimizing over their means discards most high-level statistical information.Distributional risk minimization is described as an intermediate approach.
  • Distributional Risk Minimization: Support measure machines extend SVMs to distributions, including applications involving uncertain inputs, image bag-of-words data, and group anomaly detection.The framework also allows binary, real-valued, structured, or distributional outputs.

3.8 Recovering Information from Mean Embeddings

This section examines how to recover information or representative objects from kernel mean embeddings, including distributional pre-images, weighted statistics, and kernel herding. It also reviews theoretical guarantees and practical limitations of these approaches.

  • Distributional Pre-Image Problem: Distributional pre-image methods seek input-space objects corresponding to a specified kernel mean embedding, extending the classical pre-image problem from points to distributions.They can be formulated by selecting a parameterized distribution whose embedding approximates the given embedding; point-mass distributions reduce the problem to the classical setting.
  • Distributional Pre-Image Problem: Reduced-set methods approximate a finite signed measure with another signed measure supported on fewer points while preserving its kernel mean representation as closely as possible.The original embedding is represented using n input points, whereas the approximation uses m points with m ≪ n.
  • Recovering Distributional Information: Weighted evaluations of suitable functions can recover distributional information from a consistent kernel mean estimate, including moments, interval measures, and density estimates.The underlying principle is that RKHS inner products with the mean embedding equal expectations, while later work extends convergence guarantees to functions in suitable powers of the RKHS.
  • Recovering Distributional Information: The original theoretical guarantee for the proposed recovery result was invalidated by a mistake in Theorem 1, leaving that paper’s results without guarantees.Subsequent work provided guarantees for general RKHSs under assumptions placing the integrand in a suitable power of the RKHS, including misspecified settings where f ∉ H.
  • Kernel Herding: Kernel herding greedily minimizes squared embedding error and yields an O(1/T) expectation-error rate, compared with O(1/√T) for random samples.The faster rate is attributed to negative autocorrelation and remains guaranteed when herding is performed with some error.
  • Kernel Herding: Herding can be problematic in high dimensions, and its fast convergence is not guaranteed in infinite-dimensional Hilbert spaces.Convex-optimization interpretations, including Frank-Wolfe methods, are used to address these convergence concerns.

Distributions

The survey develops conditional mean embeddings as operators or regression estimators and reviews their nonparametric probabilistic operations, theoretical guarantees, and applications.

  • Regression Interpretation: The vector-valued regression interpretation enables cross-validation for parameter selection and supports sharper performance analysis.
  • Regression Interpretation: O(log(n)/n) minimax convergence rates are derived for conditional mean embedding estimators when G is finite dimensional.
  • Basic Operations: Conditional mean embeddings support sum, product, and Bayes’ rules without parametric assumptions about the respective distributions.
  • Kernel Bayes’ Rule: Kernel Bayes’ rule performs Bayesian inference nonparametrically by expressing likelihoods and priors through covariance operators and kernel means.
  • Kernel Bayes’ Rule: The posterior mean embedding estimator is consistent, with convergence in probability as n →∞, while reported rates can be slow.
  • Graphical Models and Probabilistic Inference: Embedding-based graphical-model inference avoids parametric assumptions and often avoids difficult high-dimensional density estimation.
  • Graphical Models and Probabilistic Inference: Kernel filtering has exact prediction and conditioning updates, but estimating conditional cross-covariance operators remains statistically difficult and computationally costly.

Relationships between KME and Other Methods

The survey connects kernel mean embeddings to density estimation, characteristic functions, classical kernel algorithms, distance-based statistics, Fourier optics, and probabilistic interpretations. These connections show shared representations and highlight both practical advantages and an unresolved Bayesian interpretation.

  • Kernel density estimation: Kernel density estimation’s L2 distance is a special case of biased maximum mean discrepancy between kernel mean embeddings.The RKHS formulation bypasses density estimation, which is often difficult in high dimensions.
  • Characteristic functions: Kernel mean embeddings and empirical characteristic functions are both integral transforms that represent distributions and support statistical testing.The empirical characteristic function has a one-to-one correspondence with distributions and supports consistent, asymptotically distribution-free independence testing.
  • Kernel algorithms: Classical classifiers, anomaly detectors, and centering operations can be reinterpreted through kernel mean embeddings of distributions.This reinterpretation connects kernel mean distances to empirical risk minimization and the large-margin principle in classification.
  • Distance-based statistics: Energy distance and distance covariance are equivalent to distances between distribution embeddings under specific kernels.The associated distance kernel is built from a negative-type semimetric.
  • Fourier optics: In Fourier optics, an incoherent imaging equation can be interpreted as a kernel mean embedding of an image-induced probability measure.Image intensities define the input and output, while the shift-invariant kernel represents the optical system’s point response.
  • Probabilistic interpretation: A Gaussian-process view interprets the kernel mean as an expected covariance of functions induced by the GP prior.The survey notes that a fully Bayesian interpretation of kernel mean embedding remains open.

Future Directions

The survey identifies kernel selection as a central unresolved issue for kernel mean embeddings. Although characteristic kernels preserve distributional information theoretically, finite samples make prior knowledge and parameter selection important.

  • Kernel choice: Choosing the right kernel remains a central open problem in kernel mean embedding.The issue includes selecting suitable parameter values for the chosen kernel.
  • Kernel choice: Characteristic kernels theoretically preserve all distributional information, but this guarantee may not hold empirically with finite samples.Consequently, prior knowledge becomes more relevant when choosing a kernel for an application.

116 Future Directions

The survey identifies open problems in extending kernel mean embeddings to richer data, high-dimensional settings, causal inference, and privacy-preserving analysis. It also motivates invariant distributional representations for reasoning across domains.

  • Infinite-dimensional distributions: Kernel mean embeddings for stochastic processes remain insufficiently developed for distributions over infinite-dimensional objects.The passage points to preliminary results and notes connections to Bayesian nonparametrics.
  • Scalability: Large-scale kernel learning is an important direction for developing kernel mean embedding algorithms that handle increasingly complex and large-scale data.The survey links this direction to the need for theoretical insight alongside successful modern learning applications.
  • High-dimensional regimes: High-dimensional analysis should clarify how ambient dimension affects kernel methods and kernel mean embedding applications.The survey notes recent studies of high-dimensional MMD and related tests while emphasizing that the underlying theory remains limited.
  • Causal inference: Kernel mean embeddings for causal inference remain challenging, especially when representing counterfactual distributions that cannot be directly observed.In the potential outcome framework, causal effects compare outcome distributions under control and treatment, but one of them is never observed in practice.
  • Privacy: Privacy-preserving kernel mean embedding requires determining whether comparable performance can be achieved without direct access to individual data points or distributional information.The survey highlights two-sample testing and dependency measures as applications that often require individual-level access.
  • Invariant representations: Invariant distributional representations are needed to handle statistical properties that remain independent of the input domain.The survey frames such representations as domain-general knowledge applicable across different domains.

Conclusions

The survey reviews kernel mean embeddings as a framework for extending RKHS methods from data points to probability measures. It covers marginal and conditional embeddings, their theory and applications, and open problems across machine learning and statistics.

  • Scope and outlook: The survey reviews existing work and recent advances while identifying challenging issues and open problems that may motivate new research directions.It is intended as a reference for researchers and graduate students interested in the theory and applications of kernel mean embeddings.
  • Marginal distributions: The survey presents kernel mean embedding as a framework for applying RKHS methods to probability measures.It situates the framework within a review of RKHSs, positive definite kernels, and Hilbert-Schmidt operators.
  • Marginal distributions: Marginal distribution embeddings receive a theoretical treatment alongside applications including two-sample testing, independence testing, anomaly detection, MCMC, predictive learning, and causal inference.The survey combines theoretical guarantees with a broad application review.
  • Conditional distributions: Conditional mean embeddings generalize the framework to conditional distributions and support non-parametric sum, product, and Bayes’ rules.They also admit a natural interpretation as solutions to vector-valued regression problems.
Loading 1605.09522v4…