Maximum Mean Discrepancy

$$$$

MMD

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

MMD 启发自如下定理。

定理 1：设 $(\mathcal{X},d)$ 是一个可分的度量空间，$p,q$ 是 $\mathcal{X}$ 上的两个 Borel 概率测度，则： $$p=q⟺{\mathbb{E}}_p[f(x)]={\mathbb{E}}_q[f(x)],\mathrm{\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]:=\underset{f\in \mathcal{F}}{sup}({\mathbb{E}}_p[f(x)]-{\mathbb{E}}_q[f(x)])$$ 当取 $\mathcal{F}=C(\mathcal{X})$ 我们就回到了定理 1 的情形，但是对于实际求解而言，$C(\mathcal{X})$ 的范围太大了。因此，MMD 作者将 $\mathcal{F}$ 限制为 universal 再生核希尔伯特空间 (RKHS) 中的单位球。若加入 $\mathcal{X}$ 是紧的这一条件，那么 universal RKHS 在 $C(\mathcal{X})$ 中在 $L_{\mathrm{\infty }}$ 范数下是稠密的。这引出了下面的定理，表明限制 $\mathcal{F}$ 为 universal RKHS 中的单位球是可行的。

定理 2：设 $\mathcal{X}$ 是一个紧的度量空间，$\mathcal{H}$ 是 $\mathcal{X}$ 上的泛函构成的 universal RKHS，相应的再生核为 $k(\cdot ,\cdot )$. 设 $\mathcal{F}$ 为 $\mathcal{H}$ 中的单位球，则： $$p=q⟺\text{MMD}[\mathcal{F},p,q]=0$$ 选择 RKHS 的好处在于，利用再生核的再生性，我们能很方便地计算 MMD. 具体而言，设 $\varphi (x)=k(\cdot ,x)\in \mathcal{H}$，则根据再生性有： $$f(x)=⟨f,\varphi (x){⟩}_{\mathcal{H}}$$ 因此 MMD 可以写作： $$\begin{array}{rl}\text{MMD}[\mathcal{F},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⟨f,\varphi (x){⟩}_{\mathcal{H}}-{\mathbb{E}}_q⟨f,\varphi (x){⟩}_{\mathcal{H}})\\ & =\underset{\Vert f{\Vert }_{\mathcal{H}}\le 1}{sup}(⟨f,{\mathbb{E}}_p[\varphi (x)]{⟩}_{\mathcal{H}}-⟨f,{\mathbb{E}}_q[\varphi (x)]{⟩}_{\mathcal{H}})\\ & =\underset{\Vert f{\Vert }_{\mathcal{H}}\le 1}{sup}⟨f,{\mathbb{E}}_p[\varphi (x)]-{\mathbb{E}}_q[\varphi (x)]{⟩}_{\mathcal{H}}\\ & =\Vert {\mathbb{E}}_p[\varphi (x)]-{\mathbb{E}}_q[\varphi (x)]{\Vert }_{\mathcal{H}}\end{array}$$ 其中 ${\mathbb{E}}_p[\varphi (x)]\in \mathcal{H}$ 称作分布 $p$ 的核均值嵌入 (kernel mean embedding). 可以看见，MMD 本质上就是 RKHS 中两个点的距离。

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

值得注意的是这个估计其实是有偏的。进一步地，取平方得： $$\begin{array}{rl}\text{MMD}[\mathcal{F},X,Y{]}^2& ={\Vert \frac{1}{m}\sum _{i=1}^m\varphi (x_i)-\frac{1}{n}\sum _{i=1}^n\varphi (y_i)\Vert }_{\mathcal{H}}^2\\ & =\frac{1}{m^2}\sum _{i=1}^m\sum _{j=1}^m⟨\varphi (x_i),\varphi (x_j)⟩+\frac{1}{n^2}\sum _{i=1}^n\sum _{j=1}^n⟨\varphi (y_i),\varphi (y_j)⟩-\frac{2}{mn}\sum _{i=1}^m\sum _{j=1}^n⟨\varphi (x_i),\varphi (y_j)⟩\\ & =\frac{1}{m^2}\sum _{i=1}^m\sum _{j=1}^{m}k(x_i,x_j)+\frac{1}{n^2}\sum _{i=1}^n\sum _{j=1}^{n}k(y_i,y_j)-\frac{2}{mn}\sum _{i=1}^m\sum _{j=1}^{n}k(x_i,y_j)\end{array}$$

因此： $$\text{MMD}[\mathcal{F},X,Y]={[\frac{1}{m^2}\sum _{i=1}^m\sum _{j=1}^{m}k(x_i,x_j)+\frac{1}{n^2}\sum _{i=1}^n\sum _{j=1}^{n}k(y_i,y_j)-\frac{2}{mn}\sum _{i=1}^m\sum _{j=1}^{n}k(x_i,y_j)]}^{\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 ↩︎