复杂性与智能化：从Church-Turning Thesis到AlphaGo Thesis及其展望(1)

王飞跃

人机围棋大战之后,许多方面闻风而动,大小会议无数,投资热情高涨,使近年来已经火热的人工智能,锋势更加凶猛.然而,我更希望业内人士能够闻声而静:历史的经验告诉我们,闻风而动,一阵骚动之后,往往烟消云散,随后无影无踪;闻声而静,一段沉寂之后,可能云飞浪涌,结果惊天动地.

在短短一个多月的时间,我对于AlphaGo的看法发生了很大的变化.由于一直认为计算机围棋不可能只靠“暴力”计算来完成,必须引入智能成分,因此,觉要需要长期的努力,至少是自己退休时可以专注的一件亊情.所以,当谷歌在《自然》杂志发表AlphaGo文章后随即宣布挑战南韩棋手李世石时,我曾认为这多属商业炒作,无实质技术内容.然而,春节期间,当我认真读完几篇主要论文并粗读了其他十多篇相关文献后[1−5],对AlphaGo可能引发的冲击,有了不同的认识.比赛之前,我表示希望AlphaGo战胜李世石[6],因为机器的胜利,将使更多人清醒,认识到继“老”IT的工业技术(Industrial Technology)和“旧”IT 信息技术(Information Technology)之后,以人工智能和机器人为主要表征的“新”IT智能技术(Intelligengt Technology)时代,已经来临.为此,我们必须转变思维方式,来一场深刻变革性的“范式转移”.

为什么我会由AlphaGo产生这些看法？这与自己的研究经历和机遇密切相关.而且,我相信这也与未来的指挥与控制,特别是平行智能技术及其在智能军事与智慧战争中的作用极其相关.在此,抛砖引玉,希望更多的业内专家闻声而静,深度思索,尽快开辟一条切实有效利用新IT智能技术变革现代指挥与控制的道路.

1 复杂性与智能化:两个学术家族的故事

20世纪80年代,我刚到美国留学,在借住教堂的小图书馆里,翻到了布尔的《思维定律》(The Laws of Thought).后来,主教Ezra Pickup见我非常喜欢此书,就将书赠送给我.这本书不仅成为了我收藏的第一部珍本,也让我结识了Robert F.McNaughton教授,成为他的学生,从而对两个学术家族在复杂性和智能化研究上的成就,有了自己特别的个人体会与认识.

据布尔夫人回忆,布尔与同时代的学术好友摩根(Augustus De Morgan)和巴贝奇(Charles Babbage)在形式逻辑方向的研究都间接但深刻地受到了她的叔叔George Everest(英文喜马拉雅山的珠穆朗玛峰就是以此人命名的,Everest从1830年到1843年是印度的总勘测师,但他反对以自己的名字命名珠穆朗玛峰)的影响.三人的成就非凡,都对后世产生了巨大的冲击：布尔号称“现代逻辑之父”,其布尔代数是电路设计、信息论和计算机的核心方法;巴贝奇发明了机械计算机“Analytical Engine”,号称“计算机之父”;而摩根的摩根定律和数学归纳法更是现代逻辑和数学的基础,合起来堪称是当代计算机、人工智能和信息产业的基石.

摩根是布尔理论的坚定支持者,同时,他和自己的学生开创了深具哲学特色的复杂性与智能化研究学术家族.摩根的第一个学生Edward Routh是现代力学和控制理论的先驱,著有《固体系统动力学》(Dynamics of a System of Rigid Bodies,1860),代表性工作为控制系统的Routh稳定性判据和关于稳定性的Routh-Hurwitz定理,这是每一个控制系统学生所必须了解的.摩根还有其他一些有名的学生,包括在矩阵、数论、分割和不变量理论有着重大贡献的James Sylvester,他是19世纪中后期美国数学界的领袖,也是美国数学杂志《American Journal of Mathematics》的创办人;经济和逻辑学家William Jevons,著有《政治经济学的一般数学理论》(A General Mathematical Theory of Political Economy,1862),开创了数学经济学,特别是边际效用理论的研究,此外,Jevons还著有《科学原理》和《政治经济学理论》等,其发明之一就是机械计算的“逻辑钢琴”;摩根的学生中,与计算机最相关的是Ada Lovelace,她为巴贝奇的计算机“Dif f erence Engine”和“Analytical Engine”写下了第一个“算法”(Algorithm)或“程序”(Program),所以被称为世界上第一个程序员.Lovelace是英国著名诗人拜伦的唯一“合法”女儿,尽管后人对她在计算机的实际贡献有所置疑,但今天有许多以Lovelace命名的计算机领域奖章和奖项,就连美国国防部为嵌入和实时系统开发的面向对象的高级计算机语言Ada也是以她的名字命名的.可惜,摩根生前没有获得应有的荣誉,部分原因可能是由于生于印度,自幼一眼失明,脾气有些古怪.

Routh也有许多杰出的学生：因发现氩而获得物理诺贝尔奖的Rayleigh,同时也是表面波(瑞利波)和瑞利散射的发现者,其《声学理论》(The Theory of Sound)是声学领域的不二经典,他是继物理学家麦克斯韦之后的第二位卡文迪什教授;发现了电子并获物理诺贝尔奖的John Thomson(他的8名学生和助手,还有自己的儿子也得过物理或化学诺贝尔奖);进化论提出者达尔文的孙子、天文学和数学家George Darwin;数学和哲学家“白头”怀德海(Alfred North Whitehead),他与学生罗素和奎因(Willard Van Orman Quine)及其下一代学生,为现代哲学、计算机科学和人工智能领域做出了开拓性的贡献.

1900年8月8日,德国数学家David Hilbert在巴黎第二届国际数学大会上宣布了著名23个数学难题[7],即希尔伯特问题.个人认为,Hilbert问题还有希尔伯特关于数学机械化的设想与努力,正是二十世纪催生人工智能研究的主要源头.“打起你的背包,到哥廷根去”,至今还记得自己做学生时读《希尔伯特传》的向往与激情.Hilbert的思想,促使“白头”怀德海和他的学生罗素花了十余年的心血,完成了三卷本的《数学原理》(Principia Mathematica,简写为PM),试图利用符号逻辑建立一套公理和推理体系,从中可以在原理上导出所有的数学定理(即Mathematical Truths,应超出一般的定理,对此的理解,可参见刚刚去世的哲学家Putnam的文章及其Corcoran教授的评论[8−9]).尽管《数学原理》在数学和哲学史上有着极其重要的地位,但1930年,“白头”和罗素师徒的巨大努力被24岁的歌德尔(Kurt Godel)的“不完备性定理”无情地粉碎了,也使希尓伯特的宏伟计划成为泡影.紧接着,1936年,也是24岁的图灵,利用后来称之为“图灵机”的简单模型,重新研究歌德尓关于证明和计算能力界限的问题,证明所有可以表示为“算法”(或“程序”)的“可想象”之数学计算,都可以用“图灵机”实现,但此机的“停机”问题是不可判定的,因此解决并否定了希尓伯特的决策问题(即第十问题).实际上,另一位天才冯·诺伊曼(John von Neumann)在20岁上下也研究了与歌德尔和图灵类似的问题,并于21岁完成了关于集合论公理的博士论文,其工作深受《数学原理》的影响[10].这些工作的意义,已超出数学范畴,进入智能和哲学的领地.我认为歌德尔的不完备定理从机制上否定了完全意义下通用人工智能的可能性,而图灵的机器决策之不可判定性,又从计算上否定了通用或“强”人工智能的可能性,这也是为什么自己相信在通用智能上机器不会胜人的原因.而且,本质上,人也是一种广义机器,机器胜人在逻辑甚至语法上都是不通的,是一种无法检验的假命题.

在完成自己的工作之前,图灵并不知道远在大洋另一端的丘奇(Church)刚刚利用λ运算证明了等价的问题,并在他之前发表了论文.为此,图灵在剑桥大学的老师推荐他去普林斯顿,在丘奇的指导下完成其博士论文.就这样,图灵加入了在智能化和复杂性研究上产生巨大影响的另一个学术家族.

这个学术家族的开创者可回溯至法国科学家泊松(Poisson).泊松是一位少年天才,在力学和数学十分高产,留有泊松方程、泊松积分、泊松分布等等,其名言为：“生活只因两件事而美好：做数学和教数学”(Life is good for only two things:doing mathematics and teaching it.).泊松有两位老师,就是拉普拉斯(Laplace)和拉格朗日(Lagrange),而他们的老师分别为显赫的达朗贝尔(D’Alembert)和欧拉(Euler).泊松四代后的一位学生,就是普林斯顿高等研究院(IAS)聘用的第一位教授维布伦(Veblen),他不但培养了丘奇这样的学生,而且帮助IAS选定了冯·诺伊曼和哥德尔这样的学者.可惜,维布伦尽管招收了少年天才维纳参与其一战时所负责的研究工作,但对维纳(Norbert Wiener)的看法不是十分正面,失去了进一步合作的机会.然而,正是这些人的合作与努力,奠定了现代计算机和人工智能的基础.

图灵和丘奇关于可计算性的工作,后来称之为Church-Turning Thesis,启发了冯·诺伊曼并开始了EDVAC二进制电子计算机的研制,从而有了现代计算机的冯·诺伊曼结构、今天的计算机和信息产业、甚至本文对人工智能和AlphaGo的讨论.在此期间,冯·诺伊曼从维纳的控制论(Cybernetics)得到了许多启示,与维纳多有学术交往(特别是通过早期的Macy会议),而且他在EDVAC团队的首席工程师毕罗格(Julian Bigelow)正是维纳长期以来的左右手和系统实施者.

维纳,还有麦卡洛克(Warren McCulloch)和皮兹(Walter Pitts),曾经号称控制论和早期计算认知及神经科学的“金三角”,更是智能研究史上的传奇.三人由罗素的《数学原理》走到一起：维纳因《数学原理》的影响从动物学的研究转向数理逻辑,17岁完成其博士论文;麦卡洛克从心理学转向大脑研究,因为读了《数学原理》之后便认定大脑一定是按照其中所描述的方式工作,绘制了世界上第一张脑功能图谱,并在芝加哥建立第一个大脑神经实验室;皮兹几乎完全自学成才,12岁时在图书馆读了《数学原理》后与罗素通信,被罗素误认是大学生而邀请去英国共同研究;后来罗素赴芝加哥讲学,皮兹随去,在那里结识了维纳的学生与助理莱特文(Jerome Lettvin),再通过莱特文认识了麦卡洛克,完成McCulloch-Pitts神经元模型和神经网络(Nervous Nets),正是今天的神经元网络和深度学习之基础.1943年,在莱特文的介绍下,经过维纳的争取,没有受过正式教育的皮兹被MIT破格录为博士生,在维纳的指导下从事人和动物脑的认知研究.

20世纪50年代前后,“金三角”维纳、麦卡洛克和皮兹的研究成为了令全世界注目的焦点.在控制论、脑科学、神经科学甚至实时连续计算机和机器人等方面都有着令人惊奇的进展,正向着后来称之为“人工智能”的方向快速前进.然而,令人遗憾的是,由于说不清楚的非学术原因,正当“金三角”在MIT汇集后要用当时世界上最先进的各种仪器开始深入研究时,维纳突然宣布与另外二人及其团队完全断绝关系,令大家毫无思想准备、措手不及,彻底地改变了控制论和人工智能的发展进程.

随后就是1956年夏天的Dartmouth人工智能会议,正式宣告了“人工智能”领域的诞生.实际上,当年的春天,在MIT还组织了一次认知科学的研讨会,两次会议都有维纳的学生和助手参加.尽管维纳本人没有参与这两个会议,但他的思想及其影响显然都在发挥作用.不过,由于“金三角”的破裂以及麦卡洛克与皮兹二人的命运大转折,许多人己经对维纳“敬”而远之.例如,决裂后皮兹从天上跌到地下,失去了工作的兴趣;1954年《财富》杂志还把他列为世界上20名40岁以下最有才能的科学家,其名与信息论提出者香农(Claude Elwood Shannon)和DNA双螺旋结构发现者沃森(James Dewey Watson)相邻,此时却拒绝了送上门的博士学位,烧毁了自己的博士论文手稿和其它科研笔记,终日沉迷于酒吧和夜游,结果英年早逝.

很快,智能化的追求就遭遇了决策复杂性的问题！图灵机引发计算理论上的突破之后,迅速变成一个“无用”的符号,因为模型太不现实根本无法在实际中发挥作用.20世纪50年代后期和整个60年代,大家已把注意力转向有限自动机和网络模型,哈佛哲学家奎因的学生王浩、Robert McNaughton等,普林斯顿Church的学生Kleene、Robin和Scott等,以及Michigan大学的Burks(他的学生Holland发明了遗传算法GA)的团队,都在此方向进行了开拓性的研究[11−17].王浩还利用计算机进行定理证明,做出了引世人惊叹的成就：在早期的IBM机器上,“一击七蝇(Seven f l ies in one blow)”几分钟就证明了师叔罗素和师爷“白头”花了十多年在《数学原理》一书中证明的220个命题,引得罗素感叹：“早知今日,何必当初”.王浩应是第一个进入人工智能并做出杰出贡献的华人学者,为此,于1983年获得人工智能的里程碑奖.

此外,McNaughton和学生Yamada证明了有限状态自动机与正则语言等价,自己还证明了无限输入自动机的McNaughton定理,都是早期计算机和决策问题的重要成果.显然,McNaughton的工作深受王浩的影响.王浩也曾亲口告诉我Mc-Naughton实际上是他的学生,都是从哲学转入计算机,而且McNaughton的第一位博士生John Corcoran一直从事哲学与逻辑研究,是研究亚里士多德和布尔的专家,曾任纽约大学布法罗分校哲学系主任.王浩早年曾研究过罗素学生维特根斯坦的数学哲学,晚年与哥德尔交往密切,成立哥德尔学会,任创始会长,写过两部关于歌德尔的专著.

有限自动机很快就在控制、机器人、模式识别等领域有了广泛应用,同时为计算复杂性的研究提供了工具.1959年,通过对有限自动机决策问题的研究,Rabin和Scott为计算复杂性建立了数学基础,并于1976年获得图灵奖.之后,王浩的学生Cook,1970年因没有在伯克利获得提升和终身教职,被迫转赴加拿大执教,并于次年发表论文,成为NP-Complete计算复杂性问题的奠基之作,于1982年获得图灵奖.另一位图灵奖得主,伯克利计算机系的Karp教授曾称此事件为伯克利“永远的耻辱”.至今,已有11名学者因研究计算复杂性而获得图灵奖,使我们有了NP,NP-hard,NP-Complete和Co-NP等概念,加深了对复杂性结构的认识.然而,实际计算上,对于搜索、优化等决策复杂性问题依然束手无策,这就是人工智能一直无法取得根本性突破的关键所在.

当我开始进行关于智能机协调问题的博士论文研究时,导师G.N.Saridis建议采用有限自动机或决策Schemata.Saridis是机器人和智能控制的第一代开拓者,曾在学习控制和智能机器人中采用过这些工具. 但没有多久,我就意识到有限机带来的状态之“组合爆炸”或“维数灾难”使有限机和Schemata无法用于真正的实际问题.副导师McNaughton建议我看看他和王浩过去的网络模型和Petri网络,并把当年Carl Petri寄给他的德文博士论文《与有限机通信》(Kommunikation mit Automaten)赠给了我,成为自己收藏的第二部珍本.尽管那时我可以读德文,但对王浩、McNaughton、Burks还有Petri所用的符号十分恼火,庆幸后来在图书馆发现了Peterson采用现代符号的Petri网络专著,最后终于解决了智能机的建模问题.但决策计算复杂性还是令我头痛,实际上,我到美国后完成的第一个学术报告就是关于ε-计算复杂性的建议[18],想法就是根据Kolmogorov的概率测度思想和熵的概念,计算给定资源下智能机所能处理的复杂性程度的上界.然而,Saridis和McNaughton都认为此项工作想法很好,但对实际决策无太大用处,更不到发表水平.之后,我的兴趣转到学习方法和不同形式的博弈决策上,再也没有回到计算复杂性问题.

年初读完计算机围棋的文章后[1−5],特别是AlphaGo的胜利,让我重新回到并思考30年前所经历的这些往事,我认为,正如Church-Turning Thesis为计算问题提供了新的思路,从AlphaGo的结构与方法,我们或许能够找到处理复杂性问题的工程方式,这就是提出AlphaGo Thesis命题的目的.

真正的智能必须源自复杂性，如果AlphaGo给出一条通向复杂性之路，我们自然也就有了一条实现智能化的途径。

未完待续