In machine learning, the kernel embedding of distributions (also called the kernel mean or mean map) comprises a class of nonparametric methods in which a probability distribution is represented as an element of a reproducing kernel Hilbert space (RKHS).A. Smola, A. Gretton, L. Song, B. Schölkopf. (2007). A Hilbert Space Embedding for Distributions . Algorithmic Learning Theory: 18th International Conference. Springer: 13–31. A generalization of the individual data-point feature mapping done in classical kernel methods, the embedding of distributions into infinite-dimensional feature spaces can preserve all of the statistical features of arbitrary distributions, while allowing one to compare and manipulate distributions using Hilbert space operations such as inner products, distances, projections, linear transformations, and spectral analysis.L. Song, K. Fukumizu, F. Dinuzzo, A. Gretton (2013). Kernel Embeddings of Conditional Distributions: A unified kernel framework for nonparametric inference in graphical models. IEEE Signal Processing Magazine 30: 98–111. This learning framework is very general and can be applied to distributions over any space on which a sensible kernel function (measuring similarity between elements of ) may be defined. For example, various kernels have been proposed for learning from data which are: vectors in , discrete classes/categories, strings, graphs/networks, images, time series, manifolds, dynamical systems, and other structured objects.J. Shawe-Taylor, N. Christianini. (2004). Kernel Methods for Pattern Analysis. Cambridge University Press, Cambridge, UK.T. Hofmann, B. Schölkopf, A. Smola. (2008). Kernel Methods in Machine Learning. The Annals of Statistics 36(3):1171–1220. The theory behind kernel embeddings of distributions has been primarily developed by Alex Smola, Le Song, Arthur Gretton, and Bernhard Schölkopf. A review of recent works on kernel embedding of distributions can be found in.
The analysis of distributions is fundamental in machine learning and statistics, and many algorithms in these fields rely on information theoretic approaches such as entropy, mutual information, or Kullback–Leibler divergence. However, to estimate these quantities, one must first either perform density estimation, or employ sophisticated space-partitioning/bias-correction strategies which are typically infeasible for high-dimensional data.L. Song. (2008) Learning via Hilbert Space Embedding of Distributions. PhD Thesis, University of Sydney. Commonly, methods for modeling complex distributions rely on parametric assumptions that may be unfounded or computationally challenging (e.g. Gaussian mixture models), while nonparametric methods like kernel density estimation (Note: the smoothing kernels in this context have a different interpretation than the kernels discussed here) or characteristic function representation (via the Fourier transform of the distribution) break down in high-dimensional settings.
Methods based on the kernel embedding of distributions sidestep these problems and also possess the following advantages: Data may be modeled without restrictive assumptions about the form of the distributions and relationships between variables Intermediate density estimation is not needed Practitioners may specify the properties of a distribution most relevant for their problem (incorporating prior knowledge via choice of the kernel) If a characteristic kernel is used, then the embedding can uniquely preserve all information about a distribution, thanks to the kernel trick, while computations on the potentially infinite-dimensional RKHS can be implemented in practice as simple Gram matrix operations Dimensionality-independent rates of convergence for the empirical kernel mean (estimated using samples from the distribution) to the kernel embedding of the true underlying distribution can be proven. Learning algorithms based on this framework exhibit good generalization ability and finite sample convergence, while often being simpler and more effective than information theoretic methods Thus, learning via the kernel embedding of distributions offers a principled drop-in replacement for information theoretic approaches and is a framework which not only subsumes many popular methods in machine learning and statistics as special cases, but also can lead to entirely new learning algorithms.
Definitions
Let denote a random variable with domain and distribution . Given a symmetric, positive-definite kernel the Moore–Aronszajn theorem asserts the existence of a unique RKHS on (a Hilbert space of functions equipped with an inner product and a norm ) for which is a reproducing kernel, i.e., in which the element satisfies the reproducing property
One may alternatively consider as an implicit feature mapping (which is therefore also called the feature space), so that can be viewed as a measure of similarity between points While the similarity measure is linear in the feature space, it may be highly nonlinear in the original space depending on the choice of kernel.
Kernel embedding The kernel embedding of the distribution in (also called the kernel mean or mean map) is given by:
If allows a square integrable density , then , where is the Hilbert–Schmidt integral operator. A kernel is characteristic if the mean embedding is injective.K. Fukumizu, A. Gretton, X. Sun, and B. Schölkopf (2008). Kernel measures of conditional independence. Advances in Neural Information Processing Systems 20, MIT Press, Cambridge, MA. Each distribution can thus be uniquely represented in the RKHS and all statistical features of distributions are preserved by the kernel embedding if a characteristic kernel is used.
Empirical kernel embedding Given training examples drawn independently and identically distributed (i.i.d.) from the kernel embedding of can be empirically estimated as
Joint distribution embedding If denotes another random variable (for simplicity, assume the co-domain of is also with the same kernel which satisfies ), then the joint distribution can be mapped into a tensor product feature space via
By the equivalence between a tensor and a linear map, this joint embedding may be interpreted as an uncentered cross-covariance operator from which the cross-covariance of functions can be computed as L. Song, J. Huang, A. J. Smola, K. Fukumizu. (2009).Hilbert space embeddings of conditional distributions . Proc. Int. Conf. Machine Learning. Montreal, Canada: 961–968.
Given pairs of training examples drawn i.i.d. from , we can also empirically estimate the joint distribution kernel embedding via
Conditional distribution embedding Given a conditional distribution one can define the corresponding RKHS embedding as
Note that the embedding of thus defines a family of points in the RKHS indexed by the values taken by conditioning variable . By fixing to a particular value, we obtain a single element in , and thus it is natural to define the operator
which given the feature mapping of outputs the conditional embedding of given Assuming that for all it can be shown that
This assumption is always true for finite domains with characteristic kernels, but may not necessarily hold for continuous domains. Nevertheless, even in cases where the assumption fails, may still be used to approximate the conditional kernel embedding and in practice, the inversion operator is replaced with a regularized version of itself (where denotes the identity matrix).
Given training examples the empirical kernel conditional embedding operator may be estimated as
where are implicitly formed feature matrices, is the Gram matrix for samples of , and is a regularization parameter needed to avoid overfitting.
Thus, the empirical estimate of the kernel conditional embedding is given by a weighted sum of samples of in the feature space:
where and
Properties
The expectation of any function in the RKHS can be computed as an inner product with the kernel embedding:
In the presence of large sample sizes, manipulations of the Gram matrix may be computationally demanding. Through use of a low-rank approximation of the Gram matrix (such as the incomplete Cholesky factorization), running time and memory requirements of kernel-embedding-based learning algorithms can be drastically reduced without suffering much loss in approximation accuracy.
Convergence of empirical kernel mean to the true distribution embedding
If is defined such that takes values in for all with (as is the case for the widely used radial basis function kernels), then with probability at least :
where denotes the unit ball in and is the Gram matrix with
The rate of convergence (in RKHS norm) of the empirical kernel embedding to its distribution counterpart is and does not depend on the dimension of . Statistics based on kernel embeddings thus avoid the curse of dimensionality, and though the true underlying distribution is unknown in practice, one can (with high probability) obtain an approximation within of the true kernel embedding based on a finite sample of size . For the embedding of conditional distributions, the empirical estimate can be seen as a weighted average of feature mappings (where the weights depend on the value of the conditioning variable and capture the effect of the conditioning on the kernel embedding). In this case, the empirical estimate converges to the conditional distribution RKHS embedding with rate if the regularization parameter is decreased as though faster rates of convergence may be achieved by placing additional assumptions on the joint distribution.
Universal kernels Let be a compact metric space and the set of continuous functions. The reproducing kernel is called universal if and only if the RKHS of is dense in , i.e., for any and all there exists an such that .* All universal kernels defined on a compact space are characteristic kernels but the converse is not always true. Let be a continuous translation invariant kernel with . Then Bochner's theorem guarantees the existence of a unique finite Borel measure (called the spectral measure) on such that
For to be universal it suffices that the continuous part of in its unique Lebesgue decomposition is non-zero. Furthermore, if
then is the spectral density of frequencies in and is the Fourier transform of . If the support of is all of , then is a characteristic kernel as well.
If induces a strictly positive definite kernel matrix for any set of distinct points, then it is a universal kernel. For example, the widely used Gaussian RBF kernel
on compact subsets of is universal.
Parameter selection for conditional distribution kernel embeddings
The empirical kernel conditional distribution embedding operator can alternatively be viewed as the solution of the following regularized least squares (function-valued) regression problem S. Grunewalder, G. Lever, L. Baldassarre, S. Patterson, A. Gretton, M. Pontil. (2012). Conditional mean embeddings as regressors. Proc. Int. Conf. Machine Learning: 1823–1830.
where is the Hilbert–Schmidt norm.
One can thus select the regularization parameter by performing cross-validation based on the squared loss function of the regression problem.
Rules of probability as operations in the RKHS
This section illustrates how basic probabilistic rules may be reformulated as (multi)linear algebraic operations in the kernel embedding framework and is primarily based on the work of Song et al. The following notation is adopted:
joint distribution over random variables marginal distribution of ; marginal distribution of
conditional distribution of given with corresponding conditional embedding operator prior distribution over is used to distinguish distributions which incorporate the prior from distributions which do not rely on the prior