Two sample problem(1): Parzen Windows, Maximum Mean Discrepancy

There is a nice tutorial from Alex. I expanded the math part to show you more details. I used latex then posted screenshots.

Parzen Windows

Two sets of samples from two distributions. How do we know the differences?
13940910_841370985998471_1522505482_n
Now we want to test whether q = p. We can either estimate $\hat { p }$ and $\hat { q }$ from the observations or measure the distance and see the difference.

13884455_841373922664844_67870748_n

Same, the other two terms can be simplified in the same way:

13933054_841374989331404_1352703130_n

So, finally we will reach:

13884446_841375259331377_1350472025_n

Maximum Mean Discrepancy (MMD)

Defination

$D(p,q,\mathcal{F}) =\sup_{f\in \mathcal{F}} { E }_{ p }^{ }[f(x)]-{ E }_{ q }^{ }[f(y)]$

It is defined as the supremum of the set S, where S contains differences between expectations. Supremum is an element $a$,where for every element m in S, we have always $a\le m$ . For example, $\sup\{1,2,3\}$ = 3.

In a Reproducing Kernel Hilbert Space where $\mathcal{H}$ is universal, we have the Theorem that $D(p,q,\mathcal{F}) = 0$ iff $p=q$ , when $\mathcal{F}$ is a unit ball in the space.
Not going to prove here (well because I don’t know how to do 😦 ). But for simplicity, let us understand this way: if p=q, that means the two sets of samples come from the exact same distribution, and there is no doubt that the discrepancy is zero. If p $\neq$ q, we try some ways to represent these data and map it into some feature spaces (RKHS), then we can always find a mapping function f that would contribute providing the mean discrepancy.

In another word, we can get a squared distance between embeddings in the RKHS, given the two distributions. Then the goal for us is to estimate:
$MMD(P,Q) = ||\mu_p-\mu_q||^2_\mathcal{H}$

Replacing with $\mu_p$ and $\mu_q$

Now I will explain $\mu_p$ and $\mu_q$ .
We have a function $\phi(x)$ who is mapping the data to a feature space F. For example, the quadratic features $\phi(x)= (1,x,x^2)$ . An advantage of the kernels is that there is no need to compute $\phi(x)$ explicitly, where we have eq2: $\langle\phi(x),\phi(x')\rangle=k(x,x')$ .

In the RKHS with kernel k, the evaluation functions are eq3 $f(x)= \langle k(x,\cdot ),f \rangle$ . We also call it reproducing property. By using kernels,if you are familiar with that, we have $\phi(x)$ defined as a kernal function $k(x,\cdot)$ . We take it into eq2, then we will finally have eq4:
$\langle k(x,\cdot),k(x',\cdot) \rangle=k(x,x')$

$E_p[f(x)]=E_p[\langle k(x,\cdot),f \rangle]= \langle E_p[k(x,\cdot)],f \rangle = \langle \mu_p,f \rangle$ (take eq3 in)
And we mark $E_p[k(x,\cdot)]$ as $\mu_p$ .

Optimization Problem

Then let’s have a deep breath and start optimizing.

We take $\mu_p$ and $\mu_q$ :
$\sup_{f\in \mathcal{F}} { E }_{ p }^{ }[f(x)]-{ E }_{ q }^{ }[f(y)] = sup\langle \mu_p-\mu_q,f \rangle = ||\mu_p-\mu_q||_\mathcal{H}$

Add kernels and calculate the squared distance:
$MMD(P,Q) = ||\mu_p-\mu_q||^2_\mathcal{H}$
$= \langle \mu_p-\mu_q,\mu_p-\mu_q \rangle$
$=\langle \mu_p,\mu_p -\mu_q \rangle -\langle \mu_q,\mu_p-\mu_q \rangle$
$=\langle \mu_p,\mu_p \rangle-2\langle \mu_p,\mu_q \rangle + \langle \mu_q,\mu_q \rangle$
(Remember $\langle a,b \rangle = \langle b,a \rangle$ )

We take the first term (same as the third):
$\langle \mu_p,\mu_p \rangle$
$=\langle E_p[k(x,\cdot)], E_p[k(x',\cdot)]\rangle$
$=E_{pp}k(x,x')$
(Use eq4)

The second term:
$\langle \mu_p,\mu_q \rangle$
$=\langle E_p[k(x,\cdot)], E_q[k(y,\cdot)]\rangle$
$=E_{pq}k(x,y)$
(Use eq4)

Finally, $||\mu_p-\mu_q||^2_\mathcal{H} = E_{pp}k(x,x')-2E_{pq}k(x,y)+E_{qq}k(y,y')$ as $D(p,q,\mathcal{F})$ . The goal is to estimate it.

That means, we do not need to know the real distribution p and q (usually we do not have that!). We could estimate the MMD from given indipendent i.i.d. data from both two datasets. If we know p and q, we could use Parzen Windows.

One thought on “Two sample problem(1): Parzen Windows, Maximum Mean Discrepancy”

Pingback: Two sample problem(2): kernel function, feature space and reproducing kernel map | Irene's Blog

Two sample problem(1): Parzen Windows, Maximum Mean Discrepancy

Parzen Windows

Maximum Mean Discrepancy (MMD)

Defination

Replacing with $\mu_p$ and $\mu_q$

Optimization Problem

Published by Irene

One thought on “Two sample problem(1): Parzen Windows, Maximum Mean Discrepancy”

Leave a Reply Cancel reply

Parzen Windows

Maximum Mean Discrepancy (MMD)

Defination

Replacing with and

Optimization Problem

Share this:

Like this:

Related

Published by Irene

One thought on “Two sample problem(1): Parzen Windows, Maximum Mean Discrepancy”

Leave a Reply Cancel reply

Replacing with $\mu_p$ and $\mu_q$