形式陈述
实线上的两个分布是否需要求解一个大型线性规划才能搬运?顺序结构让最优计划可直接由分位数写出。
设 为实线上有有限 阶矩的概率测度,,分布函数理路分布函数Cumulative distribution function · CDF实值分布在每个阈值左侧累积的概率,是非降右连续且端点极限为零和一的函数。分别为 。定义广义分位数
若 ,则 是成本 下的最优输运计划理路Kantorovich 输运问题Kantorovich transport problem在指定边缘的联合分布上最小化搬运成本,允许拆分质量并利用弱紧性保证最优计划存在。,从而
这里 采用Wasserstein 距离理路Wasserstein 距离Wasserstein distance用最小平均搬运距离定义概率测度的度量,并用矩条件说明它比弱收敛多控制什么。的定义。同一个单调计划也适用于成本 ,其中 是有限凸函数;有限一阶矩与凸函数的仿射下界保证负部可积,成本允许为 。减去这条仿射下界后成本非负,而且固定边缘使所有计划的目标都只减去同一个有限常数,所以可归约到上述输运问题。若 无原子, 在 下均匀分布,可在 -几乎处处写成映射 。对 的例外零集任取一个固定实值即可得到全局可测版本;源有原子时,应保留公共均匀变量的计划表示。
直觉
从左到右给质量编号:第一份极小质量配第一份,第二份配第二份。若两条搬运路线交叉,交换目标不会增大凸位移成本。具体地,当 、,
凸函数理路凸函数Convex function函数在任意凸组合处不超过相同权重下函数值的凸组合。的等长增量随起点增加而增加,给出这条不等式。有限离散情形反复消除交叉,便得到按顺序匹配的计划;一般测度通过离散逼近和成本下半连续性得到同一结论。 时可能有不同计划达到同样成本,单调计划最优不意味着它必唯一。
横轴 是累计质量分位;每条竖箭头表示同一份质量的起点与终点。
证明:从不交叉到任意凸成本
共同分位数确实给出指定边缘。 简记 、。对 ,广义分位数满足
;右连续性处理了等号端点。因此 的分布为 ,且共同分位数计划的联合分布函数为
任何支撑不交叉的计划也有这个联合分布函数:矩形 与 不可能同时有正质量,否则满质量支撑中会出现一对交叉点。故左下矩形的质量等于两边缘质量的最小值。由半开矩形的有限差分及概率测度的唯一性,这确定整个联合律。
先处理有界支撑。 对严格凸的 ,紧空间连续成本的最优计划理路Kantorovich 输运问题Kantorovich transport problem在指定边缘的联合分布上最小化搬运成本,允许拆分质量并利用弱紧性保证最优计划存在。存在。若支撑内有 、,记 、、。则 ,交叉改送后的两个差为 ,都严格位于 之间。严格凸性给出
连续成本的邻域交换论证理路输运的循环单调性Cyclical monotonicity in transport以任意有限循环交换都不能降低成本,刻画输运支撑的最优性结构。排除这对点,所以最优计划不交叉,必是共同分位数计划。若 仅凸,先对 使用此结论,再令 ;有界支撑使平方项有统一有限界,得到所有有限凸 的结论。
一般分布的尾部。 对有限凸 ,取在零点的仿射支撑理路次梯度与次微分Subgradient · Subdifferential以全局仿射下界刻画凸函数在不可微点的支撑斜率集合。 ,令 。则 、。由于两边缘有有限一阶矩, 是与计划无关的有限常数,所以只需比较 。
令 。共同裁剪保持 的符号并缩小其绝对值;凸性和 因而给出
把任意竞争计划两坐标共同裁剪,边缘变为 。有界情形的分位数计划也就是
的联合律,因为它边缘正确且不交叉。因此
用Fatou 引理理路Fatou 引理Fatou's lemma非负可测函数列下极限的积分不超过积分的下极限。令 ,得到共同分位数对原成本的最优性,右侧为 时同样合法。这里没有偷偷要求二阶矩,也没有假定正部成本有限。
无原子时为何成为映射。 若 无原子,则 连续。对每个 ,连续性给出 ,所以在 的实现中, 几乎处处。因而
,共同分位数计划正由 诱导。端点 的例外不带源质量,可任意定义映射值。源含原子时此等式一般不成立,仍应保留计划而非强行指定映射。
例子与边界
取 、。公共质量轴分成三段:
- : 配 ,质量
- : 配 ,质量
- : 配 ,质量
因此 、。源点 的质量被分给两个目标,正说明“分位数耦合总存在”与“确定 Monge 映射总存在”是两回事。
直接执行的扫描算法
对有限加权点集,先分别按位置排序,维护当前源点和目标点的剩余质量。每步搬运两者剩余质量的较小值,然后前进到已耗尽一侧的下一个点;两侧同时耗尽则同时前进。循环不变量是已经越过的所有源质量与目标需求恰好匹配,尚未处理的质量均在当前位置右侧。
每步至少耗尽一个点,所以排序后至多产生 个非零配对,扫描耗时 。包括排序的总时间为 ;若只累加成本,额外工作空间可为常数,不计输入排序存储。
凸性不可省略。例如源点 、目标点 ,各等权,成本取距离平方根。单调配对的未加权成本为 ,交叉配对为 ,此时交叉更便宜。高维空间又缺少统一的左右顺序,逐坐标排序通常不能保持正确联合分布。
推论与应用
当 ,还可写成
对公共均匀变量产生的 ,有 。由Tonelli 定理理路Tonelli 定理Tonelli's theorem非负可测函数的二重积分与两种迭代积分相等,允许共同取无穷。交换非负积分;又因 ,两事件是同一均匀轴上的嵌套区间,不相等概率恰为 。于是得到上述 CDF 公式。分位数公式构造计划,分布函数公式则累计各截面的净搬运量。
同一CDF面积还等于所有1-Lipschitz测试函数的最大期望差。正态Stein方程理路正态Stein方程与误差接口Normal Stein equation · Gaussian Stein equation · Stein factors for normal approximation将正态近似化为一个可计算的期望缺口,证明Lipschitz测试对应的解及导数常数,并保留Wasserstein与总变差的区别。通过Fubini换序并选择导数的符号证明这个等价式,再用它把微分方程误差解释为W1距离。因而容量超额这类无界但Lipschitz的损失也可获得保证,无需先把它截成指示事件。
同一个广义分位函数还可专门观察接近一的尾概率。最大值吸引域理路最大值吸引域Maximum domain of attraction · Tail quantile criterion for extreme values最大值吸引域把总体尾部与特定极值极限联系起来,尾分位的扩展正则变化同时给出判据与归一化。使用 的缩放增量来判定极值类型并选择归一化;这个尾部极限问题不要求先计算输运成本。
参考资料