Skip to content

方法Method

一维单调输运

施工中 · 内容逐步修订

Monotone rearrangement transport · Quantile transport

按累计质量的相同分位数配对,以消除交叉证明一维凸距离成本的最优性。

形式陈述 ​

实线上的两个分布是否需要求解一个大型线性规划才能搬运?顺序结构让最优计划可直接由分位数写出。

设 μ,ν 为实线上有有限 p 阶矩的概率测度,1≤p<∞,分布函数分别为 Fμ,Fν。定义广义分位数

Fμ−1(u)=inf{x:Fμ(x)≥u},0<u<1.

若 U∼Unif(0,1),则 (Fμ−1(U),Fν−1(U)) 是成本 |x−y|p 下的最优输运计划,从而

Wp(μ,ν)p=∫01|Fμ−1(u)−Fν−1(u)|pdu.

这里 Wp 采用Wasserstein 距离的定义。同一个单调计划也适用于成本 h(x−y),其中 h:R→R 是有限凸函数;有限一阶矩与凸函数的仿射下界保证负部可积,成本允许为 +∞。减去这条仿射下界后成本非负,而且固定边缘使所有计划的目标都只减去同一个有限常数,所以可归约到上述输运问题。若 μ 无原子,Fμ(X) 在 X∼μ 下均匀分布,可在 μ-几乎处处写成映射 T(x)=Fν−1(Fμ(x))。对 Fμ(x)∈{0,1} 的例外零集任取一个固定实值即可得到全局可测版本;源有原子时,应保留公共均匀变量的计划表示。

直觉

从左到右给质量编号:第一份极小质量配第一份,第二份配第二份。若两条搬运路线交叉,交换目标不会增大凸位移成本。具体地,当 x1≤x2、y1≤y2,

h(x1−y1)+h(x2−y2)≤h(x1−y2)+h(x2−y1).

凸函数的等长增量随起点增加而增加,给出这条不等式。有限离散情形反复消除交叉,便得到按顺序匹配的计划;一般测度通过离散逼近和成本下半连续性得到同一结论。p=1 时可能有不同计划达到同样成本,单调计划最优不意味着它必唯一。

横轴 u 是累计质量分位;每条竖箭头表示同一份质量的起点与终点。

证明:从不交叉到任意凸成本 ​

共同分位数确实给出指定边缘。 简记 Qμ=Fμ−1、Qν=Fν−1。对 0<u<1,广义分位数满足 Qμ(u)≤a⟺u≤Fμ(a);右连续性处理了等号端点。因此 Qμ(U) 的分布为 μ,且共同分位数计划的联合分布函数为

P{Qμ(U)≤a, Qν(U)≤b}=min{Fμ(a),Fν(b)}.

任何支撑不交叉的计划也有这个联合分布函数:矩形 {x≤a,y>b} 与 {x>a,y≤b} 不可能同时有正质量,否则满质量支撑中会出现一对交叉点。故左下矩形的质量等于两边缘质量的最小值。由半开矩形的有限差分及概率测度的唯一性,这确定整个联合律。

先处理有界支撑。 对严格凸的 h,紧空间连续成本的最优计划存在。若支撑内有 x<x′、y>y′,记 a=x−y、b=x′−y′、δ=y−y′>0。则 b−a=(x′−x)+(y−y′)>δ,交叉改送后的两个差为 a+δ,b−δ,都严格位于 a,b 之间。严格凸性给出

h(a+δ)+h(b−δ)<h(a)+h(b).

连续成本的邻域交换论证排除这对点,所以最优计划不交叉,必是共同分位数计划。若 h 仅凸,先对 hκ(t)=h(t)+κt2 使用此结论,再令 κ↓0;有界支撑使平方项有统一有限界,得到所有有限凸 h 的结论。

一般分布的尾部。 对有限凸 h:R→R,取在零点的仿射支撑 ℓ(t)=h(0)+st,令 k=h−ℓ。则 k≥0、k(0)=0。由于两边缘有有限一阶矩,∫ℓ(x−y)dπ=h(0)+s(∫xdμ−∫ydν) 是与计划无关的有限常数,所以只需比较 k。

令 TR(t)=max(−R,min(t,R))。共同裁剪保持 x−y 的符号并缩小其绝对值;凸性和 k(0)=0 因而给出

k(TRx−TRy)≤k(x−y).

把任意竞争计划两坐标共同裁剪,边缘变为 (TR)#μ,(TR)#ν。有界情形的分位数计划也就是 (TRQμ(U),TRQν(U)) 的联合律,因为它边缘正确且不交叉。因此

∫01k(TRQμ(u)−TRQν(u))du≤∫k(TRx−TRy)dπ≤∫k(x−y)dπ.

用Fatou 引理令 R→∞,得到共同分位数对原成本的最优性,右侧为 +∞ 时同样合法。这里没有偷偷要求二阶矩,也没有假定正部成本有限。

无原子时为何成为映射。 若 μ 无原子,则 Fμ 连续。对每个 u∈(0,1),连续性给出 Fμ(Qμ(u))=u,所以在 X=Qμ(U) 的实现中,Fμ(X)=U 几乎处处。因而 Qν(Fμ(X))=Qν(U),共同分位数计划正由 T=Qν∘Fμ 诱导。端点 0,1 的例外不带源质量,可任意定义映射值。源含原子时此等式一般不成立,仍应保留计划而非强行指定映射。

例子与边界

取 μ=12δ0+12δ2、ν=14δ1+34δ3。公共质量轴分成三段:

  • 0<u<1/4:0 配 1,质量 1/4
  • 1/4<u<1/2:0 配 3,质量 1/4
  • 1/2<u<1:2 配 3,质量 1/2

因此 W1=3/2、W22=3。源点 0 的质量被分给两个目标,正说明“分位数耦合总存在”与“确定 Monge 映射总存在”是两回事。

直接执行的扫描算法 ​

对有限加权点集,先分别按位置排序,维护当前源点和目标点的剩余质量。每步搬运两者剩余质量的较小值,然后前进到已耗尽一侧的下一个点;两侧同时耗尽则同时前进。循环不变量是已经越过的所有源质量与目标需求恰好匹配,尚未处理的质量均在当前位置右侧。

每步至少耗尽一个点,所以排序后至多产生 m+n−1 个非零配对,扫描耗时 O(m+n)。包括排序的总时间为 O(mlog⁡m+nlog⁡n);若只累加成本,额外工作空间可为常数,不计输入排序存储。

凸性不可省略。例如源点 0,1、目标点 2,3,各等权,成本取距离平方根。单调配对的未加权成本为 22,交叉配对为 3+1<22,此时交叉更便宜。高维空间又缺少统一的左右顺序,逐坐标排序通常不能保持正确联合分布。

推论与应用

当 p=1,还可写成

W1(μ,ν)=∫R|Fμ(t)−Fν(t)|dt.

对公共均匀变量产生的 X,Y,有 |X−Y|=∫R|1{X≤t}−1{Y≤t}|dt。由Tonelli 定理交换非负积分;又因 {Fμ−1(U)≤t}={U≤Fμ(t)},两事件是同一均匀轴上的嵌套区间,不相等概率恰为 |Fμ(t)−Fν(t)|。于是得到上述 CDF 公式。分位数公式构造计划,分布函数公式则累计各截面的净搬运量。

同一CDF面积还等于所有1-Lipschitz测试函数的最大期望差。正态Stein方程通过Fubini换序并选择导数的符号证明这个等价式,再用它把微分方程误差解释为W1距离。因而容量超额这类无界但Lipschitz的损失也可获得保证,无需先把它截成指示事件。

同一个广义分位函数还可专门观察接近一的尾概率。最大值吸引域使用 U(t)=F−1(1−1/t) 的缩放增量来判定极值类型并选择归一化;这个尾部极限问题不要求先计算输运成本。

参考资料
关系图谱18 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系