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

博文

计算机应用中存在性证明的代数拓扑方法 精选

已有 9173 次阅读 2019-3-15 18:41 |系统分类:观点评述


“代数拓扑的语言为什么这么古怪?它究竟在说些什么?我们为什么要学习代数拓扑?在计算机方面有什么实际应用吗?”发问的是一位少年,目光澄澈,表情无辜,虽然满脸胶原蛋白,但是已经稍显谢顶的倾向,这是典型的早期男博士生的形象。


这些问题令老顾陷入深思。其实老顾内心很清楚,如果这位同学潜心钻研代数拓扑,那么不出一年,他自己应该可以完全回答前面几个理论问题,假以时日,他自然会找到计算机方面的应用。但是,令老顾纠结的是目前深度学习的方法迅猛发展,几乎颠覆了计算机视觉领域的所有分支,那么是应该让这位同学潜心学习抽象的代数拓扑还是训练他实际的调参能力?


斟酌再三,老顾决定给这位同学讲一下自己亲身经历的一些计算机科学方面的研究项目,这些项目的关键思想来自代数拓扑,再让这位同学自行决定自己未来的道路。

人工智能的符号主义

在上一次人工智能的浪潮中,人们普遍认可的方法是符号主义。人类的知识体系一直遵循着古希腊人创立的公理-定理体系,从显而易见的基本事实开始搭建公理体系,用逻辑从公理推演,从而建筑宏伟的理论体系。从欧几里得几何学到牛顿力学,直至广义相对论,都是如此构造。代数拓扑遵循这一框架,从直观的公理体系出发,通过严格的代数运算来推演一切定理。


如果将公理符号化,用逻辑代数,我们可以计算出来理论体系中的所有定理。因此,人们认为智慧在很大层面上就是逻辑推理。人工智能的主要目标之一就是开发各种算法来实现自动推理。这方面的最为成功的领域是机器定理证明,其中最为杰出的代表是吴文俊先生所创立的“吴方法”。这里的基本思想是将条件和结论都表述成多元多项式,然后判断结论多项式是否在条件多项式生成的理想里面。应用吴方法,计算机完全可以自动证明欧几里得几何学中的所有定理。后来,吴先生的高足高晓山研究员推广出“微分结式”方法,从而可以用计算机证明局部微分几何的定理,例如从黎曼度量得到高斯曲率公式。


老顾有幸有机会和高晓山教授、王东明院士请教机器定理证明的问题。他们认为目前机器定理证明依然无法证明整体微分几何定理,例如著名的高斯-博纳定理,即高斯曲率在整个曲面上的积分和欧拉示性数的关系。陈省身先生曾经指出从局部微分几何到整体微分几何的桥梁在于代数拓扑。如果机器定理证明方法能够证明代数拓扑定理,那么整体微分几何定理就可以被计算机自动证明。

人工智能的联结主义

目前我们所处的人工智能浪潮以联结主义为主,人们更加注重相关性而非因果性,用联合概率分布来取代传统的定理、定律,并在图像、语音、文本处理等很多方面取得了突破性进展。深度学习方法的理论根基在于统计概率分布的表示和变换。那么,概率分布变换的最为基本而普适的理论自然是最优传输理论(Optimal Mass Transportation Theory)。


图1. 最优传输映射可以实现流形上概率分布的变换。


最优传输理论被广泛应用于生成模型(Generative Model),例如近年来非常热门的对抗-生成网络(Generative-Adverserial Networks)。最优传输理论涉及到蒙日-安培方程(Monge-Ampere Equation),从而有一个非常直观的几何解释:闵可夫斯基(Minkowski)问题和亚历山大(Alexandroff)问题。


      图2. Alexandroff问题。


Alexandroff问题如图2所示,给定三维欧氏空间中的一族平面,平面的法向量固定,但是高度未知,这些平面的“上包络”构成一个开放的凸多面体。凸多面体向平面圆盘投影,构成圆盘的剖分,每个胞腔的面积给定,试问凸多面体是否存在,是否唯一。Alexandroff在1950年代证明了对于任意给定的胞腔投影面积,如果这些投影面积之和等于圆盘面积,那么凸多面体存在,并且彼此相差一个垂直平移。


Alexandroff的证明是基于代数拓扑中的区域不变性定理 (invariance of domain):假设  是连通开集,映射是连续单射,那么也是开集,是拓扑同胚。


Alexandroff的证明思路如下:设平面族为,这里梯度固定,截距变动;平面族的上包络函数为,上包络投影到平面,形成平面的胞腔分解,支撑平面映射到平面的胞腔,胞腔和平面圆盘的交集面积为。那么,所有胞腔面积和等于圆盘面积:;我们要求所有平面的截距和等于0:。如此我们得从截距到投影面积的映射:

显然这个映射是连续映射。由Brunn-Minkowski不等式,可以证明是单射。由区域不变性定理,我们知道是满射。因此,任给投影面积,存在截距,即存在满足要求的凸多面体。

共形模问题

图3. 共形变换:狭缝映射。


图3显示了共形变换中的狭缝映射(slit mapping)。给定一个带黎曼度量的曲面,亏格为0,带有多个边界,则存在一个共形映射,将曲面映到单位平面环带,两条边界映成内圆和外圆,其他边界映成同心圆弧(狭缝),并且这种映射彼此相差一个旋转。这种映射的存在性依赖于Hodge理论:黎曼流形上椭圆型偏微分方程解的空间维数等于相应上同调群的维数。

图4. 曲面上的全纯微分。


假设共形狭缝映射存在,那么映射的微分是曲面上的全纯微分形式(holomorphic differential),全纯微分的实部满足曲面上椭圆型PDE,每个上同调类中存在唯一的解。这里,存在性依赖于曲面的上同调群。同调群是代数拓扑的基本概念。曾经有一位清华的访问学生学会了共形狭缝映射方法,巧妙地用于图像矢量化工作,后来成为一名英国大学的教授。


图5. 圆域映射。


图5显示了另外一种典范映射,圆域映射,就是将0亏格多联通曲面映到单位圆环上,每条边界映射欧氏圆。我们需要证明这种映射的存在性和唯一性。由狭缝映射的存在性,我们知道曲面可以映到狭缝区域,如果每个狭缝区域能够贡献映射到平面圆域,那么定理得证。我们考察从圆域到狭缝区域的共形映射:


,


在圆域中,每个小圆用圆心和半径来表示;在狭缝域中,每条狭缝用半径,起始和终止角度来表示,我们用表示内圆半径,等到映射



如果两个圆域之间存在共形映射,我们将圆域关于其内部边界反演,根据Schwartz反射原理(Schwartz Reflection Principle),我们可以将共形映射拓展到反射像上。重复反演过程,直至填满整个圆盘,那么延拓后的共形映射必为恒同映射,这意味着初始的两个圆域重合。由此,我们可以证明从圆域到狭缝域的映射为单射。不难证明也是连续映射。由区域不变性定理,为满射。任何一个狭缝区域,可以映成圆域。圆域共形映射定理得证。

离散黎奇流

黎奇流方法是一种强有力的计算方法,给定目标曲率,它可以算出相应的黎曼度量。假设给黎曼度量曲面,黎曼度量诱导的高斯曲率为,满足高斯-博纳定理

,

设共形因子函数为,黎曼度量变换为,诱导的曲率为,那么它们满足Yamabe方程

,

共形因子可以由Ricci 流方法算出,

在计算机应用中,我们用离散的三角网格来逼近曲面,用边长来定义离散黎曼度量,用角欠(angle deficit,即每个顶点周角和与平面周角和之差差)来定义离散高斯曲率。我们在顶点集合上定义离散共形因子函数,离散度量的共形变换定义为。离散Ricci流和连续Ricci流定义一致。


在实际应用中,我们发现了严重的问题。在流的过程中,经常会出现某些三角形退化,其边长的三角形不等式不再成立,Ricci流无以为继,以失败而告终。那么哪些目标曲率能够达到,流过去的路径是否存在,如何设计这种路径,这些问题必须得到完满回答,否则算法不具有实用价值。后来经过大量实验,我们发现原来思想上的有一个误区,那就是保持曲面的组合结构不变,如果我们容许在流的过程中三角剖分动态变化,始终和当前的度量保持Delaunay关系,那么离散Ricci流从来不会退化。但是,我们需要严格证明在这种流下,算法能够到达目标曲率,换言之,我们需要证明离散黎奇流解的存在性。


这一证明非常困难,因为从初始黎曼度量有无穷多种路径到达目标度量,依循不同的路径,三角剖分非发生复杂的变化,我们需要证明目标度量下所有几何量和组合结构和路径选取无关。最终我们要证明从离散共形因子到离散高斯曲率

是连续单射,根据区域不变定理,这个映射是满射,因此对于任意目标曲率满足高斯-博纳条件,离散共形度量存在。


图6. 单值化定理。


这一定理可以推出离散单值化定理,即所有曲面可以配备三种标准度量中的一种:球面,欧氏或者双曲度量。

直觉与反直觉

通过上面的几个例子,我们看到代数拓扑是存在性证明的强有力的工具,对于很多非常基本的几何算法,其解的存在性和计算稳定性都需要代数拓扑作为理论支撑。在科研中,我们频繁使用区域不变定理,这一定理貌似简单,但是其证明非常艰深,并且这种艰深是来自深刻概念上的艰深。这一定理来自若当分离定理(Jordan Separation theorem),若当定理是老顾见过的最为“大智若愚”的定理。

图7. 若当曲线定理。


如图7所示,若当曲线定理(Jordan Curve Theorem)说平面上一条连续封闭简单曲线(无自交点)将平面分成两个分离的连通子集,内部和外部。每个子集自身都是道路连通的,但是彼此分离。这一定理非常符合人类直觉,以至于我们觉得它是不辩自明的。我们无法确认这一事实是一条定理,还是一条公理。人类也是经历了漫长岁月,才意识到这一事实需要严格证明,又花费了漫长岁月才真正给出严格的证明。那么,我们为什么需要用如此晦涩的语言来证明如此显而易见的事实呢?难道是出于数学家的孤芳自赏吗?


真正的原因在于人类的直觉并不可靠,很多貌似合理的论断都是似是而非的谬论。另一方面,人类在拓扑方面的直觉相对有限,高维情形很难建立起来想像力,唯一能够把握的只有严格的数学推导。比如,我们观察图7,Jordan曲线将平面分成道路连通的两部分,每一部分都是单连通的,亦即在曲线内部(或者外部)的任意封闭曲线都可以在内部(或者外部)逐渐缩成一个点。这一观察也非常符合直觉。这被称为是Schonflies定理。但是当我们将这两个结论推向高维的时候,我们发现直觉起不了太大作用,Jordan分离定理可以被推广,但是Schonflies定理在三维的时候就已经失效。


那么,我们为什么这么重视如此反直觉的拓扑定理?因为这个古怪的定理可以推出区域不变性定理,而区域不变性定理可以证明大量计算机算法解的存在性,是计算机科学不可或缺的理论基础。

小结

代数拓扑非常抽象,但是深邃优美,为工程应用提供了理论基础。从增强学术修养角度而言,也是值得学习。代数拓扑的思想手法对于研究符号主义的人工智能非常有意义,她为我们提供了一个不同的视角来思考如何定义智能。


目前计算机技术发展非常迅猛,因此在一定程度上理论分析相对滞后。很多学生忽视理论修养的培养,将有限的精力全部投入到无限的调参上去,这种学习方法值得商榷。例如,在Wasserstein GAN中,有一个广为人知的困难:如果概率分布的支集(support)具有多个连通分支,那么GAN的训练收敛非常困难。很多学生百折不挠地调整参数,试图解决这一问题。根据我们的理论结果,在这种情形下,最优传输映射无法被深度神经网络表示,换言之,在DNN的框架下,解并不存在,因此工程上无论如何努力,也弥补不了理论的缺陷。


看着少年渐渐深入深思,老顾相信他会潜心研究代数拓扑的。老顾知道他的精神必将会经历一次深刻的洗礼。希望未来有一天,他能够用代数拓扑给出某个算法解的存在性证明 ......

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





https://blog.sciencenet.cn/blog-2472277-1167769.html

上一篇:深度学习的几何理解(3) - 概率变换的几何观点
下一篇:一杯咖啡背后的拓扑
收藏 IP: 42.101.65.*| 热度|

7 王安良 田灿荣 张凯军 杨立坚 赛义甫 zjzhaokeqin Hyq18936853798

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

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

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-3-29 18:55

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部