Wasserstein 度量

前文提到, Wasserstein 度量将 Minkowski 度量从两个点的距离推广到点集上的概率分布的距离. 我们从最简单的一维离散分布情形入手讨论 Wasserstein 度量.

Wasserstein 度量: 一维离散情形

X 班和 Y 班均有 $n$ 个学生, 两个班 $p \ge 1$ 门课程期末考试成绩分别记为: $$X = \{ X(i)\}_{i=1} ^n, Y = \{ Y(i) \}_{i=1} ^n.$$ 其中每个 $X(i)$ 和 $Y(i)$ 均为 $p$ 维向量, 表示学生 $i$ 这些课程的期末成绩.

问: 我们可以如何量化两个班之间的分数分布差异? 换言之, 如何计算 $X$ 与 $Y$ 这两个分布之间的距离?

一个重要观察是: 虽然我们使用了类似向量的符号来表示分布, 但每个班的成绩分布是无序的. 换言之, 我们可以任意改变 $\{X(i)\}$ 和 $\{Y(i)\}$ 中学生的编号顺序, 这并不会改变班级成绩的分布.

• 例: 假设期末只考一门课, 即 $p=1$. 成绩分布 $\{ 91, 93, 84 \}$ 和分布 $\{ 93, 84, 91 \}$ 的距离应为零, 因为它们是同一个分布.

每个成绩分布表示的不仅仅只是 $\{ X(i)\}_{i=1} ^n$ 这一个点, 而是一个点集: 该点集包含所有 $\{ X(i)\}_{i=1} ^n$ 的重排. 基于这个观察, 我们可以考虑如下距离定义:

1. 令 $X^P$ 和 $Y^P$ 分别表示 $X$ 和 $Y$ 的某个重排. 令 $$d(X^P, Y^P) := \frac 1n \sum_{i=1}^n d_M (X^P(i), Y^P(i))$$ 其中 $d_M$ 为 $ℝ^p$ 上的某个 Minkowski 度量. 不难验证, 函数 $d$ 是良定义的测度.

2. 分布 $X$ 和 $Y$ 的距离为所有可能重排对距离的下确界, 即 $$d_W (X,Y) = \min_{X^P, Y^P} d(X^P, Y^P)$$ $$\qquad \qquad s.t. \text{ $X^P$ 和 $Y^P$ 分别为 $X$ 和 $Y$ 的重排.}$$

上述距离函数 $d_W$ 显然满足同一性和对称性. 三角不等式?

从某种意义上说, 寻找 $\{X(i)\}$ 与 $\{Y(i)\}$ 之间的距离等价于一个耦合问题: 为每个 $X_i$ 找到合适的 $Y_j$ 以最小化总损失/成本.

在这种情况下, 解法很简单: 单调耦合是最好的. 也就是说, 最小的 $X(i)$ 匹配最小的 $Y(i)$, 第二小的匹配第二小的, 以此类推.

作为最优传输的 Wasserstein 度量

一种更受欢迎的方法是将此视为一个分配博弈或最优传输问题. 这种解释很好, 因为它允许我们将之前的问题自然地推广.

最优传输的设定:

• 货物: 将每个观测值 $X(i)$ 或 $Y(i)$ 视为一个单位的质量.

• 传输: 每个 $X(i)$ 有 $1/n$ 单位的质量可供分发, 每个 $Y(j)$ 需要一个单位来填满其位置.

• 成本: 将一个单位从 $X(i)$ 移动到 $Y(j)$ 的成本为 $d(X(i), Y(j))$.

• 当 $X(i)$ 和 $Y(j)$ 是标量时, 通常使用 $L_1$ 成本或 $L_2$ 成本.

注意, 最优传输的设定比我们先前的例子要通用得多:

• 耦合可能不是一一对应的匹配, 而可以是一对多的匹配.

• 也就是说, 你可以将 $X[i]$ 的 $1/n$ 单位质量传输到 $Y$ 中的多个目的地.

最优传输问题的解可以表示为一个矩阵 $\pi$, 其每个元素 $\pi[i,j]$ 取非负值.

这个矩阵被称为耦合矩阵, 并满足:

• 行约束: 对于每个 $i$, $\pi[i,j]$ 对 $j$ 求和等于 $1/n$.

• 我们必须把 $X[i]$ 的全部质量送出.

• 列约束: 对于每个 $j$, $\pi[i,j]$ 对 $i$ 求和等于 $1/n$.

• 我们必须向每个 $Y[j]$ 精确交付 $1/n$ 的质量.

优化问题:

$$\min_{\pi} \sum_i \sum_j \pi_{i,j} \vert{}X(i) - Y(j)\vert{}^p$$

$$\text{满足行约束和列约束}$$

单调耦合解决了先前的最优化问题.

最优传输 (OT) 问题总结:

• 你有位于 $X(1), \dots, X(n)$ 的 $n$ 堆泥土, 以及位于 $Y(1), \dots, Y(n)$ 的 $n$ 个待填坑洞.

• 每个坑洞的大小相等, 为 $1/n$.

• 你求解移动所有泥土的最廉价方式, 允许任何一堆泥土分配到多个坑洞.

一些历史背景:

• 可以将 Minkowski 度量视为计算固定的一对一传输成本.

• 如果我们只考虑一对一匹配(或分配), 这也称为蒙日问题, 这里没有质量分裂.

• 当我们允许质量分裂时, 这被称为真正的最优传输问题, 由康托罗维奇(和 Wasserstein )开创.

• 最优传输问题不仅考虑匹配, 还考虑耦合: 即它们对配对的分布进行优化.

Wasserstein 度量: 一维、无限观测

利用最优传输的解释, 我们可以将该问题推广到无限观测的情形. 也就是说, 从 $X$ 和 $Y$ 的经验分布推广到累积分布函数 (CDF) $P$ 和 $Q$. 假设这两个 CDF 在区间 $[0,1]$ 上允许连续的 PDF $p$ 和 $q$.

最优传输的设定:

• 货物: 每个位置 $x$ 拥有 $dP(x) = p(x) dx$ 单位的质量.

• 每个位置 $y$ 需求 $dQ(y) = q(y) dy$ 单位的质量.

• 成本: 从位置 $x$ 移动一个单位到位置 $y$ 的成本为 $\vert{}x-y\vert{}^r$, 其中 $r \ge 1$.

• 耦合: 设 $\gamma$ 是单位正方形 $[0,1] \times [0,1]$ 上的概率测度.

• 微分元素 $\gamma(dx, dy)$ 表示从 $x$ 到 $y$ 的质量.

• $\gamma$ 下的总成本:

$$\iint \vert{}x-y\vert{}^r \gamma(dx, dy)$$

• 关于符号的说明: 如果 $\gamma$ 承认一个密度函数 $f$, 则总成本函数可以写为

$$\iint \vert{}x-y\vert{}^r f(x,y) dx dy$$

• 有些人更喜欢使用 $d\gamma(x, y)$ 而不是 $\gamma(dx, dy)$, 以强调它是勒贝格-斯蒂尔杰斯 (LS) 积分中的微分/积分变量.

• 有些人(包括我)更喜欢使用 $\gamma(dx, dy)$, 以强调在此处 $\gamma$ 是一个以微小矩形作为输入的函数.

• 它们是相同的对象, 只是书写风格不同.

• 约束: 耦合 $\gamma$ 必须以 $P$ 作为其第一个边缘分布, 以 $Q$ 作为其第二个边缘分布. 也就是说:

$$\int \gamma(x,y) dy = p(x) \quad \int \gamma(x,y) dx = q(y)$$

蒙日解

由于基础空间是一维的, 且成本是距离的(严格)凸函数, 因此最优传输问题通常允许解析解, 其中单调耦合的最优性成立.

我们不用处理一般的联合分布 $\gamma$, 而是可以寻找某种可测映射 $T: \mathbb{R} \to \mathbb{R}$, 它将 $X$ 的原始概率测度 $\mu$ 推前 (pushforward) 到 $Y$ 的概率测度 $\nu$. 也就是说:

$$\nu (B) = \mu (T^{-1} (B))$$

最优传输映射由分位数函数给出:

$$T(x) = Q^{-1} (P(x))$$

Wasserstein 度量: 二维情形

然而, 如果每个 $X(i)$ 是一个二维向量而不是标量, 那么简单的单调耦合将不再起作用.

• 事实上, 在 $\mathbb{R}^2$ 上并不存在一个普遍的序关系.