Shape Analysis课程笔记18-Optimal Transport
这个系列是MIT 6.838: Shape Analysis的同步课程笔记。本课程会介绍几何方法在图形学、机器学习、计算机视觉、医疗图像以及建筑设计等相关领域的原理和应用。本节主要介绍最优运输问题。
Introduction to Optimal Transport
最优运输(optimal transport)是使用几何视角来研究概率分布的学科，它的一个基本问题是如何比较两个概率分布，或者说如何把一个概率分布通过运输转换成另一个分布。
人们对最优运输问题的研究可以追溯到19世纪中期，实际上到今天为止仍然有很多数学家在研究最优运输问题。
限于课时有限，本节课只会简单地介绍最优运输的概念和一些常见的应用场景。关于最优运输理论更加系统的介绍可以参考专业教材。
Probability as Geometry
在最优运输理论中，我们会把概率分布看做是某种几何对象。
How We Compute Distance
在这种观察下我们首先要考虑如何计算两个概率分布的「距离」，常用的距离度量包括\(L^p\)范数或是KL散度(KL divergence)等：
\[\Vert p_1 - p_2 \Vert_p = \bigg( \int \vert p_1(x) - p_2(x) \vert^p \ dx \bigg)^{\frac{1}{p}}\] \[\text{KL} (p_1 \Vert p_2) = \int p_1(x) \ \log \frac{p_1(x)}{p(x)} \ dx\]
然而这些度量函数的缺陷在于当概率分布没有重叠区域时就无法对概率分布进行区分了。换句话说当\(p_1\)和\(p_2\)互相分离时，无论如何移动两个概率分布\(L^p\)范数或者KL散度给出的距离是相同的。
因此我们可以认为\(L^p\)范数以及KL散度实际上度量的是两个概率分布之间的重叠程度，而不是它们之间的距离。
Alternative Idea
而在最优运输问题则关心概率分布之间的「距离」。我们可以把两个概率分布想象成两个沙堆，而我们的目标是使用最小的代价把一个沙堆通过运输来得到另一个沙堆。
记\(\pi(x, y)\)表示运输过程，它需要满足相应的约束条件。
Kantorovich Problem
接着引入代价函数\(c(x, y)\)我们就可以定义最优运输问题的优化目标\(\text{OT}(\mu, \nu, c)\)，如此定义的最优运输问题称为Kantorovich问题(Kantorovich problem)。
p-Wasserstein Distance
实际上几何处理中的p-Wasserstein距离(p-Wasserstein Distance)也可以看做是一种Kantorovich问题，其代价函数为曲面上两点之间的测地距离。当\(p=1\)时p-Wasserstein距离有着完全符合Kantorovich问题的形式。
更进一步，1-Wasserstein距离和2-Wasserstein距离在一维情况下具有解析形式的解。
而在离散情况下，p-Wasserstein距离则可以通过线性规划(linear programming, LP)的方式来求解。
Semidiscrete Transport
除了连续和离散的情况，最优运输问题还会考虑半离散(semidiscrete)的情况。
Monge Formulation
还需要说明的是最优运输问题除了可以使用Kantorovich问题进行定义外，还可以使用Monge形式(Monge formulation)来进行定义。不过需要说明的是并不是所有最优运输问题的都可以转换为Monge形式。
Many Formulas
最优运输问题有很多不同的理解方式。
Discrete Transport Problem
Kantorovich Duality
利用对偶性，最小化运输代价也可以理解为最大化定价。
Flow-Based W2
对于\(p=2\)的p-Wasserstein距离，我们可以把原始概率密度和目标概率密度分别理解为气体在\(t=0\)和\(t=1\)时刻的分布，这样最优运输问题就等价于流体力学中的运输现象。
Applications
很多机器学习中的问题都可以理解为某种最优运输问题，这样就可以利用最优运输问题的标准解法来进行处理。
运筹学中的很多问题天然符合最优运输问题的定义，显然我们也可以使用相关的方法来求解。
在NLP中对词嵌入的比较也可以使用最优运输的相关理论。
在CV中最优运输理论可以帮助我们处理各种配准问题。
我们甚至可以利用最优运输理论来辅助设计复杂的光学系统。
对于各种形式的插值以及概率分布的变换问题，我们都可以考虑从最优运输的角度进行理解。
Discrete Transport
当我们需要求解最优运输问题时，不同的建模方式会产生不同的求解算法。当然这些算法各有侧重，并不存在一种能够解决一切问题的算法。
Entropic Regularization
entropic regularization是求解最优运输问题最流行的算法，此时我们需要在原始优化目标中添加运输\(T\)的熵作为正则项。
可以证明添加了正则项后的优化目标函数等价于KL散度，这样可以得到最优运输的解析解。
而要满足运输项\(T\)的约束则可以使用Sinkhorn算法进行计算，它相当于把解在两个集合上反复进行投影。
Eulerian Optimization
Semidiscrete Optimization
Extensions & Frontiers
基于最优传输的概念我们可以定义函数之间的重心坐标以实现插值。
这样的方法也可以结合到贝叶斯推断中，从而实现对分布的插值。
对于各种匹配的问题也可以借用最优运输的框架来进行处理。
最优运输理论还可以用来求解微分方程。
当然，最优运输理论在几何处理中也有非常广泛的应用。
