45
$\begingroup$

I have two data sets (source and target data) which follow different distributions. I am using MMD - that is a non-parametric distribution distance - to compute marginal distribution between the source and target data.

source data, Xs

target data, Xt

adaptation Matrix A

**Projected data, Zs = A'Xs and Zt = A'Xt

*MMD => Distance(P(Xs),P(Xt)) = | mean(A'Xs) - mean(A'Xt) |

That means: the distribution's distance between the source and target data in the original space is equivalent to the distance between means of projected source and target data in the embedded space.

I have a question about the concept of MMD.

In the MMD formula, why with computing distance in the latent space we could measure the distribution's distance in the original space?

Thanks

$\endgroup$
1
  • 1
    $\begingroup$ You haven't actually asked a question yet: you have only told us you get confused! $\endgroup$
    – whuber
    Commented Apr 28, 2017 at 15:53

4 Answers 4

112
$\begingroup$

It might help to give slightly more of an overview of MMD.$\DeclareMathOperator{\E}{\mathbb E}\newcommand{\R}{\mathbb R}\newcommand{\X}{\mathcal X}\newcommand{\h}{\mathcal H}\newcommand{\F}{\mathcal F}\DeclareMathOperator{\MMD}{MMD}$

In general, MMD is defined by the idea of representing distances between distributions as distances between mean embeddings of features. That is, say we have distributions $P$ and $Q$ over a set $\X$.

The MMD is defined based on a feature map $\varphi : \X \to \h$, where $\h$ is some Hilbert space; this corresponds to a kernel (as in SVMs, not KDE) by $k(x, y) = \langle \varphi(x), \varphi(y) \rangle_\h$. In general, the MMD is $$ \MMD(P, Q) = \big\lVert \E_{X \sim P}[ \varphi(X) ] - \E_{Y \sim Q}[ \varphi(Y) ] \big\rVert_\h .$$

As one example, we might have $\X = \h = \R^d$ and $\varphi(x) = x$, corresponding to a linear kernel. In that case: \begin{align} \MMD(P, Q) &= \bigl\lVert \E_{X \sim P}[ \varphi(X) ] - \E_{Y \sim Q}[ \varphi(Y) ] \bigr\rVert_\h \\&= \bigl\lVert \E_{X \sim P}[ X ] - \E_{Y \sim Q}[ Y ] \bigr\rVert_{\R^d} \\&= \bigl\lVert \mu_P - \mu_Q \bigr\rVert_{\R^d} ,\end{align} so this MMD is just the distance between the means of the two distributions. Matching distributions like this will match their means, though they might differ in their variance or in other ways.

Your case is slightly different: we have $\mathcal X = \mathbb R^d$ and $\mathcal H = \mathbb R^p$, with $\varphi(x) = A' x$, where $A$ is a $d \times p$ matrix. So we have \begin{align} \MMD(P, Q) &= \bigl\lVert \E_{X \sim P}[ \varphi(X) ] - \E_{Y \sim Q}[ \varphi(Y) ] \bigr\rVert_\h \\&= \bigl\lVert \E_{X \sim P}[ A' X ] - \E_{Y \sim Q}[ A' Y ] \bigr\rVert_{\R^p} \\&= \bigl\lVert A' \E_{X \sim P}[ X ] - A' \E_{Y \sim Q}[ Y ] \bigr\rVert_{\R^p} \\&= \bigl\lVert A'( \mu_P - \mu_Q ) \bigr\rVert_{\R^p} .\end{align} This MMD is the difference between two different projections of the mean. If $p < d$ or the mapping $A'$ otherwise isn't invertible, then this MMD is weaker than the previous one: it doesn't distinguish between some distributions that the previous one does.

You can also construct stronger distances. For example, if $\X = \R$ and you use $\varphi(x) = (x, x^2)$ (giving a particular quadratic kernel), then the MMD becomes $\sqrt{(\E X - \E Y)^2 + (\E X^2 - \E Y^2)^2}$, and can distinguish not only distributions with different means but with different variances as well.

And you can get much stronger than that: for general choices of kernel, you can use the kernel trick to compute the MMD: \begin{align} \MMD^2(P, Q) &= \bigl\lVert \E_{X \sim P} \varphi(X) - \E_{Y \sim Q} \varphi(Y) \bigr\rVert_\h^2 \\&= \langle \E_{X \sim P} \varphi(X), \E_{X' \sim P} \varphi(X') \rangle_\h + \langle \E_{Y \sim Q} \varphi(Y), \E_{Y' \sim Q} \varphi(Y') \rangle_\h - 2 \langle \E_{X \sim P} \varphi(X), \E_{Y \sim Q} \varphi(Y) \rangle_\h \\&= \E_{X, X' \sim P} k(X, X') + \E_{Y, Y' \sim Q} k(Y, Y') - 2 \E_{X \sim P, Y \sim Q} k(X, Y) .\end{align} It's then straightforward to estimate this with samples, for any kernel function $k$ -- even ones where $\varphi$ is infinite-dimensional, like the Gaussian kernel (also called "squared exponential" or "exponentiated quadratic") $k(x, y) = \exp\left( -\frac{1}{2\sigma^2} \lVert x - y \rVert^2 \right)$.

If your choice of $k$ is "characteristic," then the MMD becomes a proper metric on distributions: it's zero if and only if the two distributions are the same. (This is unlike when you use, say, a linear kernel, where two distributions with the same mean have zero linear-kernel MMD.) If you've heard of a "universal" kernel, those are characteristic, but there are a few kernels that are characteristic but not universal.


Here's an explanation of the name, which is also useful for understanding the MMD.

For any kernel $k : \X \times \X \to \R$, there exists a feature map $\varphi : \X \to \mathcal F$, where $\mathcal F$ is a special Hilbert space called the reproducing kernel Hilbert space (RKHS) corresponding to $k$. This is a space of functions, $f : \X \to \R$. These spaces satisfy a special key condition, called the reproducing property: $\langle f, \varphi(x) \rangle_\F = f(x)$ for any $f \in \F$.

The simplest example is the linear kernel $k(x, y) = x \cdot y$. This can be "implemented" with $\h = \R^d$ and $\varphi(x) = x$. But the RKHS is instead the space of linear functions $f_x(t) = x \cdot t$, and $\varphi(x) = f_x$. The reproducing property is $\langle f_w, \varphi(x) \rangle_\h = \langle w, x \rangle_{\R^d}$.

In more complex settings, like a Gaussian kernel, $f$ is a much more complicated function, but the reproducing property still holds.

Now, we can give an alternative characterization of the MMD: \begin{align} \MMD(P, Q) &= \lVert \E_{X \sim P}[\varphi(X)] - \E_{Y \sim Q}[\varphi(Y)] \rVert_\h \\&= \sup_{f \in \h : \lVert f \rVert_\h \le 1} \langle f, \E_{X \sim P}[\varphi(X)] - \E_{Y \sim Q}[\varphi(Y)] \rangle_\h \\&= \sup_{f \in \h : \lVert f \rVert_\h \le 1} \langle f, \E_{X \sim P}[\varphi(X)] \rangle_\h - \langle f, \E_{Y \sim Q}[\varphi(Y)] \rangle_\h \\&= \sup_{f \in \h : \lVert f \rVert_\h \le 1} \E_{X \sim P}[\langle f, \varphi(X)\rangle_\h] - \E_{Y \sim Q}[\langle f, \varphi(Y) \rangle_\h] \\&= \sup_{f \in \h : \lVert f \rVert_\h \le 1} \E_{X \sim P}[f(X)] - \E_{Y \sim Q}[f(Y)] .\end{align} The second line is a general fact about norms in Hilbert spaces that follows immediately from Cauchy-Schwarz: $\sup_{f : \lVert f \rVert \le 1} \langle f, g \rangle_\h = \lVert g \rVert$ is achieved by $f = g / \lVert g \rVert$.

The fourth line depends on a technical condition known as Bochner integrability, but is true e.g. for bounded kernels or distributions with bounded support.

Then, at the end we use the reproducing property.

This last line is why it's called the "maximum mean discrepancy" – it's the maximum, over test functions $f$ in the unit ball of $\h$, of the mean difference between the two distributions. This is also a special case of an integral probability metric.

$\endgroup$
7
  • $\begingroup$ Thanks for your explanation, it becomes more clear for me; Still I did not get this concept, In the beginning, you said: "MMD is defined by the idea of representing distances between distributions as distances between mean embeddings of features." Why this idea comes true? $\endgroup$
    – Mahsa
    Commented May 5, 2017 at 11:31
  • $\begingroup$ "MMD is defined by the idea of representing distances between distributions as distances between mean embeddings of features." Why this idea comes true?Is it related to RKHS space? $\endgroup$
    – Mahsa
    Commented May 5, 2017 at 11:38
  • 2
    $\begingroup$ It's just a definition: you can compare distributions by comparing their means. Or, you can compare distributions by comparing some transformation of their means; or by comparing their means and variances; or by comparing the mean of any other feature map, including one in an RKHS. $\endgroup$
    – Danica
    Commented May 5, 2017 at 11:39
  • $\begingroup$ Thanks for your response; I am going to read more about RKHS feature map; I was wondering, why is MMD defined distance in RKHS feature map? I mean, what is the benefit of RKHS in MMD distance definition? $\endgroup$
    – Mahsa
    Commented May 7, 2017 at 19:16
  • 1
    $\begingroup$ @danmackinlay Yeah, my phrasing here is imprecise, I should fix it. In general, if $k(x, y) = \langle \phi(x), \phi(y) \rangle_{\mathcal H}$ for any Hilbert space (not necessarily an RKHS), then (a) the MMD is defined and (b) there exists some RKHS of functions $\mathcal X \to \mathbb R$ with reproducing kernel $k$. The definition of the MMD in terms of mean embeddings doesn't care if it's an RKHS or not; they'll be equivalent. The definition in terms of means of $f(X)$, $f(Y)$ does. Strength of the MMD depends on whether $k$ is "characteristic." $\endgroup$
    – Danica
    Commented Mar 4 at 19:15
14
$\begingroup$

Here is how I interpretted MMD. Two distributions are similar if their moments are similar. By applying a kernel, I can transform the variable such that all moments (first, second, third etc.) are computed. In the latent space I can compute the difference between the moments and average it. This gives a measure of the similarity/dissimilarity between the datasets.

$\endgroup$
1
  • $\begingroup$ Note that for a Gaussian kernel, this is not exactly what you get. The feature space has a $e^{-\gamma x^2}$ coefficient in front of all the elements in the vector. I.e., check stats.stackexchange.com/a/69767/117705 $\endgroup$ Commented Feb 22, 2023 at 8:28
1
$\begingroup$

What we know today as Maximum Mean Discrepancy is actually derived from the following Integral Probability Metric [A]:

If p and q are two distributions and $\mathcal{F}$ is a class of real valued bounded bounded measurable functions, then the metric is defined as, $$D(p, q, \mathcal{F}) = \sup_{f \in \mathcal{F}} \left|\mathbb{E}_p[f(x)] - \mathbb{E}_q[f(x)]\right|$$

If you select the function class $\mathcal{F} = \{f \;\;|\;\; \|f\|_{\mathcal{H}} \leq 1\}$ where $\mathcal{H}$ represents the reproducing kernel Hilbert space with reproducing kernel $k$, it can be shown that the above metric reduces to [D]: $$D(p, q, \mathcal{F}) = \left|\mathbb{E}_p[k(x, \cdot)] - \mathbb{E}_q[k(x, \cdot)]\right|$$

Thus, it so happens, that computing the differences of the mean in the kernel space gives you the distance between the distribution computed over a certain function class. Several other metrics can actually be derived this way, by selecting certain classes of functions and analyzing the original integral probability metric under that function class e.g. Total Variation Distance, Wasserstein Distance [B].

Now, coming to the description you gave in the original post, I am a little worried about how you are going about computing the MMD. Even for the original MMD measure, the kernel had to satisfy some properties [C]. However, all you seem to be doing is multiplying your features with some matrix and computing distance in that space. Which doesn't really mean anything unless the projection matrices are special. So, it would be good to go through the linked articles and ensure that what you are doing abides by requirements of a kernel mean embedding.

[A] Integral Probability Metrics and their Generating Classes of Functions, Muller, 1997

[B] On Integral Probability Metrics, ϕ-divergences and Binary Classification, Sriperumbudur et. al, 2009

[C] Universality, Characteristic Kernels and RKHS Embedding of Measures, Sriperumbudur et. al, 2012 (PDF)

[D] Kernel Mean Embedding of Distributions: A Review and Beyond, Muandet et. al, 2016

$\endgroup$
1
  • $\begingroup$ There are no "requirements" for the kernel of an MMD, other than it being a positive-definite kernel. OP's MMD is absolutely an MMD. It is not, however, a characteristic kernel, which makes the distance a semimetric instead of a real metric (it can be zero between distributions that are different). $\endgroup$
    – Danica
    Commented Mar 8 at 21:38
0
$\begingroup$

For the Gaussian kernel $K({\mathbf x}, {\mathbf y})=e^{-||{\mathbf x}-{\mathbf y}||^2/4\sigma^2}$ on ${\mathbb R}^n$, the MMD satisfies:

${\rm MMD}(P,Q) \propto \sup\limits_{f\in L_2({\mathbb R}^n), ||f||_{L_2}\leq 1} {\mathbb E}_{X\sim P, \epsilon\sim N(0, \sigma^2I_n)} f(X+\epsilon)-{\mathbb E}_{Y\sim Q, \epsilon'\sim N(0, \sigma^2I_n)} f(Y+\epsilon')$

This representation helps to understand what MMD is about: the critic's function is from the unit ball in $L_2$ and it is applied to random vectors distributed according to ``smoothed'' $P$ and $Q$.

For the translation-invariant kernel, $K({\mathbf x}, {\mathbf y}) = k({\mathbf x} - {\mathbf y})$, one can represent MMD as:

${\rm MMD}(P,Q) \propto \sup\limits_{f\in L_2({\mathbb R}^n), ||f||_{L_2}\leq 1} {\mathbb E}_{X\sim P, \epsilon\sim E} f(X+\epsilon)-{\mathbb E}_{Y\sim Q, \epsilon'\sim E} f(Y+\epsilon')$ (1)

where $E({\mathbf x}) = \frac{F({\mathbf x})}{||F||_{L_1}}$ where $F=\mathcal{F}\big\{\sqrt{\mathcal{F}^{-1}[k]}\big\}$ and $\mathcal{F}$ denotes the Fourier transform.

Let us show why the formula (1) holds ($P$ and $Q$ are smooth pdfs, $\ast$ denotes convolution):

$ \begin{align} {\rm MMD}(P,Q)^2 = {\mathbb E}_{X, X' \sim P} k(X - X') + {\mathbb E}_{Y, Y' \sim Q} k(Y- Y') - 2 {\mathbb E}_{X \sim P, Y \sim Q} k(X- Y) = \\ \langle P, k\ast P\rangle_{L_2}+\langle Q, k\ast Q\rangle_{L_2} - 2 \langle P, k\ast Q\rangle_{L_2} \propto \\ \langle F\ast P, F\ast P\rangle_{L_2}+\langle F\ast Q, F\ast Q\rangle_{L_2} - 2 \langle F\ast P, F\ast Q\rangle_{L_2} = \\ ||F\ast P - F\ast Q||^2_{L_2} \end{align} $

Therefore,

$ \begin{align} {\rm MMD}(P,Q) = ||F\ast P - F\ast Q||_{L_2} = \\ \sup\limits_{f\in L_2({\mathbb R}^n), ||f||_{L_2}\leq 1} \langle f, F\ast P - F\ast Q\rangle_{L_2} = \sup\limits_{f\in L_2({\mathbb R}^n), ||f||_{L_2}\leq 1} \langle f, F\ast P\rangle - \langle f, F\ast Q\rangle_{L_2} = \\ \sup\limits_{f\in L_2({\mathbb R}^n), ||f||_{L_2}\leq 1} {\mathbb E}_{X\sim P, \epsilon\sim E} f(X+\epsilon)-{\mathbb E}_{Y\sim Q, \epsilon'\sim E} f(Y+\epsilon') \end{align} $

Even for the general kernel similar formulas can be obtained, but then you need some pseudo-differential calculus (see https://arxiv.org/pdf/2106.14277.pdf).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.