历史由成功者撰写！苏联 AI，一些被人遗忘的往事

作者 | Sergei Ivanov

编译 | 丛 末

翻开历史，我们会发现，历史往往是由成功者撰写的。

图灵、明斯基、麦卡锡，这些名字大家耳熟能详。然而，在人工智能的历史上，似乎鲜少出现与他们同时代的苏联科学家。

真的是，铁幕之下无 AI 吗？

翻开过往的篇章，我们会发现，事实并非如此——西方国家与苏联在人工智能发展上的竞争，并不比他们在太空领域的竞争少。苏联在 AI 方面的投入和发展亦不逊色于西方国家。

本文将围绕 Weisfeiler-Leman 算法的合作发明者Andrey Leman 以及他的同事的相关工作，带大家回顾尘封在历史长河中的苏联人工智能发展史。

Andrey Leman (1940–2012)，以合作发明了 Weisfeiler-Leman 算法而闻名，为苏联首个数据库INES 以及首个在国际象棋比赛中获得冠军的计算机程序Kaissa作出了重要贡献，是开发出了首个 AI 程序的Kronrod团队的早期成员之一。

他的一生，从在校赢得数学奥林匹克竞赛的冠军，到人工智能实验室任职，再到后来移民硅谷，都是一代有才华的苏联工程师和数学家的标志性特征。

1

源自数学奥林匹克竞赛的启蒙

像当时聪明的年轻男孩所受的典型教育一样，Andrey Leman同样也：数学成绩突出，在数学奥林匹克竞赛中出类拔萃，在国内最好的大学求学。

在那个还没有互联网的时代，数学奥林匹克竞赛便是追求数学研究生涯的灵感源泉，该领域自然而然地对 Andrey 产生了吸引力。

Andrey 获得数学奥林匹克竞赛冠军

可以说，这种对解决难题的兴趣贯穿了他的一生：一开始作为数学家致力于解出数学难题，后来又成为了程序员致力于解决计算机难题。再后来，他基于所有遇到的这些问题编撰出了一本书，多年来都是苏联学生的重要参考资料。

1957年，17岁的Andrey 成为苏联顶尖学府——莫斯科国立大学的大一新生，1962年，他大学毕业后加入了苏联首个人工智能实验室。

大学期间，他便与Boris Weisfeiler一同求学，毕业后又与后者一起共事多年，直到1975年Boris Weisfeiler移居国外。

2

苏联首个人工智能实验室

Alexander Kronrod，苏联人工智能的创始人

如果要说谁是苏联人工智能的创始人，答案便是苏联首个人工智能实验室的负责人Alexander Kronrod。

Kronrod 的整个科研生涯颇有些曲折：一开始，他是一位致力于研究复杂复习和微分方程的非常有前途的年轻数学家，后来在第二次世界大战开始时自愿参军，由此获得了几枚奖章但也在战争过程中受过两次伤而无法继续服役。于是1945年，他加入了 Kurchatov的数值数学研究所，一直到他开始意识到计算可以比“纯”数学更具丰富性。

四年后，他成为了新的理论与实验物理研究所（ITEP）的数学系负责人，致力于引领核物理的创新，这个研究方向对于整个国家而言，非常重要。如果不是他对人工智能研究的坚定信念，研究所只会停留在数值模拟的研究范围，而永远不会涉及人工智能的相关研究。与此同时，Kronrod极高的声望，也让他和他的研究团队得以开始研究能够玩纸牌和下国际象棋的智能系统。

理论与实验物理研究所（ITEP）

当时计算机科学领域的一个热门课题是离散算法的计算复杂度，Kronrod 团队也对此做出了研究贡献，其研究小组的两位成员G. Adelson-Velsky 和 E. Landis，提出了首个自平衡二叉树（Self-balancing Binary Search Tree），现在被称作AVL树。

AVL树的元素插入方式

随着首个关于多项式可解问题和NP完全问题被引入到计算机科学界，实验室开始致力于寻找各种问题的快速解答算法。

大多数问题都能很快地被排除在P问题和NP完全问题集之外，不过有两个实践中非常重要的问题——线性规划和图同构问题，却并不属于上述两类问题。

后来，另一位苏联数学家 Leonid Khachiyan 构建了一个线性规划的多项式时间算法，但图同构问题仍不属于P类问题。

图同构问题也自然而然地吸引了包括Andrey Leman和Boris Weisfeiler在内的Kronrod实验室成员的关注。他们二人在该问题上的首个重要的研究成果便是我们现在非常熟悉的 Weisfeiler-Leman 算法。

Andrey Leman和Boris Weisfeiler

近年来随着图机器学习的发展，计算机科学界对 Weisfeiler-Leman 算法的关注度也越来越高。

当时，这项关于图同构的工作，也让 Leman 在Kronrod 的指导下发表了第一篇论文。不过由于高等认证委员会（HAC）的负责人与Kronrod之间的个人恩怨，这篇论文被拒绝发表，并被给予了“这不是数学”的评价。

“我不是个数学家，我是个程序员。”— Andrey 后续忿忿不平地回应道。

随后，他将研究兴趣从组合数学转向了更偏程序员的问题，并在V.Arlazarov的指导于1973年发表了他的第二篇关于数据库管理的论文。他对苏联第一个广泛使用的数据库INES的贡献，也为他赢得了苏联部长理事会奖（USSR Council of Ministers Prize）。

不过，Andrey并没有把自己局限于数据库编程，与此同时还致力于其他软件工程问题，其中就包括——开发出首个成为世界冠军的 AI “象棋手”。

3

苏联、美国之间象棋 AI 的比拼

1966年，克劳德·香农、约翰·麦肯锡、Ed Fredkin和Joseph Weizenbaum齐聚一堂。

在艾伦·图灵发明了“通用图灵机”几年后，信息理论之父克劳德·香农就曾试图教计算机下棋。这个想法后来被广受关注，美国和苏联都开发出了会下国际象棋的程序。

在美国，程序由约翰·麦肯锡和他在麻省理工学院的学生开发出来。众所周知，“人工智能”一词便是麦肯锡在1952年跟图灵的讨论中被提出的，二者都是人工智能领域的先驱。

而在苏联，这个程序便是Kronrod在ITEP领导的团队开发出来的，叫做Kaissa。1963年，Kronrod实验室开始启动这个项目，当时实验室的成员包很多天才数学家，比如G. Adelson-Velskyi、V. Arlazarov 和 Andrey Leman等等。

值得一提的是，1965年，McCarthy 还访问了苏联，并支持Kronrod在1967年举办了他们开发的两个程序之间的首场国际象棋比赛。在四场比赛中，Kaissa 展示了非常强大的开场知识和分析能力，以3:1的成绩赢得了冠军。

计算机之间的首场国际象棋竞赛，苏联（黑棋）VS美国（白棋）

1969年， Kronrod 和其他数学家们联名签署了一封信件，为另一位收到不公正指控的苏联数学家 Esenin-Volpin 辩护。然而这种行为在大学是被严令禁止的，最终Kronrod 不幸被解雇，他的实验室也被破解散。

V. Arlazarov

而后，他的实验室成员加了控制问题研究所（ICP），Kronrod却没有加入。V. Arlazarov接替他成为了继续领导Kaissa项目研究的团队负责人，致力于将Kaissa打造成 AI 象棋世界锦标赛的冠军。

1974年， AI 象棋世界锦标赛在斯德哥尔摩举行，来自 8个国家的13个程序在这场比赛中角逐世界冠军，最终Kaissa赢得了四场比赛，并拿下了金牌，超过了来自美国的对手Chess-4、Chaos和Ribbit 各3分。

比赛现场一幕，右边正在接电话的是麦肯锡

后来，Kronrod 说道：“象棋是人工智能的果蝇”。果蝇作为一种很好的实验动物，研究人员可以使用它们来检验假设 。

4

硅谷移居潮

后来，Andrey继续和他在Kronrod实验室的同事一起共事：1968至1976年在控制问题研究所任职，1976年至1990年在系统分析研究所工作，直到苏联的铁幕倒台。

1990年，他与很多其他科学家一起，移居硅谷。

他们以硅谷的初创公司——认知技术公司（ Cognitive Technology Inc）为阵地，开发出了光学识别系统，成为了用不同语言识别扫描文档领域中的领头羊。此外，他们开发的楔形OCR解决方案被甲骨文、 IBM以及三星等多家IT 巨头企业采用。

Andrey与其同事开发的首个成功的产品——楔形OCR解决方案

1995年至2012年，Andrey在多家高科技初创公司担任程序员，他的最后一个东家是一家基因公司—— Invitae，他在这家公司开发的基础设施系统现在还在被员工大量采用。虽然，他在生物信息学领域还是一个“入门者”，但是他对于解决具有挑战性问题的好奇心同样让他在这一领域硕果累累。

Andrey在美国

2012年，Andrey与世长辞，但在人们心中，他永远是一位可靠的同事，一位忠实的朋友，有幽默感，总是乐于助人。

他和他的同事，将 AI 从一个数学的分支领域发展成了计算机科学中最具影响力的独立领域之一，他们的研究成果，已然成为苏联人工智能发展史中的篇章。

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

ACL 2020原定于2020年7月5日至10日在美国华盛顿西雅图举行，因新冠肺炎疫情改为线上会议。为促进学术交流，方便国内师生提早了解自然语言处理（NLP）前沿研究，AI 科技评论将推出「ACL 实验室系列论文解读」内容，同时欢迎更多实验室参与分享，敬请期待！

点击"阅读原文"，直达“ACL 交流小组”了解更多会议信息。