CCCF专栏 | 人工智能的边界

本文以2019年图灵大会论坛讨论的议题为契机，从计算理论的角度梳理人工智能的现实性和可能性。作者试图为探讨人工智能的局限和边界问题提供一个理论框架。

编者按：

ACM图灵大会(ACM TURC)于2019年5月在成都召开。其主题是“注智世界，赋能未来”(Interconnected, Inspired, Intelligent)。大会第一天主旨演讲者是ACM图灵奖得主莱斯利·瓦利安特(Leslie Valiant)，第二天的主旨演讲者是ACM图灵奖得主曼纽尔·布卢姆(Manuel Blum)和他的太太丽诺尔·布卢姆(Lenore Blum)。第一天主旨演讲之后的论坛主题是“人工智能超越人类智能：现状、可能性还是幻想？”(Artificial Intelligence Overtakes Human Intelligence: Reality, Possibility, or Fantasy?)论坛的嘉宾有麻省理工学院的狄娜·卡塔比(Dina Katabi)、加州大学圣克鲁兹分校的亚历山大·沃夫(Alexander Wolf)、加州大学洛杉矶分校的朱松纯(Song-Chun Zhu)、伊利诺理工大学的孙贤和(Xian-He Sun)和滑铁卢大学的李明(Ming Li)，主持人是前澳门大学校长、现任阿联酋沙迦美国大学副校长赵伟(Wei Zhao)。这次论坛主要讨论了三个问题：(1)现状(Reality)：人工智能已经达到或超过人类智能了吗？(2)可能性(Possibility)：如果目前还没达到，将来有可能达到或超越人类智能吗？(3)“幻想”(Fantasy)：人工智能根本不可能达到人类智能。对这三个问题，外行看热闹，内行看门道。那么，什么是人工智能的边界？尼克与赵伟先生专门为本刊撰文，对此问题进行梳理。

关于什么是智能，我们目前尚且无法给出一个精确的定义。就像在图灵机出现之前，我们无法对计算给出一个严格的定义一样。在一个无法定义的领域里辩论，自然是“公说公有理，婆说婆有理”。

ACM图灵大会的主旨演讲者之一是哈佛大学的理论计算机科学家莱斯利·瓦利安特(Leslie Valiant)，他因为在并行计算理论和机器学习理论方面的贡献获得了2010年的图灵奖。他演讲的题目是“什么是可行计算的极限？”(What are the Limits of Feasible Computation?)，这为论坛将要展开的讨论提供了理论基础。首先，瓦利安特把计算机科学问题参照物理学分为三个层次：超级普适性(super-generality)、普适性(generality)和数学推断(mathematical consequences)。瓦利安特只是比较了物理学和计算机科学，我们在他的基础上加入了人工智能的维度，以便得到更多的启示。物理学中，超级普适性的体现就是最广义的、永恒不变的、可以表达成数学方程的物理学定律，而在计算机科学中对应的就是计算的理论模型，图灵机就是一种计算模型，当然图灵机不是唯一的模型。物理学的普适层存在着定律，如牛顿第二定律、万有引力定律等；在图灵机的框架下，NP完全理论就是普适性的。大概在瓦利安特心目中，计算复杂性是和牛顿定律一样的存在。在数学推断层，物理学有行星椭圆轨道，而理论计算机科学会有各种具体的NP完全的问题。当超级普适层发生变化时，下面的层次也会依次变化，例如，如果计算模型变成了量子计算机，那么类似的复杂性问题就变成了有限错误量子计算多项式时间(Bounded error Quantum Polynomial time, BQP)¹之类。图1为物理学、计算机科学和人工智能的普适性分层。

当我们分析不同的问题时，会使用不同的计算模型。丘奇-图灵论题(Church-Turing Thesis)是传统的理论计算机科学的支柱，这个论题断言所有的计算模型都是等价的，也就是说，所有足够强的计算模型都是可以互相模拟的。另一个被默认的论题是中国计算机理论科学家洪加威提出的“相似性原则”(Similarity Principle)，即所有足够强的计算模型之间的模拟成本都是多项式的。相似性原则也被称为“强丘奇-图灵论题”或“扩展的丘奇-图灵论题”(Extended Church-Turing Thesis)。“强丘奇-图灵论题”不太被提起，甚至被忽视，主要原因大概是这个原则已经变成计算理论的工作假设，大家已经习以为常。近来的理论研究提出了和图灵机可能不等价的计算模型，它们的计算能力在某种意义上超越了图灵机，也违背了丘奇-图灵论题和强丘奇-图灵论题，有时也被称为“超计算”(hyper-computation)。例如，BSS(Blum-Shub-Smale)实数模型^[1]和量子计算机等。BSS的“B”就是本次大会的主旨演讲嘉宾之一丽诺尔·布卢姆(Lenore Blum)。在BSS模型上，实数的四则运算可以在单位时间内完成，这类模型可以展现出和图灵机不同的性质，例如，线性规划在图灵机上有多项式时间的算法，但在BSS上的时间复杂性还未知。三层以上神经网络学习问题在图灵机上是NP完全的，而在BSS上和线性规划等价^[2]。

量子计算被认为可能违背“强丘奇-图灵论题”。例如，和网络安全密切相关的素数分解问题在图灵机上被认为是难的，尽管还没有明确的证明，但量子计算机上整数分解的秀尔算法(Shor’s algorithm)有可能是高效的。BSS作为一个数值分析的理论模型，应该是有价值的，但可否实现则存疑；而实用的量子计算机是有可能实现的。“丘奇-图灵论题”和“强丘奇-图灵论题”更像是物理定律而不是数学定理。计算是游走于数学和物理学之间的学问，关于计算和物理的关系，可见图灵研究专家霍奇斯(Hodges)的文章^[3]，以及姚期智为纪念JACM (Journal of the ACM)出版50周年写的文章^[4]。

大会论坛的各位嘉宾虽然都来自计算机科学或者相关学科，和人工智能有着千丝万缕的关系，但他们对人工智能的看法却各有不同，即使我们给完全的外行发个调查问卷，恐怕得来的回答之间的差异与嘉宾们之间的观点差异也差不多。这是人工智能这个特定学科的性质决定的，每个颗粒度足够大或者足够抽象的问题都像是哲学问题。一个实用主义的办法可以把人工智能定义为相关从业者正在进行的研究领域，找到他们之间的共同点，求同存异。2006年之后由深度学习引发的又一次人工智能热潮，使得人们把人工智能的关注点聚焦在机器学习，从而忽视了人工智能的其他分支学科，而深度学习对大数据的依赖也自然造成了对模型的轻视。关心计算机视觉的人很容易借鉴马尔(David Marr)的分层理论。

任何一个实用主义的回答都必须有个参照物，人工智能的参照物是自然智能，或者更具体地说是人类智能。机器在一个特定的领域或任务上已经超越人类是大家的共识，此所谓弱人工智能。目前还没有可以跨任务的机器，当下强人工智能还不是现实，这也是共识。事实上，人工智能的分类常常是按照任务来的，例如计算机视觉（包括模式识别和图像处理等）、自然语言理解、认知与推理、机器人学、博弈论、机器学习等。而美国计算机学会(ACM)在某些领域里并不活跃，例如机器学习和计算机视觉。如果按照任务来，智能的定义就变成了自底向上的，这也是人工智能作为一个工程领域，从业者对其很自然的态度。不同的人会用不同的术语，一些人称为模型，另一些人称为任务。底层的大数据小任务，到了高层就变成了小数据大任务。这里所谓任务的大小，其实是指任务的复杂度。

智能的任务按照诺贝尔经济奖得主、心理学家丹尼尔·卡尼曼(Daniel Kahneman)的说法可以分为两类，一类是能快速反应的，例如计算机视觉；另一类是需要长时间思考的，例如认知与推理。有人说人类更擅长前一类任务，而机器更擅长后一类任务。人工智能的历史曾有符号主义和连接主义的交替，前一类任务更有效的解决办法是连接主义的深度学习，而后一种任务更像是符号主义的使命。但都有例外，例如深度学习尚没有找到自然语言处理的窍门；符号主义在机器定理证明领域，近几年几乎处于停滞的状态。AlphaGo及其一系列衍生程序所依赖的核心算法——强化学习则无法归类到这两派之中，而是自成一派。给人工智能下定义的过程也是一个学习的过程，特别是在没有理论指导下，这个过程尤为艰难，每个泛化推广的企图都会碰到反例。

其实不仅仅是对“人工智能”难以形成共识，即使对什么是“学习”也很难提出都可以接受的定义。有人说“机器学习”不是“学习”，不过是曲线拟合而已。但“学习”和“拟合”的真正区别又是什么呢？一个可以接受的理论是瓦利安特提出的“概率近似正确”(Probably Approximately Correct, PAC)模型^[5]。由亚里士多德开启的传统西方哲学认为，演绎和归纳是对立的，学习就是归纳，归纳必然导致犯错。在PAC模型中，错误被控制在一个范围内。瓦利安特不仅用PAC模型解释学习，还用它解释进化论。当然如果可以解释进化论，PAC模型也就可以作为强化学习的某种理论基础，强化学习可以被当作计算进化论。我们从瓦利安特的分层中可以看出，PAC模型是包含在确定多项式时间之内的。图2是计算模型的能力分层。

首先，我们回到第一个问题：现状(Reality)。所有嘉宾的共识是：在某些特定的领域，人工智能已经超越人类智能，但当下人工智能还没有全面达到人类智能。

第二个问题：可能性(Possibility)。按照瓦利安特的层次，首先从超级普适层的计算模型考虑，如果人脑的计算能力也可以用图灵机刻画，那么按照丘奇-图灵论题，用图灵机实现人脑功能自然是可能的。按照相似性原则，图灵机实现人脑的功能的成本甚至是多项式的。数学家罗杰·彭罗斯(Roger Penrose)曾经联合脑科学的朋友企图找到人脑里存在量子效应的证明。而麻省理工学院的物理学家，畅销书《生命3.0》(Life 3.0)的作者马克斯·泰格马克(Max Tegmark)在与本文作者对谈时曾提到他的观点：人工智能有图灵机就够了，不需要量子计算。

假设人脑是量子计算机，那么在超级普适层，仍然可以用图灵机等价的模型实现人类智能，而在普适层，也可以用量子计算机低成本地实现人类智能。这里倒使我们不由自主地提出一个有趣的问题：量子计算机之间是不是存在着相似性原则，换句话说，任意一台量子计算机模拟任意一台量子计算机的成本是不是多项式的？物理学家理查德·费曼(Richard Feynman)在1982年的文章《利用计算机模拟物理学》(Simulating Physics with Computers)中猜测，不大可能用经典计算机有效地模拟量子物理，但可能用量子计算机有效地模拟^{[6, 7]}。物理学家的洞见对数学家和计算机科学家是有益的。

如果能够证明多项式时间类P是BQP的真子集，那么相似性原则或者扩展的丘奇-图灵论题就被打破了。按照瓦利安特的层次分类，我们不需要量子计算就可以达到PAC模型学习。瓦利安特似乎更倾向支持泰格马克而不是彭罗斯。理论不仅给工程师们提供解释，也为他们指明方向。

第三个问题：“幻想”(Fantasy)，也就是说人脑的计算能力不可能被任何已知或未知的计算模型所模拟。这个问题和第二个问题密切相关，如果对第二个问题的回答是否定的，那自然是Fantasy。假设我们用一种进步的观点看待人工智能学科，我们会承认现在的人工智能比以前更为有力，而未来的人工智能比当下更为有力。随着时间的推移，人类智能中没有被人工智能所覆盖的部分就是Fantasy。

所以Fantasy可以被定义为：Fantasy = HI - AI_n→∞（见图3）。如果Fantasy是空集，那么我们都是乐观派，如果它不是空集，那么我们应该探索它应该包含些什么？我们可以问它应该有些什么神秘的超计算的模型，或者有什么优良的复杂性的性质不可实现。

布卢姆夫妇的主旨演讲“有意识的图灵机”(Conscious Turing Machine, CTM)很吸引人。曼纽尔·布卢姆说这是他们一家三口的联合工作（丈夫曼纽尔、太太丽诺尔和儿子阿夫里姆(Avrim)都曾是卡耐基梅隆大学(CMU)计算机学院的教授），但他们还没有联合写过一篇文章。他们企图为认知科学中饱受争议的“意识”问题提供一个计算模型。这个模型的目的并非是他们夫妇擅长的计算理论，而仅仅是某种心理学的模型可以得到一个计算的实现或者解释。

布卢姆夫妇用“痛苦”(pain)和“愉悦”(joy)作为例子来说明意识^[8]。曼纽尔负责演讲的上半场，丽诺尔负责下半场，曼纽尔开玩笑说他负责“痛苦”而太太丽诺尔负责“愉悦”。理解大脑是曼纽尔的终生兴趣，他小的时候，他爸爸就告诉他，要是他能知道大脑是如何工作的，他就会变得聪明。尽管他在麻省理工学院的博士生导师是马文·明斯基(Marvin Minsky)，但他的实际指导者则是最早提出神经网络的沃伦·麦卡洛克(Warren McCulloch)和沃尔特·皮茨(Walter Pitts)。布卢姆夫妇像认知科学家一样，把“模拟”(simulation)称为“容易”的问题，而把“体验”(experience)称为“困难”的问题。他们强调他们的模型和突破“丘奇-图灵论题”没有关系，他们的目的是为意识提供一个简单可用的模型，这样可以在这个模型上证明和意识相关的数学定理。至于说“模拟”和“体验”孰难孰易，不好追究，人们也可以说“模拟”才是人特有的进化而来的高级性质，而“体验”是低级的东西。

关于“意识”的一个有影响的模型是认知科学家伯尼·巴尔斯(Bernie Baars)提出的“剧场模型”(Theater Model)，而布卢姆的CTM就是“剧场模型”的一个计算实现。在“剧场模型”里，聚光灯下的舞台是短期记忆(Short-Term Memory, STM)，而台下的观众则是无意识(unconscious)的长期记忆(Long-Term Memory, LTM)。没有短期记忆，人就变成“僵尸”(zombie)，不同的长期记忆通过连接构成了一部异构并行计算机。某些对于计算理论缺乏基本知识的哲学家无法对他们认为是他们自己领地的“意识”问题给出精确的定义，意识这个概念在他们那里是一个移动的目标，他们辩论的底线就是任何不是自然生长出来的物体都没法具有意识。哲学家们常常分不清楚修辞和科学。布卢姆的CTM至少向一个更精确的目标走了一步。意识与心智(mind)的架构(architecture)有关，这个结论并不惊人，我们可以假设他们夫妇俩是长期的乐观派。

事实上，瓦利安特在他的PAC模型科普小册子里也提到了认知结构，他也企图利用短期和长期记忆的区别来理解意识。我们很好奇瓦利安特的“坚实逻辑”(Robust Logic)和布卢姆的CTM之间有什么关系。

不同背景的计算机科学家的论坛会碰撞出许多火花，纵横学科架构、基础理论，乃至工程实现。反思这些有趣的探讨，还有两个问题值得进一步深思：第一，当下实现图灵机的物理基础仍是半导体器件。利用一个“PN”结现象，我们得以造出物美价廉高密度极可靠的数字电路，打造了辉煌的数字计算机工业，开发出大量的高效应用，其中有些显然已经超越人类“智能”（比如超级计算机）。但是，我们可以用来做“计算”的物理现象，肯定远远不止半导体。比如，要知道一个抛物体能落在哪里，我们可以根据物理定律用数字计算机来计算，但是也可以利用物理现象做模拟计算。另外一个（正面的）例子是上面提到的彼得·秀尔(Peter Shor)发明的整数分解的量子算法。秀尔算法所利用的物理器件就不是基于半导体“PN”结现象的。人类智能不一定只依靠半导体的物理现象来实现。我们需要探索基于不同物理现象而导致的新的普适性计算模型。也许，在这些模型中，有些可能会有效实现或者接近有效实现人类智能。

第二，布卢姆提出了“有意识的图灵机”这一课题。显然，认知科学家认为意识是“智能”行为的重要组成。意识是一个智能主体对客观感知后的一种认识。所以，和传统的计算模型不同，对客观感知将必然成为人工智能计算模型的重要部分。这样的计算模型不但要考虑计算的复杂性，更要考虑感知数据的复杂性。请注意对客观感知所生成的数据不会是随意的，这是因为这些数据是自然界的表示和抽象，应当遵守某些客观规律。计算的复杂性和感知数据的复杂性是对偶的。认识感知数据的复杂性并利用其特有的客观规律应该可以提高计算效率，降低计算的复杂性。所以，在人工智能学科建设过程中，感知数据的内在规律和复杂性是一个需要认真探讨、有待突破的前沿问题。图灵机的计算模型是忽略输入数据的复杂性的，这保证了模型的简洁。也许，超计算模型为我们理解人工智能和人类智能的边界提供了理论基础。

作者介绍：

尼克

CCF专业会员。国家特聘专家。乌镇智库理事长。早年曾任职于哈佛大学和惠普，后连环创业，曾获吴文俊人工智能科技进步奖。中文著作包括《人工智能简史》，《UNIX内核剖析》和《哲学评书》等。

赵伟

CCF专业会员。CCF海外杰出贡献奖获得者。阿联酋沙迦美国大学副校长。曾任澳门大学校长、美国伦斯勒理工学院理学院院长、美国国家科学基金会(NSF)计算机暨网络系统分部主任。

脚注：

¹ 在计算复杂度理论内，BQP是一个决定性问题的复杂度类，并且其内的问题可以在多项式时间内以量子计算机解决，错误的机率小于1/3。

参考文献：

[1] Blum L, Cucker F, Shub M, et al. Complexity and Real Computation[M]. Springer-Verlag, 1998.

[2] Zhang X. Complexity of neural network learning in the real number model[C]// Workshop on Physics & Computation. IEEE, 1992.

[3] Hodges A. Alan Turing: the logical and physical basis of computing[OL]. https://www.bcs.org/upload/pdf/ewic_tur04_paper1.pdf, 2007.

[4] Yao A C. Classical physics and the Church-Turing Thesis[J]. Journal of the ACM, 2003, 50(1):100-105.

[5] ValiantL. Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World, 2013.

[6] Feynman R P. Simulating Physics with Computers[J]. International Journal of Theoretical Physics, 1982, 21(6-7):467-488.

[7] FeynmanR P. Feynman Lectures on Computation. Hey A J, Allen R W, Rev. ed , 2000.

[8] Blum M. Towards a Conscious AI: A Computer Architecture Inspired by Neuroscience，https://eecs.berkeley.edu/turing-colloquium/schedule/blum, 2018.

CCF推荐

【精品文章】

点击“阅读原文”，前往CCF数图相关栏目。