f-divergence 与 Wasserstein 距离

f-divergence

f-divergence 是 KL 散度的推广，对两个分布 $P$ 和 $Q$ 而言，如果它们各自诱导的 $R$ 上的概率测度（仍然记作） $P$ 和 $Q$ 满足 $P \ll Q$ ，即 $P$ 关于 $Q$ 绝对连续，定义：
$D_{f}(P \| Q) \equiv \int_{\Omega} f\left(\frac{d P}{d Q}\right) d Q, \quad f \;\; \text{convex}.\; f(1)=0$ 如果 $P$ 和 $Q$ 关于一个共同的测度 $\mu$ 绝对连续，那么 $dP=p d\mu$ , $dQ=q d\mu$ ，代入到上面就是：
$D_{f}(P \| Q)=\int_{\Omega} f\left(\frac{p(x)}{q(x)}\right) q(x) d \mu(x)$ 在很多资料中，还有 $\phi$ -divergence的概念，一般 f-divergence 写的是连续情况，而 $\phi$ -divergence多指离散情况。对于两个非负向量 $\mathbf{p}=\left(p_{1}, \ldots, p_{n}\right)^{T}$ 和 $\mathbf{q}=\left(q_{1}, \ldots, q_{n}\right)^{T}$ ，这里不一定要求 $\mathbf{1}^T \mathbf{p}=1$ ，用 $\phi$ -divergence衡量这两个向量的相似度：

$I_{\phi}(\mathbf{p}, \mathbf{q})=\sum_{\omega=1}^{n} q_{\omega} \phi\left(\frac{p_{\omega}}{q_{\omega}}\right), \quad \phi \;\; \text{convex}.$

仅借助 $f$ 的凸性，我们可以得到 $D_f(P\|Q)$ 的三点性质：

非负性：根据琴生不等式， $D_{f}(P \| Q) \geq f(1)=0$ 。
单调性：对任意的转移概率 $\kappa$ ，有： $D_{f}(P \| Q) \geq D_{f}\left(P_{\kappa} \| Q_{\kappa}\right)$ 。
凸性： $D_{f}(P \| Q)$ 对 $(p, q)$ 是凸的。因为凸函数的透视也是凸的。

根据 $f(t)$ 的不同，散度可以有多种形式：

这些提出来的散度，都各有各的作用。这些形式中，有的满足距离公理，所以我们称之为“距离”。

其中，JS散度是KL散度的一种改进，KL散度的缺点是不满足对称性，但如下定义的JS散度满足对称性（但仍然不是一种距离）。JS散度作为KL散度的改进被用在了GAN中。
$D_{J S}\left(P_{1} \| P_{2}\right)=\frac{1}{2} D_{K L}\left(P_{1} \| \frac{P_{1}+P_{2}}{2}\right)+\frac{1}{2} D_{K L}\left(P_{2} \| \frac{P_{1}+P_{2}}{2}\right)$

Wasserstein Distance

Wasserstein距离也是用来度量两个概率分布之间差异的方法，它满足“距离”所需要的三个条件，所以我们称之为“距离”！它有很多别名，比如 optimal transport（简称OT）、Earth Move Distance（简称EMD）。其思想于1781年被法国数学家 Gasoard Monge 在交通理论中被首次提出。

Wasserstein 距离现在在算法研究中具有非常高的热度。（2021年2月）在DBLP中搜索Wasserstein，结果数量按年限如下图：

2005-2021/02 DBLP检索Wasserstein结果数

Wasserstein距离相比其它度量分布差异的函数具有显著的优势。

一些其它的分布之间的距离：

Total Variation

$\sup _{A \in \mathcal{B} }|P(A)-Q(A)|$ TV是两个概率分布在 Borel 集上最大的概率之差。

它不能很好的比较离散和连续型随机变量的分布差异。比如 $[0, 1]$ 上的均匀分布，和 $\{0, \frac{1}{N}, \frac{2}{N}..., 1\}$ 上的离散均匀分布，按理说这两个分布之间非常接近，尤其是当 $N$ 很大的时候，但是 Total Variation 恒等于1。

这时候两个分布的 type-1 Wasserstein 距离是 $\frac{1}{N}$ ，与我们的认识更加接近。

$L^2$

$\int (p-q)^2$

Hellinger Distance

$\sqrt{\int(\sqrt{p}-\sqrt{q})^{2}}$

这些距离不能捕捉概率分布形状上的差异。

Optimal Transport

把概率分布想象成一堆石子，如何移动一堆石子，做最少的功，把它堆成另外一个目标形状，这就是 optimal transport。

假定我们要把概率分布 $p(x)$ 转变成 $q(x)$ ，设距离函数（转移成本）为 $d(x, y)$ ，那么 Wasserstein 距离定义为：
$\mathcal{W}[p, q]=\inf _{\gamma \in \Pi[p, q]} \iint \gamma({x}, {y}) d({x}, {y}) \mathrm d {x} \mathrm d {y}$ $\gamma \in \Pi[p, q]$ 指的是 $p, q$ 的联合分布。

距离函数（转移成本）常用的就是 $p$ 范数。所以 Wasserstein 距离通常就写作：
$\mathcal{W}[p, q]=\left( \inf _{\gamma \in \Pi[p, q]} \iint \gamma({x}, {y}) \| x-y\|^p \mathrm d {x} \mathrm d {y}\right)^\frac{1}{p}$

Wasserstein距离不仅给出了两个分布之间的距离，而且能够告诉我们它们具体如何不一样，即如何从一个分布转化为另一个分布，靠的就是联合分布 $\gamma (x, y)$ 。

Dual form

Wasserstein距离的计算本质上是一个约束优化问题：
$\begin{array}{l} \displaystyle\inf_{\gamma \in \Pi[p, q]} \iint \gamma (x, y) d(x, y) \mathrm d x \mathrm d y \\ \text { s.t. }\left\{\begin{array}{l} \displaystyle\int \gamma(x, y)\mathrm d y=p(x) \\ \displaystyle\int \gamma(x, y)\mathrm d x=q(y) \\ \gamma (x, y) \geqslant 0 \end{array}\right. \end{array}$ 这个优化问题的对偶问题是：
$\mathcal{W}[p, q]=\sup_{f, g}\left\{\int[p({x}) f({x})+q({x}) g({x})] d {x} \mid f({x})+g({y}) \leq d({x}, {y})\right\}$ 而 $f(x)+g(x) \leq d(x, x)=0 \Rightarrow g(x)\leq -f(x)$ $\begin{aligned} p({x}) f({x})+q({x}) g({x}) & \leq p({x}) f({x})+q({x})[-f({x})] \\ &=p({x}) f({x})-q({x}) f({x}) \end{aligned}$ 所以完全可以令 $g(x)=-f(x)$ ，从而得到最终的对偶形式： $\mathcal{W}[p, q]=\sup_{f}\left\{\int[p({x}) f({x})-q({x}) f({x})] \mathrm d {x} \mid f({x})-f({y}) \leq d({x}, {y})\right\}$

对偶形式在计算中起重要作用。

Wasserstein 距离的应用

参数估计

对于一个样本 $x_1, x_2, .., x_N$ ，可以构造一个 nominal distribution：
$\hat{\mathbb{P}} _N = \frac{1}{N}\sum_{i=1}^N \delta_{x_i}$ $\delta_{x_i}$ 是Dirac函数。

用样本去估计参数模型 $(P_\theta, \theta \in \Theta)$ 时，选取与经验分布最接近的：
$\hat \theta = \underset{\theta}{\operatorname{argmin}} \mathcal{W}\left[P_\theta, \hat{\mathbb{P}}_N \right]$

假设检验

$\sqrt{n}\left(\mathcal{W}_{2}^{2}\left(P, \hat{\mathbb{P}}_N\right)-\mathbb{E}\left[\mathcal{W}_{2}^{2}\left(P, \hat{\mathbb{P}}_N\right)\right]\right) \rightsquigarrow N\left(0, \sigma^{2}(P)\right)$ 上述渐进关系的成立能让我们构造出相应的统计量进行假设检验。

Barycenter

分布的质心（Barycenter）可以看作是一系列分布的平均。Wasserstein意义下一列分布 $P_1, P_2, ..., P_N$ 的质心是使Wasserstein距离之和最小的分布： $\hat P = \operatorname{argmin}_P \sum_{i=1}^N \mathcal{W}(P, P_i)$

probabilistic guarantees

假设我们从概率分布 $\mathbb{P}$ 中抽出 $N$ 个样本，这 $N$ 个样本构造出的nominal distribution $\hat {\mathbb{P}}_N$ ，与实际分布 $\mathbb{P}$ 之间的 Wasserstein 距离是可以保证的。

如果 $\mathbb{P}$ 是轻尾分布，即存在 $a > 1$ ，使得 $\mathbb{E}^{\mathbb{P}}\left[\exp \left(\|2 x\|^{a}\right)\right]<+\infty$ ，给定置信水平 $\eta$ ，取 $\varepsilon_{N}(\eta)=\left(\frac{\log \left(c_{1} \eta^{-1}\right)}{c_{2} N}\right)^{\frac{1}{a}} \mathbb{1}_{\left\{N<\frac{\log \left(c_{1} \eta^{-1}\right)}{c_{2} c_{3}}\right\}}+\left(\frac{\log \left(c_{1} \eta^{-1}\right)}{c_{2} N}\right)^{\frac{1}{n}} \mathbb{1}_{\left\{N \geq \frac{\log \left(c_{1} \eta^{-1}\right)}{c_{2} c_{3}}\right\}}$ 其中 $c_1, c_2, c_3$ 是不依赖于 $\varepsilon$ 的常数，这时候有： $\mathbb{P}^{N}\left\{d_{\mathrm{W}}\left(\mathbb{P}, \widehat{\mathbb{P}}_{N}\right) \geq \varepsilon\right\} \leqslant 1-\eta$