MMD

Borgwardt K., Gretton A., Rasch M., Kriegel H., Schoikopf B., Smola A. Integrating structured biological data by Kernel Maximum Mean Discrepancy. 2006.

概

本文介绍了一种衡量不同数据分布之间一致性的统计量.

主要内容

在统计中, 我们常常需要讨论两组数据是否采样自同一个分布. 一个最常见的问题或许就是, 训练数据和测试数据的偏移, 本文的重点是提出MMD作为一个衡量二者是否采样自同一个数据的指标, 后续的KMM则是其用于处理这种偏移的一种方法.

定义

假设$\mathcal{F}$是一类$f:\mathcal{X}\to \mathbb{R}$的函数, 而$p,q$分别是两个博雷尔概率分布，即概率空间为$({\mathbb{R}}^d,\mathcal{B}(\mathbb{R}{)}^d,p|q)$ . 并令$X=(x_1,x_2,\dots ,x_m),Y=(y_1,y_2,\dots ,y_n)$分别独立采样自$p,q$. 则MMD与经验MMD按照如下方式定义:
$$\begin{gathered} \mathrm{M}\mathrm{M}\mathrm{D}[\mathcal{F},p,q]:=\underset{f\in \mathcal{F}}{\sup }({\mathbb{E}}_p[f(x)]-{\mathbb{E}}_q[f(y)]) \\ \mathrm{M}\mathrm{M}\mathrm{D}[\mathcal{F},p,q]:=\underset{f\in \mathcal{F}}{\sup }(\frac{1}{m}\sum _{x\in X}f(x)-\frac{1}{n}\sum _{y\in Y}f(y)). \end{gathered}$$
​

首先, 倘若$p=q$, 那么显然$\mathrm{M}\mathrm{M}\mathrm{D}[\mathcal{F},p,q]=0$, 但是当$p\ne q$的时候, 我们总能找到一些$f$令MMD为正. 不过这一性质对于经验MMD就有所不同了, 由于采样个数有限, $X,Y$总会有一些不同, 所以这一指标往往永远不为0.

若是要估计上面的式子, 这是非常困难的, 而且某种程度上是没有意义的, 因为一旦找到一个$f$使得MMD非零, 我们可以去$f^{\prime }:=\alpha \cdot f$使得MMD任意大. 所以第一步便是要限制$\mathcal{F}$, 很自然的方式是限制其在范数球上$\Vert f\Vert \le 1$, 但这并没有改变困难的本质. 要知道$p=q$的一个充分必要条件是
$$\int f\mathrm{d}p=\int f\mathrm{d}q,\forall f\in C.$$

而所有的连续函数都能由 universal RKHS (reproducing kernel Hilbert space)中的函数来逼近, 故我们完全可以将$\mathcal{F}$限制在这样一个空间之上.

MMD for kernel function classes

接下来我们在 universal RKHS $\mathcal{H}$上讨论, 该空间通过给定核$k(\cdot ,\cdot )$来确定, 此时${\varphi }_x=k(x,\cdot )$ . 当然你也可以说是先有的$\varphi$, 然后$k(x,y)=⟨{\varphi }_x,{\varphi }_y⟩$也是可以的. 此时, 是假设对于任意的$x\in \mathcal{X}$存在$L_x:f\to f(x)$, 且$L_x$是一个有界线性算子, 根据Riesz表示引理, $L_x(f)=f(x)=⟨f,{\varphi }_x{⟩}_{\mathcal{H}}$, 其中${\varphi }_x\in \mathcal{H}$.

回到由$k(\cdot ,\cdot )$定义的$\mathcal{H}$中来, 此时的MMD可以便成了
$$\mathrm{M}\mathrm{M}\mathrm{D}[\mathcal{H},p,q]=\underset{\Vert f{\Vert }_{\mathcal{H}}\le 1}{\sup }{\mathbb{E}}_p[f(x)]-{\mathbb{E}}_q[f(x)]=\underset{\Vert f{\Vert }_{\mathcal{H}}\le 1}{\sup }{\mathbb{E}}_p[⟨{\varphi }_x,f{⟩}_{\mathcal{H}}]-{\mathbb{E}}_q[⟨{\varphi }_x,f{⟩}_{\mathcal{H}}]=\Vert {\mu }_p-{\mu }_q{\Vert }_{\mathcal{H}},$$
其中${\mu }_p={\mathbb{E}}_p[{\varphi }_x],{\mu }_q={\mathbb{E}}_q[{\varphi }_x]$.

${\mathrm{M}\mathrm{M}\mathrm{D}}^2$ 一个无偏统计量

定义
$$\begin{gathered} {\mathrm{M}\mathrm{M}\mathrm{D}}^2[\mathcal{H},p,q]=\Vert {\mu }_p-{\mu }_q{\Vert }_{\mathcal{H}}^2, \\ {\mathrm{M}\mathrm{M}\mathrm{D}}^2[\mathcal{H},X,Y]=\frac{1}{m(m-1)}\sum _{i\ne j}k(x_i,x_j)+\frac{1}{n(n-1)}\sum _{i\ne j}k(y_i,y_j)-\frac{2}{mn}\sum _{i,j}k(x_i,y_j). \end{gathered}$$
容易证明${\mathrm{M}\mathrm{M}\mathrm{D}}^2[\mathcal{H},X,Y]$是$MM{D}^2[\mathcal{H},p,q]$的一个无偏统计量.

当$m=n$的时候, 进一步有
$${\mathrm{M}\mathrm{M}\mathrm{D}}^2[\mathcal{H},X,Y]=\frac{1}{m(m-1)}\sum _{i\ne j}h(z_i,z_j),$$
其中
$$h(z_i,z_j):=k(x_i,x_j)+k(y_i,y_j)-k(x_i,y_j)-k(x_j,y_i).$$

MMD test

通过上述推论便可知我们应该如何检验, 并且具体算法如下.

注: $\mathrm{P}\mathrm{r}(z>z_{\alpha })=\alpha \Rightarrow \mathrm{P}\mathrm{r}(-z_{\alpha }<z<z_{\alpha })=1-\alpha$, 又$\mathrm{e}\mathrm{r}\mathrm{f}(x)=\Phi (\sqrt{2}x)-\Phi (-\sqrt{2}x)$, 所以$\mathrm{e}\mathrm{r}\mathrm{f}\mathrm{i}\mathrm{n}\mathrm{v}(1-2\alpha )=\frac{1}{\sqrt{2}}{z}_{\alpha }$, 这是算法里那个式子的由来.