CurvatureFlow的個人博客分享 http://blog.simestates.com/u/CurvatureFlow

博文

計算機應用中存在性證明的代數拓撲方法 精選

已有 3686 次閱讀 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日)





http://blog.simestates.com/blog-2472277-1167769.html

上一篇:深度學習的幾何理解(3) - 概率變換的幾何觀點
下一篇:技術潮汐的親歷觀察

7 趙克勤 王安良 田燦榮 張凱軍 楊立堅 賽義甫 黃裕權

該博文允許注冊用戶評論 請點擊登錄 評論 (3 個評論)

數據加載中...

Archiver|手機版|騰訊分分彩開獎歷史 ( )

GMT+8, 2019-3-26 08:53

Powered by 腾讯分分彩simestates.com

Copyright © 2007- 中國騰訊分分彩開獎記錄報社

返回頂部