|
|
| Line 1: |
Line 1: |
| 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).<ref name = "Smola2007">A. Smola, A. Gretton, L. Song, B. Schölkopf. (2007). [http://eprints.pascal-network.org/archive/00003987/01/SmoGreSonSch07.pdf A Hilbert Space Embedding for Distributions]. ''Algorithmic Learning Theory: 18th International Conference''. Springer: 13–31.</ref> 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 product]]s, distances, [[projection (linear algebra)|projections]], [[linear transformation]]s, and [[spectral theory|spectral analysis]].<ref name = "Song2013">L. Song, K. Fukumizu, F. Dinuzzo, A. Gretton (2013). [http://www.gatsby.ucl.ac.uk/~gretton/papers/SonFukGre13.pdf Kernel Embeddings of Conditional Distributions: A unified kernel framework for nonparametric inference in graphical models]. ''IEEE Signal Processing Magazine'' '''30''': 98–111.</ref> This [[machine learning|learning]] framework is very general and can be applied to distributions over any space <math>\Omega </math> on which a sensible [[kernel function]] (measuring similarity between elements of <math>\Omega </math>) may be defined. For example, various kernels have been proposed for learning from data which are: [[Vector (mathematics and physics)|vectors]] in <math>\mathbb{R}^d</math>, discrete classes/categories, [[string (computer science)|string]]s, [[graph (mathematics)|graph]]s/[[network theory|networks]], images, [[time series]], [[manifold]]s, [[dynamical systems]], and other structured objects.<ref>J. Shawe-Taylor, N. Christianini. (2004). ''Kernel Methods for Pattern Analysis''. Cambridge University Press, Cambridge, UK.</ref><ref>T. Hofmann, B. Schölkopf, A. Smola. (2008). [http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aos/1211819561 Kernel Methods in Machine Learning]. ''The Annals of Statistics'' '''36'''(3):1171–1220.</ref> The theory behind kernel embeddings of distributions has been primarily developed by [http://alex.smola.org/ Alex Smola], [http://www.cc.gatech.edu/~lsong/ Le Song ], [http://www.gatsby.ucl.ac.uk/~gretton/ Arthur Gretton], and [[Bernhard Schölkopf]].
| | Amusement Centre Manager Eure from Stevensville, has pastimes which include kite boarding, [http://ipsacert.com/?option=com_k2&view=itemlist&task=user&id=61934 top property developers in singapore] developers in singapore and crafts. Gets inspiration by making a journey to . |
| | |
| 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.<ref name = "SongThesis">L. Song. (2008) [http://www.cc.gatech.edu/~lsong/papers/lesong_thesis.pdf Learning via Hilbert Space Embedding of Distributions]. PhD Thesis, University of Sidney.</ref> Commonly, methods for modeling complex distributions rely on parametric assumptions that may be unfounded or computationally challenging (e.g. [[Mixture model#Gaussian mixture model|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 (probability theory)|characteristic function]] representation (via the [[Fourier transform]] of the distribution) break down in high-dimensional settings.<ref name = "Song2013" />
| |
| | |
| Methods based on the kernel embedding of distributions sidestep these problems and also possess the following advantages:<ref name = "SongThesis" />
| |
| # 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, while thanks to the [[kernel trick]], computations on the potentially infinite-dimensional RKHS can be implemented in practice as simple [[Gramian matrix|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 <math> X </math> denote a random variable with domain <math> \Omega </math> and distribution <math> P(X) </math>. Given a kernel <math> k </math> on <math> \Omega \times \Omega </math>, the [[Reproducing kernel Hilbert space#Moore-Aronszajn Theorem|Moore-Aronszajn Theorem]] asserts the existence of a RKHS <math> \mathcal{H} </math> (a [[Hilbert space]] of functions <math> f: \Omega \mapsto \mathbb{R} </math> equipped with inner products <math> \langle \cdot, \cdot \rangle_\mathcal{H} </math> and norms <math> || \cdot ||_\mathcal{H} </math>) in which the element <math> \ k(x,\cdot) </math> satisfies the reproducing property <math> \langle f, k(x,\cdot) \rangle_\mathcal{H} = f(x) \ \forall f \in \mathcal{H}, \forall x \in \Omega </math>. One may alternatively consider <math> \ k(x,\cdot)</math> an implicit feature mapping <math> \phi(x) </math> from <math> \Omega </math> to <math> \mathcal{H} </math> (which is therefore also called the feature space), so that <math>\ k(x, x') = \langle \phi(x), \phi(x')\rangle_\mathcal{H} </math> can be viewed as a measure of similarity between points <math> x, x' \in \Omega </math>. 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 <math> P(X) </math> in <math> \mathcal{H} </math> (also called the '''kernel mean''' or '''mean map''') is given by:<ref name = "Smola2007" />
| |
| | |
| :: <math>\mu_X := \mathbb{E}_X [k(X, \cdot) ] = \mathbb{E}_X [\phi(X) ] = \int_\Omega \phi(x) \ \mathrm{d}P(x) </math>
| |
| | |
| A kernel is ''characteristic'' if the embedding <math>\mu: \Omega \mapsto \mathcal{H} </math> is one-to-one. 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 <math>n</math> training examples <math> \{x_1, \dots, x_n\} </math> drawn [[Independent and identically distributed random variables|independently and identically distributed]] (i.i.d.) from <math> P </math>, the kernel embedding of <math> P </math> can be empirically estimated as
| |
| :: <math> \widehat{\mu}_X = \frac{1}{n} \sum_{i=1}^n \phi(x_i) </math>
| |
| | |
| ===Joint distribution embedding===
| |
| If <math> Y </math> denotes another random variable (for simplicity, assume the domain of <math> Y </math> is also <math> \Omega </math> with the same kernel <math> k </math> which satisfies <math> \langle \phi(x) \otimes \phi(y), \phi(x') \otimes \phi(y') \rangle = k(x,x') \otimes k(y,y')</math>), then the [[Joint probability distribution|joint distribution]] <math> P(X,Y) </math> can be mapped into a [[tensor product]] feature space <math> \mathcal{H} \otimes \mathcal{H} </math> via <ref name = "Song2013"/>
| |
| :: <math> \mathcal{C}_{XY} = \mathbb{E}_{XY} [\phi(X) \otimes \phi(Y)] = \int_{\Omega \times \Omega} \phi(x) \otimes \phi(y) \ \mathrm{d} P(x,y) </math>
| |
| | |
| By the equivalence between a [[tensor]] and a [[linear map]], this joint embedding may be interpreted as an uncentered [[cross-covariance]] operator <math> \mathcal{C}_{XY}: \mathcal{H} \mapsto \mathcal{H} </math> from which the cross-covariance of mean-zero functions <math>f,g \in \mathcal{H}</math> can be computed as <ref name = "SongCDE">L. Song, J. Huang, A. J. Smola, K. Fukumizu. (2009). [http://www.stanford.edu/~jhuang11/research/pubs/icml09/icml09.pdf Hilbert space embeddings of conditional distributions]. ''Proc. Int. Conf. Machine Learning''. Montreal, Canada: 961-968.</ref>
| |
| :: <math> \text{Cov}_{XY} (h(X), g(Y)) := \mathbb{E}_{XY} [f(X) g(Y)] = \langle f , \mathcal{C}_{XY} g \rangle_{\mathcal{H}} = \langle f \otimes g , \mathcal{C}_{XY} \rangle_{\mathcal{H} \otimes \mathcal{H}} </math>
| |
| | |
| Given <math>n</math> pairs of training examples <math>\{(x_1, y_1), \dots, (x_n, y_n)\} </math> drawn i.i.d. from <math> P </math>, we can also empirically estimate the joint distribution kernel embedding via
| |
| :: <math> \widehat{\mathcal{C}}_{XY} = \frac{1}{n} \sum_{i=1}^n \phi(x_i) \otimes \phi(y_i) </math>
| |
| | |
| ===Conditional distribution embedding===
| |
| Given a [[conditional distribution]] <math>P(Y \mid X) </math>, one can define the corresponding RKHS embedding as <ref name = "Song2013"/>
| |
| :: <math> \mu_{Y \mid x} = \mathbb{E}_{Y \mid x} [ \phi(Y) ] = \int_\Omega \phi(y) \ \mathrm{d}P(y \mid x) </math>
| |
| Note that the embedding of <math>P(Y \mid X) </math> thus defines a family of points in the RKHS indexed by the values <math>x</math> taken by conditioning variable <math>X </math>. By fixing <math>X</math> to a particular value, we obtain a single element in <math>\mathcal{H}</math>, and thus it is natural to define the operator
| |
| :: <math>\mathcal{C}_{Y \mid X}: \mathcal{H} \mapsto \mathcal{H}</math> as <math> \mathcal{C}_{Y \mid X} = \mathcal{C}_{YX} \mathcal{C}_{XX}^{-1} </math>
| |
| which given the feature mapping of <math>x </math> outputs the conditional embedding of <math>Y</math> given <math>X = x</math>. Assuming that for all <math> g \in \mathcal{H}: \ \mathbb{E}_{Y \mid X} [g(Y)] \in \mathcal{H} </math>, it can be shown that <ref name = "SongCDE" />
| |
| :: <math> \mu_{Y \mid x} = \mathcal{C}_{Y \mid X} \phi(x) </math>
| |
| This assumption is always true for finite domains with characteristic kernels, but may not necessarily hold for continuous domains.<ref name = "Song2013"/> Nevertheless, even in cases where the assumption fails, <math> \mathcal{C}_{Y \mid X} \phi(x) </math> may still be used to approximate the conditional kernel embedding <math> \mu_{Y \mid x} </math>, and in practice, the inversion operator is replaced with a regularized version of itself <math> (\mathcal{C}_{XX} + \lambda \mathbf{I})^{-1} </math> (where <math>\mathbf{I}</math> denotes the [[identity matrix]]).
| |
| | |
| Given training examples <math> \{(x_1, y_1),\dots, (x_n, y_n)\} </math>, the empirical kernel conditional embedding operator may be estimated as <ref name = "Song2013" />
| |
| :: <math>\widehat{C}_{Y\mid X} = \boldsymbol{\Phi} (\mathbf{K} + \lambda \mathbf{I})^{-1} \boldsymbol{\Upsilon}^T</math>
| |
| where <math>\boldsymbol{\Phi} = \left(\phi(y_i),\dots, (y_n)\right), \boldsymbol{\Upsilon} = \left(\phi(x_i),\dots, (x_n)\right) </math> are implicitly formed feature matrices, <math>\mathbf{K} =\boldsymbol{\Upsilon}^T \boldsymbol{\Upsilon} </math> is the Gram matrix for samples of <math>X</math>, and <math>\lambda</math> is a [[Regularization (mathematics)|regularization]] parameter needed to avoid [[overfitting]].
| |
| | |
| Thus, the empirical estimate of the kernel conditional embedding is given by a weighted sum of samples of <math>Y</math> in the feature space:
| |
| ::<math> \widehat{\mu}_{Y\mid x} = \sum_{i=1}^n \beta_i (x) \phi(y_i) = \boldsymbol{\Phi} \boldsymbol{\beta}(x) </math> where <math> \boldsymbol{\beta}(x) = (\mathbf{K} + \lambda \mathbf{I})^{-1} \mathbf{K}_x</math> and <math> \mathbf{K}_x = \left( k(x_1, x), \dots, k(x_n, x) \right)^T </math>
| |
| | |
| ==Properties==
| |
| | |
| * The expectation of any function <math> f </math> in the RKHS can be computed as an inner product with the kernel embedding:
| |
| :: <math> \mathbb{E}_X [f(X)] = \langle f, \mu_X \rangle_\mathcal{H} </math>
| |
| | |
| * In the presence of large sample sizes, manipulations of the <math>n \times n</math> 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.<ref name = "Song2013"/>
| |
| | |
| === Convergence of empirical kernel mean to the true distribution embedding ===
| |
| * If <math> k </math> is defined such that <math> f \in [0, 1] </math> for all <math> f \in \mathcal{H}</math> with <math> || f ||_\mathcal{H} \le 1 </math> (as is the case for the widely-used [[radial basis function]] kernels), then with probability at least <math>\ 1-\delta </math>:<ref name="SongThesis" /> <br> {{spaces|7}} <math> ||\mu_X - \widehat{\mu}_X ||_\mathcal{H} = \sup_{f \in \mathcal{B}(0,1)} \left| \mathbb{E}_X[f(X)] - \frac{1}{n} \sum_{i=1}^n f(x_i) \right| \le \frac{2}{n} \mathbb{E}_X \left[ \sqrt{\text{tr} K} \right] + \sqrt{\frac{\log (2/\delta)}{2n}} </math> <br> where <math> \mathcal{B}(0,1) </math> denotes the unit ball in <math> \mathcal{H} </math> and <math> \mathbf{K} </math> is the Gram matrix whose <math> i,j </math>th entry is <math> k(x_i, x_j) </math>.
| |
| * The rate of convergence (in RKHS norm) of the empirical kernel embedding to its distribution counterpart is <math> O(n^{-1/2}) </math> and does ''not'' depend on the dimension of <math> X </math>.
| |
| * 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 <math> O(n^{-1/2})</math> of the true kernel embedding based on a finite sample of size <math>n</math>.
| |
| * For the embedding of conditional distributions, the empirical estimate can be seen as a ''weighted'' average of feature mappings (where the weights <math>\beta_i(x) </math> 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 <math> O\left(n^{-1/4} \right) </math> if the regularization parameter <math> \lambda </math> is decreased as <math>O\left( n^{-1/2} \right) </math>, though faster rates of convergence may be achieved by placing additional assumptions on the joint distribution.<ref name="Song2013"/>
| |
| | |
| === Universal kernels ===
| |
| * Letting <math>C(\mathcal{X})</math> denote the space of [[Continuous function|continuous]] [[Bounded function|bounded]] functions on [[Compact space|compact]] domain <math>\mathcal{X}</math>, we call a kernel <math> k </math> ''universal'' if <math>k(x,\cdot)</math> is continuous for all <math>x</math> and the RKHS induced by <math>k</math> is [[Dense set|dense]] in <math>C(\mathcal{X})</math>.
| |
| | |
| * If <math>k</math> induces a strictly positive definite kernel matrix for any set of distinct points, then it is a universal kernel.<ref name = "SongThesis" /> For example, the widely-used Gaussian RBF kernel
| |
| :: <math> k(x,x') = \exp\left(-\frac{1}{2\sigma^2} ||x-x'||^2 \right) </math>
| |
| on compact subsets of <math>\mathbb{R}^d </math> is universal.
| |
| | |
| * If <math> k </math> is universal, then it is ''characteristic'', i.e. the kernel embedding is one-to-one.<ref>A. Gretton, K. Borgwardt, M. Rasch, B. Schölkopf, A. Smola. (2007). [http://www.gatsby.ucl.ac.uk/~gretton/papers/GreBorRasSchSmo07.pdf A kernel method for the two-sample-problem]. ''Advances in Neural Information Processing Systems'' '''19''', MIT Press, Cambridge, MA.</ref>
| |
| | |
| === Parameter selection for conditional distribution kernel embeddings ===
| |
| * The empirical kernel conditional distribution embedding operator <math>\widehat{\mathcal{C}}_{Y|X} </math> can alternatively be viewed as the solution of the following regularized least squares (function-valued) regression problem <ref>S. Grunewalder, G. Lever, L. Baldassarre, S. Patterson, A. Gretton, M. Pontil. (2012). [http://icml.cc/2012/papers/898.pdf Conditional mean embeddings as regressors]. ''Proc. Int. Conf. Machine Learning'': 1823–1830.</ref>
| |
| :: <math> \min_{\mathcal{C}: \mathcal{H} \mapsto \mathcal{H}} \sum_{i=1}^n || \phi(y_i) - \mathcal{C} \phi(x_i) ||_\mathcal{H}^2 + \lambda ||\mathcal{C} ||_{HS}^2 </math> where <math> ||\cdot ||_{HS} </math> is the [[Hilbert–Schmidt operator|Hilbert-Schmidt norm]].
| |
| * One can thus select the regularization parameter <math> \lambda </math> by performing [[cross-validation (statistics)|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.<ref name = "Song2013" /><ref name = "SongCDE" /> The following notation is adopted:
| |
| * <math> P(X,Y) = </math> joint distribution over random variables <math> X, Y </math>
| |
| * <math> P(X) = \int_\Omega P(X, \mathrm{d}y) = </math> marginal distribution of <math> X </math>; <math> P(Y) = </math> marginal distribution of <math> Y </math>
| |
| * <math> P(Y \mid X) = \frac{P(X,Y)}{P(X)} = </math> conditional distribution of <math> Y </math> given <math> X </math> with corresponding conditional embedding operator <math> \mathcal{C}_{Y \mid X}</math>
| |
| * <math> \pi(Y) = </math> prior distribution over <math> Y </math>
| |
| * <math> Q </math> is used to distinguish distributions which incorporate the prior from distributions <math> P </math> which do not rely on the prior
| |
| | |
| In practice, all embeddings are empirically estimated from data <math> \{(x_1,y_1),\dots, (x_n, y_n)\} </math> and it assumed that a set of samples <math>\{\widetilde{y}_1, \dots, \widetilde{y}_{\widetilde{n}} \} </math> may be used to estimate the kernel embedding of the prior distribution <math> \pi(Y) </math>.
| |
| | |
| === Kernel sum rule ===
| |
| In probability theory, the marginal distribution of <math> X </math> can be computed by integrating out <math> Y </math> from the joint density (including the prior distribution on <math> Y </math>)
| |
| :: <math> Q(X) = \int_\Omega P(X \mid Y) \mathrm{d} \pi(Y) </math>
| |
| The analog of this rule in the kernel embedding framework states that <math> \mu_X^\pi </math>, the RKHS embedding of <math> Q(X)</math>, can be computed via
| |
| :: <math> \mu_X^\pi = \mathbb{E}_{Y} [\mathcal{C}_{X \mid Y} \phi(Y) ] = \mathcal{C}_{X\mid Y} \mathbb{E}_{Y} [\phi(Y)] = \mathcal{C}_{X\mid Y} \mu_Y^\pi </math> where <math>\mu_Y^\pi</math> is the kernel embedding of <math> \pi(Y) </math>
| |
| In practical implementations, the kernel sum rule takes the following form
| |
| :: <math> \widehat{\mu}_X^\pi = \widehat{\mathcal{C}}_{X \mid Y} \widehat{\mu}_Y^\pi = \boldsymbol{\Upsilon} (G + \lambda \mathbf{I})^{-1} \widetilde{\boldsymbol{G}} \boldsymbol{\alpha} </math>
| |
| where <math>\mu_Y^\pi = \sum_{i=1}^{\widetilde{n}} \alpha_i \phi(\widetilde{y}_i)</math> is the empirical kernel embedding of the prior distribution, <math>\boldsymbol{\alpha} = (\alpha_1, \dots, \alpha_{\widetilde{n}} )^T</math>, <math>\boldsymbol{\Upsilon} = \left(\phi(x_1), \dots, \phi(x_n) \right) </math>, and <math>\mathbf{G}, \widetilde{\mathbf{G}} </math> are Gram matrices with entries <math>\mathbf{G}_{ij} = k(y_i, y_j), \widetilde{\mathbf{G}}_{ij} = k(y_i, \widetilde{y}_j) </math> respectively.
| |
| | |
| === Kernel chain rule ===
| |
| In probability theory, a joint distribution can be factorized into a product between conditional and marginal distributions
| |
| :: <math> Q(X,Y) = P(X \mid Y) \pi(Y) </math>
| |
| The analog of this rule in the kernel embedding framework states that <math> \mathcal{C}_{XY}^\pi </math>, the joint embedding of <math> Q(X,Y) </math>, can be factorized as a composition of conditional embedding operator with the auto-covariance operator associated with <math> \pi(Y) </math>
| |
| :: <math> \mathcal{C}_{XY}^\pi = \mathcal{C}_{X \mid Y} \mathcal{C}_{YY}^\pi </math> where <math> \mathcal{C}_{XY}^\pi = \mathbb{E}_{XY} [\phi(X) \otimes \phi(Y) ] </math> and <math> \mathcal{C}_{YY}^\pi = \mathbb{E}_Y [\phi(Y) \otimes \phi(Y)] </math>
| |
| In practical implementations, the kernel chain rule takes the following form
| |
| :: <math> \widehat{\mathcal{C}}_{XY}^\pi = \widehat{\mathcal{C}}_{X \mid Y} \widehat{\mathcal{C}}_{YY}^\pi = \boldsymbol{\Upsilon} (\mathbf{G} + \lambda \mathbf{I})^{-1} \widetilde{\mathbf{G}} \text{diag}(\boldsymbol{\alpha}) \boldsymbol{\Phi}^T </math>
| |
| | |
| === Kernel Bayes' rule ===
| |
| In probability theory, a posterior distribution can be expressed in terms of a prior distribution and a likelihood function as
| |
| :: <math> Q(Y \mid x) = \frac{P(x \mid Y) \pi(Y)}{Q(x)} </math> where <math> Q(x) = \int_\Omega P(x \mid y) \mathrm{d} \pi(y) </math>
| |
| The analog of this rule in the kernel embedding framework expresses the kernel embedding of the conditional distribution in terms of conditional embedding operators which are modified by the prior distribution
| |
| :: <math> \mu_{Y \mid x}^\pi = \mathcal{C}_{Y \mid X}^\pi \phi(x) = \mathcal{C}_{YX}^\pi ( \mathcal{C}_{XX}^\pi )^{-1} \phi(x) </math> where from the chain rule: <math> \mathcal{C}_{YX}^\pi = \left( \mathcal{C}_{X \mid Y} \mathcal{C}_{YY}^\pi \right)^T </math>.
| |
| In practical implementations, the kernel Bayes' rule takes the following form
| |
| :: <math> \widehat{\mu}_{Y \mid x}^\pi = \widehat{\mathcal{C}}_{YX}^\pi \left( (\widehat{\mathcal{C}}_{XX})^2 + \widetilde{\lambda} \mathbf{I} \right)^{-1} \widehat{\mathcal{C}}_{XX}^\pi \phi(x) = \widetilde{\boldsymbol{\Phi}} \boldsymbol{\Lambda}^T \left( (\mathbf{D} \mathbf{K})^2 + \widetilde{\lambda} \mathbf{I} \right)^{-1} \mathbf{K} \mathbf{D} \mathbf{K}_x </math>
| |
| where <math> \boldsymbol{\Lambda} = \left(\mathbf{G} + \widetilde{\lambda} \mathbf{I} \right)^{-1} \widetilde{\mathbf{G}} \text{diag}(\boldsymbol{\alpha}), \mathbf{D} = \text{diag}\left(\left(\mathbf{G} + \widetilde{\lambda} \mathbf{I} \right)^{-1} \widetilde{\mathbf{G}} \boldsymbol{\alpha} \right) </math>.
| |
| Two regularization parameters are used in this framework: <math>\lambda </math> for the estimation of <math> \widehat{\mathcal{C}}_{YX}^\pi, \widehat{\mathcal{C}}_{XX}^\pi = \boldsymbol{\Upsilon} \mathbf{D} \boldsymbol{\Upsilon}^T </math> and <math>\widetilde{\lambda} </math> for the estimation of the final conditional embedding operator <math> \widehat{\mathcal{C}}_{Y \mid X}^\pi = \widehat{\mathcal{C}}_{YX}^\pi \left( (\widehat{\mathcal{C}}_{XX}^\pi )^2 + \widetilde{\lambda} \mathbf{I} \right)^{-1} \widehat{\mathcal{C}}_{XX}^\pi </math>. The latter regularization is done on square of <math> \widehat{\mathcal{C}}_{XX}^\pi </math> because <math> D </math> may not be [[Positive-definite matrix|positive definite]].
| |
| | |
| ==Applications==
| |
| | |
| === Measuring distance between distributions ===
| |
| The '''maximum mean discrepancy''' (MMD) is a distance-measure between distributions <math>P(X)</math> and <math>Q(Y)</math> which is defined as the squared distance between their embeddings in the RKHS <ref name = "SongThesis" />
| |
| :: <math>\text{MMD}(P,Q) = \left| \left| \mu_X - \mu_Y \right| \right|_{\mathcal{H}}^2 </math>
| |
| While most distance-measures between distributions such as the widely-used [[Kullback–Leibler divergence]] either require density estimation (either parametrically or nonparametrically) or space partitioning/bias correction strategies,<ref name = "SongThesis" /> the MMD is easily estimated as an empirical mean which is concentrated around the true value of the MMD. The characterization of this distance as the ''maximum mean discrepancy'' refers to the fact that computing the MMD is equivalent to finding the RKHS function that maximizes the difference in expectations between the two probability distributions
| |
| :: <math>\text{MMD}(P,Q) = \sup_{||f ||_\mathcal{H} \le 1} \left( \mathbb{E}_X[f(X)] - \mathbb{E}_Y[f(Y)] \right) </math>
| |
| | |
| === Kernel two sample test ===
| |
| Given ''n'' training examples from <math>P(X)</math> and ''m'' samples from <math>Q(Y)</math>, one can formulate a test statistic based on the empirical estimate of the MMD
| |
| :: <math>\widehat{\text{MMD}}(P,Q) = \left| \left| \frac{1}{n}\sum_{i=1}^n \phi(x_i) - \frac{1}{m}\sum_{i=1}^m \phi(y_i) \right| \right|_{\mathcal{H}}^2 = \frac{1}{nm} \sum_{i=1}^n\sum_{j=1}^m \left[ k(x_i, x_j) + k(y_i, y_j) - 2 k(x_i, y_j) \right] </math>
| |
| to obtain a '''two-sample test''' <ref>A. Gretton, K. Borgwardt, M. Rasch, B. Schölkopf, A. Smola. (2012). [http://jmlr.org/papers/volume13/gretton12a/gretton12a.pdf A kernel two-sample test]. ''Journal of Machine Learning Research'', '''13''': 723-773.</ref> of the null hypothesis that both samples stem from the same distribution (i.e. <math>P = Q</math>) against the broad alternative <math>P \neq Q</math>.
| |
| | |
| === Density estimation via kernel embeddings ===
| |
| Although learning algorithms in the kernel embedding framework circumvent the need for intermediate density estimation, one may nonetheless use the empirical embedding to perform density estimation based on ''n'' samples drawn from an underlying distribution <math>P_X^*</math>. This can be done by solving the following optimization problem <ref name ="SongThesis"/><ref>M. Dudík, S. J. Phillips, R. E. Schapire. (2007). [http://classes.soe.ucsc.edu/cmps242/Winter08/lect/15/maxent_genreg_jmlr.pdf Maximum Entropy Distribution Estimation with Generalized Regularization and an Application to Species Distribution Modeling]. ''Journal of Machine Learning Research'', '''8''': 1217-1260.</ref>
| |
| :: <math> \max_{P_X} H(P_X) </math> subject to <math> ||\widehat{\mu}_X - \mu_X[P_X] ||_\mathcal{H} \le \epsilon </math>
| |
| where the maximization is done over the entire space of distributions on <math> \Omega </math>. Here, <math> \mu_X[P_X] </math> is the kernel embedding of the proposed density <math> P_X </math> and <math>H</math> is an entropy-like quantity (e.g. [[Entropy (information theory)|Entropy]], [[Kullback–Leibler divergence|KL divergence]], [[Bregman divergence]]). The distribution which solves this optimization may be interpreted as a compromise between fitting the empirical kernel means of the samples well, while still allocating a substantial portion of the probability mass to all regions of the probability space (much of which may not be represented in the training examples). In practice, a good approximate solution of the difficult optimization may be found by restricting the space of candidate densities to a mixture of ''M'' candidate distributions with regularized mixing proportions. Connections between the ideas underlying [[Gaussian process]]es and [[conditional random fields]] may be drawn with the estimation of conditional probability distributions in this fashion, if one views the feature mappings associated with the kernel as sufficient statistics in generalized (possibly infinite-dimensional) [[exponential family|exponential families]].<ref name = "SongThesis"/>
| |
| | |
| === Measuring dependence of random variables ===
| |
| A measure of the statistical dependence between random variables <math> X </math> and <math> Y </math> (from any domains on which sensible kernels can be defined) can be formulated based on the Hilbert–Schmidt Independence Criterion <ref>A. Gretton, O. Bousquet, A. Smola, B. Schölkopf. (2005). [http://www.gatsby.ucl.ac.uk/~gretton/papers/GreBouSmoSch05.pdf Measuring statistical dependence with Hilbert–Schmidt norms]. ''Proc. Intl. Conf. on Algorithmic Learning Theory'': 63–78.</ref>
| |
| :: <math> \text{HSIC}(X, Y) = \left| \left| \mathcal{C}_{XY} - \mu_X \otimes \mu_Y \right| \right|_{\mathcal{H} \otimes \mathcal{H}}^2 </math>
| |
| and can be used as a principled replacement for [[mutual information]], [[Pearson correlation]] or any other dependence measure used in learning algorithms. Most notably, HSIC can detect arbitrary dependencies (when a characteristic kernel is used in the embeddings, HSIC is zero if and only if the variables are [[independence (probability theory)|independent]]), and can be used to measure dependence between different types of data (e.g. images and text captions). Given ''n'' i.i.d. samples of each random variable, a simple parameter-free [[Bias of an estimator|unbiased]] estimator of HSIC which exhibits [[Concentration of measure|concentration]] about the true value can be computed in <math>O(n(d_f^2 +d_g^2))</math> time,<ref name = "SongThesis"/> where the Gram matrices of the two datasets are approximated using <math>\mathbf{A} \mathbf{A}^T, \mathbf{B} \mathbf{B}^T </math> with <math> \mathbf{A} \in \mathbb{R}^{n \times d_f}, \mathbf{B} \in \mathbb{R}^{n \times d_g}</math>. The desirable properties of HSIC have led to the formulation of numerous algorithms which utilize this dependence measure for a variety of common machine learning tasks such as: [[feature selection]] (BAHSIC <ref>L. Song, A. Smola , A. Gretton, K. Borgwardt, J. Bedo. (2007). [http://www.machinelearning.org/proceedings/icml2007/papers/244.pdf Supervised feature selection via dependence estimation]. ''Proc. Intl. Conf. Machine Learning'', Omnipress: 823–830.</ref>), [[Cluster analysis|clustering]] (CLUHSIC <ref>L. Song, A. Smola, A. Gretton, K. Borgwardt. (2007). [http://machinelearning.wustl.edu/mlpapers/paper_files/icml2007_SongSGB07.pdf A dependence maximization view of clustering]. ''Proc. Intl. Conf. Machine Learning''. Omnipress: 815–822.</ref>), and [[dimensionality reduction]] (MUHSIC <ref>L. Song, A. Smola, K. Borgwardt, A. Gretton. (2007). [http://machinelearning.wustl.edu/mlpapers/paper_files/NIPS2007_492.pdf Colored maximum variance unfolding]. ''Neural Information Processing Systems''.</ref>).
| |
| | |
| === Kernel belief propagation ===
| |
| [[Belief propagation]] is a fundamental algorithm for inference in [[graphical models]] in which nodes repeatedly pass and receive messages corresponding to the evaluation of conditional expectations. In the kernel embedding framework, the messages may be represented as RKHS functions and the conditional distribution embeddings can be applied to efficiently compute message updates. Given ''n'' samples of random variables represented by nodes in a [[Markov Random Field]], the incoming message to node ''t'' from node ''u'' can be expressed as <math> m_{ut}(\cdot) = \sum_{i=1}^n \beta_{ut}^i \phi(x_t^i) </math> if it assumed to lie in the RKHS. The '''kernel belief propagation update''' message from ''t'' to node ''s'' is then given by <ref name = "Song2013"/>
| |
| :: <math> \widehat{m}_{ts} = \left( \odot_{u \in N(t) \backslash s} \mathbf{K}_t \boldsymbol{\beta}_{ut} \right)^T (\mathbf{K}_s + \lambda \mathbf{I})^{-1} \boldsymbol{\Upsilon}_s^T \phi(x_s)</math>
| |
| where <math> \odot </math> denotes the element-wise vector product, <math>N(t) \backslash s </math> is the set of nodes connected to ''t'' excluding node ''s'', <math> \boldsymbol{\beta}_{ut} = \left(\beta_{ut}^1, \dots, \beta_{ut}^n \right) </math>, <math>\mathbf{K}_t, \mathbf{K}_s </math> are the Gram matrices of the samples from variables <math>X_t, X_s </math>, respectively, and <math>\boldsymbol{\Upsilon}_s = \left(\phi(x_s^1),\dots, \phi(x_s^n)\right)</math> is the feature matrix for the samples from <math>X_s</math>.
| |
| | |
| Thus, if the incoming messages to node ''t'' are linear combinations of feature mapped samples from <math> X_t </math>, then the outgoing message from this node is also a linear combination of feature mapped samples from <math> X_s </math>. This RKHS function representation of message-passing updates therefore produces an efficient belief propagation algorithm in which the [[Markov Random Field#Clique factorization|potentials]] are nonparametric functions inferred from the data so that arbitrary statistical relationships may be modeled.<ref name = "Song2013"/>
| |
| | |
| === Nonparametric filtering in hidden Markov models ===
| |
| In the [[hidden Markov model]] (HMM), two key quantities of interest are the transition probabilities between hidden states <math> P(S^t \mid S^{t-1})</math> and the emission probabilities <math> P(O^t \mid S^t) </math> for observations. Using the kernel conditional distribution embedding framework, these quantities may be expressed in terms of samples from the HMM. A serious limitation of the embedding methods in this domain is the need for training samples containing hidden states, as otherwise inference with arbitrary distributions in the HMM is not possible.
| |
| | |
| One common use of HMMs is [[Hidden Markov Model#Filtering|filtering]] in which the goal is to estimate posterior distribution over the hidden state <math> s^{t}</math> at time step ''t'' given a history of previous observations <math>h^t = (o^1, \dots, o^t)</math> from the system. In filtering, a '''belief state''' <math> P(S^{t+1} \mid h^{t+1}) </math> is recursively maintained via a prediction step (where updates <math>P(S^{t+1} \mid h^t) = \mathbb{E}_{S^t \mid h^t} [P(S^{t+1} \mid S^t)] </math> are computed by marginalizing out the previous hidden state) followed by a conditioning step (where updates <math> P(S^{t+1} \mid h^t, o^{t+1}) \propto P(o^{t+1} \mid S^{t+1}) P(S^{t+1} \mid h^t) </math> are computed by applying Bayes' rule to condition on a new observation).<ref name = "Song2013"/> The RKHS embedding of the belief state at time ''t+1'' can be recursively expressed as
| |
| :: <math> \mu_{S^{t+1} \mid h^{t+1}} = \mathcal{C}_{S^{t+1} O^{t+1}}^\pi \left(\mathcal{C}_{O^{t+1} O^{t+1}}^\pi \right)^{-1} \phi(o^{t+1}) </math>
| |
| by computing the embeddings of the prediction step via the [[#Kernel Sum Rule|kernel sum rule]] and the embedding of the conditioning step via [[#Kernel Bayes' Rule|kernel Bayes' rule]]. Assuming a training sample <math>(\widetilde{s}^1, \dots, \widetilde{s}^T, \widetilde{o}^1, \dots, \widetilde{o}^T) </math> is given, one can in practice estimate <math> \widehat{\mu}_{S^{t+1} \mid h^{t+1}} = \sum_{i=1}^T \alpha_i^t \phi(\widetilde{s}^t) </math> and filtering with kernel embeddings is thus implemented recursively using the following updates for the weights <math>\boldsymbol{\alpha} = (\alpha_1, \dots, \alpha_T)</math> <ref name = "Song2013"/>
| |
| :: <math> \mathbf{D}^{t+1} = \text{diag}\left((G+\lambda \mathbf{I})^{-1} \widetilde{G} \boldsymbol{\alpha}^t \right)</math>
| |
| :: <math> \boldsymbol{\alpha}^{t+1} = \mathbf{D}^{t+1} \mathbf{K} \left( (\mathbf{D}^{t+1} K)^2 + \widetilde{\lambda} \mathbf{I} \right)^{-1} \mathbf{D}^{t+1} \mathbf{K}_{o^{t+1}} </math>
| |
| where <math> \mathbf{G}, \mathbf{K} </math> denote the Gram matrices of <math>\widetilde{s}^1, \dots, \widetilde{s}^T </math> and <math> \widetilde{o}^1, \dots, \widetilde{o}^T</math> respectively, <math> \widetilde{\mathbf{G}} </math> is a transfer Gram matrix defined as <math> \widetilde{\mathbf{G}}_{ij} = k(\widetilde{s}_i, \widetilde{s}_{j+1}) </math>, and <math> \mathbf{K}_{o^{t+1}} = (k(\widetilde{o}^1, o^{t+1}), \dots, k(\widetilde{o}^T, o^{t+1}))^T </math>.
| |
| | |
| === Support measure machines ===
| |
| The '''support measure machine''' (SMM) is a generalization of the [[support vector machine]] (SVM) in which the training examples are probability distributions paired with labels <math> \{P_i, y_i\}_{i=1}^n, \ y_i \in \{+1, -1\} </math>.<ref name = "SMM">K. Muandet, K. Fukumizu, F. Dinuzzo, B. Schölkopf. (2012). [http://books.nips.cc/papers/files/nips25/NIPS2012_0015.pdf Learning from Distributions via Support Measure Machines]. ''Advances in Neural Information Processing Systems'': 10–18.</ref>
| |
| SMMs solve the standard SVM [[Support vector machine#Dual form|dual optimization problem]] using the following '''expected kernel'''
| |
| :: <math> K\left(P(X), Q(Z)\right) = \langle \mu_X , \mu_Z \rangle_\mathcal{H} = \mathbb{E}_{XZ} [k(x,z)] </math>
| |
| which is computable in closed form for many common specific distributions <math> P_i </math> (such as the Gaussian distribution) combined with popular embedding kernels <math>k</math> (e.g. the Gaussian kernel or polynomial kernel), or can be accurately empirically estimated from i.i.d. samples <math>\{x_i\}_{i=1}^n \sim P(X), \{z_j\}_{j=1}^m \sim Q(Z) </math> via
| |
| ::<math> \widehat{K} \left(X, Z\right) = \frac{1}{n m} \sum_{i=1}^n \sum_{j=1}^m k(x_i, z_j) </math>
| |
| Under certain choices of the embedding kernel <math>k</math>, the SMM applied to training examples <math>\{P_i, y_i\}_{i=1}^n </math> is equivalent to a SVM trained on samples <math>\{x_i, y_i\}_{i=1}^n</math>, and thus the SMM can be viewed as a ''flexible'' SVM in which a different data-dependent kernel (specified by the assumed form of the distribution <math> P_i </math>) may be placed on each training point.<ref name = "SMM" />
| |
| | |
| === Domain adaptation under covariate, target, and conditional shift ===
| |
| The goal of '''domain adaptation''' is the formulation of learning algorithms which generalize well when the training and test data have different distributions. Given training examples <math> \{ (x_i^{tr}, y_i^{tr}) \}_{i=1}^n </math> and a test set <math> \{ (x_j^{te}, y_j^{te}) \}_{j=1}^m </math> where the <math> y_j^{te} </math> are unknown, three types of differences are commonly assumed between the distribution of the training examples <math> P^{tr}(X,Y)</math> and the test distribution <math> P^{te}(X,Y)</math>:<ref name = "DA">K. Zhang, B. Schölkopf, K. Muandet, Z. Wang. (2013). [http://jmlr.org/proceedings/papers/v28/zhang13d.pdf Domain adaptation under target and conditional shift]. ''Journal of Machine Learning Research, '''28'''(3): 819–827.</ref><ref name = "CovS">A. Gretton, A. Smola, J. Huang, M. Schmittfull, K. Borgwardt, B. Schölkopf. (2008). Covariate shift and local learning by distribution matching. ''In J. Quinonero-Candela, M. Sugiyama, A. Schwaighofer, N. Lawrence (eds.). Dataset shift in machine learning'', MIT Press, Cambridge, MA: 131–160.</ref>
| |
| # '''Covariate Shift''' in which the marginal distribution of the covariates changes across domains: <math> P^{tr}(X) \neq P^{te}(X)</math>
| |
| # '''Target Shift''' in which the marginal distribution of the outputs changes across domains: <math> P^{tr}(Y) \neq P^{te}(Y)</math>
| |
| # '''Conditional Shift''' in which <math> P(Y)</math> remains the same across domains, but the conditional distributions differ: <math> P^{tr}(X \mid Y) \neq P^{te}(X \mid Y)</math>. In general, the presence of conditional shift leads to an [[Well-posed problem|ill-posed]] problem, and the additional assumption that <math> P(X \mid Y) </math> changes only under [[Location parameter|location]]-[[Scale parameter|scale]] (LS) transformations on <math> X </math> is commonly imposed to make the problem tractable.
| |
| | |
| By utilizing the kernel embedding of marginal and conditional distributions, practical approaches to deal with the presence of these types of differences between training and test domains can be formulated. Covariate shift may be accounted for by reweighting examples via estimates of the ratio <math>P^{te}(X) / P^{tr}(X) </math> obtained directly from the kernel embeddings of the marginal distributions of <math>X</math> in each domain without any need for explicit estimation of the distributions.<ref name = "CovS"/> Target shift, which cannot be similarly dealt with since no samples from <math>Y</math> are available in the test domain, is accounted for by weighting training examples using the vector <math>\boldsymbol{\beta}^*(\mathbf{y}^{tr}) </math> which solves the following optimization problem (where in practice, empirical approximations must be used) <ref name = "DA"/>
| |
| :: <math> \min_{\boldsymbol{\beta}(y)} \left|\left|\mathcal{C}_{{(X \mid Y)}^{tr}} \mathbb{E}_{Y^{tr}} [ \boldsymbol{\beta}(y) \phi(y)] - \mu_{X^{te}} \right|\right|_\mathcal{H}^2 </math> subject to <math> \boldsymbol{\beta}(y) \ge 0, \mathbb{E}_{Y^{tr}} [ \boldsymbol{\beta}(y)] = 1 </math>
| |
| | |
| To deal with location scale conditional shift, one can perform a LS transformation of the training points to obtain new transformed training data <math> \mathbf{X}^{new} = \mathbf{X}^{tr} \odot \mathbf{W} + \mathbf{B} </math> (where <math>\odot </math> denotes the element-wise vector product). To ensure similar distributions between the new transformed training samples and the test data, <math>\mathbf{W},\mathbf{B}</math> are estimated by minimizing the following empirical kernel embedding distance <ref name =
| |
| "DA"/>
| |
| :: <math> \left| \left| \widehat{\mu}_{X^{new}} - \widehat{\mu}_{X^{te}} \right| \right|_{\mathcal{H}}^2 = \left| \left| \widehat{\mathcal{C}}_{(X \mid Y)^{new}} \widehat{\mu}_{Y^{tr}} - \widehat{\mu}_{X^{te}} \right| \right|_{\mathcal{H}}^2 </math>
| |
| In general, the kernel embedding methods for dealing with LS conditional shift and target shift may be combined to find a reweighted transformation of the training data which mimics the test distribution, and these methods may perform well even in the presence of conditional shifts other than location-scale changes.<ref name = "DA"/>
| |
| | |
| === Domain generalization via invariant feature representation ===
| |
| Given ''N'' sets of training examples sampled i.i.d. from distributions <math>P^{(1)}(X,Y), P^{(2)}(X,Y), \dots, P^{(N)}(X,Y)</math>, the goal of '''domain generalization''' is to formulate learning algorithms which perform well on test examples sampled from a previously unseen domain <math>P^*(X,Y)</math> where no data from the test domain is available at training time. If conditional distributions <math>P(Y \mid X)</math> are assumed to be relatively similar across all domains, then a learner capable of domain generalization must estimate a functional relationship between the variables which is robust to changes in the marginals <math>P(X)</math>. Based on kernel embeddings of these distributions, Domain Invariant Component Analysis (DICA) is a method which determines the transformation of the training data that minimizes the difference between marginal distributions while preserving a common conditional distribution shared between all training domains.<ref name = "DICA">K. Muandet, D. Balduzzi, B. Schölkopf. (2013).[http://jmlr.org/proceedings/papers/v28/muandet13.pdf Domain Generalization Via Invariant Feature Representation]. ''30th International Conference on Machine Learning''.</ref> DICA thus extracts ''invariants'', features that transfer across domains, and may be viewed as a generalization of many popular dimension-reduction methods such as [[kernel principal component analysis]], transfer component analysis, and covariance operator inverse regression.<ref name = "DICA"/>
| |
|
| |
| Defining a probability distribution <math>\mathcal{P}</math> on the RKHS <math>\mathcal{H}</math> with <math>\mathcal{P}(\mu_{X^{(i)}Y^{(i)}}) = 1/N \text{ for } i=1,\dots, N</math>, DICA measures dissimilarity between domains via '''distributional variance''' which is computed as
| |
| :: <math>V_\mathcal{H} (\mathcal{P}) = \frac{1}{N} \text{tr}(\mathbf{G}) - \frac{1}{N^2} \sum_{i,j=1}^N \mathbf{G}_{ij} </math> where <math>\mathbf{G}_{ij} = \langle \mu_{X^{(i)}}, \mu_{X^{(j)}} \rangle_\mathcal{H} </math>
| |
| so <math>\mathbf{G}</math> is a <math>N \times N</math> Gram matrix over the distributions from which the training data are sampled. Finding an [[Orthogonal matrix|orthogonal transform]] onto a low-dimensional [[Linear subspace|subspace]] ''B'' (in the feature space) which minimizes the distributional variance, DICA simultaneously ensures that ''B'' aligns with the [[Basis function|bases]] of a '''central subspace''' ''C'' for which <math>Y</math> becomes independent of <math>X</math> given <math>C^T X</math> across all domains. In the absence of target values <math>Y</math>, an unsupervised version of DICA may be formulated which finds a low-dimensional subspace that minimizes distributional variance while simultaneously maximizing the variance of <math>X</math> (in the feature space) across all domains (rather than preserving a central subspace).<ref name = "DICA"/>
| |
| | |
| == Example ==
| |
| In this simple example, which is taken from Song et al.,<ref name = "Song2013"/> <math>X, Y</math> are assumed to be [[Probability distribution#Discrete probability distribution|discrete random variables]] which take values in the set <math>\{1,\dots,K\} </math> and the kernel is chosen to be the [[Kronecker delta]] function, so <math>k(x,x') = \delta(x,x')</math>. The feature map corresponding to this kernel is the [[standard basis]] vector <math>\phi(x) = \mathbf{e}_x</math>. The kernel embeddings of such a distributions are thus vectors of marginal probabilities while the embeddings of joint distributions in this setting are <math>K\times K </math> matrices specifying joint probability tables, and the explicit form of these embeddings is
| |
| :: <math>\mu_X = \mathbb{E}_X [\mathbf{e}_x] = \left(
| |
| \begin{array}{c}
| |
| P(X=1) \\
| |
| \vdots \\
| |
| P(X=K) \\
| |
| \end{array}
| |
| \right) </math>
| |
| :: <math> \mathcal{C}_{XY} = \mathbb{E}_{XY} [\mathbf{e}_X \otimes e_Y] = \bigg( P(X=s, Y=t) \bigg)_{s,t \in \{1,\dots,K\}} </math>
| |
| | |
| The conditional distribution embedding operator <math> \mathcal{C}_{Y\mid X} = \mathcal{C}_{YX} \mathcal{C}_{XX}^{-1} </math> is in this setting a conditional probability table
| |
| :: <math> \mathcal{C}_{Y \mid X} = \bigg( P(Y=s \mid X=t) \bigg)_{s,t \in \{1,\dots,K\}} </math>
| |
| : and <math> \mathcal{C}_{XX} =\left(
| |
| \begin{array}{c c c}
| |
| P(X=1) & \dots & 0 \\
| |
| \vdots & \ddots & \vdots \\
| |
| 0 & \dots & P(X=K) \\
| |
| \end{array}
| |
| \right)
| |
| </math>
| |
| Thus, the embeddings of the conditional distribution under a fixed value of <math>X</math> may be computed as
| |
| :: <math> \mu_{Y \mid x} = \mathcal{C}_{Y \mid X} \phi(x) = \left(
| |
| \begin{array}{c}
| |
| P(Y=1 \mid X = x) \\
| |
| \vdots \\
| |
| P(Y=K \mid X = x) \\
| |
| \end{array}
| |
| \right) </math>
| |
| | |
| In this discrete-valued setting with the Kronecker delta kernel, the [[#Rules of probability as operations in the RKHS|kernel sum rule]] becomes
| |
| :: <math> \underbrace{ \left(
| |
| \begin{array}{c}
| |
| Q(X=1) \\
| |
| \vdots \\
| |
| P(X = N) \\
| |
| \end{array}
| |
| \right) }_{\mu_Y^\pi} = \underbrace{ \left( \begin{array}{c} \\ P(X=s \mid Y=t) \\ \\ \end{array} \right) }_{ \mathcal{C}_{X\mid Y} } \underbrace{ \left(
| |
| \begin{array}{c}
| |
| \pi(Y=1) \\
| |
| \vdots \\
| |
| pi(Y = N) \\
| |
| \end{array}
| |
| \right) }_{ \mu_Y^\pi} </math>
| |
| | |
| The [[#Rules of probability as operations in the RKHS|kernel chain rule]] in this case is given by
| |
| :: <math> \underbrace{ \left( \begin{array}{c} \\ Q(X=s,Y=t) \\ \\ \end{array} \right) }_{\mathcal{C}_{XY}^\pi} =
| |
| \underbrace{ \left( \begin{array}{c} \\ P(X=s \mid Y=t) \\ \\ \end{array} \right) }_{\mathcal{C}_{X \mid Y}}
| |
| \underbrace{ \left(
| |
| \begin{array}{c c c}
| |
| \pi(Y=1) & \dots & 0 \\
| |
| \vdots & \ddots & \vdots \\
| |
| 0 & \dots & \pi(Y=K) \\
| |
| \end{array}
| |
| \right) }_{\mathcal{C}_{YY}^\pi} </math>
| |
| | |
| ==References==
| |
| {{reflist}}
| |
| | |
| [[Category:Machine learning| ]]
| |
| [[Category:Statistics]]
| |