[High Dimensional Statistics] Maximum Mean Discrepancy(MMD)

References

• Yonsei univ. STA9104 : Statistical theory for high dimensional and big data
• A Kernel two-sample test , Gretton, 2012.

1. IntroductionPermalink

1. 1. Two sample test problem settingPermalink

$X_1,\cdots ,X_n\stackrel{iid}{\sim }p$ and $Y_1,\cdots ,Y_n\stackrel{iid}{\sim }q$

Hypothesis : $H_0:p=q,H_1:p\ne q$

• classical method to test two-sample test.

  there are many classical ways for two-sample test. It include,

  1. t-test, in case of 1-dimensional
  2. Hotelling $T-squared$ test , which is generalization of t-test into ${\mathbb{R}}^d$
     • However, it only applies when $n<d$ and only sensitive to mean difference
  3. Tests based on empirical CDF, e.g. K.S. test and CVM test
     • Sensitive to any difference in distribution,
     • However, hard to generalize to ${\mathbb{R}}^d$

• MMD solve a lot of problems.
  1. It workd well for multivariate data
  2. It is sensitive to general alternatives
  3. It is easy to estimate
  4. It is an example of IPM (Intergral Probability Metrics)

1.2. Integral Probability Metrics(IPM)Permalink

Definition (Integral Probability Metrics) for a class if function $\mathcal{F}$, IPM between $p$ and $q$ is defined as

Examples are total variation distance, wasserstein distance, kolmogorov distance.

2. Maximun Mean Discrepancy(MMD)Permalink

• If $\mathcal{F}$ is too larger, it is difficult to estimate IPM($p,q$). Also, if $\mathcal{F}$ is too small, $IPM(p,q)=0$ even if $p\ne q$.

• MMD takes middle ground between these two extremes,

  It takes $\mathcal{F}$ to be a unit ball in a RKHS $\mathcal{H}$

2.1. Reproducin Kernel Hilbert spacePermalink

Definition (Reproducing kernel Hibert space)

A RKHS is a Hilber space $\mathcal{F}$ defined with an inner product $<\cdot ,\cdot {>}_{\mathcal{F}}$ where it has a reproducing kernel property

$\begin{array}{rl}\mathcal{k}:\chi \times \chi ⟶& \mathbb{R}suchthat\\ \mathrm{\forall }x\in \chi ,\mathrm{\forall }f\in \mathcal{F},& \underset{ReprodcingProperty}{\underbrace{<f(x),\mathcal{k}(:,x){>}_{\mathcal{F}}=f(x)}}\end{array}$

2.2. Definition of MMDPermalink

Definition (Maximun Mean Discrepancy)

Let $\mathcal{F}$ to be a unit ball in a RKHS such that $\mathrm{\forall }f\in \mathcal{F}$ , $||f|{|}_{\mathcal{F}}=\sqrt{<f,f{>}_{\mathcal{F}}}\le 1$.Then,

, That is, MMD is a IPM with $f$ being unit ball in RKHS.

2.3. Properties of MMDPermalink

• Property 1

  If RKHS is associated with a “characteristic kernel”, such as gaussian kernel, then

$MMD(p,q)=0ifandonlyifp=q$

• Property 2

$\begin{array}{rl}MM{D}^2(p,q)& =[\underset{f\in \mathcal{F}}{sup}|{\mathbb{E}}_p[f(x)]-{\mathbb{E}}_q[f(x)]|{]}^2\\ & =[\underset{f\in \mathcal{F}}{sup}<f,{\mathbb{E}}_p[\mathcal{k}(\cdot ,x)]-{\mathbb{E}}_q[\mathcal{k}(\cdot ,x)]{]}^2⟵bythereproducingproperty\\ & \le ||f|{|}_{\mathcal{H}}^2||{\mathbb{E}}_p[\mathcal{k}(\cdot ,x)]-{\mathbb{E}}_q[\mathcal{k}(\cdot ,x)|{|}_{\mathcal{H}}^2⟵||f|{|}_{\mathcal{H}}^2\le 1\\ & \le <{\mathbb{E}}_p[\mathcal{k}(\cdot ,x)]-{\mathbb{E}}_q[\mathcal{k}(\cdot ,x)],{\mathbb{E}}_p[\mathcal{k}(\cdot ,x)]-{\mathbb{E}}_q[\mathcal{k}(\cdot ,x)]{>}_{\mathcal{H}}\\ & =<{\mathbb{E}}_p[\mathcal{k}(\cdot ,x)],{\mathbb{E}}_p[\mathcal{k}(\cdot ,x^{\prime })]>+<{\mathbb{E}}_q[\mathcal{k}(\cdot ,x)],{\mathbb{E}}_q[\mathcal{k}(\cdot ,x^{\prime })]>-2<{\mathbb{E}}_p[\mathcal{k}(\cdot ,x)],{\mathbb{E}}_q[\mathcal{k}(\cdot ,x^{\prime })]>\\ & ={\mathbb{E}}_{X,X^{\prime }\stackrel{ind}{\sim }p}[\mathcal{k}(X,X^{\prime })]+{\mathbb{E}}_{Y,Y^{\prime }\stackrel{ind}{\sim }q}[\mathcal{k}(Y,Y^{\prime })]-2{\mathbb{E}}_{X\stackrel{ind}{\sim }p,Y\stackrel{ind}{\sim }q}[\mathcal{k}(X,Y)]⟵\underset{RKHSproperty.}{\underbrace{\mathcal{k}(x,x^{\prime })=<\mathcal{k}(\cdot ,x),\mathcal{k}(\cdot ,x^{\prime }){>}_{\mathcal{H}}}}\end{array}$

​ In fact, the upper bound can be achievd by some $f\in \mathcal{F}$, hence,

is achived. Even if it is sup, since it can be achieved, we can say that sup is achieved. That is, optimization problem in IPM calculation, which is obtaining supremum, is bypassed.

​

​ For estimation, consider Plug-in estimator, or a V-statistic in our context :

2.4. Convergence of MMDPermalink

Let $X_1,\cdots ,X_m$ be $i.i.d.$ observations from $p$ and $Y_1,\cdots ,Y_n$ be $i.i.d.$ observation from $q$. Assum that these two samples are mutually independent. Let $\mathcal{F}$ be the unit ball in a reproducing kernel Hilbert space(RKHS) associated with kernel $\mathcal{k}$ and define

Also, assume that the kernel $k$ is bounded as $0\le \mathcal{k}(x,y)\le K$ for all $x,y$ in the domain $\mathcal{X}$.

Want to show :

$\mathbb{P}[|\widehat{MMD}-MMD|>2(\sqrt{\frac{K}{m}}+\sqrt{\frac{K}{n}})+t]\le \exp (-\frac{t^{2}mn}{2K(m+n)})$

proof)

Step 1) obtain upper bound for Rademacher Complexity

Let ${ϵ}_t,\cdots ,{ϵ}_m$ be $i.i.d.$ Rademacher random variables taking values of $\$1,2\$$where $\mathbb{P}({ϵ}_1=-1)=\mathbb{P}({ϵ}_1=1)=\frac{1}{2}$. Then, the Rademacher coplexity of $\mathcal{F}$ satisfies

why?

$\begin{array}{rl}{\mathcal{R}}_m(\mathcal{F})& ={\mathbb{E}}_{X,ϵ}[\underset{f\in \mathcal{F}}{sup}|\frac{1}{m}\sum _{i=1}^m{ϵ}_{i}f(X_i)|]\\ & ={\mathbb{E}}_{X,ϵ}[\underset{f\in \mathcal{F}}{sup}|<f,\frac{1}{m}\sum {ϵ}_i\mathcal{k}(X_i){>}_{\mathcal{H}}|]⟵reproducingproperty\\ & \le \frac{1}{m}{\mathbb{E}}_{X,ϵ}[||f|{|}_{\mathcal{H}}||\sum {ϵ}_i\mathcal{k}(X_i)|{|}_{\mathcal{H}}]⟵CauchySchwarzinequality\\ & \le \frac{1}{m}{\mathbb{E}}_{X,ϵ}[||\sum {ϵ}_i\mathcal{k}(X_i)|{|}_{\mathcal{H}}]⟵\mathcal{F}isunitball\\ & =\frac{1}{m}{\mathbb{E}}_{X,ϵ}[⟨\sum _{i=1}^m{ϵ}_i\mathcal{k}(X_i),\sum _{j=1}^m{ϵ}_j\mathcal{k}(X_j){⟩}_{\mathcal{H}}^{\frac{1}{2}}]\\ & =\frac{1}{m}{\mathbb{E}}_{X,ϵ}[\sum _{i=1}^m\sum _{j=1}^m{ϵ}_i{ϵ}_j⟨\mathcal{k}(X_i),\mathcal{k}(X_j){⟩}_{\mathcal{H}}^{\frac{1}{2}}]\\ & =\frac{1}{m}{\mathbb{E}}_{X,ϵ}[(\sum _{i=1}^m\sum _{j=1}^m{ϵ}_i{ϵ}_j\mathcal{k}(X_i,X_j){)}^{\frac{1}{2}}]⟵reproducingproperty\\ & \le \frac{1}{m}(\sum _{i=1}^m\sum _{j=1}^m{\mathbb{E}}_{X,ϵ}[{ϵ}_i{ϵ}_j\mathcal{k}(X_i,X_j)]{)}^{\frac{1}{2}}⟵Jense{n}^{\prime }sinequality\\ & =\frac{1}{m}(\sum _{i=1}^m{\mathbb{E}}_{X_i}[\mathcal{k}(X_i,X_i)]{)}^{\frac{1}{2}}⟵ifi\ne j,0\because E[{ϵ}_i{ϵ}_j]=0\\ & \le \frac{1}{m}(mK{)}^{\frac{1}{2}}\\ & =\sqrt{\frac{K}{m}}\end{array}$

Step 2) Implment McDiarmid’s Inequality

To use McDiardmid’s inequality, we need to derive Bounded difference condition.

Fisrt, bound the $|\widehat{MMD}-MMD|$ by some formula satisfying bounded difference condition .

Here, Let’s denote

as

Then, we can find bounded difference condition for $\mathrm{△}(X,Y)$

for $i=1,2,\cdots ,m$,

Therefore, if we do smiliar procedure to $i=m+1,\cdots ,m+n$,

Because $\sum _{i=1}^{m+n}{L}_i^2=\frac{(m+n)4K}{mn}$, applying Mcdiarmid’s inequality

Step 3) control $\mathbb{E}\mathbf{[}\mathrm{△}\mathbf{(}\mathbf{X}\mathbf{,}\mathbf{Y}\mathbf{)}\mathbf{]}$

To control $\mathbb{E}[\mathrm{△}(X,Y)]$, Symmtetrization and Rademacher coplexity is used. The result from class is

Applying the above result (a), It is easy to verify that

Step 4) Merge the ingredients

Merging two results,

2.5. Testing based on MMDPermalink

Suppose that we want to test whether $H_0:p=q$ or $H_1:p\ne q$. Based on above ineqaulity, we can construct a valid level $\alpha$ test $\varphi :X_1,\cdots ,X_m,Y_1,\cdots ,Y_n\to 0,1$ such that $\mathbb{P}(\varphi =1)\le \alpha$ under $H_{:}p=q$.

Because $p=q$ under $H_0$ , $MMD=0$ and we can treat $Y_i=X_i‘$. ($\because$ both from same distribution $p=q$). Therefore,

$\widehat{MMD}-MMD=\widehat{MMD}=\underset{f\in \mathcal{F}}{sup}(\frac{1}{m}\sum _{i=1}^m(f(x_i)-f(x_i‘))$

applying similar procedure as 2.4. , we can find

By letting $\alpha =\exp (-\frac{t^{2}m}{4K})$ , $t=\sqrt{\frac{-4Klog\alpha }{m}}$

Therefore, we reject $H_0$ if the calculated estimator is larger than $\sqrt{\frac{2K}{m}}+\sqrt{\frac{-4Klog\alpha }{m}}$

• Because Information distribution is not needed. there is no term related to $p$ or $q$

2.6. Permutation test based on MMDPermalink

Procedure

• for $i$ : 1 to $B$:

  • Randomly permute ($X_1,\cdots ,X_m,Y_1,\cdots ,Y_n$)

    $⟶$ ($\tilde{X},\tilde{Y}$) =(${\tilde{X}}_1,\cdots ,{\tilde{X}}_m,{\tilde{Y}}_1,\cdots ,{\tilde{Y}}_n$)

  • Calculate ${\widehat{MMD}}_i^2(\tilde{X},\tilde{Y})$
  • Reject the null of $p=q$ if $\widetilde{pval}=\frac{1}{B+1}|\sum _{i=1}^{B}I(\widehat{MMD}>{\widehat{MMD}}_{obs})+1|\le \alpha$