27
$\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
    Apr 28 '17 at 15:53
76
$\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}\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 by a feature map $\varphi : \X \to \h$, where $\mathcal H$ is what's called a reproducing kernel Hilbert space. In general, the MMD is $$ \MMD(P, Q) = \lVert \E_{X \sim P}[ \varphi(X) ] - \E_{Y \sim Q}[ \varphi(Y) ] \rVert_\h .$$

As one example, we might have $\X = \h = \R^d$ and $\varphi(x) = x$. In that case: \begin{align} \MMD(P, Q) &= \lVert \E_{X \sim P}[ \varphi(X) ] - \E_{Y \sim Q}[ \varphi(Y) ] \rVert_\h \\&= \lVert \E_{X \sim P}[ X ] - \E_{Y \sim Q}[ Y ] \rVert_{\R^d} \\&= \lVert \mu_P - \mu_Q \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) &= \lVert \E_{X \sim P}[ \varphi(X) ] - \E_{Y \sim Q}[ \varphi(Y) ] \rVert_\h \\&= \lVert \E_{X \sim P}[ A' X ] - \E_{Y \sim Q}[ A' Y ] \rVert_{\R^p} \\&= \lVert A' \E_{X \sim P}[ X ] - A' \E_{Y \sim Q}[ Y ] \rVert_{\R^p} \\&= \lVert A'( \mu_P - \mu_Q ) \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)$, 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: if $\varphi$ maps to a general reproducing kernel Hilbert space, then you can apply the kernel trick to compute the MMD, and it turns out that many kernels, including the Gaussian kernel, lead to the MMD being zero if and only the distributions are identical.

Specifically, letting $k(x, y) = \langle \varphi(x), \varphi(y) \rangle_\h$, you get \begin{align} \MMD^2(P, Q) &= \lVert \E_{X \sim P} \varphi(X) - \E_{Y \sim Q} \varphi(Y) \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} which you can straightforwardly estimate with samples.


Update: here's where the "maximum" in the name comes from.

The feature map $\varphi: \X \to \h$ maps into a reproducing kernel Hilbert space. These are spaces of functions, and satisfy a key property (called the reproducing property): $\langle f, \varphi(x) \rangle_\h = f(x)$ for any $f \in \h$.

In the simplest example, $\X = \h = \R^d$ with $\varphi(x) = x$, we view each $f \in \h$ as the function corresponding to some $w \in \R^d$, by $f(x) = w' x$. Then the reproducing property $\langle f, \varphi(x) \rangle_\h = \langle w, x \rangle_{\R^d}$ should make sense.

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: $\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 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.

$\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
    May 5 '17 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
    May 5 '17 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
    May 5 '17 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
    May 7 '17 at 19:16
  • $\begingroup$ The explanation here is focused on the "Mean Discrepancy" as opposed to "Maximum Mean Discrepancy". Could anyone elaborate on the "Maximization" part? $\endgroup$ Jun 17 '19 at 16:40
12
$\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$
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$
0
$\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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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