深度学习的几何理解(2) – 学习能力的上限

(最近,哈佛大学丘成桐先生领导的团队,大连理工大学罗钟铉教授、雷娜教授领导的团队应用几何方法研究深度学习。老顾受邀在一些大学和科研机构做了题为“深度学习的几何观点”的报告,汇报了这方面的进展情况。这里是报告的简要记录,具体内容见【1】。)


上一次博文(深度学习的几何理解(1) – 流形分布定律)引发很大反响,许多新朋老友和老顾联系,深入探讨学术细节,并给出宝贵意见和建议,在此一并深表谢意。特别是中国科学技术大学的陈发来教授提出了和传统流形学习相比较的建议;和熊楚渝先生提出通用学习机的X-形式理论等等。


图1.jpg

图1. 巴塞罗那的马赛克(barcelona mosaic)兔子,揭示深度学习的本质。

(感谢李慧斌教授,赠送给我们艺术品,启发我们领悟深度学习。)

1.jpg

图2. 流形结构。

上一讲我们将深度学习成功的原因之一归功于流形分布定律:自然的高维数据往往集中在低维流形附近。深度学习的主要功能是学习流形的参数化映射(编码映射)2.jpg,和流形的参数化表示(解码映射3.jpg,这里4.jpg是隐空间,5.jpg是背景空间,如图2所示;同时,学习流形间的映射6.jpg,可以表示成隐空间之间的映射7.jpg

8.png

很多时候,我们在关注流形的时候,也希望能够控制其上的概率分布,这可以由流形到自身的自同胚来实现:9.jpg

流形是嵌入在背景空间之中,背景空间10.jpg是欧氏空间,隐空间11.jpg也是欧氏空间,因此所有流形间的映射最终都归结为欧氏空间之间的非线性映射:12.jpg。深度神经网络的终极目标之一就是逼近欧氏空间之间的非线性映射13.jpg

万有逼近定理

深度学习之所以有效,一个核心原因在于深度神经网络表示的函数能够以任意精度逼近连续函数,即所谓的万有逼近定理任意的连续函数14.jpg,都可以被深度神经网络以任意精度逼近。

为了方便讨论,我们假设神经网络的激活函数为ReLU函数,定义如下:

15.jpg

我们将其推广到矢量输入函数16.jpg

17.jpg.

给定一个神经网络,带有k个隐层,18.jpg,输入为19.jpg维,输出为20.jpg维,每个隐层具有21.jpg个神经元。两个相邻的隐层之间有一个仿射映射22.jpg,整个网络代表一个分片线性映射23.jpg

24.jpg.

万有逼近定理的基本证明思路如下:分片线性函数(piecewise linear function)在希尔伯特空间25.jpg中稠密,因此能够以任意精度逼近任何可积的连续函数。任意分片线性函数26.jpg可以分解为分片线性凸函数之和、之差,

27.jpg,

这里系数28.jpg29.jpg是分片线性凸函数,

30.jpg.

31.jpg可以用两层神经网络来实现,隐层的激活函数为ReLU,

32.png

由此给定任意分片线性函数33.jpg,我们都可以构造一个ReLU神经网络来加以实现。由此,对于给定的连续函数和误差界,我们都可以构造一个神经网络来逼近函数,其误差小于误差界。

但是,我们更为关心的是给定一个流形,给定一个深度神经网络,这个网络能否学习这个流形,即能否实现参数化映射,构造参数表示?

网络学习过程的观察

图2.jpg图3.jpg

图3. 自动编码器学习一条螺旋线。

我们考察一个最为简单的例子,如图3所示,一条螺旋线嵌入在二维平面上(上行左帧),autoencoder计算了编码映射,将其映射到一维直线上(上行中帧),同时计算了解码映射,将直线映回平面,得到重建的曲线(上行右帧)。编码映射诱导了平面的胞腔分解(下行左帧),编码映射和解码映射的复合诱导了更为细致的胞腔分解(下行中帧),编码映射的水平集显示在下行右帧。

由此可见,ReLU深度神经网络的每个神经元代表一个超平面,将输入空间一分为二;众多超平面将输入空间剖分,然后将每个胞腔线性映射到输出空间,由此得到编码、解码映射的分片线性逼近。进一步,我们可以得到如下关键的观察:流形(螺旋线)被输入空间上的胞腔分解分割成很多片,每片流形所在的胞腔被线性映射到参数域上(一段直线),这个线性映射限制在流形上是拓扑同胚

我们将这一计算框架和有限元方法进行类比。线性有限元也是将空间剖分,然后用分片线性函数来逼近目标函数。但是,在有限元方法中,空间剖分和线性逼近是分离的两个过程。在深度学习中,这两个过程混合在一起,密不可分。有限元的剖分更加局部灵活,深度学习的剖分全局刻板。同时,两者都是基于变分法则,即在函数空间中优化某种损失函数。我们可以将每个神经元的参数归一化,那么深度网络的所有参数构成一个紧集,损失函数是网络参数的连续函数,必然存在最大最小值。在传统有限元计算中,人们往往寻求凸能量,这样可以保证解的唯一性。在深度学习中,损失函数的凸性比较难以分析。

从历史经验我们知道,有限元分析中最为困难的步骤在于设计胞腔分解,这直接关系到解的存在性和计算的精度和稳定性。深度神经网络所诱导的输入空间剖分对于优化过程实际上也是至关重要的,我们可以定量地分析网络的空间剖分能力。

网络学习的能力

图4 (2).jpg图4.jpg

图4. 米勒佛的参数化(编码)映射。

我们参看弥勒佛曲面的编码映射,如图4所示,编码映射(参数化映射)可以被ReLU神经网络表示成分片线性映射,右列显示了输入空间和参数空间的胞腔分解。

令编码映射为34.jpg,给定一个属于背景空间的点35.jpg,那么在计算36.jpg时被激活的神经元集合记为37.jpg,称之为点38.jpg关于39.jpg的活跃路径。两个点40.jpg,如果对应的活跃路径(激活神经元集合)相同41.jpg,则我们说这两点关于映射42.jpg彼此等价。所有彼此等价的点构成了背景空间中的一个胞腔,胞腔为凸多面体。由此,43.jpg诱导了整个背景空间的一个胞腔分解,记为44.jpg。同样,编码映射和解码映射的复合也诱导了背景空间的胞腔分解45.jpg。显然,46.jpg47.jpg的一个细分(subdivision)。我们用48.jpg表示胞腔的个数。

其实,编码映射构造了一系列胞腔分解,后面的胞腔分解细分了前面的胞腔分解:

49.jpg

如果没有这些胞腔分解,那么神经网络所表达的映射只能是线性映射。正因为有了这些胞腔分解,才使得映射成为非线性映射。我们可以大致估算50.jpg的胞腔个数,以此为网络学习能力的一个指标,我们称

51.jpg

为网络的分片线性复杂度Rectified Linear Complexity)。

图5.jpg

图5.左帧编码映射诱导的空间剖分52.jpg,和右帧重建映射映诱导的空间剖分 53.jpg54.jpg55.jpg的一个细分。

图5显示了自动编码器在学习弥勒佛曲面时诱导的空间剖分,每个胞腔都是一个三维的凸多面体,被线性映射到二维参数平面上的一个低维凸多面体,可能是多边形,线段或者点。整体映射是连续的,并且限制在弥勒佛曲面上是整体拓扑同胚。这些胞腔的像显示在图4右下角。我们观察到,精细的空间剖分对于保证整体同胚性至关重要。

直接估计网络的分片线性复杂度相对困难,我们这里可以估计一个粗略的上界。我们考虑一个线性映射56.jpg, 这个映射相当于在d维欧氏空间中用n个超平面划分,所得胞腔数目的最大值记为 57.jpg。我们首先考察最为简单的二维情形-切披萨问题:假设n刀切下去,披萨最多被切成几片?一刀把披萨切成两片,假设第n刀将披萨切成58.jpg片,那么第(n+1)刀的直线和前面n条直线相交,被分成(n+1)条线段,每条线段将59.jpg中的某片一分二,由此我们得到递归公式

60.jpg.

由此,我们得到切披萨公式

61.jpg

同样推理,假设将d维欧氏空间中用n个超平面划分,所得胞腔数目为 62.jpg,第(n+1)个超平面为(d-1)维欧氏空间,被前面n个超平面划分成63.jpg个胞腔,每个(d-1)维的胞腔将 64.jpg中的某个d维胞腔一分为二,由此我们得到类似的递归公式

65.jpg

由此,我们得到欧氏空间被超平面划分所得胞腔个数的上限为:

66.jpg.

我们考虑一个前馈式神经网络,输入为67.jpg维,输出为68.jpg维,每个隐层具有69.jpg个神经元,记为

70.jpg,

那么71.jpg所诱导的胞腔分解最多有72.jpg个胞腔。复合映射所诱导的胞腔分解满足估计:

73.jpg

这一粗略估计给出了神经网络所表达的所有分片线性函数的片数的上限,亦即网络分片线性复杂度的上限。这一不等式也表明:相对于增加网络宽度,增加网络的深度能够更为有效地加强网络的复杂度,即加强网络的学习能力。

流形被学习的难度

我们再来考虑一个流形被学习的困难程度。给定一个m维的流形嵌入在n为欧氏空间中74.jpg。一个自动编码器将流形编码,即参数化75.jpg,这里隐空间为m维的欧氏空间,编码映射限制在流形上76.jpg为拓扑同胚,即连续双射,逆映射也是连续映射。这里,流形的嵌入和编码映射的同胚为流形的可被编码性(可被学习性)提出了苛刻的拓扑和几何要求。


如果流形的维数等于隐空间的维数,编码映射将流形同胚地映射到m维的欧氏空间的区域中,77.jpg,因此78.jpg的拓扑和m维的欧氏空间区域的拓扑相同,这为79.jpg的拓扑增加很多限制。例如80.jpg不可能是闭流形。在米勒佛的例子中,81.jpg为曲面,和平面某个区域同胚,则曲面必为亏格为0的多联通曲面。这意味着目前的自动编码器只能学习拓扑简单的流形,或者只能学习拓扑复杂流形的一个局部。


图6.jpg

图6. 克莱因瓶。

如果82.jpg的维数小于隐空间的维数,情形更加复杂。比如背景空间为4维欧氏空间,流形83.jpg为克莱因瓶(Klein bottle),隐空间为3维欧氏空间。那么根据矢量丛理论,克莱因瓶无法嵌入到三维欧氏空间,编码映射不存在。由此,流形的拓扑为其可学习性带来本质困难。目前,人们对于深度学习理论的理解尚未达到需要应用拓扑障碍理论的高度,我们相信未来随着深度学习方法的发展和完备,拓扑理论会被逐步引入。


图7.png

图7. 可被线性编码和不可被线性编码的曲线。

其次,参数化映射84.jpg为分片线性映射,限制在流形上85.jpg为同胚映射,这个条件决定了学习难度。假设m维流形嵌入在n维欧氏空间中86.jpg,如果存在整体线性映射87.jpg,限制在流形上为拓扑同胚,那么我们说嵌入流形是线性可编码的


图7显示了一条嵌入在平面上的曲线,左帧的曲线线性可编码,右帧的曲线不可线性编码。假如右侧曲线线性可编码,那么88.jpg的水平集是一族平行直线,每条直线被称为一根纤维。每根纤维和曲线至多只有一个交点。如果一根纤维和曲线相切,我们将纤维进行微小平移,则纤维和曲线有两个交点。曲线的切线方向涵盖了所有方向,因此我们无法找到一族平行直线,每根纤维和曲线至多只有一个交点。由此曲线不可被线性编码。


这个观察可以被推广,如果m维流形嵌入在n维欧氏空间中(m<n),并且流形可被线性编码,我们来求一个必要条件。假如流形89.jpg可以被同胚地垂直投影到一个(n-1)维的超平面90.jpg上,那么和此超平面垂直的直线和流形至多只有一个交点。我们在流形上取相异的两点,过此两点做一条直线,那么所有这种直线都不和超平面91.jpg垂直。构造映射:

92.jpg,

这里93.jpg是积流形,94.jpg是积流形中的对角线,

95.jpg,

96.jpg实射影空间,代表欧氏空间97.jpg中所有的1维线性子空间(过原点的直线)。如果像98.jpg覆盖整个实射影空间,那么流形99.jpg向任何超平面投影都不是同胚,即流形100.jpg不可被线性编码。

如图1所示,巴塞罗那的马赛克兔子,整体不可被线性编码。我们可以将流形分成很多片,每一片都是线性可编码,然后映分片线性映射来构造编码解码映射,如此分解所需要的最少片数被定义成流形的分片线性复杂度(Rectified Linear Complexity)


图8.png

图8. Peano曲线。

我们可以构造分片线性复杂度任意高的流形。图8显示了经典的皮亚诺曲线。我们首先构造一个单元,如左帧左上角红色框内所示,然后将此单元拷贝,旋转平移,重新连接,得到左帧的曲线;如果我们将单元缩小一倍,重新构造,得到右帧所示曲线。重复这一过程,我们可以构造越来越复杂的皮亚诺曲线,直至极限,极限曲线通过平面上的每一个点。在迭代过程中,每一条皮亚诺曲线所包含的单元个数呈指数增长。每个单元都是线性不可编码的,因此亚诺曲线的分片线性复杂度大于单元个数。在迭代过程中,皮亚诺曲线的分片线性复杂度呈指数增长。经过修改,Peano曲线可以经过任意维欧氏空间中的任意一点。我们将Peano曲线直积上高维球面101.jpg,就可以构造(k+1)为流形,这种流形具有任意高的复杂度。

如果一个ReLU神经网络能够对一个嵌入流形进行编码,那么网络的分片线性复杂度必定不低于流形的分片线性复杂度。通过以上讨论,我们看到对于固定组合结构的神经网络,其分片线性复杂度可以被组合结构所界定,我们可以构造一个流形其复杂度超过网络复杂度的上界。由此我们得到结论:给定一个具有固定组合结构的神经网络,存在一个流形,此网络无法学习(编码)这个流形。虽然大家都在直觉上相信这一结论,但是严格的数学证明并不普遍。这里我们将人所共知的一个基本信念加以数学证明。

图9.jpg图9-2.jpg

图9. 不同的学习效果:左帧,输入流形;右帧,Autoencoder重建的流形。

在实际应用中,深度学习具有很大的工程难度,需要很多经验性的技巧。特别是深度学习网络的学习能力取决于网络的超参数,如何设计超参数,目前主要依赖于经验。如图9所示,我们用autoencoder编码解码弥勒佛头像曲面,上面一行显示了输入输出曲面,重建后的曲面大体上模仿了米勒佛的总体形状,但是失去具体的局部细节。在下面一行,我们加宽了网络,修改了超参数,重建曲面的逼近精度提高很多。

小结

ReLU深度神经网络用分片线性函数来逼近一般的非线性函数:每个神经元定义一个超平面,所有的超平面将输入空间进行胞腔分解,每个胞腔是一个凸多面体。映射在每个胞腔上都是线性映射,整体上是连续的分片线性映射。编码映射限制在输入流形上是拓扑同胚。

深度神经网络将输入空间分解的最多胞腔个数定义为网络的分片线性复杂度,代表了网络学习能力的上限;流形需要被分解,每一片可以被背景空间的线性映射所参数化,这种分解所需的最少片数定义为流形的分片线性复杂度。一个网络能够学习一个流形的必要条件是:流形的复杂度低于网络的复杂度。对于任意一个网络,我们都可以构造一个流形,使得此网络无法学习。

目前所做的估计非常粗糙,需要进一步精化;对于优化过程的动力学,目前没有精细的理论结果,未来需要建立。

在深度学习的应用中,人们不单单只关心流形,也非常关心流形上的概率分布。如何通过改变编解码映射,使得重建概率分布很好地逼近数据概率分布,使得隐空间的概率分布符合人们预定的标准分布?这些是变分编码器(VAE)和对抗生成网络(GAN)的核心问题。下一讲,我们讨论控制概率分布方法的理论基础【2,3】。



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

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

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

上一篇:《计算共形几何》教程第一章
下一篇:深度学习的几何理解(3) – 概率变换的几何观点

© 版权声明
THE END
喜欢就支持一下吧
点赞0 分享
评论 抢沙发
头像
欢迎您留下宝贵的见解!
提交
头像

昵称

取消
昵称表情代码图片