从 Minkowski 度量到 Wasserstein 度量

对任意集合 $M$, 我们希望用某个实函数 $$d: (x,y) \mapsto d(x,y)$$ 来表示其中任意两点 $(x,y)$ 的距离, 并称函数 $d$ 为距离函数. 距离不能是负数, 所以我们要求函数值 $d(x,y)$ 总是非负的. 非负性是我们对距离函数的唯一要求.

如果距离函数 $d$ 还满足其它的一些限制, 就称它是集合 $M$ 的度量. 本文先介绍 Minkowski 度量, 然后引出 Hausdorff 度量和 Wasserstein 度量, 它们都可以看成是 Minkowski 度量的推广.

度量和度量空间

称距离函数 $d: M × M \to [0,\infty)$ 为集合 $M$ 的度量, 若距离函数满足:

• 同一性: 对任意 $x,y \in M$, $d(x,y) =0$ 若且唯若 $x=y$;

• 对称性: 对任意 $x,y \in M$, $d(x,y) = d(y,x)$;

• 三角不等式: 对任意 $x,y,z \in M$, $d(x,z) \le d(x,y) + d(y,z)$.

度量的主要直觉是物理世界里两点的 (最短) 距离. 在这个类比下, 同一性和对称性比较容易理解, 三角不等式则对应着 “三角形两边之和大于第三边” 这个几何观察.

如果集合 $M$ 上存在度量 $d$, 就称二元组 $(M, d)$ 为度量空间. 所谓空间, 通常指的是配备了某些结构的集合. 顾名思义, 度量空间就是配备了某个度量的集合.

伪度量和非对称度量

如果距离函数满足对称性和三角不等式, 但违背了同一性, 我们就称它为伪度量 (pseudometric). 对于伪度量, 可以通过定义等价类的方式, 把满足 $d(x,y) = 0$ 的 $x$ 和 $y$ 视为同一类, 从而将其转化为度量.

如果距离函数满足同一性和三角不等式, 但违背了对称性, 就称它为非对称度量. 对于非对称度量 $\hat d(x,y)$, 可定义 $$d (x,y) = \max \{ \hat d(x,y), \hat d(y,x) \}$$ 以此补上对称性, 这样得到的 $d$ 是一个度量. 我们将这个技巧总结为下面的命题. 之后证明 Hausdorff 度量满足三角不等式时会用到这个技巧.

命题. 若 $\hat d(x,y)$ 为集合 $M$ 的非对称度量, 则 $d (x,y) = \max \{ \hat d(x,y), \hat d(y,x) \}$ 为集合 $M$ 的度量.

Minkowski 度量

我们的讨论先聚焦于 Minkowski 度量, 该度量空间中的三角不等式成立性由 Minkowski 不等式保证. 下面先给出 Minkowski 度量的一些例子. 你不必急着验证这些例子都满足度量空间的三个要求, 验证三角不等式通常需要一些技巧, 但这些例子中的三角不等式都是 Minkowski 不等式的直接推论.

Minkowski 度量例 1: 对任意两个有限 $N$-维实数序列: $x=\{ x(i) \}$ 和 $y=\{ y(i) \}$, 令 $$d(x, y) = \sqrt[2]{\sum_{i=1}^N \vert{}x(i) - y(i)\vert{}^2}$$ 即得到传统的欧氏距离空间.

Minkowski 度量例 2: 对任意两个 $N$-维实数序列: $x=\{ x(i) \}$ 和 $y=\{ y(i) \}$, 令 $$d(x, y) = \sqrt[p] {\sum_i | x(i) - y(i) |^p},$$ 它对于任意 $p \ge 1$ 都是一个良定义的距离.

Minkowski 度量例 3: 对任意有限闭区间 $[a,b]$, 令 $C[a,b]$ 表示定义在区间 $[a,b]$ 上的所有连续函数构成的集合. 给定 $C[a,b]$ 中的两个连续函数 $f$ 和 $g$, 令 $$d(f, g) = \sqrt[p] {\int | f(x) - g(x) | ^p \, dx}$$ 它对于任意 $p \ge 1$ 都是一个良定义的距离.

上面三个距离都是 Minkowski 度量. 该度量最广泛使用的情形是 $p = 2$, 也就是通常所说的欧氏距离.

然而, 对于经济学研究者而言, 最有趣的情形是 $p = \infty$: 不同于那些有限的 $p$, 当 $p = \infty$ 时求距离需要求解一个最优化问题.

$p=\infty$ 情形的 Minkowski 度量

当 $p = \infty$ 时, Minkowski 度量仅关注两个向量 (或函数) 在所有点之间的最大距离: $$d(f,g) = \max_{x \in D} \vert{}f-g\vert{} (x)$$ 此时计算 Minkowski 度量需要求解一个最优化问题.

利用夹逼技巧 (和一些代数运算) 不难推导出该表达式是 $d(f, g) = \sqrt[p] {\int | f(x) - g(x) | ^p \, dx}$ 在 $p$ 趋于无穷时的极限. 为保证该最优化问题是良定义的, 我们要求定义域 $D$ 是紧集, 且函数 $f$ 和 $g$ 均连续.

$p=\infty$ 情形的 Minkowski 度量也被称为 Chebyshev 度量. Chebyshev 将该度量 — 即选用最大误差而不是平方误差 — 作为选择逼近多项式的指标, 并发展出关于多项式一致逼近的丰富理论.

对经济学研究者而言, 这个度量也可以理解为最坏情况距离 (worst-case distance), 因为它只考虑最远距离. 此时一个自然的问题是: 我们能否在所有点中考察函数 $f$ 和 $g$ 之间的最小距离 (而不是最大距离), 作为两个函数的距离?

如果我们把函数理解为路径 (或点集), 那么使用最短路径作度量是很自然的想法. 我们接下来将这个想法进一步完善.

Hausdorff 度量

有限维欧氏空间中, 计算一个点 ($y$) 到一个紧集 ($X$) 的距离时, 一般会使用点到集合的最短路径: $$d(y, X) = \min_{x \in X} d(y,x)$$

上述函数 $d$ 是良定义的, 但它并不是一个度量, 因为度量要求其定义域必须具有对称性: $d: X \times X \to \mathbb{R}$. 换言之, 我们需要将上述点到集合的距离推广到集合到集合的距离.

要实现该推广, 我们可以借鉴 Chebyshev 度量中的最坏情况思想. 考虑如下算法:

1. 对于任意两个紧集 $X \in \mathbb{R}^N$ 和 $Y \in \mathbb{R}^N$:

   • 对所有 $x \in X$, 考虑其到集合 $Y$ 的最短距离 $d(x, Y)$;

   • 对所有 $y \in Y$, 考虑其到集合 $X$ 的最短距离 $d(y, X)$.

2. 求上述所有距离的上确界 (sup), 并将该上确界作为集合 $X$ 和 $Y$ 的距离.

这就是 Hausdorff 度量, 它考虑所有点到集合距离的最坏可能情形: $$d_H (X,Y) := \sup \Big ( \{ d(x, Y) : x \in X \} ∪ \{ d(y, X) : y \in Y \} \Big)$$

为了揭示 Hausdorff 度量定义背后的一些结构, 我们

验证三角不等式

我们接下来验证 Hausdorff 度量满足三角不等式. 令 $d_M(x,y)$ 表示 Minkowski 度量, 我们将函数 $d$ 的第一个参数推广到点集, 定义点到集合的距离为: $$d(x, Y) := \sup_{y \in Y} d(x,y).$$ 对任意两个紧集 $X, Y$, 考虑如下辅助函数: $$\hat d (X,Y) = \sup d(x,Y)$$

注意, 每个 $d(x, Y)$ 以及 $d(y, X)$ 的值本身都是一个最小化问题的解. 因此, 寻找 Hausdorff 距离是一个极大极小 (maxmin) 问题. 换言之, Hausdorff 距离就是以下两个极大极小值中较大的一个: $$\max_{y \in Y} \, \min_{x \in X} \, d(x,y), \quad \max_{x \in X} \, \min_{y \in Y} \, d(x,y).$$

从有序向量到无序向量

Hausdorff 度量可以看成 Minkowski 度量的推广: Minkowski 度量适用于点, Hausdorff 度量适用于点集. 并且, 这个推广具有一定的 “组合味”, 具体而言:

• 从 Minkowski 度量出发, 它确定了两个点的距离 $d(x, y)$;

• 然后, 通过考察最短路径, 定义点 $x$ 与集合 $Y$ 之间的距离 $d(x, Y)$

• 最后, 考察所有 (点, 集) 对的距离, 并将其最大值定义为两个集合之间的距离.

Wasserstein 度量是 Minkowski 度量的另一种推广, 因为我们希望该度量适用于无序元组, 而不仅仅是有序向量.

Wasserstein 度量: 一维、有限观测

无序元组的一个很好例子是经验分布.

例如, 我们有两个随机变量 $X$ 和 $Y$ 的 $n$ 个观测值. 将这些观测值记为

$$\{ X(i), Y(i) \}_{i=1} ^n$$

我们应当如何衡量 $\{X(i)\}$ 与 $\{Y(i)\}$ 之间的距离?显然, Minkowski 距离在这里并不适用, 因为它将 $\{X(i)\}$ 视为有序向量. 然而, 我们可以自由地重新排列 $\{X(i)\}$(或 $\{Y(i)\}$)中的观测值, 这并不会改变我们的数据.

• 事实上, 这里一个良定义的度量不应当考虑每个数字的顺序.

• $(1, 3, 4)$ 和 $(3, 4, 1)$ 应当被视为相同, 它们之间的距离为零.

基于这种思路, 我们应当考虑:

1. $\{X(i)\}$ 与 $\{Y(i)\}$ 的每个可能排列之间的 Minkowski 距离.

2. $\{Y(i)\}$ 与 $\{X(i)\}$ 的每个可能排列之间的 Minkowski 距离.

3. 使用上述距离中的最短者作为最终度量.

不难验证, 第 (2) 步是冗余的: 我们只需要第 (1) 步就能找到 $\{X(i)\}$ 与 $\{Y(i)\}$ 之间的距离.

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

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

作为最优传输的 Wasserstein 度量

此前, 我们将 Wasserstein 度量动机化为 Minkowski 度量从有序向量向无序集合的推广.

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

最优传输的设定:

• 货物: 将每个观测值 $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$ 上并不存在一个普遍的序关系.