Kernel Mean Embedding relationship to regular kernel functions

Question

I am struggling to understand kernel mean embeddings and how it relates to typical kernel functions.

Review of Kernel Basics:

Basically, a kernel function maps points (or vectors) from one feature space to another space. The idea is that this new representation of data facilitates analysis in some way. For example, it is now easier to classify the data in this new feature space than its original feature space. Other examples include Kernel PCA, SVMs, etc.

Let $\mathcal{X}$ be a non-empty set. A kernel function $k: \mathcal{X} \times \mathcal{X} \rightarrow\mathbb{R}$ exists if there is a Hilbert space, $\mathcal{H}$, with corresponding map $\phi:\mathcal{X} \rightarrow\mathcal{H}$ such that:

$$k(x,y) = \langle\phi(x), \phi(y) \rangle_{\mathcal{H}}$$

where $x,y \in \mathcal{X} $ (just two elements in this set). This can also be interpreted as the distance between $x$ and $y$ in this new feature space, $\mathcal{H}$. Note usually $k$ is selected to make $\mathcal{H}$ a reproducing kernel Hilbert space (RKHS).

Kernel Mean Embeddings:

Kernel embeddings are a sort of generalization of the basic kernel transformation shown above. It uses the same premise ($\mathcal{X}$, $\mathcal{H}$) & tools (kernel functions) but instead of mapping vectors, they map distributions to a new feature space.

From Wikipedia, let $X$ denote a random variable with domain $ \Omega $ and distribution $P$. Given a kernel $k$ on $\Omega \times \Omega$, the kernel embedding of the distribution $P$ in $\mathcal {H}$ (also called the kernel mean or mean map) is given by:

$$\mu_{X}:=\mathbb{E}[k(X, \cdot)]=\mathbb{E}[\phi(X)]=\int_{\Omega} \phi(x) \mathrm{d} P(x)$$

Given $n$ training examples ${\{x_{1},\ldots ,x_{n}\}}$ drawn independently and identically distributed (i.i.d.) from $P$, the kernel embedding of $P$ can be empirically estimated as: $$\hat{\mu}_{X}=\frac{1}{n} \sum_{i=1}^{n} \phi\left(x_{i}\right)$$

My questions are:

1. Is there some kind of analogy one could use to help visualize what is going when a kernel mean embedding is applied?
2. Why are mapping distributions called "embeddings" when mapping basic vectors aren't called "embeddings"?
3. How are we mapping a distribution if in the end, we just average a kernel mapping of sampled points? Doesn't seem to be a representation of the distribution in a new feature space, just it's average in a new feature space.
4. Why do we need to map into a RKHS? Can't it just be a regular Hilbert space?
5. Is $\mu_X$ (or $\hat{\mu}_{X}$) a function or a real number?
6. How is a kernel mean embedding different from a parzen window (KDE)?

Answer 1

To simplify matters, I'll assume the kernel $k$ is bounded. Otherwise for technical reasons (basically to guarantee the expectation in the definition of the kernel mean map exists), we need to restrict attention to only probability distributions satisfying $$\mathbb{E}_{X\sim P} \sqrt{k(X,X)} <\infty$$

Let $\mathrm{Prob}(\mathcal{X})$ denote the set of probability measures on $\mathcal{X}$. You can think of $\mathcal{X}$ as being essentially a subset of $\mathrm{Prob}(\mathcal{X})$, by identifying each point with the measure that assigns probability $1$ to that point. The main result here is that for a bounded kernel, the map $\phi: \mathcal{X}\rightarrow\mathcal{H}$ can always be extended to a map $\tilde{\phi}: \mathrm{Prob}(\mathcal{X})\rightarrow\mathcal{H}$ which maps probability distributions to vectors in $\mathcal{H}$. Similarly a bounded kernel on $\mathcal{X}$ can always be extended to a kernel on $\mathrm{Prob}(\mathcal{X})$. To answer the second question, since the map $\phi$ is often called an embedding (even if it isn't injective), it is common to call $\tilde{\phi}$ the kernel mean embedding. Note that it is $\tilde{\phi}$ that is called an embedding and not $\mu_X = \tilde{\phi}(P)$.

There is no need to work with an RKHS instead of an explicit Hilbert space. However, it is sometimes simpler to do so. Additionally, it isn't significantly less general. To study a map $\phi:\mathcal{X}\rightarrow \mathcal{H}$, we don't need to think about the entire space $\mathcal{H}$. It suffices instead to work with the smallest closed subspace containing the image of $\phi$. Since it follows from the proof of the Moore–Aronszajn theorem that this is isometrically isomorphic to the RKHS with kernel $k(x,y)=\langle \phi(x),\phi(y)\rangle$, we may as well work with an RKHS instead of a general Hilbert space.

There are two natural ways of constructing $\mu_X = \tilde{\phi}(P)$ for a random variable $X\sim P$. The first is to consider $\mathbb{E}\phi(X)$ as in your post. This runs in to the issue that we are taking the expectation of a Hilbert space valued variable, which is a bit more technical to define than for real valued variables. However, in the case of an RKHS, the elements of $\mathcal{H}$ are just functions and it turns out you get the right result by taking expectations pointwise. In other words, $\mu_X$ is the function given by $$\mu_X(t) = \mathbb{E}\phi(X)(t)$$ This expression involves only real valued expectations so is somewhat simpler.

There is an alternate (more technical) approach, which is similar to how the kernel associated to an RKHS $\mathcal{H}$ is usually constructed. For $x\in\mathcal{X}$, define the evaluation functional $ev_x:\mathcal{H}\rightarrow \mathbb{R}$ by $ev_x(f)=f(x)$. Part of the definition of an RKHS is that this functional is bounded so we can apply the Riesz representation theorem to get some $k_x\in X$ such that for every f $$f(X) = \langle k_x, f \rangle$$ This property is called the reproducing property. The map $\phi$ given by $\phi(x)=k_x$ is the canonical embedding into the RKHS. The kernel is then constructed as $k(x,y)=\langle k_x,k_y\rangle$. You can mimic this for the expectation functional $f\mapsto \mathbb{E}_{X\sim P} f(X)$. A simple argument involving Cauchy-Schwartz and the condition $\mathbb{E}_{X\sim P} \sqrt{k(X,X)} <\infty$ shows this is bounded, so we can apply the Riesz representation theorem to get some function $\mu_X$ such that $$\mathbb{E}\phi(X) = \langle \mu_X, f\rangle$$ We can see explicitly that this gives the same answer as the other construction as follows $$\mu_X(t) = \langle \mu_X, k_t\rangle = \mathbb{E} k_t(X) = \mathbb{E} \langle k_X, k_t\rangle = \mathbb{E} k_X(t)= \mathbb{E} \phi(X)(t)$$

The distribution of a random variable $X$ is entirely determined by the expectations of functions of $X$. This is still true if you restrict to a suitably large class of functions - many reproducing kernel Hilbert spaces work. You can think of $\mu_X$ as a representation of the distribution of $X$ since for any $f$ in the RKHS, it determines $$\langle f(X), \mu_X\rangle=\mathbb{E}f(X)$$

I think the similiarity to kernel density estimation is coincidental. To define the kernel mean embedding, the kernel does not need to have integral equal to $1$ or to be centered near $x=y$. In fact, we can define the kernel mean embedding on more general spaces than $\mathbb{R}^n$ (e.g. strings of text) including some where notions of integrals and pdfs aren't really defined. On the other hand, the kernels in kernel density estimation don't need to be positive semidefinite.