復(fù)雜性與智能化：從Church-Turning Thesis到AlphaGo Thesis及其展望(1)

王飛躍

人機(jī)圍棋大戰(zhàn)之后,許多方面聞風(fēng)而動,大小會議無數(shù),投資熱情高漲,使近年來已經(jīng)火熱的人工智能,鋒勢更加兇猛.然而,我更希望業(yè)內(nèi)人士能夠聞聲而靜:歷史的經(jīng)驗告訴我們,聞風(fēng)而動,一陣騷動之后,往往煙消云散,隨后無影無蹤;聞聲而靜,一段沉寂之后,可能云飛浪涌,結(jié)果驚天動地.

在短短一個多月的時間,我對于AlphaGo的看法發(fā)生了很大的變化.由于一直認(rèn)為計算機(jī)圍棋不可能只靠“暴力”計算來完成,必須引入智能成分,因此,覺要需要長期的努力,至少是自己退休時可以專注的一件亊情.所以,當(dāng)谷歌在《自然》雜志發(fā)表AlphaGo文章后隨即宣布挑戰(zhàn)南韓棋手李世石時,我曾認(rèn)為這多屬商業(yè)炒作,無實質(zhì)技術(shù)內(nèi)容.然而,春節(jié)期間,當(dāng)我認(rèn)真讀完幾篇主要論文并粗讀了其他十多篇相關(guān)文獻(xiàn)后[1?5],對AlphaGo可能引發(fā)的沖擊,有了不同的認(rèn)識.比賽之前,我表示希望AlphaGo戰(zhàn)勝李世石[6],因為機(jī)器的勝利,將使更多人清醒,認(rèn)識到繼“老”IT的工業(yè)技術(shù)(Industrial Technology)和“舊”IT 信息技術(shù)(Information Technology)之后,以人工智能和機(jī)器人為主要表征的“新”IT智能技術(shù)(Intelligengt Technology)時代,已經(jīng)來臨.為此,我們必須轉(zhuǎn)變思維方式,來一場深刻變革性的“范式轉(zhuǎn)移”.

為什么我會由AlphaGo產(chǎn)生這些看法？這與自己的研究經(jīng)歷和機(jī)遇密切相關(guān).而且,我相信這也與未來的指揮與控制,特別是平行智能技術(shù)及其在智能軍事與智慧戰(zhàn)爭中的作用極其相關(guān).在此,拋磚引玉,希望更多的業(yè)內(nèi)專家聞聲而靜,深度思索,盡快開辟一條切實有效利用新IT智能技術(shù)變革現(xiàn)代指揮與控制的道路.

1 復(fù)雜性與智能化:兩個學(xué)術(shù)家族的故事

20世紀(jì)80年代,我剛到美國留學(xué),在借住教堂的小圖書館里,翻到了布爾的《思維定律》(The Laws of Thought).后來,主教Ezra Pickup見我非常喜歡此書,就將書贈送給我.這本書不僅成為了我收藏的第一部珍本,也讓我結(jié)識了Robert F.McNaughton教授,成為他的學(xué)生,從而對兩個學(xué)術(shù)家族在復(fù)雜性和智能化研究上的成就,有了自己特別的個人體會與認(rèn)識.

據(jù)布爾夫人回憶,布爾與同時代的學(xué)術(shù)好友摩根(Augustus De Morgan)和巴貝奇(Charles Babbage)在形式邏輯方向的研究都間接但深刻地受到了她的叔叔George Everest(英文喜馬拉雅山的珠穆朗瑪峰就是以此人命名的,Everest從1830年到1843年是印度的總勘測師,但他反對以自己的名字命名珠穆朗瑪峰)的影響.三人的成就非凡,都對后世產(chǎn)生了巨大的沖擊：布爾號稱“現(xiàn)代邏輯之父”,其布爾代數(shù)是電路設(shè)計、信息論和計算機(jī)的核心方法;巴貝奇發(fā)明了機(jī)械計算機(jī)“Analytical Engine”,號稱“計算機(jī)之父”;而摩根的摩根定律和數(shù)學(xué)歸納法更是現(xiàn)代邏輯和數(shù)學(xué)的基礎(chǔ),合起來堪稱是當(dāng)代計算機(jī)、人工智能和信息產(chǎn)業(yè)的基石.

摩根是布爾理論的堅定支持者,同時,他和自己的學(xué)生開創(chuàng)了深具哲學(xué)特色的復(fù)雜性與智能化研究學(xué)術(shù)家族.摩根的第一個學(xué)生Edward Routh是現(xiàn)代力學(xué)和控制理論的先驅(qū),著有《固體系統(tǒng)動力學(xué)》(Dynamics of a System of Rigid Bodies,1860),代表性工作為控制系統(tǒng)的Routh穩(wěn)定性判據(jù)和關(guān)于穩(wěn)定性的Routh-Hurwitz定理,這是每一個控制系統(tǒng)學(xué)生所必須了解的.摩根還有其他一些有名的學(xué)生,包括在矩陣、數(shù)論、分割和不變量理論有著重大貢獻(xiàn)的James Sylvester,他是19世紀(jì)中后期美國數(shù)學(xué)界的領(lǐng)袖,也是美國數(shù)學(xué)雜志《American Journal of Mathematics》的創(chuàng)辦人;經(jīng)濟(jì)和邏輯學(xué)家William Jevons,著有《政治經(jīng)濟(jì)學(xué)的一般數(shù)學(xué)理論》(A General Mathematical Theory of Political Economy,1862),開創(chuàng)了數(shù)學(xué)經(jīng)濟(jì)學(xué),特別是邊際效用理論的研究,此外,Jevons還著有《科學(xué)原理》和《政治經(jīng)濟(jì)學(xué)理論》等,其發(fā)明之一就是機(jī)械計算的“邏輯鋼琴”;摩根的學(xué)生中,與計算機(jī)最相關(guān)的是Ada Lovelace,她為巴貝奇的計算機(jī)“Dif f erence Engine”和“Analytical Engine”寫下了第一個“算法”(Algorithm)或“程序”(Program),所以被稱為世界上第一個程序員.Lovelace是英國著名詩人拜倫的唯一“合法”女兒,盡管后人對她在計算機(jī)的實際貢獻(xiàn)有所置疑,但今天有許多以Lovelace命名的計算機(jī)領(lǐng)域獎?wù)潞酮勴?就連美國國防部為嵌入和實時系統(tǒng)開發(fā)的面向?qū)ο蟮母呒売嬎銠C(jī)語言Ada也是以她的名字命名的.可惜,摩根生前沒有獲得應(yīng)有的榮譽,部分原因可能是由于生于印度,自幼一眼失明,脾氣有些古怪.

Routh也有許多杰出的學(xué)生：因發(fā)現(xiàn)氬而獲得物理諾貝爾獎的Rayleigh,同時也是表面波(瑞利波)和瑞利散射的發(fā)現(xiàn)者,其《聲學(xué)理論》(The Theory of Sound)是聲學(xué)領(lǐng)域的不二經(jīng)典,他是繼物理學(xué)家麥克斯韋之后的第二位卡文迪什教授;發(fā)現(xiàn)了電子并獲物理諾貝爾獎的John Thomson(他的8名學(xué)生和助手,還有自己的兒子也得過物理或化學(xué)諾貝爾獎);進(jìn)化論提出者達(dá)爾文的孫子、天文學(xué)和數(shù)學(xué)家George Darwin;數(shù)學(xué)和哲學(xué)家“白頭”懷德海(Alfred North Whitehead),他與學(xué)生羅素和奎因(Willard Van Orman Quine)及其下一代學(xué)生,為現(xiàn)代哲學(xué)、計算機(jī)科學(xué)和人工智能領(lǐng)域做出了開拓性的貢獻(xiàn).

1900年8月8日,德國數(shù)學(xué)家David Hilbert在巴黎第二屆國際數(shù)學(xué)大會上宣布了著名23個數(shù)學(xué)難題[7],即希爾伯特問題.個人認(rèn)為,Hilbert問題還有希爾伯特關(guān)于數(shù)學(xué)機(jī)械化的設(shè)想與努力,正是二十世紀(jì)催生人工智能研究的主要源頭.“打起你的背包,到哥廷根去”,至今還記得自己做學(xué)生時讀《希爾伯特傳》的向往與激情.Hilbert的思想,促使“白頭”懷德海和他的學(xué)生羅素花了十余年的心血,完成了三卷本的《數(shù)學(xué)原理》(Principia Mathematica,簡寫為PM),試圖利用符號邏輯建立一套公理和推理體系,從中可以在原理上導(dǎo)出所有的數(shù)學(xué)定理(即Mathematical Truths,應(yīng)超出一般的定理,對此的理解,可參見剛剛?cè)ナ赖恼軐W(xué)家Putnam的文章及其Corcoran教授的評論[8?9]).盡管《數(shù)學(xué)原理》在數(shù)學(xué)和哲學(xué)史上有著極其重要的地位,但1930年,“白頭”和羅素師徒的巨大努力被24歲的歌德爾(Kurt Godel)的“不完備性定理”無情地粉碎了,也使希尓伯特的宏偉計劃成為泡影.緊接著,1936年,也是24歲的圖靈,利用后來稱之為“圖靈機(jī)”的簡單模型,重新研究歌德尓關(guān)于證明和計算能力界限的問題,證明所有可以表示為“算法”(或“程序”)的“可想象”之?dāng)?shù)學(xué)計算,都可以用“圖靈機(jī)”實現(xiàn),但此機(jī)的“停機(jī)”問題是不可判定的,因此解決并否定了希尓伯特的決策問題(即第十問題).實際上,另一位天才馮·諾伊曼(John von Neumann)在20歲上下也研究了與歌德爾和圖靈類似的問題,并于21歲完成了關(guān)于集合論公理的博士論文,其工作深受《數(shù)學(xué)原理》的影響[10].這些工作的意義,已超出數(shù)學(xué)范疇,進(jìn)入智能和哲學(xué)的領(lǐng)地.我認(rèn)為歌德爾的不完備定理從機(jī)制上否定了完全意義下通用人工智能的可能性,而圖靈的機(jī)器決策之不可判定性,又從計算上否定了通用或“強(qiáng)”人工智能的可能性,這也是為什么自己相信在通用智能上機(jī)器不會勝人的原因.而且,本質(zhì)上,人也是一種廣義機(jī)器,機(jī)器勝人在邏輯甚至語法上都是不通的,是一種無法檢驗的假命題.

在完成自己的工作之前,圖靈并不知道遠(yuǎn)在大洋另一端的丘奇(Church)剛剛利用λ運算證明了等價的問題,并在他之前發(fā)表了論文.為此,圖靈在劍橋大學(xué)的老師推薦他去普林斯頓,在丘奇的指導(dǎo)下完成其博士論文.就這樣,圖靈加入了在智能化和復(fù)雜性研究上產(chǎn)生巨大影響的另一個學(xué)術(shù)家族.

這個學(xué)術(shù)家族的開創(chuàng)者可回溯至法國科學(xué)家泊松(Poisson).泊松是一位少年天才,在力學(xué)和數(shù)學(xué)十分高產(chǎn),留有泊松方程、泊松積分、泊松分布等等,其名言為：“生活只因兩件事而美好：做數(shù)學(xué)和教數(shù)學(xué)”(Life is good for only two things:doing mathematics and teaching it.).泊松有兩位老師,就是拉普拉斯(Laplace)和拉格朗日(Lagrange),而他們的老師分別為顯赫的達(dá)朗貝爾(D’Alembert)和歐拉(Euler).泊松四代后的一位學(xué)生,就是普林斯頓高等研究院(IAS)聘用的第一位教授維布倫(Veblen),他不但培養(yǎng)了丘奇這樣的學(xué)生,而且?guī)椭鶬AS選定了馮·諾伊曼和哥德爾這樣的學(xué)者.可惜,維布倫盡管招收了少年天才維納參與其一戰(zhàn)時所負(fù)責(zé)的研究工作,但對維納(Norbert Wiener)的看法不是十分正面,失去了進(jìn)一步合作的機(jī)會.然而,正是這些人的合作與努力,奠定了現(xiàn)代計算機(jī)和人工智能的基礎(chǔ).

圖靈和丘奇關(guān)于可計算性的工作,后來稱之為Church-Turning Thesis,啟發(fā)了馮·諾伊曼并開始了EDVAC二進(jìn)制電子計算機(jī)的研制,從而有了現(xiàn)代計算機(jī)的馮·諾伊曼結(jié)構(gòu)、今天的計算機(jī)和信息產(chǎn)業(yè)、甚至本文對人工智能和AlphaGo的討論.在此期間,馮·諾伊曼從維納的控制論(Cybernetics)得到了許多啟示,與維納多有學(xué)術(shù)交往(特別是通過早期的Macy會議),而且他在EDVAC團(tuán)隊的首席工程師畢羅格(Julian Bigelow)正是維納長期以來的左右手和系統(tǒng)實施者.

維納,還有麥卡洛克(Warren McCulloch)和皮茲(Walter Pitts),曾經(jīng)號稱控制論和早期計算認(rèn)知及神經(jīng)科學(xué)的“金三角”,更是智能研究史上的傳奇.三人由羅素的《數(shù)學(xué)原理》走到一起：維納因《數(shù)學(xué)原理》的影響從動物學(xué)的研究轉(zhuǎn)向數(shù)理邏輯,17歲完成其博士論文;麥卡洛克從心理學(xué)轉(zhuǎn)向大腦研究,因為讀了《數(shù)學(xué)原理》之后便認(rèn)定大腦一定是按照其中所描述的方式工作,繪制了世界上第一張腦功能圖譜,并在芝加哥建立第一個大腦神經(jīng)實驗室;皮茲幾乎完全自學(xué)成才,12歲時在圖書館讀了《數(shù)學(xué)原理》后與羅素通信,被羅素誤認(rèn)是大學(xué)生而邀請去英國共同研究;后來羅素赴芝加哥講學(xué),皮茲隨去,在那里結(jié)識了維納的學(xué)生與助理萊特文(Jerome Lettvin),再通過萊特文認(rèn)識了麥卡洛克,完成McCulloch-Pitts神經(jīng)元模型和神經(jīng)網(wǎng)絡(luò)(Nervous Nets),正是今天的神經(jīng)元網(wǎng)絡(luò)和深度學(xué)習(xí)之基礎(chǔ).1943年,在萊特文的介紹下,經(jīng)過維納的爭取,沒有受過正式教育的皮茲被MIT破格錄為博士生,在維納的指導(dǎo)下從事人和動物腦的認(rèn)知研究.

20世紀(jì)50年代前后,“金三角”維納、麥卡洛克和皮茲的研究成為了令全世界注目的焦點.在控制論、腦科學(xué)、神經(jīng)科學(xué)甚至實時連續(xù)計算機(jī)和機(jī)器人等方面都有著令人驚奇的進(jìn)展,正向著后來稱之為“人工智能”的方向快速前進(jìn).然而,令人遺憾的是,由于說不清楚的非學(xué)術(shù)原因,正當(dāng)“金三角”在MIT匯集后要用當(dāng)時世界上最先進(jìn)的各種儀器開始深入研究時,維納突然宣布與另外二人及其團(tuán)隊完全斷絕關(guān)系,令大家毫無思想準(zhǔn)備、措手不及,徹底地改變了控制論和人工智能的發(fā)展進(jìn)程.

隨后就是1956年夏天的Dartmouth人工智能會議,正式宣告了“人工智能”領(lǐng)域的誕生.實際上,當(dāng)年的春天,在MIT還組織了一次認(rèn)知科學(xué)的研討會,兩次會議都有維納的學(xué)生和助手參加.盡管維納本人沒有參與這兩個會議,但他的思想及其影響顯然都在發(fā)揮作用.不過,由于“金三角”的破裂以及麥卡洛克與皮茲二人的命運大轉(zhuǎn)折,許多人己經(jīng)對維納“敬”而遠(yuǎn)之.例如,決裂后皮茲從天上跌到地下,失去了工作的興趣;1954年《財富》雜志還把他列為世界上20名40歲以下最有才能的科學(xué)家,其名與信息論提出者香農(nóng)(Claude Elwood Shannon)和DNA雙螺旋結(jié)構(gòu)發(fā)現(xiàn)者沃森(James Dewey Watson)相鄰,此時卻拒絕了送上門的博士學(xué)位,燒毀了自己的博士論文手稿和其它科研筆記,終日沉迷于酒吧和夜游,結(jié)果英年早逝.

很快,智能化的追求就遭遇了決策復(fù)雜性的問題！圖靈機(jī)引發(fā)計算理論上的突破之后,迅速變成一個“無用”的符號,因為模型太不現(xiàn)實根本無法在實際中發(fā)揮作用.20世紀(jì)50年代后期和整個60年代,大家已把注意力轉(zhuǎn)向有限自動機(jī)和網(wǎng)絡(luò)模型,哈佛哲學(xué)家奎因的學(xué)生王浩、Robert McNaughton等,普林斯頓Church的學(xué)生Kleene、Robin和Scott等,以及Michigan大學(xué)的Burks(他的學(xué)生Holland發(fā)明了遺傳算法GA)的團(tuán)隊,都在此方向進(jìn)行了開拓性的研究[11?17].王浩還利用計算機(jī)進(jìn)行定理證明,做出了引世人驚嘆的成就：在早期的IBM機(jī)器上,“一擊七蠅(Seven f l ies in one blow)”幾分鐘就證明了師叔羅素和師爺“白頭”花了十多年在《數(shù)學(xué)原理》一書中證明的220個命題,引得羅素感嘆：“早知今日,何必當(dāng)初”.王浩應(yīng)是第一個進(jìn)入人工智能并做出杰出貢獻(xiàn)的華人學(xué)者,為此,于1983年獲得人工智能的里程碑獎.

此外,McNaughton和學(xué)生Yamada證明了有限狀態(tài)自動機(jī)與正則語言等價,自己還證明了無限輸入自動機(jī)的McNaughton定理,都是早期計算機(jī)和決策問題的重要成果.顯然,McNaughton的工作深受王浩的影響.王浩也曾親口告訴我Mc-Naughton實際上是他的學(xué)生,都是從哲學(xué)轉(zhuǎn)入計算機(jī),而且McNaughton的第一位博士生John Corcoran一直從事哲學(xué)與邏輯研究,是研究亞里士多德和布爾的專家,曾任紐約大學(xué)布法羅分校哲學(xué)系主任.王浩早年曾研究過羅素學(xué)生維特根斯坦的數(shù)學(xué)哲學(xué),晚年與哥德爾交往密切,成立哥德爾學(xué)會,任創(chuàng)始會長,寫過兩部關(guān)于歌德爾的專著.

有限自動機(jī)很快就在控制、機(jī)器人、模式識別等領(lǐng)域有了廣泛應(yīng)用,同時為計算復(fù)雜性的研究提供了工具.1959年,通過對有限自動機(jī)決策問題的研究,Rabin和Scott為計算復(fù)雜性建立了數(shù)學(xué)基礎(chǔ),并于1976年獲得圖靈獎.之后,王浩的學(xué)生Cook,1970年因沒有在伯克利獲得提升和終身教職,被迫轉(zhuǎn)赴加拿大執(zhí)教,并于次年發(fā)表論文,成為NP-Complete計算復(fù)雜性問題的奠基之作,于1982年獲得圖靈獎.另一位圖靈獎得主,伯克利計算機(jī)系的Karp教授曾稱此事件為伯克利“永遠(yuǎn)的恥辱”.至今,已有11名學(xué)者因研究計算復(fù)雜性而獲得圖靈獎,使我們有了NP,NP-hard,NP-Complete和Co-NP等概念,加深了對復(fù)雜性結(jié)構(gòu)的認(rèn)識.然而,實際計算上,對于搜索、優(yōu)化等決策復(fù)雜性問題依然束手無策,這就是人工智能一直無法取得根本性突破的關(guān)鍵所在.

當(dāng)我開始進(jìn)行關(guān)于智能機(jī)協(xié)調(diào)問題的博士論文研究時,導(dǎo)師G.N.Saridis建議采用有限自動機(jī)或決策Schemata.Saridis是機(jī)器人和智能控制的第一代開拓者,曾在學(xué)習(xí)控制和智能機(jī)器人中采用過這些工具. 但沒有多久,我就意識到有限機(jī)帶來的狀態(tài)之“組合爆炸”或“維數(shù)災(zāi)難”使有限機(jī)和Schemata無法用于真正的實際問題.副導(dǎo)師McNaughton建議我看看他和王浩過去的網(wǎng)絡(luò)模型和Petri網(wǎng)絡(luò),并把當(dāng)年Carl Petri寄給他的德文博士論文《與有限機(jī)通信》(Kommunikation mit Automaten)贈給了我,成為自己收藏的第二部珍本.盡管那時我可以讀德文,但對王浩、McNaughton、Burks還有Petri所用的符號十分惱火,慶幸后來在圖書館發(fā)現(xiàn)了Peterson采用現(xiàn)代符號的Petri網(wǎng)絡(luò)專著,最后終于解決了智能機(jī)的建模問題.但決策計算復(fù)雜性還是令我頭痛,實際上,我到美國后完成的第一個學(xué)術(shù)報告就是關(guān)于ε-計算復(fù)雜性的建議[18],想法就是根據(jù)Kolmogorov的概率測度思想和熵的概念,計算給定資源下智能機(jī)所能處理的復(fù)雜性程度的上界.然而,Saridis和McNaughton都認(rèn)為此項工作想法很好,但對實際決策無太大用處,更不到發(fā)表水平.之后,我的興趣轉(zhuǎn)到學(xué)習(xí)方法和不同形式的博弈決策上,再也沒有回到計算復(fù)雜性問題.

年初讀完計算機(jī)圍棋的文章后[1?5],特別是AlphaGo的勝利,讓我重新回到并思考30年前所經(jīng)歷的這些往事,我認(rèn)為,正如Church-Turning Thesis為計算問題提供了新的思路,從AlphaGo的結(jié)構(gòu)與方法,我們或許能夠找到處理復(fù)雜性問題的工程方式,這就是提出AlphaGo Thesis命題的目的.

真正的智能必須源自復(fù)雜性，如果AlphaGo給出一條通向復(fù)雜性之路，我們自然也就有了一條實現(xiàn)智能化的途徑。

未完待續(xù)