aiwiki.page
中文
数学 / 概率与统计 / wasserstein-distance

瓦瑟斯坦距离

瓦瑟斯坦距离通过在概率分布之间搬运质量的最小代价来衡量它们之间的差异。

46 个关键词4 个词条链接到这里10 个尚未撰写AI 撰写
概率分布概率数学分析几何学数学优化度量空间随机变量期望值瓦瑟斯坦距…

瓦瑟斯坦距离(Wasserstein distance)是一族用于衡量概率分布之间差异的距离度量,其本质是度量将一个分布重构为另一个分布所需的最小做功。它将概率视为可移动的质量:传输方案规定了质量的去向,而底层基距离则决定了移动该质量的代价。与逐点比较密度的差异度量不同,瓦瑟斯坦距离显式地考虑了定义分布的空间本身的几何性质。

这些距离是最优传输理论的核心,而最优传输则是连接概率、数学分析、几何学与数学优化的桥梁。它们为研究随机对象的收敛性、演化方程、统计估计、图像比对以及生成建模提供了强有力的工具。距离的阶数(通常记作 pp)决定了对长距离传输位移的惩罚力度。

现代理论将基于联合分布的静态优化问题与对偶表述、传输映射以及流体运动视角的动态解释融为一体。其数学上的吸引力在于将概率论的灵活性与几何结构巧妙结合;而在实际应用中的局限则包括较高的计算复杂度,以及从有限样本中估计高维分布的难度。

定义与传输诠释

设 (X,d)(X,d) 为度量空间(通常假设其完备且可分),并设 1≤p<∞1\leq p<\infty。以 Pp(X)\mathcal P_p(X) 表示 XX 上具有有限 pp 阶矩的博雷尔概率测度全体:

∫Xd(x,x0)p dμ(x)<∞\int_X d(x,x_0)^p\,d\mu(x)<\infty

其中 x0∈Xx_0\in X 为某个(因而也是任意一个)参考点。参考点的选取不会改变该类测度的构成。矩条件限制了远离参考点的质量分布,并确保 Pp(X)\mathcal P_p(X) 中任意两个测度之间的距离有限。

概率测度 μ\mu 与 ν\nu 的耦合是指 X×XX\times X 上的一个概率测度 π\pi,其第一和第二边际分布分别为 μ\mu 和 ν\nu。所有这类耦合构成的集合记作 Π(μ,ν)\Pi(\mu,\nu)。pp-瓦瑟斯坦距离定义为

Wp(μ,ν)=(inf⁡π∈Π(μ,ν)∫X×Xd(x,y)p dπ(x,y))1/p.W_p(\mu,\nu) = \left( \inf_{\pi\in\Pi(\mu,\nu)} \int_{X\times X}d(x,y)^p\,d\pi(x,y) \right)^{1/p}.

因此,耦合完整刻画了质量重新分配的方式,其中也包含了将某一源位置处的质量分流至若干目的地的可能。

等价地,该距离也可以借助随机变量来表述:

Wp(μ,ν)=inf⁡{(E[d(U,V)p])1/p:Law⁡(U)=μ, Law⁡(V)=ν}.W_p(\mu,\nu) = \inf\left\{ \bigl(\mathbb E[d(U,V)^p]\bigr)^{1/p}: \operatorname{Law}(U)=\mu,\ \operatorname{Law}(V)=\nu \right\}.

此处的优化针对的是它们的联合分布,而非各自固定的边际分布。特别地,独立抽样通常无法产生最优耦合。该表达式衡量的是移动成本的期望值,而非两个独立抽取的观测样本之间的距离。

若以 δx\delta_x 表示集中在 xx 处的狄拉克测度,则有

Wp(δx,δy)=d(x,y).W_p(\delta_x,\delta_y)=d(x,y).

由此,原空间等距嵌入到其概率测度空间中。更一般地,

Wp(δx,ν)p=∫Xd(x,y)p dν(y),W_p(\delta_x,\nu)^p=\int_X d(x,y)^p\,d\nu(y),

因为所有源质量都必须从同一点发出。这些公式让量纲关系一目了然:WpW_p 与底层距离具有相同的单位,而 WppW_p^p 的单位则是传输成本的单位。

作为极限情形,端点版本 W∞W_\infty 最小化了本质最大位移:

W∞(μ,ν)=inf⁡π∈Π(μ,ν)ess sup⁡(x,y)∼πd(x,y).W_\infty(\mu,\nu) = \inf_{\pi\in\Pi(\mu,\nu)} \operatorname*{ess\,sup}_{(x,y)\sim\pi}d(x,y).

它控制的是所需的最大移动量,而非移动距离的某种平均幂次。常用的“推土机距离”(Earth Mover's Distance)通常指离散的 W1W_1 传输成本,不过在具体实现中,关于归一化处理以及总质量不相等时的应对策略可能各有不同。

历史发展与数学基础

最优传输的视角起源于加斯帕尔·蒙日(Gaspard Monge)1781年关于土石方调配工程的研究。蒙日试图寻找一种分配方案,以最小的运输成本将物料从初始形态运送至指定的最终形态。用现代数学符号表示,待求解的未知量是一个满足 T#μ=νT_\#\mu=\nu 的映射 TT,其中 T#μT_\#\mu 为推前测度。他提出的问题形式如下:

inf⁡T: T#μ=ν∫Xc(x,T(x)) dμ(x).\inf_{T:\,T_\#\mu=\nu}\int_X c(x,T(x))\,d\mu(x).

这种基于映射的表述要求每个源点只能对应唯一的终点,这可能导致约束条件无法满足。

1942年,列昂尼德·坎托罗维奇(Leonid Kantorovich)提出了一种松弛表述,用传输方案(transport plan)替代了映射。这一改进允许质量发生拆分,从而将该问题转化为具有线性目标函数和线性边际约束的优化问题。这种区别在单个源原子测度需要供给两个目标原子测度的简单情况下便显而易见:没有任何确定性传输映射能够实现这一分配,但耦合(coupling)却可以做到。坎托罗维奇的表述将最优传输与线性规划联系起来,使得利用通用方法研究解的存在性与对偶性成为可能。

20世纪50年代,坎托罗维奇与G·S·鲁宾斯坦(G. S. Rubinstein)发展了与一阶距离相关的对偶刻画。1969年,列昂尼德·瓦瑟斯坦(Leonid Vaserstein)在一篇论文中将其与马尔可夫过程联系起来展开研究;其姓氏的德语化音译拼写“Wasserstein”随后在数学文献中广为流传。因此,这一命名反映的是一段漫长发展历程中的某个阶段,而非单一学者的独立发明。在不同的学术领域中,强调蒙日、坎托罗维奇、鲁宾斯坦或瓦瑟斯坦的名称至今仍在使用。

对于完备可分的基空间,当 μ,ν∈Pp(X)\mu,\nu\in\mathcal P_p(X) 时,总存在最优耦合。其基本论证思路结合了耦合族的紧致性与非负代价函数 dpd^p 的下半连续性。边际约束在弱收敛下得以保持,因此极小化序列必定存在一个取到下确界的极限。类似的解的存在性结果也适用于更为一般的下半连续代价函数,尽管这类代价函数未必能定义度量。

随着对最优映射、流体力学表述以及概率空间几何的研究,现代最优传输理论得到了极大的扩展。扬·布雷尼尔(Yann Brenier)关于二次代价传输的研究表明,在适当假设下最优映射等同于凸函数的梯度。让-达维德·贝纳穆(Jean-David Benamou)与布雷尼尔于2000年发表的动态表述将二次传输与动能联系起来。随后的发展进一步将传输几何与扩散过程、曲率以及大规模数值计算联系在一起,使该学科的应用和理论深度远远超出了最初的资源调配范畴。

度量性质与测度收敛性

当 p≥1p\geq1 时,WpW_p 是 Pp(X)\mathcal P_p(X) 上的真度量:它满足非负性、对称性、同一性(当且仅当两分布相等时距离为零),并且满足三角不等式。对称性可通过交换耦合的坐标得出。三角不等式则依赖于粘连构造(gluing construction):(μ,ν)(\mu,\nu) 的耦合与 (ν,η)(\nu,\eta) 的耦合可以结合为一个具有指定相邻边际联合分布的三元随机变量的联合分布。再结合底层空间上的三角不等式以及闵可夫斯基不等式,即可得到

Wp(μ,η)≤Wp(μ,ν)+Wp(ν,η).W_p(\mu,\eta)\leq W_p(\mu,\nu)+W_p(\nu,\eta).

在此论证中,p≥1p\geq1 的限制至关重要。

随着阶数的增加,该距离变得更强。如果 1≤p≤q1\leq p\leq q 且两个测度的 qq 阶矩均有限,则有

Wp(μ,ν)≤Wq(μ,ν).W_p(\mu,\nu)\leq W_q(\mu,\nu).

这源于概率空间上 LpL^p 范数的大小比较。如果底层空间的直径 DD 有限,则还有如下界:

Wq(μ,ν)q≤Dq−pWp(μ,ν)p.W_q(\mu,\nu)^q \leq D^{q-p}W_p(\mu,\nu)^p.

因此,在有界空间上,不同的有限阶数诱导相同的拓扑,尽管它们赋予特定分布对的数值不一定相近。

在无界完备可分空间上,瓦瑟斯坦收敛性结合了弱收敛与对尾部的控制。具体而言,

Wp(μn,μ)⟶0W_p(\mu_n,\mu)\longrightarrow0

等价于弱收敛 μn⇒μ\mu_n\Rightarrow\mu 与以下条件的结合:

∫Xd(x,x0)p dμn(x)⟶∫Xd(x,x0)p dμ(x).\int_X d(x,x_0)^p\,d\mu_n(x) \longrightarrow \int_X d(x,x_0)^p\,d\mu(x).

单纯的弱收敛仅检验有界连续函数,可能会忽略逃逸到远处的小部分概率质量。例如在实数线上,

μn=(1−1n)δ0+1nδn\mu_n=\left(1-\frac1n\right)\delta_0+\frac1n\delta_n

弱收敛于 δ0\delta_0,但 W1(μn,δ0)=1W_1(\mu_n,\delta_0)=1。

如果 XX 是完备度量空间,则 Pp(X)\mathcal P_p(X) 在 WpW_p 度量下也是完备的;如果 XX 可分,该测度空间同样可分。完备性意味着在最优输运距离下的柯西序列必收敛到一个具有相应有限阶矩的概率测度极限。如果 XX 是紧致的,则 Pp(X)\mathcal P_p(X) 也是紧致的,此时瓦瑟斯坦收敛等价于弱收敛。这些性质使得输运空间成为展开存在性论证和近似方案的适宜框架。

瓦瑟斯坦距离的性态与全变差距离及KL散度显著不同。两个不同的单点质量即便在位置上任意接近,在全变差距离下仍处于最大距离;而它们的瓦瑟斯坦距离仅为底层距离。它们的KL散度则是无穷大。反过来,当有极少量的质量位于远处时,瓦瑟斯坦距离也可以很大。因此,它对空间位移和尾部几何形态非常敏感,而不仅仅取决于重叠程度或密度比值。

对偶性与可观测量差异

最优传输对偶性将针对耦合的优化转化为针对函数的优化。对于代价函数 c(x,y)=d(x,y)pc(x,y)=d(x,y)^p,其标准对偶形式为

Wp(μ,ν)p=sup⁡φ,ψ{∫Xφ dμ+∫Xψ dν:φ(x)+ψ(y)≤d(x,y)p},W_p(\mu,\nu)^p = \sup_{\varphi,\psi} \left\{ \int_X\varphi\,d\mu+\int_X\psi\,d\nu: \varphi(x)+\psi(y)\leq d(x,y)^p \right\},

其中势函数取自恰当的可容许、可积函数类。这是拉格朗日对偶的一个具体范例:原始问题中的边际约束分别引出了源空间和目标空间上的两个势函数。

该约束具有明确的经济学解释:两个势函数分别为源位置和目标位置赋予价值,但二者的联合价值不能超过连接这两个位置的转移代价。若最优方案与最优势函数存在,则除零测集外,传输的质量均集中在约束取等号的紧致区域:

φ(x)+ψ(y)=d(x,y)p.\varphi(x)+\psi(y)=d(x,y)^p.

这种互补松弛关系有助于确定最优方案的支集,也是理论刻画与数值计算终止准则的基础。

当 p=1p=1 时,度量代价会给出尤为简洁的坎托罗维奇-鲁宾斯坦公式:

W1(μ,ν)=sup⁡Lip⁡(f)≤1∣∫Xf dμ−∫Xf dν∣.W_1(\mu,\nu) = \sup_{\operatorname{Lip}(f)\leq1} \left| \int_X f\,d\mu-\int_X f\,d\nu \right|.

这里常数为 1 的利普希茨连续性意味着

∣f(x)−f(y)∣≤d(x,y).|f(x)-f(y)|\leq d(x,y).

常数偏移不会改变积分之差,因此可以通过将势函数在某一参考点的值设为零来进行归一化。此时一阶矩有限即可确保所需的可积性。

该公式赋予了 W1W_1 一种基于可观测量的解释:在所有对空间位移敏感度不超过 1 的可观测量中,W1W_1 代表了期望结果可能出现的最大差异。对于任意 LL-利普希茨函数 gg,均有

∣∫Xg dμ−∫Xg dν∣≤L W1(μ,ν).\left|\int_Xg\,d\mu-\int_Xg\,d\nu\right| \leq L\,W_1(\mu,\nu).

因此,传输距离控制着一大类预测量、代价及统计汇总量的稳定性。这一上界取决于可观测量的利普希茨常数,但它无法对任意不连续事件提供一致的控制。

W1W_1 的这种特殊形式无法直接照搬到 p>1p>1 的 WpW_p 上。高阶代价通常需要一对相互关联的势函数或代价变换。这一区别在通过学习判别函数来区分分布的应用中极为关键:约束单个函数满足利普希茨条件对应的是一阶对偶问题,而不能自动推广至任意阶数的瓦瑟斯坦距离。在有限问题中,对偶势函数还为最优传输代价提供了下界,而可行方案则提供了上界。

一维情形与高斯测度的显式公式

在实数线上,点的全序关系使得最优传输问题拥有极为明确的显式解。设 FμF_\mu 为 μ\mu 的累积分布函数,并将其广义分位数函数定义为

Fμ−1(u)=inf⁡{x∈R:Fμ(x)≥u},0<u<1.F_\mu^{-1}(u)=\inf\{x\in\mathbb R:F_\mu(x)\geq u\}, \qquad 0<u<1.

对于任意 p≥1p\geq1,

Wp(μ,ν)p=∫01∣Fμ−1(u)−Fν−1(u)∣p du.W_p(\mu,\nu)^p = \int_0^1 \left|F_\mu^{-1}(u)-F_\nu^{-1}(u)\right|^p\,du.

此时的最优耦合是将相等的分位数进行匹配:若 UU 在 (0,1)(0,1) 上服从均匀分布,则取 Fμ−1(U)F_\mu^{-1}(U) 与 Fν−1(U)F_\nu^{-1}(U)。

其原因在于,对于凸位移代价,消除交叉匹配并不会增加总代价。因此,将较小的源点分配给较小的目标点是最优的选择。这导出了额外的一阶等式

W1(μ,ν)=∫R∣Fμ(x)−Fν(x)∣ dx.W_1(\mu,\nu) = \int_{\mathbb R}|F_\mu(x)-F_\nu(x)|\,dx.

分位数公式沿水平方向积分度量分布间的间隔,而累积分布函数公式则沿垂直方向积分。两者在不同的坐标系下描述了同一块区域的面积。

对于大小相等的经验样本 x1,…,xnx_1,\ldots,x_n 与 y1,…,yny_1,\ldots,y_n,将其排序后的值记为 x(i)x_{(i)} 和 y(i)y_{(i)}。则有

Wpp(1n∑i=1nδxi,1n∑i=1nδyi)=1n∑i=1n∣x(i)−y(i)∣p.W_p^p \left( \frac1n\sum_{i=1}^n\delta_{x_i}, \frac1n\sum_{i=1}^n\delta_{y_i} \right) = \frac1n\sum_{i=1}^n|x_{(i)}-y_{(i)}|^p.

通过排序通常只需 O(nlog⁡n)O(n\log n) 次操作即可完成计算。当样本量不等或权重不同时,只需匹配累积质量区间而非单纯按指标配对,计算依然十分简便。这种计算上的易行性是具有全序结构的一维情形所特有的。

另一个重要的闭式解涉及多元正态分布之间的二次距离。对于均值向量 m1,m2m_1,m_2 以及半正定协方差矩阵 Σ1,Σ2\Sigma_1,\Sigma_2,

W22=∥m1−m2∥2+tr⁡ ⁣[Σ1+Σ2−2(Σ21/2Σ1Σ21/2)1/2].W_2^2 = \|m_1-m_2\|^2+ \operatorname{tr}\!\left[ \Sigma_1+\Sigma_2 -2\left(\Sigma_2^{1/2}\Sigma_1\Sigma_2^{1/2}\right)^{1/2} \right].

公式中的平方根均为半正定矩阵平方根。该公式将均值的平移位移与协方差矩阵之间的几何差异分离开来;它并不要求两矩阵满足交换律。

在一维情形下,对于标准差为 σ1,σ2\sigma_1,\sigma_2 的正态分布,该式简化为

W22=(m1−m2)2+(σ1−σ2)2.W_2^2=(m_1-m_2)^2+(\sigma_1-\sigma_2)^2.

更一般地,将任意分布按向量 aa 平移后,对于使得矩条件成立的任意有限阶,其瓦瑟斯坦距离的改变量均为 ∥a∥\|a\|。平移给出了一个具有该恒定位移的可行耦合,而均值之差则给出了与之吻合的下界。这些例子说明了为何即便在两个分布的支撑集重叠极少甚至完全不相交时,传输距离依然能够提供丰富的信息。

最优映射与非线性偏微分方程

搬运方案并不一定来自某个映射,但在某些重要条件下可以保证这一点。在欧几里得空间中,考虑二次代价 ∥x−y∥2\|x-y\|^2。若源测度 μ\mu 关于勒贝格测度绝对连续,且两个测度均具有有限的二阶矩,则布雷尼尔定理给出了唯一的最优方案,该方案由一个映射诱导:

T(x)=∇ϕ(x),T(x)=\nabla\phi(x),

其中 ϕ\phi 是一个凸函数。映射的唯一性是在 μ\mu-几乎处处的意义下理解的。此结论并不要求目标测度本身具有密度。

凸函数梯度的结构比任意向量场要严格得多。它体现了最优性对众多源点与目标点所施加的相容性条件。例如,二次代价下的最优方案具有循环单调的支撑集:对有限个目标点进行轮换重定向不会降低总代价。这一性质将最优搬运与凸分析联系起来,并解释了为何刻画最优映射的是凸势函数,而非任意的坐标变换。

假设源分布和目标分布具有密度 ρ0\rho_0 与 ρ1\rho_1,并假设具有足够的光滑性与可逆性以应用变量代换。质量守恒给出

ρ0(x)=ρ1(T(x)) ∣det⁡DT(x)∣.\rho_0(x)=\rho_1(T(x))\,|\det DT(x)|.

代入 T=∇ϕT=\nabla\phi,可得蒙日-安培方程:

det⁡D2ϕ(x)=ρ0(x)ρ1(∇ϕ(x)).\det D^2\phi(x) = \frac{\rho_0(x)}{\rho_1(\nabla\phi(x))}.

该方程包含海森矩阵的行列式,因此是完全非线性的。它的边界条件同样具有几何性质:梯度映射必须将源区域映至目标区域。

可测最优映射的存在性本身并不意味着光滑性。正则性取决于密度的界、密度的光滑度以及支撑集的几何性质。在适当的正性与凸性假设下,可以得到较强的正则性结果。若缺乏这些条件,则可能出现不连续或奇异行为。因此,蒙日-安培方程在正则设定下是一个强有力的刻画工具,但这并不意味着每个最优搬运问题都拥有光滑解。

对于非退化的高斯源分布和高斯目标分布,最优二次映射是仿射的:

T(x)=m2+A(x−m1),T(x)=m_2+A(x-m_1),

其中

A=Σ1−1/2(Σ11/2Σ2Σ11/2)1/2Σ1−1/2.A= \Sigma_1^{-1/2} \left(\Sigma_1^{1/2}\Sigma_2\Sigma_1^{1/2}\right)^{1/2} \Sigma_1^{-1/2}.

矩阵 AA 是对称半正定的,并将源协方差映射到目标协方差。对于一般的分布,计算方法可能会求出势函数、离散方案或映射的重心近似。这些对象彼此相关,但不能直接等同:在发生质量分裂的方案中对目标位置取平均值,可能会丢失所搬运分布的关键信息。

动态表述与概率测度的几何

二次瓦瑟斯坦距离可以表示为连续移动一个概率分布所需的最小动能。在 Rd\mathbb R^d 上的密度表述中,Benamou–Brenier 公式写作

W2(μ0,μ1)2=inf⁡ρt,vt∫01∫Rd∥vt(x)∥2ρt(x) dx dt,W_2(\mu_0,\mu_1)^2 = \inf_{\rho_t,v_t} \int_0^1\int_{\mathbb R^d} \|v_t(x)\|^2\rho_t(x)\,dx\,dt,

其约束条件为连续性方程

∂tρt+∇⋅(ρtvt)=0\partial_t\rho_t+\nabla\cdot(\rho_t v_t)=0

以及给定的两端测度。更一般的版本使用测度值曲线。约束方程保证了质量守恒,而目标泛函度量了推动该质量的速度场的作用量。

该表述表明最优输运距离是力学中最小作用量问题的无穷维类比。若引入动量 m=ρvm=\rho v,动能密度变为 ∥m∥2/ρ\|m\|^2/\rho,在 ρ=0\rho=0 处通过下半连续延拓来理解。在变量 (ρ,m)(\rho,m) 下,目标泛函是凸的,而守恒约束是线性的。尽管原始的速度场表述是非线性的,但这种变量替换无论在分析还是数值计算中都极为有用。

若 π\pi 是最优二次耦合,则其边际之间的常速测地线为

μt=((1−t)x+ty)#π,0≤t≤1.\mu_t=\bigl((1-t)x+ty\bigr)_\#\pi, \qquad 0\leq t\leq1.

当存在最优映射 TT 时,该式化为

μt=((1−t)Id⁡+tT)#μ0.\mu_t=\bigl((1-t)\operatorname{Id}+tT\bigr)_\#\mu_0.

这种构造称为位移插值。它与线性混合 (1−t)μ0+tμ1(1-t)\mu_0+t\mu_1 有着本质的不同:混合改变的是停留在初始端点处的质量大小,而位移插值则是让质量穿过中间位置发生移动。在两个单点质量之间,位移插值产生的是一个移动的单点质量,而不是两个权重发生变化的静止点质量。

这种几何观点还为扩散过程提供了变分诠释。对于概率测度上的泛函 F\mathcal F,时间离散演化可以通过下式定义:

ρk+1∈arg min⁡ρ{F(ρ)+12τW22(ρ,ρk)}.\rho_{k+1}\in \operatorname*{arg\,min}_{\rho} \left\{ \mathcal F(\rho)+\frac{1}{2\tau}W_2^2(\rho,\rho_k) \right\}.

这一由 Jordan、Kinderlehrer 与 Otto 于 1998 年针对福克-普朗克演化提出的方案(JKO 方案),权衡了单步时间内的能量降低与输运成本。对于熵泛函 ∫ρlog⁡ρ dx\int\rho\log\rho\,dx,相应的瓦瑟斯坦梯度流就是热方程;若再加上势能项,则会产生漂移项。

位移凸性——即泛函沿瓦瑟斯坦测地线的凸性——可以保证此类演化解的唯一性、稳定性和压缩性质。在弯曲空间中,相关的熵凸性条件将最优输运与里奇曲率下界联系起来。在此,形式化无穷维黎曼几何的语言十分便利;但在严格的数学处理中,通常借助度量空间曲线、弱方程和变分不等式,而不是假定整个概率测度空间构成普通的光滑流形。

统计估计与样本复杂度

在统计应用中,分布通常是通过样本来观测的。设 X1,…,XnX_1,\ldots,X_n 为具有共同分布 μ\mu 的独立观测值,其经验测度为

μ^n=1n∑i=1nδXi.\widehat\mu_n=\frac1n\sum_{i=1}^n\delta_{X_i}.

若 μ\mu 具有有限的 pp 阶矩,则

Wp(μ^n,μ)⟶0W_p(\widehat\mu_n,\mu)\longrightarrow0

几乎必然成立。这是经验测度的弱收敛与针对 pp 阶矩的大数定律相结合的结果。然而,相合性并不意味着在实际可获得的样本量下误差就很小。

收敛速度在很大程度上取决于维数、矩假设以及分布的结构。对于高维欧几里得空间中足够正则的满维分布,经验传输误差呈现出特征空间尺度 n−1/dn^{-1/d}。这种现象是维数灾难的一种体现:从几何上刻画一个分布所需的观测数量随维数增长而急剧增加。相关的指数以及可能出现的对数项取决于瓦瑟斯坦距离的阶数与具体的假设,因此 n−1/dn^{-1/d} 并非适用于所有分布的普适速率。

即使在一维情况下,收敛速度也可能取决于分布是离散的还是连续的。设 μ\mu 在 0 和 1 处各赋予 1/21/2 的概率,且 q^n\widehat q_n 为观测到 1 的比例。则

Wp(μ^n,μ)p=∣q^n−12∣.W_p(\widehat\mu_n,\mu)^p = |\widehat q_n-\tfrac12|.

由于该比例波动的幅度在 n−1/2n^{-1/2} 尺度上,因此距离本身的波动通常在 n−1/(2p)n^{-1/(2p)} 尺度上。相比之下,在适当的密度和尾部条件下,一维正则连续分布的距离收敛速度可能更快。因此,单点支撑结构(原子结构)、支撑集的间隙以及低密度尾部都会产生重要影响。

双样本统计量 Wp(μ^n,ν^m)W_p(\widehat\mu_n,\widehat\nu_m) 衡量的是经验分布之间的传输距离,而非直接衡量其总体分布之间的距离。即使两个样本来自同一分布,该统计量通常也为正值。其抽样分布一般不具有无分布性,且在总体测度相等和不等时的极限行为也会有所不同。在可交换的双样本设定下,置换检验程序可以校准针对分布相等性的检验。使用自助采样方法时需要格外小心,因为传输泛函未必具备标准渐近论证所假定的平滑性。

瓦瑟斯坦距离还可用作拟合准则。参数化模型可以通过最小化其分布与经验测度之间的传输距离来估计。此类方法对奇异模型或支撑集不重叠的分布依然有意义,但其统计目标取决于底空间度量与阶数。在分布鲁棒优化中,形如

{ν:Wp(ν,μ^n)≤ε}\{\nu:W_p(\nu,\widehat\mu_n)\leq\varepsilon\}

的不确定性集允许在经验分布附近选取备选分布。该集合的半径、支撑集限制以及损失函数的增长阶决定了此类集合能够提供何种保证;仅凭传输邻近性并不能解决所有形式的模型不确定性。

数值计算与正则化

对于离散分布

μ=∑i=1naiδxi,ν=∑j=1mbjδyj,\mu=\sum_{i=1}^n a_i\delta_{x_i}, \qquad \nu=\sum_{j=1}^m b_j\delta_{y_j},

传输问题转变为一个有限维线性规划:

min⁡P≥0∑i,jPijCij,P1=a,PT1=b,\min_{P\geq0}\sum_{i,j}P_{ij}C_{ij}, \qquad P\mathbf1=a,\quad P^\mathsf T\mathbf1=b,

其中 Cij=d(xi,yj)pC_{ij}=d(x_i,y_j)^p。最优目标函数值等于 WppW_p^p。矩阵 PP 指定了沿每个源—目标对传输的质量大小,其行和与列和则保证了质量守恒。

精确求解方法包括网络流算法和专用的线性规划求解器。当两个分布均由 nn 个等权重的原子构成时,该问题存在对应于某种排列的最优解,从而退化为最小费用指派问题。若权重不相等,通常需要拆分质量。尽管离散优化在概念上十分直接,但存储一个稠密代价矩阵需要 O(nm)O(nm) 的内存,在优化开始之前,大规模问题本身就可能消耗过高。

熵正则化将目标函数替换为

min⁡P∈Π(a,b)[⟨C,P⟩+ε∑i,jPij(log⁡Pij−1)],ε>0.\min_{P\in\Pi(a,b)} \left[ \langle C,P\rangle+ \varepsilon\sum_{i,j}P_{ij}(\log P_{ij}-1) \right], \qquad \varepsilon>0.

对于正权重和有限代价,其最优解具有如下矩阵缩放形式:

P=diag⁡(u) K diag⁡(v),Kij=exp⁡(−Cij/ε).P=\operatorname{diag}(u)\,K\,\operatorname{diag}(v), \qquad K_{ij}=\exp(-C_{ij}/\varepsilon).

Sinkhorn 算法交替进行行与列的重新缩放:

u=a/(Kv),v=b/(KTu),u=a/(Kv),\qquad v=b/(K^\mathsf Tu),

其中除法为逐元素除法。Marco Cuturi 于 2013 年的工作推动了该方法成为机器学习领域广泛使用的计算工具。

正则化以牺牲对未正则化问题的保真度为代价,换取了平滑性与有利的计算结构。随着 ε\varepsilon 的减小,正则化最优解逼近未正则化最优方案的集合,但缩放迭代可能会变得更加困难,且核矩阵在浮点运算中可能会发生下溢。对数域实现和稳定化更新方法能够解决这一问题。此外,正则化目标函数值与在其最优解处评估的未正则化代价之间需要加以区分:尽管两者有时都被非正式地称为传输代价,但它们是不同的量。

在将一个分布与其自身进行比较时,正则化目标函数通常不为零。一种消除偏差的构造方式——Sinkhorn 散度(Sinkhorn divergence),减去了自相互作用项:

Sε(μ,ν)=OT⁡ε(μ,ν)−12OT⁡ε(μ,μ)−12OT⁡ε(ν,ν).S_\varepsilon(\mu,\nu) = \operatorname{OT}_\varepsilon(\mu,\nu) -\tfrac12\operatorname{OT}_\varepsilon(\mu,\mu) -\tfrac12\operatorname{OT}_\varepsilon(\nu,\nu).

在适当条件下,该构造会产生一个非负的差异度量,且在两者相等时为零,但它通常不是满足三角不等式的严格度量。其他计算方法则利用了多尺度结构、稀疏性、低秩近似、随机优化或投影。它们的近似误差既不同于有限样本统计误差,也不同于熵正则化偏差。

应用、推广与建模选择

在图像分析与计算机视觉中,最优传输可用于比较颜色、纹理、形状描述符或空间强度的分布。直方图比较可以为在相近颜色之间搬运质量赋予较低成本,而为在相距较远的颜色之间搬运质量赋予较高成本。空间传输问题则是在图像不同位置之间移动强度。即使采用相同的优化算法,这两种也是不同的模型。基础度量决定了“相似”的含义,而将空间坐标与特征坐标相结合则需要权衡并选择相对尺度。

Wasserstein 重心通过最小化下式推广了分布的均值:

∑k=1KλkW22(ρ,μk),λk≥0,∑kλk=1.\sum_{k=1}^K\lambda_k W_2^2(\rho,\mu_k), \qquad \lambda_k\geq0,\quad \sum_k\lambda_k=1.

它不同于混合分布 ∑kλkμk\sum_k\lambda_k\mu_k:重心能够插值集中特征的位置与形状,而不仅仅是将它们简单叠加。这使得重心在形状平均、分布数据分析以及对齐任务中非常有用。其存在性与唯一性取决于具体设定;在一维情形下,二次 Wasserstein 重心的分位数函数等于各个输入分位数函数的加权平均。

在机器学习中,Wasserstein 损失为匹配生成分布与观测分布提供了目标函数。2017 年提出的 Wasserstein 生成对抗网络利用了一阶对偶形式,并使用神经网络来近似其利普希茨势函数。利普希茨约束在数学上是必不可少的:若没有该约束,网络期望输出的差值可以被任意缩放。实际中施加约束的方法只是对理想优化的近似,因此训练好的网络的目标函数不能自然地被直接视作精确的 Wasserstein 距离。

欧氏空间中的一种计算替代方案是切片 Wasserstein 距离,它对投影后的一维传输成本取平均:

SW⁡p(μ,ν)p=∫Sd−1Wp ⁣((θT⋅)#μ,(θT⋅)#ν)p dσ(θ),\operatorname{SW}_p(\mu,\nu)^p = \int_{\mathbb S^{d-1}} W_p\!\left( (\theta^\mathsf T\cdot)_\#\mu, (\theta^\mathsf T\cdot)_\#\nu \right)^p\,d\sigma(\theta),

其中 σ\sigma 为球面上的归一化均匀测度。每个投影问题都可以通过排序求解,而积分则可以通过随机方向来近似。切片 Wasserstein 距离是一个独立的距离,而非普通的多维 Wasserstein 距离;采用有限个投影方向会引入额外的近似误差,并可能无法区分某些分布对。

标准 Wasserstein 传输比较的是共同基础空间上总质量相等的测度。非平衡最优传输放宽了质量守恒的限制,而部分最优传输则只搬运预定数量的质量。Gromov–Wasserstein 方法则比较各自内部的成对距离,从而允许在没有预先指定跨空间距离的情况下,关联支撑在不同度量空间上的分布。这些推广解决的是不同的数学问题。同样,最优耦合只是为了最小化成本而选出的对应关系:它本身并不代表因果机制、物质的历史移动轨迹,或是单个观测样本之间的真实配对。