CurvatureFlow的个人博客分享 http://blog.sciencenet.cn/u/CurvatureFlow

博文

菲尔兹奖青睐的领域:最优传输和蒙日-安培方程

已有 3441 次阅读 2019-2-15 18:17 |系统分类:观点评述

巴西里约时间2018年8月1日上午10点,被誉为数学界的奥林匹克盛会-第28届国际数学家大会(International Congress of Mathematicians)在巴西里约热内卢正式开幕。国际数学联盟主席菲尔兹奖得主日本数学家森重文(Shigefumi MORI)教授颁发2018年菲尔兹奖。其中来自苏黎世联邦理工学院的阿雷西奥-费加里(Alessio Figalli,意大利,34岁)与其他三位数学家分享这一殊荣。Alessio Figalli是菲尔兹奖得主Cedric Villani的得意门生,继承了Villani最优传输理论的衣钵。Alessio Figalli的主要研究兴趣为变分法、最优传输理论及其与蒙日-安培方程的联系,为最优传输理论及该理论在偏微分方程、度量几何和概率方面的应用做出了重要贡献。


其实早在1982年,丘成桐先生由于其在微分方程、代数几何中的卡拉比猜想、广义相对论中的正质量猜想以及实和复的蒙日-安培方程等领域里所在的杰出贡献,荣获菲尔兹奖。由此可见,蒙日-安培方程在数学中的重要性。


实际上,最优传输理论和蒙日-安培方程在工程和医疗方面已经被推广应用,近几年来愈发广泛。最优传输和蒙日-安培方程理论同时紧密连接着偏微分方程、微分几何和概率,其内在解法具有非常鲜明的几何意味。同时,这一理论在计算机图形学、计算机视觉、医学图像,特别是深度学习方面具有不可替代的应用。

图1. 法国数学家,最优传输理论的奠基人:蒙日(Gaspard Monge)。



最优传输问题


最优传输理论起源于法国数学家蒙日(Monge)于1781年提出的著名的最优传输问题,这一问题可以简单解释如下。我们考虑美国的马铃薯生产和消费情况:首先,假设整个国家自给自足,每年总产量等于总消耗量。其次,我们考虑定义在美国领土上面的两个密度函数:马铃薯的每年亩产量和每年每亩消耗量。比如, 纽约市区的消耗率很高,亩产率几乎为零;爱达荷州的亩产率很高,但是消耗率很低。政府需要设计一个传输方案,将马铃薯由生产地运往销售地,满足两个条件:首先是产销平衡,任何一个产地,运出的马铃薯总量等于生产总量,任何一个地区,消耗的马铃薯总量等于运进的总量;其次是传输代价最小。满足产销平衡的传输方案有无穷多种,如何从中挑选一个方案,使得总的汽油费用最少。


通常,最优传输方案将同一个产地的马铃薯运往不同的销售地点;但是在特殊情况下,同一个产地的马铃薯运往同一个销售地点,这时传输方案退化成最优传输映射。最优传输方案退化成最优传输映射依赖于传输代价函数。


最优传输理论主要关心的是传输映射的存在性、唯一性和光滑性问题。计算最优传输理论最为关心的最优传输映射的计算复杂度、稳定性和收敛性。最优传输理论用凸几何、非线性偏微分方程解决概率统计的问题,最近在深度学习领域引发了研究热潮。


概率论侧面


给定欧氏空间中的两个区域和定义其上的概率测度,总测度相等。假设是一个区域间的映射,如果对于任意的可测集合,都有

,

那么我们说此映射保持测度,记成。对于任意,它们之间的距离为,那么映射的传输代价定义为:

.


最优传输问题就是寻找保持测度的传输映射,使得传输代价最小,。这个映射被称为是最优传输映射,最优传输映射的传输代价被称为是两个概率测度之间的Wasserstein距离,记为 。Wasserstein距离经常用于测量两个概率测度之间的距离,定量描述概率测度间的异同。


1970年代,俄国数学家Kantorovich将传输映射(transportation map)减弱为传输规划(transportation scheme),用联合概率分布来表示传输规划,其边际概率分布等于Kantarovich发明了线性规划来求解这一问题,由此得到1975年的诺贝尔经济奖。



图2. 最优传输映射对概率分布的控制【1,3】。


图2显示了应用最优传输理论来控制曲面上的概率分布。我们用微分同胚将曲面映射到平面圆盘,这一映射将平面圆盘上的均匀分布拉回到曲面上面。上面一行的拉回概率分布不是均匀分布,下面一行的拉回概率分布在曲面上是均匀的。两个圆盘之间的映射实质上是一个最优传输映射。


偏微分方程侧面


二十世纪八十年代,法国数学家Brenier进一步发展了Kantarovich的理论。如果采用距离函数,,那么存在一个凸函数,其梯度映射给出了最优传输映射,。我们称这个凸函数为Brenier势能函数


图3. Hermann Minkowski。


最优传输映射保持测度,因此映射满足雅克比方程:

这里是映射的雅克比矩阵。因为我们得到Brenier势能函数满足蒙日-安培方程(Monge-Ampere Equation)



这种蒙日-安培方程是高度非线性的椭圆型方程,其解的存在性,唯一性,光滑性在偏微分方程领域一直是重要的问题。



凸几何侧面


最优传输的理论等价于特殊的蒙日-安培方程,蒙日-安培方程最早出现于凸几何的闵可夫斯基-亚历山大夫理论。


图4. 闵可夫斯基定理。


如图4所示,给定一个凸多面体,每个面的法向量已知,面积已知,所有面的面积和法向量的乘积之和等于0,闵可夫斯基(Minkowski)定理证明这样的凸多面体存在,并且彼此相差一个平移。


 图5. Aleksandr Danilovich Alexandrov. 


图6 亚历山大定理。


Boris Delaunay的学生亚历山大(Alexandroff)将闵可夫斯基的结果推广到开的凸多面体,如图6所示。给定凸多面体每个面的法向量,和每个面向平面圆盘的投影面积,总投影面积等于平面圆盘面积,那么这样的凸多面体存在,并且彼此相差一个垂直平移。


闵可夫斯基定理和亚历山大夫定理可以可以直接推广到光滑凸曲面情形,其满足的偏微分方程就是蒙日-安培方程。由此,求解蒙日-安培方程就等价于构造凸多面体。丘成桐团队给出了基于变分法的证明【2】,从而将求解蒙日-安培方程转化成凸优化问题,从而证明了解的存在性和唯一性。同时给出了蒙日-安培方程的数值解法。


计算机图形学:曲面参数化


图7. 曲面参数化【7】。


在动漫动画领域,三维曲面经常被映射到平面区域上,这种映射被称为曲面参数化。曲面参数化将弯曲的三维曲面变成平坦的二维平面区域,不可避免地会带来一些几何畸变。各种参数化算法都试图尽量减少这些畸变。共形参数化保持角度不变,保面积参数化保持面积元不变。如图7所示,左侧共形参数化将曲面上相交的曲线映成平面上相交的曲线,并且保持交角不变;右侧保面积参数化将曲面上的任意区域映射到平面上的一个区域,并且曲面区域面积等于参数平面区域面积。共形参数化映射和保面积参数化映射之间相差一个最优传输映射。


图8. 保体积参数化【6】。


基于求解蒙日-安培方程的最优传输映射可以推广到任意维空间,如图8所示,这种方法可以计算保体积的三维流形参数化。


计算机视觉:曲面配准


图9. 曲面配准【8】。


曲面配准(Surface Registration)是计算机视觉的一个基本问题。对于几何复杂的曲面,直接在三维空间中计算配准映射较为困难。一个切实可行的方法是将三维曲面映射到平面上的二维区域,然后计算平面像之间的配准映射。这样就减小了搜索空间,提高计算精度和速度。


图9中显示了两个姿态不同的Armadillo曲面间的配准。正确配准Armadillo的手指非常具有挑战性。应用最优传输映射,我们将曲面保面积映射到平面区域,使得每根手指都在平面上占据的区域和三维空间中手指皮肤的区域具有相同的面积。这样,平面像之间的映射会将相应的手指匹配,从而保证配准的精度。


大数据:几何聚类


图10.几何聚类【8】


最优传输理论可以用于几何大数据中的聚类(clustering)。例如,如图10所示,给定带有不同表情的三维人脸曲面,我们希望根据表情将其聚类。



图11. 几何-概率测度转换。



首先,我们需要将几何数据转换成概率分布。如图11所示,我们首先用黎曼映照(Riemann Mapping)将人脸曲面共形地映射到平面圆盘上面,再用莫比乌斯变换将映射归一化,使得鼻尖映射到原点,经过两个瞳孔的直线水平。共形映射将曲面上的面积元推前到平面圆盘上面,形成平面圆盘上的一个测度。这样,我们将人脸曲面的几何信息(黎曼度量信息),转换成平面圆盘上的一个测度。不同的人脸曲面,对应着圆盘上不同的测度。

圆盘上的任意一对测度之间存在Wasserstein距离。我们将Wasserstein距离视为人脸曲面之间的距离,将每一张人脸曲面视作一个点。我们将这些点等距地嵌入到欧氏空间之中,使得欧氏距离约等于Wasserstein距离,然后我们在欧氏空间中施行聚类,将邻近的点归为一类,如此,实现了三维人脸表情分类。




计算机、社交网络:网络特征提取


给定一个黎曼流形,流形上所有的概率分布构成Wasserstein空间,流形上的最优传输映射给出了概率分布间的Wasserstein距离。每一个概率分布定义了信息熵。Wasserstein距离定义了Wasserstein空间中的测地线。沿着一条测地线,每一点代表一个概率分布,有着对于的熵,如此在测地线上定义了一个函数。流形的Ricci曲率为负,则沿着测地线的熵函数为凸函数。由此,我们看到最优传输和流形曲率之间的深刻关系。


图12. 图上的Ricci曲率【5】。


通常意义下,曲率是定义在光滑流形上面的,在离散组合结构上无法直接定义曲率。但是,最优传输是可以定义在组合结构上面的。因此,我们可以将曲率的概率推广到离散结构上面。如图12所示,我们计算了Internet上各个节点(或者链接)的Ricci曲率,骨干网上节点(链接)曲率为负,网络边缘节点(链接)曲率为正。应用图上的曲率,我们可以进行更为深入和灵活的网络分析。


深度学习:对抗生成网络(GAN)


图13. VAE和基于最优传输理论的生成模型比较【4】。


对抗生成网络(Generative Adversral Network,GAN)是深度学习领域中非常强有力的模型。GAN模型由生成器和判别器两个深度网络构成,生成器生成伪造数据来欺骗判别器;判别器同时接收真实数据和生成数据,力图判别真伪。两个神经网络彼此对抗竞争,共同提升,最后达到纳什均衡。在平衡态,生成器生成的数据能够瞒天过海,以假乱真。


从最优传输理论来解释,判别器核心是在计算真实数据分布和生成数据分布之间的Wassersein距离;生成器本质是在计算最优传输映射。两个网络都是在用深度神经网来求解最优传输问题。由于问题规模庞大,和深度神经网络的黑箱性质,传统GAN模型的优化过程难以理论分析。如果我们采用的传输代价,那么生成器和判别器都在解同一个蒙日-安培方程【1,3】,很多中间计算结果可以直接分享,网络体系结构可以简化。那么,我们自然可以将GAN模型的一部分用透明的最优传输理论模型来取代。图13左帧是用变分自动编码器生成的人脸图片,右帧是用基于最优传输理论设计的模型生成的人脸图片【4】。



小结


最优传输理论具有悠久的历史,不停地焕发新春,从而得到菲尔兹奖的青睐。这一理论非常深刻而优美,横跨概率论、偏微分方程和凸几何领域,连接离散和连续范畴,给出强烈而简单的几何直观,相对容易理解。但是,蒙日-安培方程本身具有强烈的非线性,其计算归结为复杂的凸优化。由于最优传输理论既可以用于解决几何问题,也可以用于解决概率统计问题,它具有非常宝贵的实用价值。


最优传输理论目前在工程和医疗领域得到广泛应用,例如图形学中的参数化、视觉中的曲面注册、大数据中的几何分类、网络中的特征提取,特别是最优传输理论为深度学习的生成模型奠定了坚实的理论基础


最优传输理论是数学历史上美学价值和实用价值相结合的一个典范!



References

                                     

  1. Na Lei, Zhongxuan Luo, Shing-Tung Yau and David Xianfeng Gu.  "Geometric Understanding of Deep Learning". arXiv:1805.10451 . 

    https://arxiv.org/abs/1805.10451

  2. Xianfeng Gu, Feng Luo, Jian Sun, and Shing-Tung Yau. "Variational principles for minkowski type problems, discrete optimal transport", and discrete monge-ampere equations. Asian Journal of Mathematics (AJM), 20(2):383-398, 2016.

  3. Na Lei,Kehua Su,Li Cui,Shing-Tung Yau,David Xianfeng Gu, "A Geometric View of Optimal Transportation and Generative Model", arXiv:1710.05488. https://arxiv.org/abs/1710.05488

  4. Huidong L,Xianfeng Gu, Dimitris Samaras, "A Two-Step Computation of the Exact GAN Wasserstein Distance", ICML 2018.

  5. Chien-Chun Ni, Yu-Yao Lin, Jie Gao, Xianfeng Gu and Emil Saucan, "Ricci curvature of the Internet topology", Infocom 2015.

  6. Kehua Su, Wei Chen, Na Lei, Junwei Zhang, Kun Qian, Xianfeng Gu, "Volume preserving mesh parameterization based on optimal mass transportation", Computer-Aided Design 82:42-56 (2017).

  7. Kehua Su, Li Cui, Kun Qian, Na Lei, Junwei Zhang, Min Zhang, Xianfeng Gu, "Area-preserving mesh parameterization for poly-annulus surfaces based on optimal mass transportation". Computer Aided Geometric Design 46:76-91 (2016)。

  8. Zhengyu Su, Yalin Wang, Rui Shi, Wei Zeng, Jian Sun, Feng Luo, Xianfeng Gu: “Optimal Mass Transport for Shape Matching and Comparision”. IEEE Trans. Pattern Anal. Mach. Intell. 37(11)2246-2259 (2015).


原文发布在【老顾谈几何】公众号 (2018年8月8日)



http://blog.sciencenet.cn/blog-2472277-1162363.html

上一篇:魔方和群论(2)
下一篇:超材料设计中的共形几何

5 王金良 刘全慧 范会勇 李毅伟 liyou1983

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2019-10-16 13:23

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部