沃瑟斯坦度量

沃瑟斯坦度量（英語：Wasserstein metric）又称为沃瑟斯坦距离（Wasserstein distance）、坎托罗维奇–鲁宾施泰因度量（Kantorovich–Rubinstein metric），在数学中是指某一给定度量空间${\displaystyle M}$上概率分布之间的距离函数，其名称源于俄裔美国数学家列昂尼德·沃瑟斯坦（英语：Leonid Vaserstein）。

直观而言，可以将每个概率分布都看作${\displaystyle M}$上堆积的单位数量的土堆，则沃瑟斯坦度量便是指将一个土堆变成另一土堆的最小代价，可定义为需要移动的土壤量乘以需要移动的平均距离。这一问题于1781年由法国数学家加斯帕尔·蒙日首次正式提出。基于上述土堆类比，该度量在计算机科学中也被称为推土机距离。

“沃瑟斯坦距离”这一名称是苏联数学家罗兰·多布鲁申（英语：Roland Dobrushin）于1970年提出的，他在沃瑟斯坦关于描述大型自动机系统的马尔可夫过程的工作中了解到了这一概念。^[1]不过早在1939年，另一位苏联数学家列昂尼德·坎托罗维奇就在研究货物的最优运输问题时最早定义了该度量。^[2]因此一些学者认为使用“坎托罗维奇度量”或“坎托罗维奇距离”来称呼此度量更为恰当。

定义

对于一个度量空间${\displaystyle (M,d)}$，假设${\displaystyle M}$上每个博雷尔概率测度都是拉东测度（即该度量空间为拉东空间）。对有限${\displaystyle p\geq 1}$，${\displaystyle P_{p}(M)}$表示${\displaystyle M}$上所有有${\displaystyle p}$阶矩的概率测度${\displaystyle \mu }$的集合，即${\displaystyle M}$中存在${\displaystyle x_{0}}$满足

${\displaystyle \int _{M}d(x,x_{0})^{p}\,\mathrm {d} \mu (x)<\infty .}$

于是，${\displaystyle P_{p}(M)}$中两个概率测度${\displaystyle \mu }$和${\displaystyle \nu }$之间的${\displaystyle p}$阶沃瑟斯坦距离可定义为

${\displaystyle W_{p}(\mu ,\nu ):=\left(\inf _{\gamma \in \Gamma (\mu ,\nu )}\int _{M\times M}d(x,y)^{p}\,\mathrm {d} \gamma (x,y)\right)^{1/p},}$

其中${\displaystyle \Gamma (\mu ,\nu )}$表示${\displaystyle M\times M}$上所有测度的集合，即${\displaystyle \mu }$与${\displaystyle \nu }$的所有耦合（英语：Coupling (probability)）组成的集合。

此外，沃瑟斯坦度量也可等效地定义为

${\displaystyle W_{p}(\mu ,\nu )=\left(\inf \operatorname {\mathbf {E} } {\big [}d(X,Y)^{p}{\big ]}\right)^{1/p},}$

其中${\displaystyle \mathbf {E} [Z]}$表示随机变量${\displaystyle Z}$的期望值，下确界则由随机变量${\displaystyle X}$和${\displaystyle Y}$的所有联合分布确定，它们分别对应边缘分布${\displaystyle \mu }$和${\displaystyle \nu }$。

与最优运输问题的联系

x轴与y轴上分别绘有两个一维分布${\displaystyle \mu }$和${\displaystyle \nu }$，中间是两者一种可能的联合分布（不唯一），而这一联合分布即定义了${\displaystyle \mu }$和${\displaystyle \nu }$之间的一个运输方案。

理解上述定义的一种方法是将其与最优运输问题联系起来。对于空间${\displaystyle X}$上的某一质量分布${\displaystyle \mu (x)}$，我们希望以某种方式运输其质量，使其转化同一个空间中的另一分布${\displaystyle \nu (x)}$，即将“土堆”${\displaystyle \mu }$转换为“土堆”${\displaystyle \nu }$。两者的总质量必须相同，因而可以不失一般性地假设${\displaystyle \mu }$和${\displaystyle \nu }$是总质量为1的概率分布。此外还需假设代价函数

${\displaystyle c(x,y)\mapsto [0,\infty ),}$

表示从点${\displaystyle x}$运输质量到点${\displaystyle y}$的代价。一个从${\displaystyle \mu }$到${\displaystyle \nu }$的运输方案可以用函数${\displaystyle \gamma (x,y)}$来描述，该函数表明从${\displaystyle x}$移动到${\displaystyle y}$的质量。一个运输方案${\displaystyle \gamma (x,y)}$必须满足以下性质

${\displaystyle {\begin{aligned}\int \gamma (x,y)\,\mathrm {d} y=\mu (x),\\\int \gamma (x,y)\,\mathrm {d} x=\nu (y),\end{aligned}}}$

前者表示从某一点${\displaystyle x}$移到其他所有点的土堆总质量必须等于最初该点${\displaystyle x}$上的土堆质量，后者则表示从所有点移到某一点${\displaystyle y}$的土堆总质量必须等于最终该点${\displaystyle y}$上的土堆质量。

这一性质相当于要求${\displaystyle \gamma }$是边缘分布${\displaystyle \mu }$与${\displaystyle \nu }$对应的联合概率分布。于是可得到运输方案${\displaystyle \gamma }$的总代价

${\displaystyle \iint c(x,y)\gamma (x,y)\,\mathrm {d} x\,\mathrm {d} y=\int c(x,y)\,\mathrm {d} \gamma (x,y).}$

方案${\displaystyle \gamma }$并不是唯一的，所有可能的运输方案中代价最低的方案即为最优运输方案。最优运输方案的代价为

${\displaystyle C=\inf _{\gamma \in \Gamma (\mu ,\nu )}\int c(x,y)\,\mathrm {d} \gamma (x,y).}$

如果两点之间移动的代价等于两点之间的距离，那么最小代价则与${\displaystyle W_{1}}$距离等价。

参考文献

1. Vaserstein LN. Markov processes over denumerable products of spaces, describing large systems of automata (PDF). Problemy Peredači Informacii. 1969, 5 (3): 64–72.
2. Kantorovich LV. Mathematical Methods of Organizing and Planning Production. Management Science. 1939, 6 (4): 366–422. JSTOR 2627082. doi:10.1287/mnsc.6.4.366.