Maximum Mean Discrepancy

\[ \newcommand{\coloneqq}{\mathrel{\mathrel{\vcenter{:}}=}} \]

MMD

Maximum Mean Discrepancy (MMD)^[1][2] 是一个衡量两个分布差异的指标。具体而言，设 \(p,q\) 是 \(\mathcal X\) 上的概率分布，给定从 \(p\) 采样出的独立同分布样本 \(X=\{x_1,\ldots,x_m\}\) 以及从 \(q\) 采样出的独立同分布样本 \(Y=\{y_1,\ldots,y_n\}\)，我们询问 \(p\) 是否等于 \(q\) ？

MMD 启发自如下定理。

定理 1：设 \((\mathcal X,d)\) 是一个可分的度量空间，\(p,q\) 是 \(\mathcal X\) 上的两个 Borel 概率测度，则： \[ p=q\quad\iff\quad\mathbb E_p[f(x)]=\mathbb E_q[f(x)],\;\forall f\in C(\mathcal X) \] 其中 \(C(\mathcal X)\) 表示 \(\mathcal X\) 上所有连续有界泛函。

基于上述定理，当 \(p=q\) 时总有 \(\mathbb E_{p}[f(x)]-\mathbb E_{q}[f(x)]=0\)，因此用这个差值作为衡量指标似乎是一个不错的选择。不过这个差值还依赖于 \(f\) 的选取，一个自然的想法是选择使得差值最大的那个 \(f\). 综上，我们得到了 MMD 的定义。

定义 (MMD)：设 \(\mathcal F\) 是 \(\mathcal X\) 上的泛函的集合，\(p,q,X,Y\) 如上文所定义。定义 MMD 为： \[ \text{MMD}[\mathcal F,p,q]\coloneqq\sup_{f\in\mathcal F}\Big(\mathbb E_{p}[f(x)]-\mathbb E_{q}[f(x)]\Big) \] 当取 \(\mathcal F=C(\mathcal X)\) 我们就回到了定理 1 的情形，但是对于实际求解而言，\(C(\mathcal X)\) 的范围太大了。因此，MMD 作者将 \(\mathcal F\) 限制为 universal 再生核希尔伯特空间 (RKHS) 中的单位球。若加入 \(\mathcal X\) 是紧的这一条件，那么 universal RKHS 在 \(C(\mathcal X)\) 中在 \(L_\infty\) 范数下是稠密的。这引出了下面的定理，表明限制 \(\mathcal F\) 为 universal RKHS 中的单位球是可行的。

定理 2：设 \(\mathcal X\) 是一个紧的度量空间，\(\mathcal H\) 是 \(\mathcal X\) 上的泛函构成的 universal RKHS，相应的再生核为 \(k(\cdot,\cdot)\). 设 \(\mathcal F\) 为 \(\mathcal H\) 中的单位球，则： \[ p=q\quad\iff\quad\text{MMD}[\mathcal F,p,q]=0 \] 选择 RKHS 的好处在于，利用再生核的再生性，我们能很方便地计算 MMD. 具体而言，设 \(\phi(x)=k(\cdot,x)\in\mathcal H\)，则根据再生性有： \[ f(x)=\langle f,\phi(x)\rangle_\mathcal H \] 因此 MMD 可以写作： \[ \begin{align} \text{MMD}[\mathcal F,p,q]&=\sup_{\Vert f\Vert_\mathcal H\leq 1}\Big(\mathbb E_{p}[f(x)]-\mathbb E_{q}[f(x)]\Big)\\ &=\sup_{\Vert f\Vert_\mathcal H\leq 1}\Big(\mathbb E_{p}\langle f,\phi(x)\rangle_{\mathcal H}-\mathbb E_{q}\langle f,\phi(x)\rangle_{\mathcal H}\Big)\\ &=\sup_{\Vert f\Vert_\mathcal H\leq 1}\Big(\langle f,\mathbb E_{p}[\phi(x)]\rangle_{\mathcal H}-\langle f,\mathbb E_{q}[\phi(x)]\rangle_{\mathcal H}\Big)\\ &=\sup_{\Vert f\Vert_\mathcal H\leq 1}\big\langle f,\mathbb E_{p}[\phi(x)]-\mathbb E_{q}[\phi(x)]\big\rangle_{\mathcal H}\\ &=\big\Vert\mathbb E_{p}[\phi(x)]-\mathbb E_{q}[\phi(x)]\big\Vert_{\mathcal H} \end{align} \] 其中 \(\mathbb E_{p}[\phi(x)]\in\mathcal H\) 称作分布 \(p\) 的核均值嵌入 (kernel mean embedding). 可以看见，MMD 本质上就是 RKHS 中两个点的距离。

使用样本近似期望，得到 MMD 的经验估计： \[ \text{MMD}[\mathcal F,X,Y]=\left\Vert\frac{1}{m}\sum_{i=1}^m\phi(x_i)-\frac{1}{n}\sum_{i=1}^n\phi(y_i)\right\Vert_{\mathcal H} \]

值得注意的是这个估计其实是有偏的。进一步地，取平方得： \[ \begin{align} \text{MMD}[\mathcal F,X,Y]^2&=\left\Vert\frac{1}{m}\sum_{i=1}^m\phi(x_i)-\frac{1}{n}\sum_{i=1}^n\phi(y_i)\right\Vert_{\mathcal H}^2\\ &=\frac{1}{m^2}\sum_{i=1}^{m}\sum_{j=1}^m\langle\phi(x_i),\phi(x_j)\rangle+\frac{1}{n^2}\sum_{i=1}^{n}\sum_{j=1}^n\langle\phi(y_i),\phi(y_j)\rangle-\frac{2}{mn}\sum_{i=1}^m\sum_{j=1}^n\langle\phi(x_i),\phi(y_j)\rangle\\ &=\frac{1}{m^2}\sum_{i=1}^{m}\sum_{j=1}^mk(x_i,x_j)+\frac{1}{n^2}\sum_{i=1}^{n}\sum_{j=1}^nk(y_i,y_j)-\frac{2}{mn}\sum_{i=1}^m\sum_{j=1}^nk(x_i,y_j) \end{align} \]

因此： \[ \text{MMD}[\mathcal F,X,Y]=\left[\frac{1}{m^2}\sum_{i=1}^{m}\sum_{j=1}^mk(x_i,x_j)+\frac{1}{n^2}\sum_{i=1}^{n}\sum_{j=1}^nk(y_i,y_j)-\frac{2}{mn}\sum_{i=1}^m\sum_{j=1}^nk(x_i,y_j)\right]^{\frac{1}{2}} \] 这就是我们在实际应用中使用的 MMD 计算公式，其中再生核一般取高斯核或者拉普拉斯核。

References

1. Gretton, Arthur, Karsten Borgwardt, Malte Rasch, Bernhard Schölkopf, and Alex Smola. A kernel method for the two-sample-problem. Advances in neural information processing systems 19 (2006). ↩︎
2. Gretton, Arthur, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. The Journal of Machine Learning Research 13, no. 1 (2012): 723-773. ↩︎
3. 迁移学习简介之最大均值差异（Maximum Mean Discrepancy） - 姚远的文章 - 知乎. https://zhuanlan.zhihu.com/p/679276071 ↩︎