东莞|对话李国杰：突破麦肯锡和图灵的框框，人工智能要解决大问题丨GAIR 2021( 四 )

为什么以AlphaFold为例？这是基于我对人工智能的一个基本判断：人工智能不仅要模仿人，更要解决大问题。从计算机科学的角度来讲，人工智能应该关注NP-hard级别的难题。我们现有的人工智能研究，要么不够顶天，只能解决小问题，要么难以落地，难以在实际场景中得到应用。

“人工智能是拿来解决大问题的”

东莞|对话李国杰：突破麦肯锡和图灵的框框，人工智能要解决大问题丨GAIR 2021

文章插图

“顶天”意味着什么

雷峰网：您此前提到，学术界的人工智能研究过分局限于约翰·麦肯锡的定义，也就是人工智能的目标是“像人”，并指出我们应该突破对智能的狭义理解。这与AI要解决NP-hard级别难题有什么联系？
李国杰：“像人”的人工智能是一个已经被大家很重视的方向，但我认为人工智能的另一个发力点是「解决大问题」。尤其是用机器学习的方法解决意义重大的科学难题，即在多项式时间内“有效解决”指数复杂性问题。
所谓指数复杂性是指求解一个问题所需的时间或空间（存储用量）随着问题规模增加而指数性地增加。这也就人们常说的组合爆炸。在计算复杂性理论中，将一大类目前还找不到多项式级复杂性算法的问题划归为NP-hard问题。如果一个问题能找到多项式级复杂性的算法，例如排序算法等，直接按确定的程序计算就能精确求解，人们一般不认为是人工智能应用。人工智能要研究的问题几乎都是NP-hard问题，从其诞生开始就要对付组合爆炸。从这种意义上讲，人工智能的“天”就是组合爆炸，所谓“顶天”就是找到巧妙的办法克服组合爆炸。
经过60多年的人工智能研究，对付计算机视觉、听觉、机器翻译等领域的组合爆炸已取得令人满意的进步，但在基础研究和实际应用中还有大量的NP-hard问题等着我们去突破。随着氨基酸单体的增加，蛋白质结构预测的计算复杂度呈指数级上升，如果用野蛮搜索，蛋白质结构预测的可能组合高达10的几百次方，这是典型的NP-hard问题。如今的“卡脖子”的芯片设计问题也是NP-hard问题。中国科学院计算所正在探索用“芯片学习”取代“芯片设计”，这可能是破解芯片设计人才缺口的出路。
这些才是真正的大问题，人工智能研究要顶天，就必须进入这些过去认为不可能的“禁区”。
难以落地是“不为也”，“非不能也”
雷峰网：上述您提到的两个例子，蛋白质结构预测和EDA都是应用价值很高的问题。您认为只要专注NP-hard级别的难题，就可以让人工智能研究既可顶天又能落地吗？
李国杰：还不够，这关系到计算机科学界的一个“传统”。有一本经典的关于NP问题的研究生教材《Computers and Intractability: A Guide to the Theory of NP》。书里第一页就是幅漫画，画中两个人在对话，一个人说：“我找不到有效的算法，但所有这些最优秀的人也找不到”（见下图）。这其实代表了计算机理论界对NP-hard问题的态度。

文章插图

直到50年后的今天，这一“传统”仍在持续影响着一代又一代计算机科学领域的学者。人们都在拼命证明“这个问题是不是NP-hard”。只要是NP-hard问题，就没有‘我们’的责任了，而不再想有没有什么办法解决困难问题，这是很滑稽的局面。其他学科都在努力解决各种难题，唯独计算机科学整天在讨论什么问题解决不了。
只纠结于理论边界的证明，而不去想办法解决问题，这是我们无法让困难问题落地的根本原因。几十年来，我们将NP-hard问题视作障碍，认为这是我们无法解决的问题。但是随着人工智能和计算机技术的进步，我们发现通过启发式搜索、知识工程和机器学习，加上充分大的算力，很多NP-hard问题可以得到满意的解。NP-hard意味着不可能的时代已经过去，NP-hard只是意味着可能没有始终有效和可扩展的算法而已，但许多NP-hard问题对于应用而言实际上有可以解决。人工智能学者的任务就是发掘出貌似不可能中的可行方案。