本文通过数学家 Andrey Leman 及其同事的人生故事,带你回首被世人遗忘的苏联 AI 往事。
现如今,阿兰·图灵、马文·明斯基、约翰·麦卡锡这些来自西方国家的计算机科学和人工智能之父的姓名即便还不是家喻户晓,但至少在相关领域内人尽皆知。但是,很少有人知道苏联的铁幕之下也曾有过人工智能开发活动,尽管有时在这一领域中两种体制之间竞争的激烈程度要低于太空竞赛。本文通过主角 Andrey Leman 及其同事的人生故事,带你回首被世人遗忘的苏联 AI 往事。
Andrey Leman 苏联的 AI 故事始于 1955 年,那时候,一组苏联数学家获得了计算机 M-2 的使用权,然后开始通过软件工程来求解科学问题和数学谜题。 当时这个团队正在开发第一个 AI 程序,领导者是苏联著名数学家和计算机科学家亚历山大·克朗罗德(Alexander Kronrod),而我们的主角 Andrey Leman(1940–2012)则是该团队的早期成员之一。也许你曾在一些技术方法或其它事迹中听说过 Leman 的名字,比如他参与研发了 Weisfeiler-Leman 算法、参与构建了苏联第一个数据库 INES、参与设计了首个计算机国际象棋世锦赛冠军 Kaissa。 他的人生历程在他那一代苏联工程师和数学家人才中是颇为典型的:先是在学校中赢得了数学奥林匹克竞赛,然后在 AI 实验室中工作,后来移居到了美国硅谷。 数学奥林匹克竞赛 Andrey Leman 的教育经历是那个年代的聪明男孩所经历的典型教育:数学好,在数学奥林匹克竞赛上取得好成绩,然后进入该国最好的大学学习。在没有互联网的年代,在数学奥林匹克竞赛上取得好成绩通常意味着未来会走向职业数学家道路,Andrey 也不例外。
1958 年的数学奥林匹克竞赛颁奖仪式 这种求解谜题的兴趣持续了 Andrey 的一生——他一开始以数学家的身份解决难题,后来则换成了程序员的身份。后来,他将这些问题汇集成了一本书;多年以后,这本书仍然是苏联学生准备数学竞赛的一大主要资源。 17 岁那年,Andrey 进入苏联最好的大学莫斯科国立大学就读。他与 Boris Weisfeiler 是同学,而且两人一直密切合作,直到 1975 年 Boris 移民去美国才停止。1962 年,他从莫斯科国立大学毕业,加入了苏联「首个人工智能实验室」。 人工智能实验室
亚历山大·克朗罗德,苏联的人工智能之父 如果非要说谁是苏联的人工智能之父,那么苏联首个 AI 实验室的负责人亚历山大·克朗罗德(Alexander Kronrod)必定当之无愧。克朗罗德的科学家生涯很有意思。他一开始是一位研究复变分析和微分方程的出色年轻数学家,后来在第二次世界大战开始时志愿参军,并在军中获得了多枚英勇勋章,但也受了两次伤,使得他无法再继续服役。1945 年,他加入苏联核科学技术领导者伊戈尔·库尔恰托夫(Igori Kurchatov)的研究所研究数值数学,但后来他意识到计算比「纯数学」更容易出成果。
苏联(俄罗斯)理论与实验物理研究所(ITEP) 四年后,他成为新成立的理论与实验物理研究所(ITEP)数学部门负责人,而该研究所的目标是领导核物理的创新,包括计算核反应堆与基本粒子加速器、处理云室中的观察结果等等。如果不是因为克朗罗德对 AI 有很强的执念,那么该实验室可能只会进行数值模拟,AI 也就永远不会在这个研究所出现。但是,由于克朗罗德有很高的声望,因此他和他的团队还可以额外研究玩纸牌游戏和下国际象棋的智能系统。 当时计算机科学领域一个热门研究主题是离散算法的计算复杂性,克朗罗德团队对此亦有贡献。该团队的两位成员 G. Adelson-Velsky 和 E. Landis 提出了首个自平衡二叉查找树,现在被称为 AVL 树。
向 AVL 树注入元素,AVL 树方法来自 ITEP。 引入了最早的多项式可解问题和 NP 完全问题后,该实验室希望找到能快速求解各种问题的算法。 大多数问题都可以很快地分类到 P 或 NP 完全问题类别中,但线性规划和图同构(graph isomorphism)却很难分类。 后来,另一位苏联数学家 Leonid Khachiyan 提出了一种用于线性规划问题的多项式时间算法,但人们仍不知道图同构问题是否属于 P 类别。 很自然,包括 Andrey Leman 和 Boris Weisfeiler 在内的克朗罗德实验室成员对图同构问题很感兴趣。他们的第一个重大成果就是今天的 Weisfeiler-Leman 算法(1968)。
Andrey Leman 和 Boris Weisfeiler 近来随着图机器学习及图神经网络的发展,人们对 Weisfeiler-Leman 算法的兴趣与日俱增。 对图同构问题的这项研究成就了 Andrey Leman 在克朗罗德指导下的第一篇论文,但是,由于克朗罗德与高级认证委员会(HAC)负责人之间存在个人恩怨,这篇论文以「不是数学」的理论被拒了。 「我不是数学家,我是程序员。」Andrey 痛苦地回应道。 然后,他的研究兴趣从组合学转向了更偏程序员的问题,并在 1973 年捍卫了自己在 V. Arlazarov 指导下写的第二篇论文——一个关于数据库管理的研究成果。他为苏联第一个数据库 INES 做出了重大贡献,而且因为这个数据库在苏联得到了广泛的使用,苏联还授予了他部长理事会奖。 Andrey 没有止步于数据库编程,他还研究了软件工程的其它问题。其中之一是开发能玩国际象棋的 AI 程序,而且他开发的 AI 程序还成为国际象棋 AI 比赛的首个世界冠军。 国际象棋 AI
克劳德·香农、约翰·麦卡锡、Ed Fredkin 与约瑟夫·维森鲍姆(1966) 在阿兰·图灵发明了「通用图灵机」概念一年之后,信息论之父克劳德·香农想要教会计算机下国际象棋。后来,这个思路日渐流行,美国和苏联都各自有团队在开发能下国际象棋的算法。 美国这边,约翰·麦卡锡在 MIT 带一群学生在做这件事。约翰·麦卡锡是 1952 年与图灵等人共同确定「artificial intelligence」这一术语的人之一,是 AI 领域当之无愧的先驱人物。 而在苏联这边,开发国际象棋 AI 程序的正是 ITEP 的克朗罗德团队。克朗罗德实验室的开发工作始于 1963 年,很多天才数学家参与其中,其中包括 G. Adelson-Velskyi、V. Arlazarov 和 Andrey Leman。苏联的《Komsomolka》报组织过一场读者与该程序的比赛,而这些读者最后决定将这个程序命名为 Kaissa——国际象棋女神。 1965 年,约翰·麦卡锡造访苏联并与克朗罗德达成协议,举办两个程序之间的首场国际比赛。1967 年,两个程序迎来首次交锋。比赛共 4 场,Kaissa 凭借在开局知识和分析技术上的强大能力,以 3:1 的成绩赢得比赛。但这只是世界杯之前的热身赛。