缘起
1995年秋季,第二作者刚刚来到哈佛大学开始攻读计算机科学领域的博士学位,并在数学系学习丘成桐先生的微分拓扑课程,同时在麻省理工学院人工智能实验室学习Berthold Horn教授的机器人视觉课程. Horn教授提倡从物理的角度来理解视觉机理,用偏微分方程来解决工程问题.Horn教授讲解了他的经典工作“Shape from Shading”,将从二维图片重建三维几何的问题归结为求解双曲型偏微分方程. Horn教授也讲解了“Extended Gauss Image”的想法,目的是用Gauss曲率来重建凸曲面,这等价于微分几何中的Minkowski问题,归结为求解Monge-Ampère方程.但是,那时计算机视觉领域并没有严格高效的计算方法.当时,由于无法理解艰深的非线性偏微分方程理论,为了求解Minkowski问题,第二作者冒昧地向丘先生求教.丘先生非常平易近人,看到有人对Minkowski问题有兴趣,他非常兴奋,并且亲自复印了他与郑绍远教授的经典论文“On theRegularity of the Solution of then-Dimensional Minkowski Problem”.在文章中,丘先生与郑教授证明了任意维Minkowski问题解的存在性、唯一性和正则性.在丘先生的指导下,第二作者系统地学习了Alexandrov和Pogorelov的经典文章和著作.在随后的多次讨论中,丘先生传授了求解Monge-Ampère方程的算法. Monge-Ampère方程具有强烈的非线性,而那个时代,通用计算机的算力非常有限,每次实验运行时间都会长达数天,因此算法设计与实验颇具挑战性。
时代要求二十多年后,人工智能再度兴起,大数据、深度学习技术在工程领域取得了巨大成功,但是这些算法背后的理论解释依然处于初始状态.为新一代人工智能技术奠定理论基础,成为时代发展的迫切要求.在丘先生的带领下,作者团队用现代拓扑几何理论为深度学习提出了一个理论框架.在计算机视觉领域,每个概念对应一类自然的图像数据;每个图像被视为高维图像空间中的一个点;同类图像构成图像空间中的一个稠密点云,而此点云分布在某个低维数据流形附近.由此,此类数据被表示为数据流形上的概率分布.从而,我们得到深度学习的两个核心任务:学习数据流形的结构,学习流形上的概率分布.深度学习算法本质上是在数据流形上以所有概率测度构成的空间中进行优化.而最优传输映射为第二个核心任务(即学习概率分布)提供了坚实的理论基础和强大的计算工具.
正是因为深度学习和大数据的兴起,最优传输理论进入了计算机科学的中心舞台.交叉学科开始涌现,近似计算方法层出不穷.在各类方法中,最为直观、最为精确的算法却是来自最优传输的Brenier理论,而这一理论恰恰与Minkowski、Alexandrov和Pogorelov的凸微分几何理论等价,最后归结为求解Monge-Ampère方程.这令作者百感交集,感慨万千,对于丘先生的高瞻远瞩更是无比钦佩.每个年轻学者的终极梦想都是希望在刚入门时导师能够给出一套深刻直观的方法,同时指明一个有长远发展前景的方向.为此,作者深感幸运,对丘先生更是无比感激!
简明历史
2010年前后,丘先生与作者团队开始了最优传输几何化方向的研究,很快给出了Alexandrov定理的构造性证明,发展了几何变分算法,并且很快应用于可解释深度学习的研究.同时,我们在海内外的一些大学(包括纽约州立大学石溪分校、清华大学丘成桐数学科学中心、大连理工大学、首都师范大学)开设最优传输理论的课程,并在数十个国际会议、大学讨论班中做了相关演讲. 2020年,由于全球疫情的影响,作者在线上讲授了“最优传输理论和算法”的课程.在高峰期,一节课有三万多人同时听讲,同学们的巨大热情令作者非常感动.同学们来自社会的各行各业,既有高等院校计算机科学、数学、电子自动化等理工专业的本科生与研究生,又有自动驾驶、虚拟现实、动漫动画、医学影像、电子金融、人工智能等领域高科技公司的技术科研人员.这些都显示了最优传输理论、可解释人工智能技术的广阔应用前景.内容简介我们课程的重点在于了解理论体系,建立几何直觉,开发实用算法,应用于工程实践.线上大篇幅讲解最优传输理论具有很大的挑战性,该理论的体系宏大,内容艰深,对数理基础要求较高,初学者难以掌握.针对绝大多数同学都是来自信息技术产业,具有工程科学背景,作者为课程安排了多次编程作业,将复杂算法分解成多个步骤,循序渐进,由浅入深,这有助于同学们将抽象的理论和具体的算法实现联系起来,通过动手实践来加深并检验对于抽象理论的理解.在课程结束后,课程的关键算法在网上开源,以帮助同学们进一步理解,并且在实践中找到具体应用.
课程特色在于从多种观点讲解最优传输理论,并且核心理论与计算方法并重.最优传输理论大致有三种主要观点,同时有相应的计算方法:对偶观点、几何观点和流体观点.这些观点相辅相成,浑然一体.我们首先介绍了Monge-Kantorovich理论, Monge最早提出了最优传输映射问题,Kantorovich将其推广为最优传输方案,并且发展出线性规划方法,提出了等价的对偶问题. Kantorovich对偶问题成为后来理论发展的起点.在深度学习领域中,常用的Sinkhorn算法本质上是线性规划加上熵正则项.如果传输代价为欧氏距离的平方, Brenier证明了最优传输映射是Brenier势能函数的梯度映射,而Brenier势能函数满足经典的Monge-Ampère方程,Monge-Ampère方程又天然联系着Minkowski问题和Alexandrov问题.于是,我们进入了最优传输理论的几何观点,即Minkowski、Alexandrov和Pogorelov的经典凸几何理论,丘先生在高维的推广以及汪徐家教授在球面几何上的推广.从计算角度而言,我们应用顾险峰–罗锋–孙剑–丘成桐定理,与经典计算几何的power图理论相联系,详细介绍了几何变分算法,并且从欧氏空间推广到球面几何,从低维推广到高维.第三个阶段,我们介绍了流体力学观点下的最优传输理论,着重介绍Benamou-Brenier理论,将最优传输映射和极小化动能流场相联系,用流体力学方程来描述最优传输问题.这一观点自然将Riemann几何引入最优传输理论,为流形上以概率测度构成的无穷维抽象空间引入了测地线、Riemann度量和协变微分.从计算角度而言,我们着重介绍了Benamou-Brenier算法和Tennanbaum算法.更进一步,我们简要介绍了Monge-Ampère方程理论,用经典方法证明了解的存在性、唯一性和正则性,然后介绍了Monge-Ampère方程的数值方法和最优传输映射的计算方法.最后,我们介绍了最优传输映射在人工智能领域的应用,用最优传输理论的Riemann几何观点,重新诠释了深度学习中的最大熵原则,用Monge-Ampère方程的正则性理论来解释最优传输中的模式坍塌问题,等等.
鸣谢
Monge于1781年提出最优传输问题,历经二百余年的发展,目前这一理论已经广袤深邃,博大精深.为了教学,我们收集了大量的资料,主要的经典教材包括Cédric Villani、Alessio Figalli、A. D. Alexandrov、Fillippo Santambrogio的著作,主要的论文包括丘成桐、汪徐家、Brenier及很多数学家和计算机科学家的工作.我们也将自己团队近期的理论工作、计算方法,以及在人工智能、计算机视觉、图形学等领域的工作融汇其中.在本书编写过程中,我们得到了很多师长、朋友和学生们的帮助,作者表示衷心的感谢!特别是丘成桐、汪徐家、方复全、徐宗本、高小山、罗钟铉等教授,为这门课程提供了大力支持;罗锋、孙剑、王雅琳、苏科华、崔丽、刘佳堃、陈世炳等教授,与我们团队共同建立了最优传输的几何优化理论,提出了严密精确的算法; Arie Kaufman、段晔、曾薇、章敏、马明、郑晓朋等教授, Joe Marino、Saad Nadeem、苏正宇、陈伟、温成峰、齐鑫、李新元、安东生、郭洋、涂颜帅、王发强等博士,将算法加以实现,并且广泛应用于人工智能、计算机视觉、图形学与医学影像各领域,作者对所有这些合作者以及帮助过我们的学者朋友,表示由衷的谢意!
期望
一门课程无法涵盖这门理论的方方面面,也无法达到理想的深度;同时因为最优传输计算方法的飞速发展,我们无法详细追踪新建立的算法.在本书编写过程中,不可避免地存在错误和遗漏,希望广大读者指出,以帮助作者进一步改进!
展望未来,作者认为经典的最优传输映射正则性理论忽略了映射的奇异集合,而这正是深度学习中模式坍塌的关键所在,由此最优传输映射奇异集理论需要长足发展.同时,经典最优传输映射的计算方法,通常只关注于低维方法的精确度和收敛性分析,而高维的近似方法则过于粗略.发展高效而精密的高维最优传输映射的算法,是人工智能技术发展不可或缺的环节.作者希望更多的年轻人能够投入到这一古老而又年轻的领域,从理论到实践,进一步推动最优传输理论的发展,更加深刻地应用到工程和医疗领域,引领下一代人工智能技术发展的浪潮!
雷娜、顾险峰 2021年7月
微弱而不好意思的链接：微博
目录
第一部分最优传输的对偶理论
第一章Monge-Kantorovich 理论
1.1 凸函数的Alexandrov 理论
1.1.1 次微分
1.1.2 Legendre-Fenchel 变换
1.1.3 Alexandrov 定理
1.2 Monge 问题与Kantorovich 问题
1.2.1 空间、弱收敛和连续性
1.2.2 M(X) 和C0(X) 间的对偶
1.2.3 紧空间上连续代价函数的Kantorovich 问题
1.2.4 紧空间下半连续代价函数的Kantorovich 问题
1.2.5 Polish 空间下半连续代价函数Kantorovich 问题的解
第二章对偶理论
2.1 对偶问题
2.1.1 广义Lagrange 乘子法
2.1.2 连续函数空间的紧致性
2.1.3 c-变换
2.2 Kantorovich 问题和对偶问题的等价性
2.2.1 循环单调性
2.2.2 连续代价函数(KP) 与(DP) 的等价性
2.2.3 下半连续代价函数(KP) 与(DP) 的等价性
第三章Brenier 理论
3.1 Brenier 问题
3.1.1 严格凸的代价函数
3.1.2 欧氏距离平方代价函数
3.1.3 最优性条件
3.1.4 稳定性条件
3.2 Brenier 极分解
3.2.1 实矩阵的极分解
3.2.2 向量场的Hodge-Helmholtz 分解
3.2.3 Brenier 极分解
第二部分凸几何理论
第四章Minkowski-Alexandrov 凸几何理论
4.1 Brunn-Minkowski 不等式
4.2 等周不等式
4.3 Alexandrov 映射引理
4.4 Minkowski 问题I
4.5 Minkowski 问题II
4.6 Alexandrov 定理
第五章半离散最优传输的变分原理
5.1 变分法原则
5.2 Legendre-Fenchel 对偶
5.3 Alexandrov 定理证明的推广
5.4 Pogorelov 定理的证明
第三部分球面最优传输
第六章球面power 图理论
6.1 曲面微分几何基本概念
6.2 球面微分几何
6.3 球面power 图
第七章Minkowski I 问题
7.1 球面的Legendre 对偶
7.2 求解Minkowski I 问题
第八章反射镜曲面设计
8.1 反射镜设计问题
8.2 具有均匀反射性质的表面
8.3 广义解和广义Legendre 变换
8.4 存在性和唯一性定理
8.5 最优传输的观点
8.6 反射曲面设计的计算方法
第九章折射透镜设计
9.1 折射透镜设计问题
9.2 具有均匀折射特性的区面
9.3 广义解和广义Legendre 变换
9.4 存在唯一性定理
9.5 折射透镜设计的算法
第四部分流体力学方法
第十章流体动力学
10.1 Euler 观点和Lagrange 观点
10.2 时变速度场的流
10.3 不可压缩流体的Euler 方程
10.4 可压缩流体的连续性方程
10.5 Arnold 几何化理论
第十一章依赖时间的最优传输理论
11.1 依赖时间的最优传输
11.2 McCann 插值
11.3 平移凸性
11.4 最优性方程
第十二章Benamou-Brenier 理论
12.1 Benamou-Brenier 定理
12.2 Otto 的理论解释
12.3 最大熵原理
12.4 Benamou-Brenier 泛函和公式
12.5 Benamou-Brenier 算法
12.6 Angenent-Haker-Tannenbaum 算法
第五部分Monge-Ampère 方程
第十三章Monge-Ampère 方程
13.1 Monge-Ampère 方程的退化性
13.2 Alexandrov 解
13.3 Dirichlet 问题
13.4 Alexandrov 二分法和C1 正则性
第十四章Monge-Ampère 方程解的估计
14.1 最大椭球引理
14.2 归一化解的Alexandrov 估计
14.3 解的严格凸性
14.4 解的C1,α 估计
14.5 最优传输映射正则性
第十五章最优传输映射的奇异集合理论
15.1 Fréchet 距离与自由空间
15.2 最优传输映射的奇异点
15.3 奇异点存在的曲率条件
15.4 power 中轴
15.5 次级多面体理论
15.6 奇异点同伦
第六部分计算方法
第十六章基于Delaunay 三角剖分的网格生成
16.1 三角剖分
16.2 增量凸包算法
16.3 Delaunay 三角剖分和Voronoi 图
16.4 Delaunay 细化算法
第十七章Monge-Ampère 方程的数值方法
17.1 Monge-Ampère 方程的数值方法
17.1.1 显式解法
17.1.2 半隐式解法
17.1.3 线性化Monge-Ampère 算子
17.2 Oliker-Prussner 方法
17.2.1 离散化
17.2.2 分段线性凸函数的Legendre 变换
17.2.3 迭代算法
第十八章半离散最优传输算法
18.1 半离散最优传输
18.1.1 胞腔测度的导数
18.1.2 泛函导数
18.2 Alexandrov 问题
18.3 最差传输映射
第七部分人工智能方面的应用
第十九章最优传输在人工智能上的应用
19.1 流形分布定则
19.2 流形嵌入定理
19.3 万有逼近定理
19.4 生成模型
19.5 模式坍塌和模式混淆
19.6 几何生成模型
参考文献
名词索引
