“最优传输理论和算法”课程简介

最优传输理论具有数百年的历史，发展到今天已经根深叶茂，博大精深。依随人工智能的发展浪潮，特别是深度学习的勃然兴起，最优传输理论再度焕发了新春！

图1. 逼真的人脸图片，由基于最优传输理论构造的生成模型所生成。

根据深度学习的流形分布定律：一类自然数据可以被视作高维背景空间中的低维数据流形上的一个概率分布，深度学习的主要任务包括两个，学习流形结构，表示概率分布。深度神经网络本质上是表达欧氏空间之间的非线性映射，因此如何用映射表示概率分布成为研究重点。而最优传输理论恰是研究概率分布之间映射的学问。为了响应时代要求，我们决定讲授最优传输理论和算法课程。

疫情期间，老顾在线上为计算机系和数学系学生讲解最优传输理论和算法课程，目前已经接近尾声。最优传输理论体系宏大，内容艰深，初学者难以掌握；最优传输映射的计算具有特殊的难度，需要很高的数值技巧，课后作业的难度很大。这篇短文旨在为同学们勾勒一下课程的逻辑线索，主要涵盖的问题和理论，使得同学们可以提纲挈领，抓住要点，从而有的放矢，自我加强，而不至于淹没于繁琐的细节之中。

最优传输理论大致有三种主要观点，同时有相应的计算方法：对偶观点 、几何观点和流体观点。这些观点相辅相成，浑然一体。我们课程的重点在于了解理论体系，建立几何直觉，开发实用算法，应用于工程实践。

对偶观点

法国数学家蒙日（Monge）提出了蒙日问题，成为最优传输理论的发轫。

蒙日问题 （Monge Problem） 假设是欧氏空间中的区域，和是上的两个测度，满足总质量相等条件，. 一个映射  被称为是保测度的，如果

,

简记为 .  给定传输代价函数，，映射的总传输代价为

.

蒙日问题是求所有保测度映射中，总传输代价最小者：

.

蒙日问题的解被称为最优传输映射。最优传输映射的总代价被称为是和之间的Wasserstein距离，例如如果传输代价是欧氏距离的平方，那么相应的Wasserstein距离为：

.

在深度学习中，Wasserstein距离被广泛应用于测量概率分布之间的相异程度，与传统方法相比，这种度量更加精确。

在长达二百年的期间内，蒙日问题一直没有被彻底解决，其核心原因在于最优传输映射有可能并不存在。例如，如果源测度集中在一个点上，目标测度集中在多个点上，我们需要将源点劈开，分配给目标点，这时最优传输映射不存在。

康塔洛维奇问题 （Kantorovich Problem）康塔洛维奇将传输映射放松成传输方案，用联合概率分布表示，， 代表从起点传到终点  的质量。传输方案的边际概率等于和，即我们有

这里投影映射 ，。由此，传输映射成为传输方案的特例，即传输映射诱导了传输方案：

.

康塔洛维奇问题是求代价最小的传输方案：

.

康塔洛维奇问题是线性规划问题。我们可以用单纯形方法、椭球法进行优化。但是，线性规划有内在缺陷：如果最优传输映射存在，那么线性规划找到的最优传输方案中绝大多数的变量是浪费的；同时这种算法没有利用到问题本身的内在结构，因此过于简单粗暴。

图2. 最优传输映射，对应的原像和像点用同样的颜色渲染。

康塔洛维奇对偶问题 （Kantorovich Problem）康塔洛维奇问题的对偶形式揭示了更为丰富的内在结构。这里，我们求两个具有一定正则性的函数，被称为康塔洛维奇的势能函数和，极大化下面的能量：

.

康塔洛维奇问题的原形式和对偶形式的等价性是基于最优传输方案的一个性质：循环单调性（Cyclic Monotonocity）。我们在最优传输方案的支集内任取点对：，那么我们有不等式：

这里是角标的任意排列。

图3. 循环单调性（Cyclic Monotone）。

对偶能量的优化过程本质是将两个康塔洛维奇势能函数和用对方的c-变换来替换，循环往复，直至收敛。这里，c-变换是最优传输理论中至关重要的一个概念，定义成：

.

几何上看，如果我们固定一点，则我们得到一张支撑曲面，

这些支撑曲面的包络就给出了c-变换 。

图4. 凸函数的支撑集是直线，函数的图是支撑直线的包络。

图5. c-变换。

应用c-变换，我们得到对偶问题

由这里，我们可以导出最优传输映射满足的偏微分方程。由c-变换的定义，我们得到最优传输方案支集中的点满足条件：

。

如果代价函数是一个严格凸函数，满足形式

那么代价函数的梯度映射可逆，则最优映射满足微分方程：

这里是最优康塔洛维奇势能函数。

Brenier问题  如果传输代价函数是欧氏距离的平方，

，

那么最优传输映射是某个凸函数的梯度映射：

这个凸函数被称为Brenier势能函数。由最优传输映射的保测度性质，我们得到此映射的Jacobian矩阵行列式等于对应点的概率密度之比，从而得到关于Brenier势能函数的蒙日-安培方程 （Monge-Ampere）：

.

Brenier问题就是求取Brenier势能函数。Brenier极分解定理断言任意一个传输映射，满足，可以分解为一个Brenier最优传输映射和一个保持体元的映射。

几何观点

蒙日-安培方程紧密地联系着最优传输理论和微分几何。微分几何中，通过高斯曲率来复制曲面的问题，最终都归结为蒙日-安培类型的偏微分方程。因此，这一类问题既可以用纯粹几何方法来研究，也可以用最优传输理论来研究，这两个分支为彼此提供了深刻的洞察。

闵可夫斯基问题 （Minkowski Problem） 给定一个凸曲面，高斯映射将曲面的上的每个点映射到该点处的法向量，，从而将曲面的高斯曲率映射到单位球面上，得到定义在单位球面上的曲率函数，。闵可夫斯基问题就是从定义在单位球面上的高斯曲率，来反解凸曲面。历史上，闵可夫斯基证明低维情形解的存在性和唯一性，丘先生证明了高维情形解的存在性和唯一性。

图6：Minkowski问题。

闵可夫斯基问题的离散提法非常直观：给定单位向量和正数：

满足线性限制：

构造凸多面体，每个面的法向量和面积等于给定的单位向量和正数，如图6所示。闵可夫斯基可以用变分法和平面包络的算法实现。

亚历山大问题 （Alexandrov Problem） 

给定一个凸曲面，其极坐标表示为

其中 是极径函数。曲面的高斯曲率函数为，通过极坐标表示，我们得到定义在单位球面上的曲率函数，。亚历山大问题就是从定义在单位球面上的高斯曲率，来反解凸曲面，等价的极径函数 。亚历山大问题等价于球面上的最优传输问题，其传输代价为 

.

对应的支撑曲面为平面，最终归结为求平面的包络。

图7. Alexandrov问题的解。

图7显示了亚历山大问题的求解实例。我们将一个怪兽模型（左上）共形映射到单位球面上（右上），然后计算球面最优传输映射（右下），得到相应的凸曲面（左下）。

非紧闵可夫斯基问题 （Non-compact Minkowski Problem） 

非紧闵可夫斯基问题求定义在凸区域 上的一个凸函数，函数图是一个开放凸曲面，使得此凸曲面的高斯曲率等于给定的非负函数 。

图8：非紧Minkowski问题。

这一问题的离散提法如下：给定平面上的凸区域 ，给定单位向量和正数

满足线性限制：

构造凸多面体，每个面的法向量和向 投影的面积等于给定的单位向量和正数，如图8所示。亚历山大定理证明解的存在性和唯一性。本质上，亚历山大定理和Brenier定理彼此等价，可以用变分法和平面上包络的算法实现。

图9：基于Alexandrov定理算出的最优传输映射。

图9显示的是基于Alexandrov定理计算的Brenier映射。我们将一张人脸曲面（左上）用黎曼映照映射到平面圆盘上（左下）。黎曼映照将曲面的面积测度（面元）映射到平面圆盘上，我们称之为推前测度。我们用Alexandrov定理计算推前测度到平面勒贝格测度的Brenier映射（欧氏距离平方下的最优传输映射），映射的像显示在（右下）。我们在平面上铺设圆盘填充（circle packing）的纹理图像，再拉回到人脸曲面上。（左上）显示了黎曼映照保持了小圆的形状，但是改变了小圆的面积；（右上）显示了最优传输映射改变了小圆的形状，但是保持了小圆的面积。

图10. 共形映射和最优传输映射比较。

图10显示了和图9类似的计算过程，我们可以直接比较共形映射和最优传输映射的结果。左下，共形映射带来剧烈的局部面积变化，三角剖分的疏密程度相差甚远；右下，最优传输映射保持面积，但是三角形的形状变化剧烈。因此，如何设计曲面上的采样，如何构造曲面的三角剖分，这些都会对最优传输的计算带来剧烈影响。

反射曲面设计问题 （Reflector Design Problem） 

图11. 反射镜面设计问题。

图12. 反射镜面设计的计算实例。

1992年，丘成桐先生提出了100个微分几何领域的开放问题，其中一个问题就是如何求解反射曲面设计问题。如图11和图12所示，给定一张图像（左上，蒙日的肖像），我们希望能够设计一张曲面，如下面一行所示。从点光源发射的光线经过反射镜面反射后，在远处墙面上投射出同样的画面（右上，用光线追踪法得到的图像）。传统投影设备的方法利用微小镜面阵列，如DMD芯片，每个像素对应一个小镜子，小镜子具有两种状态，反射和遮挡，通过高频转换这两种状态，调节两者的比例，每个像素的光强能够被精确控制。但是这种方法会浪费大量光能，被遮挡的光能转化成热能。这里的方法是将入射光能重新分配，没有任何浪费。

这种反射光学系统的设计最终归结为球面最优传输问题，应用凸支撑曲面的包络来进行计算。因为涉及到球面几何，我们需要大量的超越函数运算。通常计算机用泰勒展开来逼近超越函数的运算，精度达不到要求。因此，这类算法的难度更高。

正则性问题 （Regularity） 

通常计算机科学领域计算的结果都是弱解、分布意义下的解，或者亚历山大意义下的解，因此对于最优传输映射的光滑性（正则性）考虑不足。但是近期深度学习中出现的一些问题，例如算法收敛困难，算法敏感脆弱，特别是模式崩溃，这些都和最优传输映射的正则性紧密相关。

图13. 最优传输映射有可能非连续。

经典的Caffarelli理论揭示了距离平方代价下最优传输映射的正则性依赖于很多因素：概率密度函数和的光滑性，支集的凸性和边界光滑性，代价函数的光滑性。长期以来，一般代价函数下最优传输映射的正则性问题一直悬而未决。维拉尼称赞汪徐家教授的研究带来了巨大突破。汪教授和合作者们指出了如果代价函数的四次微分满足特定条件，那么最优传输映射的正则性得以保证，这一条件被称为Ma-Trudinger-Wang曲率条件。Loeper给出了这一曲率条件的几何解释：这一条件保证了c-凸函数的c-次微分的连通性。

图14. 深度学习中经常出现的模式崩溃问题，左上 VAE，右上 WGAN，下行用最优传输理论得到的模型，改善了模式崩溃。

如图14所示，我们用生成模型学习手写体数字，MNIST数据集具有10个模式。传统的变分编码器（VAE，左上），Wasserstein GAN（右上）会生成一些介于模式之间的图像，令人难以辨认。很多时候，生成模型会忘掉一些模式，这些现象被笼统地称为模式崩溃（mode collapse）。

图13给出了这一现象的理论解释，我们计算实心兔子内部的均匀分布到实心球体内部的均匀分布之间的最优传输映射（逆映射），我们看到映射在实体内部是微分同胚，但是兔子表面剧烈产生皱褶，映射在皱褶处不再连续。这意味着如果目标区域非凸，那么传输映射整体上不再连续。然而，深度神经网络只能表达连续映射，这种内在矛盾诱导了模式崩溃。

图15. 人脸图像流形的边缘，中间行，双目不同颜色的生成样本。

同时，再深度学习中，图13的皱褶对应着数据分布的边缘，那里样本的存在性是合理的，但是在现实中出现的概率为0. 例如，我们的训练集中只有黑色双睛或者蓝色双睛，最优传输映射的间断处给出了一只眼睛为黑色、另一只眼睛为蓝色的生成样本，即为人脸图片流形的边缘，如图15所示。

流体力学观点

流体力学的观点更符合物理直观。我们考察特殊气体在空间的流动。从宏观上看，在时刻，空间点处的气体密度为。从拉格朗日观点来看，每个气体粒子的运动轨迹为一条空间曲线。假设粒子轨迹为，起始点为，粒子的速度为。如果不同粒子的轨迹在某个时刻相交，那么宏观上流场出现激波（shock）。我们假设没有激波出现，那么在时刻，每个粒子的初始位置映射到当前位置，我们得到全空间的整体微分同胚：

。

在时刻，粒子的速度向量为。这一时刻，全空间的整体速度场表示为，简记为，那么微分同胚满足常微分方程：

.

如果给定速度场，我们可以得到相应的微分同胚群。换言之，如果速度场足够光滑，那么流场不会出现激波。光滑速度场诱导的微分同胚群，

如果代价函数是严格凸函数，那么拉格朗日观点下每个粒子都做匀速直线运动，其轨迹是常速度直线段：

这里是最优康塔洛维奇势能函数，这被称为是 McCann 平移。

动态最优传输问题 （Time Dependent Optimal Transport Problem） 

给定微分代价函数，定义在速度向量上，那么整条路径代价函数为：

.

动态最优传输问题求一个连接和的流场，使得所有路径的总代价最小：

动态和静态最优传输问题等价的一个充分条件是测地线的长度等于起点、终点之间的距离：

.

假设代价函数是严格凸函数，我们来看动态最优传输问题解所满足的微分方程。那么由 McCann 平移，我们得到速度场的欧拉方程：

由质量守恒，我们得到密度的连续方程：

欧拉方程、连续方程对任意严格凸代价函数都成立，具体的代价函数信息隐含在初始条件之中。由 McCann 平移，每个粒子的速度都是常值，因此我们得到速度场的初始条件

.

这里是最优康塔洛维奇势能函数。

Benamou-Brenier问题

给定任意时刻，速度场的动能为

.

我们考察所有联结和的流场构成的空间，我们将简写成，则

显然，当且仅当，这里，即动量是无散场。Benamou-Brenier问题求所有中的流场总动能最小者：

.

我们用变分法来求最优速度场满足的必要条件：

这里是任意无散场，由Hodge定理，最优速度场和任意无散场“垂直”，因此为梯度场，即存在函数族，满足 。这也可以由McCann平移得出。

坦尼博姆观察到，在最优传输映射下，向量场  必为某个函数的梯度场。坦尼博姆算法（Tannenbaum）首先求得一个传输映射，满足，然后将投影成一个无散场，在边界处满足诺依曼边值条件，速度场 诱导流场 ，从而定义微分同胚，的传输代价低于初始映射的代价。如此，我们构造流场：

在此流场下，的传输代价单调下降，直至为梯度向量场。

Benamou-Brenier引入了新的能量，使得Benamou-Brenier问题的解成为能量的鞍点，通过极小-极大优化来求得。

算法设计的考虑

与经典的椭圆型偏微分方程相比，蒙日-安培方程的求解难度大为增加。如图16所示，我们将人手曲面映射到平面单位圆盘，在计算共形映射过程中，曲面的三角剖分不需要改变；在计算最优传输映射过程中，三角剖分在不停的变动，最终的三角剖分与初始三角剖分非常不同。同时在计算过程中，如果有一步出错，会造成算法崩溃。因此，如何在曲面上采样，如何构造三角剖分，如何保持解的凸性，如何严格监控算法流程，这些需要仔细考虑。特别是，目前的软件硬件条件无法支持高效的高维最优传输映射计算。

图16. 共形映射和最优传输映射的对比。

总结

最优传输理论的三种观点从不同的角度描绘了整个理论大厦，提供了迥然不同的计算方法，希望同学们熟练掌握，并且积极尝试，争取在工程和医学领域找到实际应用。我们相信随着人工智能的发展，历史悠久的最优传输理论和算法会跟随现代步伐，进一步迅猛发展！

---

---

请长按下方二维码，选择 “识别图中二维码”，即可关注。

【老顾谈几何】邀请国内国际著名纯粹数学家，应用数学家，理论物理学家和计算机科学家，讲授现代拓扑和几何的理论，算法和应用。