跳转到内容

沃瑟斯坦度量

维基百科,自由的百科全书

沃瑟斯坦度量(英语:Wasserstein metric)又称为沃瑟斯坦距离Wasserstein distance)、坎托罗维奇–鲁宾施泰因度量Kantorovich–Rubinstein metric),在数学中是指某一给定度量空间概率分布之间的距离函数,其名称源于俄裔美国数学家列昂尼德·沃瑟斯坦英语Leonid Vaserstein

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

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

定义

对于一个度量空间,假设上每个博雷尔概率测度都是拉东测度(即该度量空间为拉东空间)。对有限表示上所有有的概率测度的集合,即中存在满足

于是,中两个概率测度之间的沃瑟斯坦距离可定义为

其中表示上所有测度的集合,即的所有耦合英语Coupling (probability)组成的集合。

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

其中表示随机变量期望值下确界则由随机变量的所有联合分布确定,它们分别对应边缘分布

与最优运输问题的联系

x轴与y轴上分别绘有两个一维分布,中间是两者一种可能的联合分布(不唯一),而这一联合分布即定义了之间的一个运输方案。

理解上述定义的一种方法是将其与最优运输问题联系起来。对于空间上的某一质量分布,我们希望以某种方式运输其质量,使其转化同一个空间中的另一分布,即将“土堆”转换为“土堆”。两者的总质量必须相同,因而可以不失一般性地假设是总质量为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.