CCCF“CNCC2017特邀报告”丘成桐：现代几何学与计算机科学

2017 年 12 月 18 日 中国计算机学会 丘成桐

点击上方“中国计算机学会”轻松订阅!

来源：《中国计算机学会通讯》2017年第12期《CNCC2017特邀报告》

丘成桐教授是当代最著名的数学家之一，他在中国计算机大会的特邀报告讲的是几何学对计算机科学（包括人工智能）的贡献，计算机领域的学者可从中受到启发。也许人们没有想过几何学对计算机科学的影响会如此之大，如果要更上一层楼，应该学习更高深的数学知识。

我很荣幸受邀来到中国计算机大会上演讲。我本人主要从事微分几何等基础数学领域的研究。但最近十多年来，因为我的学生，美国石溪大学顾险峰教授及其他朋友的缘故，我进行了一些与计算机科学有关的研究。通过研究我发现，纯数学尤其是几何学在计算机科学中大有作为。

现代几何的历史及几何学重要概念

现代几何的历史

在历史上，几何学是数学的开始。古希腊数学家欧几里得(Ευκλειδης)¹（公元前330~前275年）将平面几何的所有定理组合，发现这些定理都可以由五个公理推导出来，这是人类理性科学文明的重要里程碑之一。所以我也鼓励大家把这个方法运用到人工智能上——从复杂多样的网络中找到其最简单的公理。如果能够实现，将会是人工智能的里程碑！

当时希腊人的数学工具不够，除了二次方程定义的图形（直线、圆、平面、球等），没有能力处理更一般的图形。直到古希腊哲学家、数学家、物理学家阿基米德(Archimedes)²（公元前287~前212年）开始利用简单的微积分的无限算法计算体积，并开始发展射影几何理论。微积分的出现使得几何学进入了新纪元，微分几何由此诞生。几何学在瑞士数学家欧拉(Leonhard Euler)（公元1707~1783年）和德国数学家高斯(C.F.Gauss)（公元1777~1855年）手上突飞猛进，变分方法和组合方法被大量引用来描述几何现象和物理现象。

现代几何起源于德国数学家黎曼(Riemann)（公元1826~1866年）在1854年的博士论文，论文中首次将几何空间看成一个抽象而自足的空间，同时可以研究曲率和有关的几何问题。后来这个空间成为现代物理的基础，现在物理学中研究的引力波就是从这个空间开始的。没有这个空间，爱因斯坦(Albert Einstein)就不可能研究出广义相对论。黎曼的论文中认为离散空间也是一个重要的空间，它包含了我们现在研究的图论，或许可以用来研究宇宙万物可能产生的一切。因此，黎曼的这篇论文为现代几何奠定了基础，他的思想在现代几何学中具有不可替代的作用。150年后，我们还是看得到他的智慧。

对称

几何学能够提供很多重要的想法，其影响无所不在。其中一个重要的概念是“对称”。我们中国人讲的“阴阳”就是一个对称的例子。数学上有一个叫庞加莱对偶的概念，其实也是阴阳，但比阴阳更加具体。19世纪挪威数学家索菲斯·李(Sophus Lie)发展的李群，是物理学中的一个重要工具。现代物理中几乎没有一个学科可以离开李群。在几何学上，德国数学家克莱因(Klein)于1870年发表的《埃尔朗根纲领》中提出了用对称来统治几何的重要原理。随后，产生了许多重要的几何学分支，例如仿射几何、保角几何和投影几何等。这些几何都与图像处理有着密切的联系，近十多年来我们都是用保角几何等来处理各种图像问题。所以，当年被认为不重要的几何学，现在却有重要的实际用处。从大范围对称到小范围对称，都对20世纪的基础研究产生了重要的影响。

平行移动

另一个很重要的概念是平行移动。通俗地讲，平行移动就是空间中的一点与另外一点之间的一个比较的方法。这个概念在物理学和工程中已有广泛的应用，但至今还没有被引进到计算机科学中来。这是一个在数学中很重要、很广泛的概念，它影响了整个数学界两千年。所以，我期望平行移动能够在计算机科学中大放异彩。

几何学与计算机科学的相互影响

几何对于计算机科学的影响

现代几何为计算机科学奠定了理论基础，并且指导计算机科学未来的发展方向。

● 现代几何广泛应用于计算机科学几乎所有的分支，例如计算机图形学、计算机视觉和计算机辅助几何设计、计算机网络、数字几何处理、数字安全和医学图像等；

● 黎曼几何有助于理解社交网络；

● 现代几何理论有望用来理解人工智能的黑箱，例如深度学习、生成对抗网络和机器定理证明等；

● 所有与图像或者网络有关的问题都是几何问题的一部分。

计算机科学对于几何的影响

计算机科学的发展为现代几何提供了需求和挑战，并推动了跨学科的发展。例如：

● 人工智能中的机械定理证明推动了计算代数的发展；

● 数据安全、比特币和区块链的发展推动了代数数论、椭圆曲线和模型式的发展；

● 社交网络和大数据的发展，催生了持续同调理论的发展；

● 动漫和游戏的发展推动了计算共形几何学科的诞生和发展；

● 机器学习的发展推动了最优传输理论的发展。

几何学在计算机科学的应用案例

图论

图论在计算机科学中的重要性是根本的。图由顶点和边组成，允许重边和过单顶点的圈。我们通过研究定义在顶点和边上的函数，就可以研究图的组合问题。例如，如何将原图分解成很多简单的子图，如何衡量各个分支间的连接度，如何将图染色等，这些问题都与图上的特征函数紧密相连。

事实上，图上的特征函数与光滑流形上的特征函数具有很多相似的地方。我们将四十年前我和郑绍远³、李伟光⁴所做的关于黎曼流形的特征函数的工作推广到图上，得到了很好的结果。图上的拉普拉斯算子自然定义了图上的取平均的操作，其特征根及其特征函数与图的组合函数密切相关。我们研究了图上的热扩散过程，发现运用李-丘估计能够控制热核。通过研究图上的薛定谔方程，定义了图上的量子隧道概念。这些概念都是从物理上来的，被借用到图上。我们将流形的拓扑结构推广到有向图上，定义了图上的同调群。同调群可以用来研究图上密切的关系和它的内容。

进化图论为表达种群结构提供了数学工具：顶点代表个体，边代表个体的交互作用。图可以用来代表各种具有空间结构的种群，例如细菌、动植物、组织结构、多细胞器官和社交网络。在进化过程中，每个个体依据自身的适应程度进行繁殖并侵占到邻近顶点。图的拓扑反映了基因的演化——变异和选择的平衡。特别地，互联网是一个非常复杂的网络。社交行为的进化可以用进化博弈论来研究。个体和邻居博弈，根据收益而繁殖。个体繁殖速率受到自身与其他个体的交互作用影响，从而产生进化博弈的动态演化。其核心问题在于，对于给定的图，如何决定哪种策略会取得成功。

2017年初，我们在Nature上发表了一篇文章⁵，得到了在任何给定的图上进行弱选择，自然选择从两种彼此竞争的策略中如何进行挑选的一个条件。这个理论框架适用于人类决策，也适用于任何集群组织的生态演化。我们从弱选择极限得到的结果，解释了何种组织结构导致何种行为。我们发现，如果存在成对的强纽带结构，合作就会大规模出现。我们用数学证明了社会学方面的一个结论：稳定的伙伴或者伴侣，对于形成合作型的社会起到了骨干作用。

计算机图形学：全局参数化

“基于共形几何的全局参数化”是我们研究了近20年的一个方向，自1999年顾险峰在哈佛大学读博士时就已经开始做这方面的工作了。曲面参数化问题就是如何将曲面整体光滑映射到二维参数区域，使得几何畸变最小。曲面参数化是纹理贴图和法向贴图等技术的基础。共形几何是从古典的黎曼几何中产生的一个很重要的几何分支。

我们将大卫雕像模型（如图1(a)）共形（保角）地映射到平面上（如图1(b)），看上去似乎变化很大，其实不然，因为这是保持角度不变的。如果我们在参数区域平面上画好网格点，然后将这些网格点映射到人脸上，就能在人脸上显示出很漂亮的网格图形（如图1(c)）。共形映射在工程中应用很广，因为它能将图上的无穷小圆仍然映射成无穷小圆，从而不会导致太大的变化。

图1 曲面的共形映射

上述应用中需要数学上一个很重要的定理，即庞加莱单值化定理。该定理是说映射的几何图形只与它的拓扑性有关，任何几何本质上可以归结为三种几何，即球面几何、欧氏几何、双曲几何。这样，我们就可以将很多很重要但又很复杂的几何用很简单的方式描述出来。

但保角映射也有其不足，所以我们发展了第二类映射——保面元映射。保面元映射能使面元的面积被保持，但角度不一定被保持。如图2所示，保角映射有可能将一个面拉得很远（如图2(b)），而保面元映射（如图2(c)）则不会产生这种情况。根据凸几何中的闵可夫斯基定理和亚历山大定理，保面元映射可以通过求解蒙日-安培方程得到。

图2 曲面的保角映射和保面元映射

计算机视觉：动态曲面追踪

计算机视觉中一个很重要的问题是动态曲面追踪（如图3），即给定一系列动态三维曲面，如何自动找到曲面间的光滑映射，使得特征点匹配，映射带来的几何畸变最小。共形映射也可以用来求解动态曲面追踪，并且应用到表情识别和追踪中，可以从一个人的各种面部表情得到他的重要面部特征。主要方法是用共形映射或保面元映射将它们映射到平面上，然后用拟共形映射来寻找最佳微分同胚。拟共形映射是一个很重要的数学工具，它在计算机数学上具有广泛应用。至今，数学家们仍在研究拟共形映射及其性质。它不是一个正则方程，而是一个伪正则方程，即Beltrami方程。在研究图形图像变形时这个方程非常重要，我们可以在微分同胚空间中进行变分，得到最优的映射。该方法在医疗和动漫中都有很重要的应用。

图3 动态曲面追踪

计算力学：六面体网格生成

在计算力学中会经常用到六面体网格来进行有限元分析。我们也可以使用共形映射生成一个网格曲面的规则六面体网格，并且具有尽量少的奇异点和奇异线。图4是在一只兔子模型内部生成了比较好的六面体网格。根据拓扑学理论，生成六面体网格时通常会产生一些奇异点。基于叶状结构理论，我们对这些奇异点进行分类，并进行了一些深入的研究，从而得出了一些在计算机科学上有意义的结论。

图4 兔子曲面的六面体网格生成

数字几何处理：几何压缩

数字几何处理中一个很重要的问题是几何压缩。在进行几何压缩时需要用到蒙日-安培理论和几何逼近理论。如何压缩复杂几何数据，保证几何误差最小，并同时保证黎曼度量、曲率测度和微分算子的收敛性，这就是几何压缩问题。我们采取的解决方法是用共形映射将曲面映射到平面，再用蒙日-安培理论，将高曲率区域放大，然后重新采样，并在共形参数域上进行Delaunay三角剖分。这样得到的简化多面体网格就能够保证黎曼度量、曲率测度和微分算子收敛。采用不同的几何压缩方法将图5(a)所示的三角网格压缩到4000个顶点所得的结果如图5(b)和图5(c)所示。

图5 不同的几何压缩方法对比

人工智能

机器学习算法需要大量的有标注的样本数据。对于图像分类，经常需要使用上千万张有标注的图像来进行训练。对于语音识别，需要成千上万小时有标注的语音数据。对于机器翻译，通常是在千万量级的双语语对上进行训练。但是很多领域却无法收集大数据，一是因为实例过少，例如医疗方面的疑难杂症；二是由于过于抽象，例如几何研究中的高维流形等。

机器学习算法中的深度神经网络需要数十亿个参数，需要昂贵的硬件支持和漫长的计算时间，训练难度很大。机器学习算法等价于能量优化。由于规模庞大，无法用二阶优化，因而一般是用随机梯度下降法。由于深度神经网络层数过深，经常出现梯度消失和梯度爆炸的问题，因此训练过程收敛困难。

目前，以神经网络为代表的统计机器学习在工程实践中取得了成功，但是其理论基础非常薄弱，被人们称为黑箱算法。人工智能算法的不可解释性，极大地阻碍了这一领域的进一步应用和发展。深度学习理论的建立，应该是目前最为迫切的问题。

人类的智能主要包括归纳总结和逻辑演绎，对应着人工智能中的联结主义（如人工神经网络）和符号主义（如Groebner Basis方法）。人类对大量的视觉听觉信号的感知处理都是下意识的，是基于大脑皮层神经网络的学习方法；大量的数学推导和定理证明是有强烈主观意识的，是基于公理系统的符号演算方法。

虽然人工智能的算法原理目前没有被透彻理解，但我们相信其内在原理可以用现代几何原理来解释。例如，对于机器定理的证明，我们运用了希尔伯特定理；对于生成对抗网络，我们运用了亚历山大定理和蒙日-安培方程。

人工智能中，符号主义的一个代表就是机器定理证明。目前基于符号计算的机器定理证明的理论根基是希尔伯特定理：多元多项式环中的理想都是有限生成的。首先，我们将一个几何命题的条件转换成代数多项式，同时把结论也转换成多项式，然后证明条件多项式生成的根理想包含结论对应的多项式，即将定理证明转化为根理想成员判定问题。一般而言，多项式理想的基底并不唯一，Groebner基方法可以生成满足特定条件的理想基底，因此可以自动判定理想成员问题。从计算角度而言，Groebner基方法所要解决的问题的本质复杂度都是超指数级别的，所以即便对于简单的几何命题，其机器证明过程都可能引发储存空间的指数爆炸，这揭示了机器定理证明的本质难度。到目前为止，机器定理证明方法还没有发现深刻的定理。

生成对抗网络是联结主义的一个例子。生成对抗网络其实就是以己之矛克己之盾，在矛盾中发展，使得矛更加锋利，盾更加强韧。这里的盾被称为判别器，矛被称为生成器。通常生成器G将一个随机变量（例如高斯分布或者均匀分布），通过参数化的概率生成模型（通常是用一个深度神经网进行参数化）进行概率分布的逆变换采样，从而得到一个生成的概率分布。判别器D通常也采用深度卷积神经网络。例如，给定两个概率分布μ和v，其中μ是随机白噪声，v是人脸相片的概率分布。这样，生成对抗网络问题就是在两个概率分布μ和v之间找到一个最优传输映射（见图6）。我们可以通过对蒙日-安培方程进行求解来找到最优传输映射，从而节省很多生成对抗的时间。蒙日-安培方程本身就等价于微分几何中的亚历山大定理。

图6 生成模型

生成对抗网络实质上是用深度神经网络来计算概率测度之间的变换。虽然规模宏大，但是数学本质并不复杂。应用相对成熟的最优传输理论和蒙日-安培理论，我们可以为机器学习的黑箱给出透明的几何解释，这有助于设计出更为高效和可靠的计算方法。

总结与展望

现代数学和计算机科学的发展紧密相关。共形几何的单值化定理、蒙日-安培理论、最优传输理论、凸几何的Minkowski-Alexandrov理论等现代几何中的深刻定理，已经应用到计算机科学的许多领域。特别地，数字金融中的区块链技术依赖于数论的现代成果，人工智能的理论解释依赖于现代代数中的希尔伯特理论等。

希望我们能够将更多的数学理论应用到计算机科学中，不仅能有效地提出各种计算机算法，而且能给出理论的基础。人工智能需要一个坚实的理论基础，否则它的发展会有很大困难。我们期待计算机科学与现代几何能有更为深刻和密切的结合，更多的跨学科领域被创立、成长和壮大。我们相信人工智能的理论基础，深度学习的几何解释和数字金融的理论近期会得到蓬勃发展！

（本文根据CNCC 2017特邀报告整理而成）

刘利刚

整理者：

CCF专业会员、杰出演讲者，CCF计算机辅助设计与图形学专委会常委。中国科学技术大学数学科学学院计算与应用数学系主任、教授。主要研究方向为计算机图形学与计算几何。

lgliu@ustc.edu.cn

脚注

1. 欧几里得（希腊文：Ευκλειδης，公元前330年~前275年），也被称为亚历山大里亚的欧几里得，以便区别于墨伽拉的欧几里得。古希腊数学家，被称为“几何学之父”。他活跃于托勒密一世（公元前323年~前283年）时期的亚历山大里亚，也是亚历山大学派的成员。他在著作《几何原本》中提出五大公设，成为欧洲数学的基础。欧几里得也写过一些关于透视、圆锥曲线、球面几何学及数论的作品。欧几里得几何被广泛认为是数学领域的经典之作。

2. 阿基米德（Archimedes，公元前287年~前212年），古希腊哲学家、数学家、物理学家、力学家，静态力学和流体静力学的奠基人，享有“力学之父”的美称。阿基米德和高斯、牛顿并列为世界三大数学家。“给我一个支点，我就能撬起整个地球”是他的名言。

3. 郑绍远，1970年毕业于香港中文大学联合书院数学系，师从国际著名数学家陈省身先生，在美国加州大学伯克利分校获得博士学位。后在普林斯顿大学、纽约州立大学石溪分校、加州大学洛杉矶分校等任教，之后在香港中文大学、香港科技大学数学系任系主任。他的卓越贡献是黎曼流形上的Laplacian特征值的比较定理。他与丘成桐教授合作解决了高级Minkowski问题，对Monge-Ampere方程、黎曼流形的特征值估计等方面作出了突出贡献。

4. 李伟光(Peter Li)，美国加州大学尔湾分校数学系华裔教授，美国艺术和科学院院士。1982年丘成桐与李伟光合著的论文，给出了线性热方程的逐点微分不等式，在沿曲线积分后可以给出经典的Harnack不等式。被称为“李-丘”的工作所得到的Harnack不等式也是汉米尔顿(Hamilton)开创早先解决方案进行分析的基础。李伟光19岁赴美国求学，先后获得加州大学弗雷斯诺分校数学学士，加州大学伯克利分校数学硕士和博士学位。

5. Allen B, Lippner G, Chen Y T, et al. Evolutionary dynamics on any population structure[J]. Nature, 2017, 544(7649):227.

中国计算机学会

微信号：ccfvoice