MMD（Maximum Mean Discrepancy）和核函数

MMD

MMD（Maximum Mean Discrepancy）衡量的是：P(X) 与 P(Y) 这两个分布是否相同，其回答的是在某个函数空间 $\mathcal{F}$ 里，$P$ 和 $Q$ 的期望差异能有多大：

$$\text{MMD}(\mathcal{F},P,Q)=\underset{f\in \mathcal{F}}{sup}({\mathbb{E}}_{x\sim P}[f(x)]-{\mathbb{E}}_{y\sim Q}[f(y)])$$

找一类“判别函数” $f$，看是否存在某个 $f$ 能明显区分 $P$ 和 $Q$。如果 $P=Q$，则所有 $f$ 在计算出来的期望的差都约等于 0，即 MMD 约等于 0。

核函数

如果 $\mathcal{F}$ 太大（随便任何可测函数），上面的 $sup$ 很难算。做法：让 $\mathcal{F}$ 变成 某个核对应的 Reproducing Kernel Hilbert Space（RKHS，再生核希尔伯特空间） 单位球：

$$\mathcal{F}=\{f\in \mathcal{H}:\parallel f{\parallel }_{\mathcal{H}}\le 1\}$$

RKHS（再生核希尔伯特空间）：由一个核函数 k(x,y) 定义的函数空间。在这个空间中，每个函数可以通过 k(x,·) 的线性组合构成。

给定一个核函数，例如 RBF 核：

$$k(x,y)=e^{-\frac{(x-y{)}^2}{2{\sigma }^2}}$$

令第二个变量 $y=z$，它变成一个关于 $x$ 的函数：

$$k_z(x):=k(x,z)$$

这些函数就是 RKHS 的“基础积木”。在 RKHS 中，一个函数 f(x) 可以写成：

$$f(x)=\sum _{i=1}^m{\alpha }_{i}k(x,x_i)$$

也就是说：取若干个核函数 $k(\cdot ,x_i)$，各乘以一个系数 ${\alpha }_i$，加起来就得到一个新函数 f(x)

此时，MMD 的计算变成：

$$\text{MMD}(\mathcal{H},P,Q)=\Vert {\mu }_P-{\mu }_Q{\Vert }_{\mathcal{H}}$$

其中：

$${\mu }_P:={\mathbb{E}}_{x\sim P}[\phi (x)],{\mu }_Q:={\mathbb{E}}_{y\sim Q}[\phi (y)]$$

• $\phi (x)$ 是核对应的特征映射（一般是高维甚至无限维）
• ${\mu }_P,{\mu }_Q$ 是 $P$, $Q$ 在 RKHS 中的“均值向量”（mean embedding）

$\phi (x)$ 难以直接求得，但是可以换种形式写 MMD。给定核函数 $k(x,y)=⟨\phi (x),\phi (y)⟩$，有：

$${\text{MMD}}^2(P,Q)=\parallel {\mu }_P-{\mu }_Q{\parallel }_{\mathcal{H}}^2$$

可以展开成：

$${\text{MMD}}^2(P,Q)={\mathbb{E}}_{x,x^{\prime }\sim P}[k(x,x^{\prime })]+{\mathbb{E}}_{y,y^{\prime }\sim Q}[k(y,y^{\prime })]-2{\mathbb{E}}_{x\sim P,y\sim Q}[k(x,y)]$$

这是实际用得最多的形式：全都写成核期望，不用显式知道 $\phi$。

经验估计

样本：

• $x_1,\dots ,x_m\sim P$
• $y_1,\dots ,y_n\sim Q$

$${\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 计算的复杂度是 $O(n^2)$

MMD-RBF

RBF 核：

$$k(x,y)=\exp (-\frac{\parallel x-y{\parallel }^2}{2{\sigma }^2})$$

放进 $MM{D}^2$ 公式就是 MMD-RBF。RBF 是 characteristic kernel → MMD=0 等价于分布完全相同，所以它确实是“真正的距离”意义。

核函数的性质

不是任何函数都能当 kernel。kernel 必须是“高维向量的内积”。但不是任何函数都能表示成某个高维向量空间里的内积。

一个函数 $k(x,y)$ 要成为 kernel，必须满足：它是对称的，并且对应的 Gram 矩阵永远是半正定的（PSD）。

对于矩阵 $A$，半正定表示（PSD, Positive Semi-Definite）对所有非零向量 $x$ 都有：

$$x^{\mathrm{\top }}Ax\ge 0,$$

正定（PD, Positive Definite）则表示对所有非零向量 $x$ 都有：

$$x^{\mathrm{\top }}Ax>0,。$$

下面证明核函数的 Gram 矩阵一定是半正定的。设：

• $\varphi (x_i)$ 是 $\phi (x)$ 在高维空间中的向量
• 把它们排成矩阵：

$$\mathrm{\Phi }=\left[\begin{array}{c}\varphi (x_1{)}^{\mathrm{\top }}\\ \varphi (x_2{)}^{\mathrm{\top }}\\ ⋮\\ \varphi (x_n{)}^{\mathrm{\top }}\end{array}\right]$$

那么 Gram 矩阵：

$$K_{ij}=⟨\varphi (x_i),\varphi (x_j)⟩$$

就是

$$K=\mathrm{\Phi }{\mathrm{\Phi }}^{\mathrm{\top }}$$

对于任意的向量 $c$，我们有：

$$\begin{array}{rl}{c}^{\mathrm{\top }}Kc& =\sum _{i,j}{c}_i{c}_j{K}_{ij}=\sum _{i,j}{c}_i{c}_j⟨\varphi (x_i),\varphi (x_j)⟩\\ & =⟨\sum _i{c}_i\varphi (x_i),\sum _j{c}_j\varphi (x_j)⟩\\ & ={\Vert \sum _i{c}_i\varphi (x_i)\Vert }^2\ge 0\end{array}$$