歷史由成功者撰寫！蘇聯(lián) AI，一些被人遺忘的往事

作者 | Sergei Ivanov

編譯 | 叢 末

翻開歷史，我們會(huì)發(fā)現(xiàn)，歷史往往是由成功者撰寫的。

圖靈、明斯基、麥卡錫，這些名字大家耳熟能詳。然而，在人工智能的歷史上，似乎鮮少出現(xiàn)與他們同時(shí)代的蘇聯(lián)科學(xué)家。

真的是，鐵幕之下無 AI 嗎？

翻開過往的篇章，我們會(huì)發(fā)現(xiàn)，事實(shí)并非如此——西方國家與蘇聯(lián)在人工智能發(fā)展上的競爭，并不比他們在太空領(lǐng)域的競爭少。蘇聯(lián)在 AI 方面的投入和發(fā)展亦不遜色于西方國家。

本文將圍繞 Weisfeiler-Leman 算法的合作發(fā)明者Andrey Leman 以及他的同事的相關(guān)工作，帶大家回顧塵封在歷史長河中的蘇聯(lián)人工智能發(fā)展史。

Andrey Leman (1940–2012)，以合作發(fā)明了 Weisfeiler-Leman 算法而聞名，為蘇聯(lián)首個(gè)數(shù)據(jù)庫INES 以及首個(gè)在國際象棋比賽中獲得冠軍的計(jì)算機(jī)程序Kaissa作出了重要貢獻(xiàn)，是開發(fā)出了首個(gè) AI 程序的Kronrod團(tuán)隊(duì)的早期成員之一。

他的一生，從在校贏得數(shù)學(xué)奧林匹克競賽的冠軍，到人工智能實(shí)驗(yàn)室任職，再到后來移 民硅谷，都是一代有才華的蘇聯(lián)工程師和數(shù)學(xué)家的標(biāo)志性特征。

1 源自數(shù)學(xué)奧林匹克競賽的啟蒙

像當(dāng)時(shí)聰明的年輕男孩所受的典型教育一樣，Andrey Leman同樣也：數(shù)學(xué)成績突出，在數(shù)學(xué)奧林匹克競賽中出類拔萃，在國內(nèi)最好的大學(xué)求學(xué)。

在那個(gè)還沒有互聯(lián)網(wǎng)的時(shí)代，數(shù)學(xué)奧林匹克競賽便是追求數(shù)學(xué)研究生涯的靈感源泉，該領(lǐng)域自然而然地對(duì) Andrey 產(chǎn)生了吸引力。

Andrey 獲得數(shù)學(xué)奧林匹克競賽冠軍

可以說，這種對(duì)解決難題的興趣貫穿了他的一生：一開始作為數(shù)學(xué)家致力于解出數(shù)學(xué)難題，后來又成為了程序員致力于解決計(jì)算機(jī)難題。再后來，他基于所有遇到的這些問題編撰出了一本書，多年來都是蘇聯(lián)學(xué)生的重要參考資料。

1957年，17歲的Andrey 成為蘇聯(lián)頂尖學(xué)府——莫斯科國立大學(xué)的大一新生，1962年，他大學(xué)畢業(yè)后加入了蘇聯(lián)首個(gè)人工智能實(shí)驗(yàn)室。

大學(xué)期間，他便與Boris Weisfeiler一同求學(xué)，畢業(yè)后又與后者一起共事多年，直到1975年Boris Weisfeiler移居國外。

2 蘇聯(lián)首個(gè)人工智能實(shí)驗(yàn)室

Alexander Kronrod，蘇聯(lián)人工智能的創(chuàng)始人

如果要說誰是蘇聯(lián)人工智能的創(chuàng)始人，答案便是蘇聯(lián)首個(gè)人工智能實(shí)驗(yàn)室的負(fù)責(zé)人Alexander Kronrod。

Kronrod 的整個(gè)科研生涯頗有些曲折：一開始，他是一位致力于研究復(fù)雜復(fù)習(xí)和微分方程的非常有前途的年輕數(shù)學(xué)家，后來在第二次世界大戰(zhàn)開始時(shí)自愿參軍，由此獲得了幾枚獎(jiǎng)?wù)碌苍趹?zhàn)爭過程中受過兩次傷而無法繼續(xù)服役。于是1945年，他加入了 Kurchatov的數(shù)值數(shù)學(xué)研究所，一直到他開始意識(shí)到計(jì)算可以比“純”數(shù)學(xué)更具豐富性。

四年后，他成為了新的理論與實(shí)驗(yàn)物理研究所（ITEP）的數(shù)學(xué)系負(fù)責(zé)人，致力于引領(lǐng)核物理的創(chuàng)新，這個(gè)研究方向?qū)τ谡麄€(gè)國家而言，非常重要。如果不是他對(duì)人工智能研究的堅(jiān)定信念，研究所只會(huì)停留在數(shù)值模擬的研究范圍，而永遠(yuǎn)不會(huì)涉及人工智能的相關(guān)研究。與此同時(shí)，Kronrod極高的聲望，也讓他和他的研究團(tuán)隊(duì)得以開始研究能夠玩紙牌和下國際象棋的智能系統(tǒng)。

理論與實(shí)驗(yàn)物理研究所（ITEP）

當(dāng)時(shí)計(jì)算機(jī)科學(xué)領(lǐng)域的一個(gè)熱門課題是離散算法的計(jì)算復(fù)雜度，Kronrod 團(tuán)隊(duì)也對(duì)此做出了研究貢獻(xiàn)，其研究小組的兩位成員G. Adelson-Velsky 和 E. Landis，提出了首個(gè)自平衡二叉樹（Self-balancing Binary Search Tree），現(xiàn)在被稱作AVL樹。

AVL樹的元素插入方式

隨著首個(gè)關(guān)于多項(xiàng)式可解問題和NP完全問題被引入到計(jì)算機(jī)科學(xué)界，實(shí)驗(yàn)室開始致力于尋找各種問題的快速解答算法。

大多數(shù)問題都能很快地被排除在P問題和NP完全問題集之外，不過有兩個(gè)實(shí)踐中非常重要的問題——線性規(guī)劃和圖同構(gòu)問題，卻并不屬于上述兩類問題。

后來，另一位蘇聯(lián)數(shù)學(xué)家 Leonid Khachiyan 構(gòu)建了一個(gè)線性規(guī)劃的多項(xiàng)式時(shí)間算法，但圖同構(gòu)問題仍不屬于P類問題。

圖同構(gòu)問題也自然而然地吸引了包括Andrey Leman和Boris Weisfeiler在內(nèi)的Kronrod實(shí)驗(yàn)室成員的關(guān)注。他們二人在該問題上的首個(gè)重要的研究成果便是我們現(xiàn)在非常熟悉的 Weisfeiler-Leman 算法。

Andrey Leman和Boris Weisfeiler

近年來隨著圖機(jī)器學(xué)習(xí)的發(fā)展，計(jì)算機(jī)科學(xué)界對(duì) Weisfeiler-Leman 算法的關(guān)注度也越來越高。

當(dāng)時(shí)，這項(xiàng)關(guān)于圖同構(gòu)的工作，也讓 Leman 在Kronrod 的指導(dǎo)下發(fā)表了第一篇論文。不過由于高等認(rèn)證委員會(huì)（HAC）的負(fù)責(zé)人與Kronrod之間的個(gè)人恩怨，這篇論文被拒絕發(fā)表，并被給予了“這不是數(shù)學(xué)”的評(píng)價(jià)。

“我不是個(gè)數(shù)學(xué)家，我是個(gè)程序員?！薄?Andrey 后續(xù)忿忿不平地回應(yīng)道。

隨后，他將研究興趣從組合數(shù)學(xué)轉(zhuǎn)向了更偏程序員的問題，并在V.Arlazarov的指導(dǎo)于1973年發(fā)表了他的第二篇關(guān)于數(shù)據(jù)庫管理的論文。他對(duì)蘇聯(lián)第一個(gè)廣泛使用的數(shù)據(jù)庫INES的貢獻(xiàn)，也為他贏得了蘇聯(lián)部長理事會(huì)獎(jiǎng)（USSR Council of Ministers Prize）。

不過，Andrey并沒有把自己局限于數(shù)據(jù)庫編程，與此同時(shí)還致力于其他軟件工程問題，其中就包括——開發(fā)出首個(gè)成為世界冠軍的 AI “象棋手”。

3 蘇聯(lián)、美國之間象棋 AI 的比拼

1966年，克勞德·香農(nóng)、約翰·麥肯錫、Ed Fredkin和Joseph Weizenbaum齊聚一堂。

在艾倫·圖靈發(fā)明了“通用圖靈機(jī)”幾年后，信息理論之父克勞德·香農(nóng)就曾試圖教計(jì)算機(jī)下棋。這個(gè)想法后來被廣受關(guān)注，美國和蘇聯(lián)都開發(fā)出了會(huì)下國際象棋的程序。

在美國，程序由約翰·麥肯錫和他在麻省理工學(xué)院的學(xué)生開發(fā)出來。眾所周知，“人工智能”一詞便是麥肯錫在1952年跟圖靈的討論中被提出的，二者都是人工智能領(lǐng)域的先驅(qū)。

而在蘇聯(lián)，這個(gè)程序便是Kronrod在ITEP領(lǐng)導(dǎo)的團(tuán)隊(duì)開發(fā)出來的，叫做Kaissa。1963年，Kronrod實(shí)驗(yàn)室開始啟動(dòng)這個(gè)項(xiàng)目，當(dāng)時(shí)實(shí)驗(yàn)室的成員包很多天才數(shù)學(xué)家，比如G. Adelson-Velskyi、V. Arlazarov 和 Andrey Leman等等。

值得一提的是，1965年，McCarthy 還訪問了蘇聯(lián)，并支持Kronrod在1967年舉辦了他們開發(fā)的兩個(gè)程序之間的首場國際象棋比賽。在四場比賽中，Kaissa 展示了非常強(qiáng)大的開場知識(shí)和分析能力，以3:1的成績贏得了冠軍。

計(jì)算機(jī)之間的首場國際象棋競賽，蘇聯(lián)（黑棋）VS美國（白棋）

1969年， Kronrod 和其他數(shù)學(xué)家們聯(lián)名簽署了一封信件，為另一位收到不公正指控的蘇聯(lián)數(shù)學(xué)家 Esenin-Volpin 辯護(hù)。然而這種行為在大學(xué)是被嚴(yán)令禁止的，最終Kronrod 不幸被解雇，他的實(shí)驗(yàn)室也被破解散。

V. Arlazarov

而后，他的實(shí)驗(yàn)室成員加了控制問題研究所（ICP），Kronrod卻沒有加入。V. Arlazarov接替他成為了繼續(xù)領(lǐng)導(dǎo)Kaissa項(xiàng)目研究的團(tuán)隊(duì)負(fù)責(zé)人，致力于將Kaissa打造成 AI 象棋世界錦標(biāo)賽的冠軍。

1974年， AI 象棋世界錦標(biāo)賽在斯德哥爾摩舉行，來自 8個(gè)國家的13個(gè)程序在這場比賽中角逐世界冠軍，最終Kaissa贏得了四場比賽，并拿下了金牌，超過了來自美國的對(duì)手Chess-4、Chaos和Ribbit 各3分。

比賽現(xiàn)場一幕，右邊正在接電話的是麥肯錫

后來，Kronrod 說道：“象棋是人工智能的果蠅”。果蠅作為一種很好的實(shí)驗(yàn)動(dòng)物，研究人員可以使用它們來檢驗(yàn)假設(shè)。

4 硅谷移居潮

后來，Andrey繼續(xù)和他在Kronrod實(shí)驗(yàn)室的同事一起共事：1968至1976年在控制問題研究所任職，1976年至1990年在系統(tǒng)分析研究所工作，直到蘇聯(lián)的鐵幕倒臺(tái)。

1990年，他與很多其他科學(xué)家一起，移居硅谷。

他們以硅谷的初創(chuàng)公司——認(rèn)知技術(shù)公司（ Cognitive Technology Inc）為陣地，開發(fā)出了光學(xué)識(shí)別系統(tǒng)，成為了用不同語言識(shí)別掃描文檔領(lǐng)域中的領(lǐng)頭羊。此外，他們開發(fā)的楔形OCR解決方案被甲骨文、 IBM以及三星等多家IT 巨頭企業(yè)采用。

Andrey與其同事開發(fā)的首個(gè)成功的產(chǎn)品——楔形OCR解決方案

1995年至2012年，Andrey在多家高科技初創(chuàng)公司擔(dān)任程序員，他的最后一個(gè)東家是一家基因公司—— Invitae，他在這家公司開發(fā)的基礎(chǔ)設(shè)施系統(tǒng)現(xiàn)在還在被員工大量采用。雖然，他在生物信息學(xué)領(lǐng)域還是一個(gè)“入門者”，但是他對(duì)于解決具有挑戰(zhàn)性問題的好奇心同樣讓他在這一領(lǐng)域碩果累累。

Andrey在美國

2012年，Andrey與世長辭，但在人們心中，他永遠(yuǎn)是一位可靠的同事，一位忠實(shí)的朋友，有幽默感，總是樂于助人。

他和他的同事，將 AI 從一個(gè)數(shù)學(xué)的分支領(lǐng)域發(fā)展成了計(jì)算機(jī)科學(xué)中最具影響力的獨(dú)立領(lǐng)域之一，他們的研究成果，已然成為蘇聯(lián)人工智能發(fā)展史中的篇章。

via https://towardsdatascience.com/a-forgotten-story-of-soviet-ai-4af5daaf9cdf