目录

• 概
• 主要内容
  • 定义
  • MMD for kernel function classes
  • 一个无偏统计量
  • MMD test

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} \rightarrow \mathbb{R}\)的函数, 而\(p, q\)分别是两个博雷尔概率分布，即概率空间为\((\mathbb{R}^d, \mathscr{B}(\mathbb{R})^d, p|q)\) . 并令\(X=(x_1, x_2,\ldots, x_m), Y=(y_1, y_2,\ldots, y_n)\)分别独立采样自\(p, q\). 则MMD与经验MMD按照如下方式定义:

\[\mathrm{MMD}[\mathcal{F},p,q] := \sup_{f \in \mathcal{F}} (\mathbb{E}_p [f(x)] - \mathbb{E}_q[f(y)]) \\
\mathrm{MMD}[\mathcal{F},p,q] := \sup_{f \in \mathcal{F}} (\frac{1}{m} \sum_{x \in X} f(x) - \frac{1}{n} \sum_{y\in Y} f(y)). \\
\]

​

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

若是要估计上面的式子, 这是非常困难的, 而且某种程度上是没有意义的, 因为一旦找到一个\(f\)使得MMD非零, 我们可以去\(f':=\alpha \cdot f\)使得MMD任意大. 所以第一步便是要限制\(\mathcal{F}\), 很自然的方式是限制其在范数球上\(\|f\| \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)\)来确定, 此时\(\phi_x=k(x, \cdot)\) . 当然你也可以说是先有的\(\phi\), 然后\(k(x, y)=\langle \phi_x, \phi_y \rangle\)也是可以的. 此时, 是假设对于任意的\(x \in \mathcal{X}\)存在\(L_x: f \rightarrow f(x)\), 且\(L_x\)是一个有界线性算子, 根据Riesz表示引理, \(L_x(f)=f(x) = \langle f, \phi_x \rangle_{\mathcal{H}}\), 其中\(\phi_x \in \mathcal{H}\).

回到由\(k(\cdot, \cdot)\)定义的\(\mathcal{H}\)中来, 此时的MMD可以便成了

\[\mathrm{MMD}[\mathcal{H}, p, q] = \sup_{\|f\|_{\mathcal{H}} \le 1} \mathbb{E}_p [f(x)] - \mathbb{E}_q [f(x)]
= \sup_{\|f\|_{\mathcal{H}} \le 1} \mathbb{E}_p [\langle \phi_x, f\rangle_{\mathcal{H}}] - \mathbb{E}_q [\langle \phi_x, f\rangle_{\mathcal{H}}] = \|\mu_p-\mu_q\|_{\mathcal{H}},
\]

其中\(\mu_p=\mathbb{E}_p [\phi_x], \mu_q = \mathbb{E}_q [\phi_x]\).

\(\mathrm{MMD}^2\) 一个无偏统计量

定义

\[\mathrm{MMD}^2 [\mathcal{H}, p, q] = \|\mu_p - \mu_q\|_{\mathcal{H}}^2, \\
\mathrm{MMD}^2 [\mathcal{H}, X, Y] = \frac{1}{m(m-1)}\sum_{i \not = j}k(x_i, x_j) + \frac{1}{n(n-1)}\sum_{i \not = j } k(y_i, y_j) - \frac{2}{mn} \sum_{i,j} k(x_i, y_j).
\]

容易证明\(\mathrm{MMD}^2[\mathcal{H}, X, Y]\)是\(MMD^2[\mathcal{H}, p, q]\)的一个无偏统计量.

当\(m=n\)的时候, 进一步有

\[\mathrm{MMD}^2[\mathcal{H}, X, Y]= \frac{1}{m(m-1)} \sum_{i \not =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{Pr}(z > z_{\alpha}) = \alpha \Rightarrow \mathrm{Pr}(-z_{\alpha}<z <z_{\alpha})=1-\alpha\), 又\(\mathrm{erf}(x) = \Phi(\sqrt{2}x) - \Phi(-\sqrt{2}x)\), 所以\(\mathrm{erfinv}(1-2\alpha) = \frac{1}{\sqrt{2}} z_{\alpha}\), 这是算法里那个式子的由来.