吕陈君:“狗”为什么能弈胜人?

——关于人工智能的数学基础的思考
选择字号:   本文共阅读 1413 次 更新时间:2019-08-04 10:41

进入专题: 人工智能   超穷序数  

吕陈君  


摘  要:本文利用超穷序数的方法,建立起了一个相当简洁的分层神经网络的数学模型,解释了机器深度学习的工作机制。在此基础上,说明了“狗”(AlphaGo)下围棋为什么要比人类棋手聪明得多,并剖析了电脑和人脑在结构上的重要区别。


关键词:超穷序数,分层神经网络,反向传播,宽度,深度,复杂度


AlphaGo是AI史上一个里程碑事件,其“围棋上帝”般的棋力令人震惊,它甚至独立发现了人类2000年围棋史上从未发现过的博弈策略和游戏规则,这一事件毫无异议地说明:至少在下围棋这个智力游戏上,机器的学习能力远远超过了人类,它比人类棋手更“聪明”。但遗憾的是,其设计者Demis Hassabis博士说过,他并不知道AlphaGo是如何下一步棋的。“深度学习教父”G. Hinton教授也表示过,没有人知道神经网络究竟是如何工作的。我们认为,这可能需要回到计算机和人工智能的数学基础上,才能真正理解机器是如何思考和学习的。


1 从图灵博士论文谈起


计算机和人工智能的发明都源于Hilbert纲领的研究,在1900年国际数学家大会上,Hilbert提出了著名的23个问题,其中第一、第二和第十问题都是关于数学基础的。Turing为解决第十问题(丢番图方程的可解性),定义了一种能执行机械计算程序的机器,即图灵机,它是通用计算机的数学模型。Gödel在解决第二问题(公理系统的相容性)时,出人意料地证明了两个不完备性定理,在证明中,他首次使用了“程序内存”的思想,它相当于说:假设有一台机器能证明所有的数学公式,其计算程序也可以表示为一个数学公式,但这个程序公式却是不可计算的。所以,Gödel不完备性定理充分表明:任何计算机都存在着极限,通用计算机无法实现自我编程。

如果机器只能按照设计好的固定程序执行任务,它的每一步都是确定的,输出的结果也是确定的,这样它当然就谈不上具有“智能”,特别是,它不能自己修改程序,因此也就无法具备学习能力。所以,要想使机器具有“智能”,它就必须突破不完备性定理的限制,具备自动修改程序的能力,这样它才能通过不断学习来改进自己的计算方法,解决原来不可计算的问题。所以,计算机和学习机是两个概念,计算机不能自我编程,而学习机可以自我编程。

1936年,Turing写出其经典论文《论可计算数及其在可判定性问题上的应用》[1]后,就开始思考计算机如何突破不完备性定理的问题。其思考的结果,就是他1936-1938年在普林斯顿完成的博士论文《以序数为基础的逻辑系统》。[2]他的想法很简单:任何一个数学公式A都对应着一个序数a(即表示为一串数字长度),它可以用逻辑L_a来判定;利用Cantor的超穷序数,可以形成不断递增的序数序列w ,2w ,等等,相应的,就有不断递增的逻辑系统L_w,L_2w,等等,后一个系统都比前一个系统更完备,即可判定的数学公式更多。所以,如果一个公式A在L_w中不可判定,那么我们可以通过重复序数递增的过程,构造一个更完备的逻辑系统L_2w来判定它。显然,Turing序数逻辑的想法,跟后来Gödel “可构成集”[3]的概念是一脉相承的。

但Turing也意识到了,这种不断递增的序数逻辑系统,最终也逃脱不了Gödel不完备性定理的限制,它就相当于是把许多台图灵机 T1, T2, …,Ti叠加起来,后一台给前一台修改程序,但最后一台图灵机 还是存在不可计算的程序公式,不能自我修改程序,所以,整个系统完全等价于一台较大的图灵机,其程序仍是事先被设计好、固定死的。这就等于又退回到原点了。在博士论文中,图灵多少有些无奈地提出一种“神谕机”(oracle-machines)的概念,他设想存在一种“超计算”的机器,可瞬间对一个不可计算的数学问题做出判定。当然,这完全没有任何实际的意义。

后来Turing认识到了计算机和学习机之间存在重大差别。1948年他写了一篇《智能机器》的文章,提出了一种“B型非结构化机器”的神经网络,具有自动学习能力,但此文在他生前并未发表。在1950年发表的经典论文《计算机器与智能》[4]中,Turing专门谈到了学习机问题,他认为学习机是一类可以自己修改程序的统计机器,它具有不确定性,这跟图灵机是不一样的。就像Hinton谈到的:“Turing认为人类大脑是一个没有什么明确结构、连接权重也都是随机值的设备,然后只需要用强化学习的方式改变这些权重,它就可以学到任何东西,他觉得‘智慧’的最好模式就是这样的。”[5]

Turing的看法其实已经很接近现在流行的深度学习了。在他的序数逻辑方法的启发下,我们可以用超穷数来构造一个神经网络的数学模型,并对机器的思维过程做出一种纯逻辑的解释。


2 分层神经网络的超穷数模型


要理解神经网络的工作机制,我们还是得回到数学基础研究上,也就是Hilbert第一问题,它需要判定这样一个问题:实数集的数目2^w究竟等于哪一个超穷基数w_i?Cantor猜测等于2^w=w_1 ,这就是著名的连续统假设CH。

我们给出了一种构造超穷基数的新方法,[6]不同的w_i正好就构成了分层神经网络K。一台通用图灵机就是一条有w个格子的无穷长带, w表示全体自然数的数目,我们这样来理解:这w个格子就构成了K的第一层神经网络,具有 w个储存状态,它是K的“基础处理器”,即不管K具有多少层神经网络,这一层总是负责输入和输出的信号处理。

然后,我们可以定义一个 w上的递归函数f,f是可以重复叠加计算的,也就是说,它可以形成f(w)、f(f(w))、f(f(f(w)))、……等等,重复叠加计算i次,就得到一个递归函数集 f^i(w),它就是K的第i+1层神经网络。如果我们把f(w)定义为“w的全体有穷储存状态构成的集合”,那么就可以证明

w_1= f(w)

这样就会依次形成f(w_1) 、f(w_2) 、…、f(w_i)等等,任一f(w_i)都表示“w_(i-1) 的全体有穷储存状态构成的集合”,并且都有

w_(i+1)= f(w_i)

这就意味着:K的每一层神经网络,其单个储存状态都是有穷状态集合,但是其储存状态的数目是不断递增的,它就可以用来证明任何以自然数表示的算术定理。

现在我们来讨论分层神经网络,譬如,一个双层的神经网络K2 ,当输入某个信号或公式P(n)在 w层无法判定时,通过正向传播f(n)就把它输入到 w_1层,因为 w_1层的储存状态数目比 w层要大,所以,这个信号P(n)有可能在w_1层获得判定,再通过反向传播 f^(-1)(n)把它输回 w层,重新进行计算,并最终输出结果S(n)。所以,只要形成分层神经网络,系统就会自动修改通用图灵机(基础处理器)的程序,它就转变成了一台学习机。我们把这样一台能自动修改程序的机器称作“哥德尔机”。 [7]

容易理解,正向传播f是一个递归函数,而其反向传播 就是深度学习中的BP算法,它是一个概率分布函数。为什么反向传播会导致概率呢?我们可以用最简单的方法来解释。反向传播的直观含义就是:把 w_1个球装进w 个袋子中,由于w_1 > w,那么每个袋子分配球的权重均为 w⁄w_1。这是一种理想的线性分配模型。但实际上,反向传播是w_1 维状态空间到 w维状态空间上的连续映射,它是高度非线性的。[8]即,每个袋子分配球的权重是不一致的。

我们证明了:所有的w_i 都小于 2^w。这就意味着:可以形成无穷层次的神经网络,任一 w_i层和 w_(i+1)层之间均可形成正向传播 f^i和反向传播 f^(-i)。这就是深度学习的超穷数模型。

最近,2001年沃尔夫数学奖得主、集合论专家S.Shelah证明了一个有趣的定理:实数的基数2^w ,要么比所有超穷基数 w_i都大,要么就不超过 w_4。[9]这似乎就意味着:神经网络最多可能搭建到第4层为止。但这跟代数中五次代数方程无通解,是否存在着某种更深刻的内在联系,引起了人们极大的兴趣。需要说明的是:本文讨论的神经网络的层次,跟工程上搭建的层次是不同的概念,我们讲的是一种纯粹的数学概念。


3 “狗”的棋力为什么远超人类


实际上,无论电脑还是人脑,其内部储存状态数目都不可能是无限多的,也就是说,其分层神经网络的基础处理器只能是有穷长带,其分层也只能是有限层数,所以,神经网络K就是一个四元组:

n表示其基础处理器的格子数,称为K的“宽度”; imax表示其最大的分层数,称为K的“深度”;f是定义在 n上的计算规则;N是K执行一项任务的复杂度,


且n远小于 N。通过重复叠加计算,K最多可以形成 imax个层次f(n)、f((n))、…、 f^(imax)(n),令ni = f^i(n),则有

ni > n_(i-1)

如果存在一个i,使得

f^i(n)≥ N

我们就称“复杂度N被分解”,那么机器就可以通过反向传播来执行任务了。但如果 f^(imax)(n) < N,此项任务就无法执行。也就是说,正向传播是递归计算,反向传播是概率演算,只要达到f^(imax)(n) ≥ N,这两种过程就构成一种必然发生的互逆性或互补性的自组织系统。

“狗”(AlphaGo)是一个二进位制多维Boolean函数空间,其递归计算函数f定义为:

f^i(n)=2^(n_(i-1))

其每一层储存状态数目是按幂指数来递增的,这个增速是极为迅速的。假如“狗”的宽度为10,即其基础处理器是一个10个格子的图灵机,那么只要形成2层神经网络——“狗”包括“策略网络”和“价值网络”两层,它就可以具备2^1024 个内部储存状态,这就远远超过围棋所有能走的步骤数 ,即围棋的复杂度。这样看来,围棋的复杂度并不算高。

如果把“狗脑”和人脑都看作是两台分层神经网络,那么下围棋,为什么“狗”要远远超过人呢?这是因为,“狗脑”的宽度要远远大于人脑的宽度,人脑一次最多只能计算不到20步棋,而“狗脑”一次可以计算上百万步棋。对下围棋这样复杂度不算太高的任务来说,走棋的效率取决于其宽度而不是深度。如果是复杂度非常高的任务,执行的效率就取决于其深度而非宽度了,因为深度的增加会带来内部储存状态数目的指数暴涨。人脑的结构要比“狗脑”复杂得多,它可能比“狗脑”的层次更深,即“狗脑”比人脑要宽很多,但可能没有人脑那么深。从这种意义上说,在执行更复杂的任务时,譬如自然语言理解、自由联想、表达情感、群集(swarm)、遗传、进化等,“狗”可能就未必会超过人了。

大家之所以对“狗”走棋感到很神秘,因为这一步棋不是计算出来的,但是我们能通过反向传播来计算出走这一步棋的概率。打个比方来说,明天下不下雨是不确定的,但我们能准确计算出明天下雨的概率。在不确定性中往往又隐藏着某种确定性,这其实一点也不神秘。所以,像意识、思维、智力、智慧等这些概念,无须把它们想得太神秘了。凡是能在不确定性的状态中找到某种确定性的结果或结构,我们都称之为“智力”或“智慧”。不仅人脑具有这种智慧,自然界许多自组织系统也广泛存在这种智慧。我们相信,机器也具有这种智慧。因为,这些不同类型的“智慧”都遵循着共同的数学原理。


4 一个数学猜想:超穷数和计算复杂性


在计算机中,一个信息都可以表示成一个数字符号0或1的长串,这就是一个编码,其长度可以用一个超穷序数a来表示,a就表示这个信息的复杂度。显然,越复杂的信息,其编码的长度a就越大。这里,我们先要讲清楚两个问题:

第一, 实数集和复数集都比自然数集的长度要大,也就是复杂度更大,所以,如果要计算定义在这些集合上的函数复杂度时,当然就需要用到比自然数集的长度w更大的超穷序数a,这是自然的;

第二, 任何计算机只能处理有穷数,也就是说,它不可能真的有一条无穷长的带子,所以,我们必须还要把一个超穷序数a处理成一个自然数n的迭代函数,这样它才可以真的用于计算。

所以,我们提出一个数学猜想:可以用超穷序数来表示一个数学公式的计算复杂性,这个超穷序数还能表示成一个可计算的自然数迭代函数。这样一来,就等于是建立了一个通用学习机的超穷数模型。

按照康托的超穷数理论,超穷序数的增长有两种方式,一种是序数增加但基数不变,譬如序数从 w^2增长到w^3 ,它是按基数w的指数w^n来增长的,我们就称之为“指数复杂性”,这种情况,集合的元素数目是不变的,迭代函数都在同一个集合w中取值;另一种是序数增加、基数也增加,譬如序数从w_1增长到w_2 ,这种情况,集合的元素数目也在增加,也就是说,迭代函数在集合 w_1中取值就变成了在集合w_2 中取值,但可以规定:

任一u∈w_i g(u) =: 任一u1,u2 ,…,ui ∈w g^i( u1,u2 ,…, ui, u_(i+1)),i≥1

也就是说,我们可以把一个在集合w_i 中取值的单元函数g,等价转换成一个在集合w中取值的i维空间函数g^i ,所以,如果在集合w_1 中取值,就相当于一个二维空间<(u1 ,u2 )|u1 ,u2 ∈w>,在 w_2中取值,就相当于一个三维空间<( u1, u2,u3 ) | u1, u2, u3∈w>,它是按维数来增长的,我们就称之为“维数复杂性”。

所以,计算复杂性可分为“指数复杂性”和“维数复杂性”两种类型,这对我们理解机器的内部结构是关键性的概念。一个计算系统的复杂性按照指数和维数来递增,都可以形成分层结构,但这两者的计算行为是不一样的,我们来做一个简单的描述:

在指数复杂性的计算系统中,其上下层存储状态集的基数是相等的,所以,它的反向传播也是确定性的,只要一步一步去搜寻,必然就会找到匹配的结果。我们打个比方来说,譬如一个密码系统,如果密码的编号就在系统的存储集中,我们只要一步一步去搜寻,总能找到匹配的结果。此时,其反向传播就是线性代数,这就是一个线性的概率分布空间。像AlphaGo就是这样的计算系统,机器总能找到最优的算法,现在AlphaGo能做到13层网络,但它们都是在同一维度空间内的分层结构。我们猜想:在指数复杂性的计算系统中,“N⁄NP问题”是成立的。因为,我们最后总能找到密码,也就是说,机器总能写出一个正确的程序。

但在维数复杂性的计算系统中,其上下层存储状态集的基数是不相等的,所以,它的反向传播也是不确定性的,我们一步一步去搜寻,最后不一定能找到匹配的结果。譬如,一个密码系统,如果密码的编号不在系统的存储集中,一步一步去搜寻,最后也不一定就能找到匹配的结果。此时,其反向传播就是高维空间向低维空间的投影映射,这就是一个非线性的概率分布空间。我们猜想:在维数复杂性的计算系统中,“N⁄NP问题”是不成立的。因为,我们最后不一定能找到密码,也就是说,机器不一定能写出一个正确的程序。

这就是我们对计算复杂性的两种直觉思考,当然它还需要做进一步的严格数学定义,还只是一种数学想象。两种计算复杂性,其实也就是两种不同的计算行为。图灵机可以处理指数复杂性问题,但对维数复杂性就不行了,我们必须去探索新的计算模式。通用学习机也好,GAI也好,都需要突破图灵机,这是新一代人工智能理论突破的关键所在。现在人们对计算复杂性、对数学基础的理解,都超越了图灵和哥德尔的时代,新世纪的数学曙光已经照耀在地平线之上。


References

[1] A. M.Turing(1936) :“On Computable Numbers”,with an Application to the Entscheidungsproblem”,Proc.London Math.Soc.43:544;also 42(1936).

[2] A. M.Turing(1938) :“Systems of logic based on ordinals”, transcribed by Artificial Intelligence and Computer Science Laboratory, Universidade do Porto, Portugal, September 18, 2014.

[3] K. G?del(1939):“The Consistency of the Continuum Hypothesis”,Proc.Natl.Acad.U.S.A,25,(1939),pp220-224.

[4] A. M.Turing(1950) :“?Computing Machinery and Intelligence”,Mind.LIX,no.2236(1950.10),pp433-460.

[5]AI科技评论(2019):“和 Geoffery Hinton 面对面聊聊”,文章来源: https://mp.weixin.qq.com/s/dXidHuHgLPGc8-nH6E76Ew.

[6] Chenjun Lv(2016):“Negative Proof about Continuum Hypothesis”,文章来源:https://www.researchgate.net/publication/333942528_Negative_Proof_about_Continuum_Hypothesisrevised_editionpdf.

[7] Chenjun?Lv,Xiaohui?Zou(2018):“How to Understand the Mathematical Basis of Two Basic Types of Computational Behavior”,文章来源:https://link.springer.com/chapter/10.1007/978-981-13-7983-3_27?from=timeline&isappinstalled=0.

[8]Rumelhart D,Hinton G,Williams R(1986):“Learning internal representations by error propagation”,in Parallel Distributed Processing,chapter 8.MIT Press,Cambridge,MA.

[9] M. Malliaris, S. Shelah(2018):“A separation theorem for simple theories”,文章来源:https://www.researchgate.net/publication/328474877_A_separation_theorem_for_simple_theories.



    进入专题: 人工智能   超穷序数  

本文责编:limei
发信站:爱思想(https://www.aisixiang.com)
栏目: 科学 > 科学评论
本文链接:https://www.aisixiang.com/data/117444.html
文章来源:作者授权爱思想发布,转载请注明出处(https://www.aisixiang.com)。

爱思想(aisixiang.com)网站为公益纯学术网站,旨在推动学术繁荣、塑造社会精神。
凡本网首发及经作者授权但非首发的所有作品,版权归作者本人所有。网络转载请注明作者、出处并保持完整,纸媒转载请经本网或作者本人书面授权。
凡本网注明“来源:XXX(非爱思想网)”的作品,均转载自其它媒体,转载目的在于分享信息、助推思想传播,并不代表本网赞同其观点和对其真实性负责。若作者或版权人不愿被使用,请来函指出,本网即予改正。
Powered by aisixiang.com Copyright © 2023 by aisixiang.com All Rights Reserved 爱思想 京ICP备12007865号-1 京公网安备11010602120014号.
工业和信息化部备案管理系统