浅谈Maximum Mean Discrepancy (MMD)
MMD有什么用
MMD用于检验两堆数据是否是来源于同一分布，即假设
\(D_s = (x_1,x_2,\cdots,x_n) \sim P(x)\)和\(D_t=(y_1,y_2,\cdots,y_n)\sim Q(y)\)，MMD用于检验\(P=Q\)是否成立。
MMD与KL散度（Kullback–Leibler divergence）的区别？
KL散度定义是
\[KL(P,Q)=\sum P(x)\log \frac{P(x)}{Q(x)}
\]
当\(P(x)\)与\(Q(x)\)越相似，KL散度越小。
为了计算KL散度，必须要知道\(P\)和\(Q\)的密度函数。因此KL散度常用于监督学习方法，用于衡量训练的分布\(P_{model}\)与真实分布\(Q_{real}\)之间的相似性。（交叉熵损失本质上就是KL散度的变形）
而MMD评价两堆数据是否具有相似性。这与KL散度具有本质上的不同。
例子
假设有两堆手写数字的图片，一堆是数据库MINIST里面的，一堆是由GAN模型生成的。如何断别GAN生成图片的质量呢？（即检验两堆数据是否来自于同一分布）
MMD就是干这个的。而KL散度是无法处理这个问题的。
MMD的定义
寻找一个"well-behaved"函数\(f:\mathcal{x}\mapsto \mathbb{R}\in \mathcal{F}\)，使得下面的目标最大：
\[R = \max_{f\in \mathcal{F}} |\mathbb{E}_{x\sim P(x)}f(x) - \mathbb{E}_{y\sim Q(y)}f(y)|
\]
\[\hat R=\max_{f\in \mathcal{F}} \frac{1}{n}\sum_x f(x)-\frac{1}{m}\sum_y f(y)
\]
这个目标为什么能反应出分布\(P\)和\(Q\)之间的差异呢？
函数\(f\)将分布\(P\)和\(Q\)中的所有样本映射成一个实数，遍历函数空间\(\mathcal{F}\)中所有的函数，将这两堆实数的均值差最大值用于衡量分布的差异。
如果\(P=Q\)，则对于任意的\(f\)，都有\(|\mathbb{E}_{x\sim P(x)}f(x) - \mathbb{E}_{y\sim Q(y)}f(y)|=0\)，故最大差异\(R=0\)。
如果\(P\)和\(Q\)很相似，则可能存在很多\(f\)使得\(|\mathbb{E}_{x\sim P(x)}f(x) - \mathbb{E}_{y\sim Q(y)}f(y)|=0\)，因此这些\(f\)并不能客观反映出\(P\)和\(Q\)之间的差异，所以需要选择一个合适的\(f\)，使得两个分布最不相似的特性被刻画出来。
在RKHS中计算R
\(R\)中涉及到积分运算，而且我们只关心\(R\)的数值，并不关心\(f\)到底是什么。
为了解决这些问题，我们可以限制\(f\)的形式。
回忆一下
对于核函数\(k\)，其对应的特征向量是\(\phi:\mathcal{x}\mapsto \mathcal{H}\)，其中\(\mathcal{H}\)是与\(k\)相对应的再生核Hilbert空间。
对于\(\forall f\in \mathcal{H}\)，核函数\(k\)满足重构属性：
\[f(x)=\left<f,\phi(x)\right>_\mathcal{H}
\]
利用重构属性，可以非常轻松的将\(f\)与样本\(x\)分开，然后可以非常轻松的对\(f\)取最大值。
因此我们假设\(f\in \mathcal{H}\)。
基于这样的假设，我们有
\[R=\sup_{f}|\mathbb{E}_{x\sim P(x)}f(x) - \mathbb{E}_{y\sim Q(y)}f(y)|
\]
\[=\sup_{f}|\mathbb{E}_{x\sim P(x)}\left<f,\phi(x)\right> - \mathbb{E}_{y\sim Q(y)}\left <f,\phi(y)\right>|
\]
\[=\sup_{f}|\left<f,\mathbb{E}_P \phi(x) - \mathbb{E}_Q \phi(y)\right>|
\]
进一步限制\(f\)：我们假设\(f\)的模小于等于1，即\(\|f\|_\mathcal{H} \leq 1\)。
此时，当
\[f=\frac{\mathbb{E}_P \phi(x) - \mathbb{E}_Q \phi(y)}{\|\mathbb{E}_P \phi(x) - \mathbb{E}_Q \phi(y)\|}
\]
时，\(|\left<f,\mathbb{E}_P \phi(x) - \mathbb{E}_Q \phi(y)\right>|\)取最大值。
此时,
\[R = \|\mathbb{E}_P \phi(x) - \mathbb{E}_Q \phi(y)\|_{\mathcal{H}}
\]
——————
注：可以将\(f\)和\(\mathbb{E}_P \phi(x) - \mathbb{E}_Q \phi(y)\)当成是\(\mathbb{R}^n\)中的元素（两个向量）。当两个向量相等时，其积取最大值。
——————
MMD定义
假设\(\mathcal{X}\)是一个非空集，函数\(k:\mathcal{X}\times \mathcal{X}\mapsto \mathbb{R}\)是一个正定核函数，其对应的RKHS\(\mathcal{H}\)，特征映射是\(\phi:\mathcal{X}\mapsto \mathcal{H}\)。给定两个数据集，\(D_s = (x_1,x_2,\cdots,x_n) \sim P(x)\)和\(D_t=(y_1,y_2,\cdots,y_m)\sim Q(y)\)，则最大均值依赖MMD的定义及其经验评估为，
\[\text{MMD}(P,Q)=\left \|\mathbb{E}_P \phi(x) - \mathbb{E}_Q \phi(y)\right \|
\]
\[\widehat{\text{MMD}}(P,Q)=\left \|\frac{1}{m}\sum_{x_i} \phi(x_i) - \frac{1}{n}\sum_{y_i} \phi(y_i)\right \|_2
\]
MMD如何计算
直接平方展开。
\[\widehat{\text{MMD}}(P,Q)^2=\left \|\frac{1}{m}\sum_{x_i} \phi(x_i) - \frac{1}{n}\sum_{y_i} \phi(y_i)\right \|^2_2
\]
\[=\|\frac{1}{m}\sum_{x_i} \phi(x_i)\|^2 + \|\frac{1}{n}\sum_{y_i} \phi(y_i)\|^2 - 2\|\frac{1}{m}\sum_{x_i} \phi(x_i) \frac{1}{n}\sum_{y_i} \phi(y_i)\|
\]
而
\[\|\frac{1}{m}\sum_{x_i} \phi(x_i)\|^2=\frac{1}{m^2} (\phi(x_1)+\phi(x_2)+\cdots+\phi(x_m))^T(\phi(x_1)+\phi(x_2)+\cdots+\phi(x_m))
\]
\[=\frac{1}{m^2}\{\phi(x_1)^T\phi(x_1) + \cdots + \phi(x_1)^T\phi(x_m)
\]
\[+\phi(x_2)^T\phi(x_1) + \cdots + \phi(x_2)^T\phi(x_m)
\]
\[\cdots+\phi(x_m)^T\phi(x_1) + \cdots + \phi(x_m)^T\phi(x_m)\}
\]
\[=\frac{1}{m^2}\{k(x_1,x_1)+k(x_1,x_2)+\cdots +k(x_1,x_m) + k(x_2,x_1)+\cdots+k(x_2,x_m) +\cdots\}
\]
\[=\frac{1}{m^2}\sum_{i,j} k(x_i,x_j)
\]
同理可得，
\[\|\frac{1}{n}\sum_{y_i} \phi(y_i)\|^2=\frac{1}{n^2}\sum_{i,j} k(y_i,y_j)
\]
\[\|\frac{1}{m}\sum_{x_i} \phi(x_i) \frac{1}{n}\sum_{y_i} \phi(y_i)\|=\frac{1}{mn}\sum_{i,j}k(x_i,y_j)
\]
所以有，
\[\widehat{\text{MMD}}^2=\frac{1}{m^2}\sum_{i,j} k(x_i,x_j)+\frac{1}{n^2}\sum_{i,j} k(y_i,y_j)-\frac{2}{mn}\sum_{i,j}k(x_i,y_j)
\]
下面，将会介绍MMD的重要性质，如 \(MMD = 0\)与\(P=Q\)之间的等价性等。