编译 | 陈彩娴
近日，ACM 通讯（Communications of the ACM）刊登了一篇德国科技记者 Allyn Jackson 对著名数学家 Martin Davis 的采访。
在采访中，Martin Davis 提出了一个有意思的观点：“机器学习是一个收敛过程，一个连续逼近，已在分析中应用多年。如果你在构建多级神经网络时选择正确的函数，那么它就会迅速收敛…”
Martin Davis 于1928年在美国出生，1950年从普林斯顿大学取得数学博士学位，博士导师为现代计算机理论之父、著名的数学家与逻辑学家 Alonzo Church。后来，他加入纽约大学任教，成为了 NYU 计算机科学系最重要的创始人之一。
在他数十年的研究生涯中，Martin Davis 最为人称道的是他在数理逻辑上的研究成果，尤其是对希尔伯特第十问题（H10）的深入研究。希尔伯特第十问题是关于不定方程的可解答性，希望对于任意多个未知数的整系数不定方程，可以找到一个可行算法，借助该算法后，通过有限次的运算就能判定该方程是否有整数解。
在他的博士答辩论文中，Martin Davis 提出了著名的“戴维斯的大胆假设”（Davis's daring hypothesis），在逻辑与数论之间建立了联系。他假设了递归可枚举集（recursively enumerable sets）与丢番图集（Diophantine sets）是相同的，从而判定 H10 不可解。
后来，在与数学家 Hilary Putnam 与 Julia Robinson 的合作中，Davis 进一步证明了这个大胆的假设，并为俄罗斯计算机科学家 Yuri Matiyasevich 后来在1970 年最终证明 H10 不可解提供了重要的理论基础。
此外，上世纪60年代，Martin Davis 与 Hilary Putnam 一起设计的 Davis-Putnam 算法（简称“DP算法”）成为 SAT 问题的第一个算法，在 SAT 问题被证明为 NP-Complete 问题后，DP算法也成为了所有完备问题算法的基本框架。
以下是 ACM 通讯对 Martin Davis 的访谈问答：
Q1：您对 “P 不同于 NP”持怀疑态度，是这样吗？
人们认为 NP 类是类似于递归可枚举集的。这种类比是基于假设多项式时间的可计算性是可计算性的类比，多项式时间的可计算性是切实可行的可计算性。为什么你会相信这个说法呢？这个说法并不合理。如果你有一个包含大数值系数的高阶多项式边界，那么它在计算上根本是不可行的。NP类具有良好的数学闭合特性。这当然是一个有趣的类别，但为什么认为它可行呢？
在实际的应用中，存在非常有用且运行良好的指数时间算法（exponential-time algorithms）。我的这个观点是参考了 Margaret Wright 的研究工作。起初，人们认为线性规划不是多项式时间。所以，在发现用于线性规划的多项式时间算法时，人们认为这是一项重大突破，但事实上，这个算法的效果并不出色！如 Margaret Wright 所展示，在最坏的情况下呈指数的单纯形法（simplex method）在许多案例中性能更好，也更快。
我的部分怀疑也与我在研究 H10 问题的经历有关。在 H10 这个问题上，人们显然对高级多项式没有任何直觉。
顺便说一句，虽然我不知道 Donald Knuth 的推理依据是什么，但他的看法跟我一样，即“P 不同于 NP”绝对不是一个开放与封闭的案例，所以我会说，概率是一半一半吧。
Q2：那您对 NP-Complete 问题怎么看？
我认为 NP-complete 问题肯定是难题。我不认为有人可以为任何 NP-Complete 问题找到一个漂亮、可爱又快速的算法。不过，这并不意味着研究人员找不到多项式时间算法，只是这也许不是一个非常可行的算法。关于启发式的争论背后，总是有一个观点，即“多项式时间”（polynomial-time）与“可行”（feasible）是一回事。
Q3：如何更好地定义“可行”？
目前还不清楚是否有一个非常精确的概念。定义的方式可能就像“有些算法比其他算法更难”，只有一个范围。
此外，什么是可行的，部分要取决于你有哪些可用的计算机设备。在我写的《通用计算机》（The Universal Computer）中，我想用数字 π 来解释关于收敛的想法。所以我用莱布尼茨的数列 π/ 4 = 1 - 1/3 + 1/5 - 1/7…写了一个程序，并计算出这个数列大约有 20,000 项。
但最近，又感觉通过将莱布尼茨级数中的 20,000 项相加来计算 π 的想法似乎是非常愚蠢的。不过，这只是一个业余爱好者可以轻松地使用家里的电脑和计算机编程知识的表现罢了。
Q4：在《通用计算机》的 2018 年版本中，您添加了一些关于机器学习与人工智能的新内容。机器学习最让您感到惊喜的是什么？
这些神经网络模型非常有用，而且它们的功能非常强大。多年来，我一直对神经网络抱有怀疑的态度。最初的想法是，神经网络是在模仿大脑。然后我想，“这只是另一种模式，没有什么特别的优点。”但事实是，对于某些问题，例如围棋比赛，神经网络的效果出奇地好。在这一点上，我的直觉是完全错误的。
Q5：目前没有理论解释为什么机器学习这么有效。您认为会出现这样的理论吗？
我不认为机器学习有多神秘。机器学习就是一个收敛过程，一个逐次逼近，已经在分析中应用多年。如果在构建多层神经网络时选择正确的函数，那么它就会迅速收敛，所以我不认为机器学习涉及到了特殊的深层理论。我甚至怀疑神经网络是在模仿自然。
如果你要成为钢琴演奏家，你每天要练习七个小时。那么，为什么你不能只读一本手册，上面告诉你“你必须要成为一名钢琴演奏家”？因为这行不通。你坐在钢琴前，去请教一位老师，他也只会看着你做的事情，然后说：“你这不对，你的小指放的位置偏离了一点点。” 这就是一个收敛过程。
Q6：目前，人工智能的研究成果与社会应用正呈爆炸式增长。这是一件好事，还是一件需要警惕的事？
我是这样想的：我们有没有可能制造一台自动机，可以帮我们做所有事情，甚至做得更好？比如围棋和国际象棋之类难度极高的游戏。是的，我们可以。在这些方面，人类已经不能打败机器。
这就涉及到我们自己如何做这些事情，但我们真的不了解。大脑真的会执行算法吗？大脑确实会一些。当我们制造一台自动机器去执行算法时，我们也会使用算法。我们的大脑显然会进行搜索。我们试图记住一条信息，它不会立即弹出来，但我们等一会，它就会突然弹出。当然，我们知道，通用计算不需要太多。Stephen Wolfram 几乎把通用计算机搞成了一种邪教，称通用计算可以在非常小的实体中使用。事实上，如果大脑要通过执行算法来完成所有奇妙的事情，那么我们也肯定能够制造出做同样事情的计算机。
莱斯大学有一位学者讨论过这个问题。他的名字是什么...？
Moshe Vardi?
是的。看，你刚刚在电脑上搜了他的名字！他说，在一个时代后，我们将可以拥有一台能做人类做的任何事情的机器。这个说法可能有点过于乐观了。
如果你看这些神经网络的惊人成就，你会发现，他们无法产生新的想法。问题是，我们的大脑中在多大程度上产生一些更高级的想法，就像完全不同的技术一样。不过，我的看法不同，我怀疑，在另一个层面上，这些技术是完全相同的。毕竟，我们要通过研究大量的数学知识，才能成为优秀的数学家。
Q7：那么您如何解释伟大的数学家在感知新结构、或将两个看起来非常不同的事物联系起来时所产生的洞察力或想象力的飞跃？您在研究 H10 问题时就是这样的，当时您认为递归可枚举集和丢番图集可能是相同的。
嗯……一个集毕竟是另一个集的子集，所以我不是将两个完全不同的事物连接在一起。这更像是扩展了一些看起来非常有限的事物的研究范围。
Q8：但这是跳出条框思考，思考您的知识以外的内容。如果大脑真的只是接收和合成信息，您如何解释这种飞跃？
很显然，我不知道我们的大脑是如何做到这一点的。但是，这显然是一种有用的生存技能，也是人类社会建立的可能因素之一。如他人曾说：“火不仅仅只会烧伤我们，也可以烹饪出美味的食物。”
Q9：您怎么看待莫扎特写交响曲这件事？计算机还做不了这种事。
嗯……计算机已经可以创作音乐了，只是还没有创作出我所欣赏的音乐。但莫扎特是非常罕见的。就像任何作曲家一样，莫扎特的技能要经过磨练，他的大脑以某种非常特殊的方式连接在一起，从而产生了美妙的音乐创意。我们不知道他是怎么做到的，也不知道如何“造出”一个莫扎特。但未来，也许我们会知道。
Q10：所以您认为这是可能的。
我想不出为什么它应该是不可能的。这会使旧思想更顽固。如果你问哥德尔，他会说，认为原生质（protoplasm）成就一切的想法是荒谬的。他相信思想是产生抽象、甚至超越的事物，思想使用了大脑，但大脑并不产生思想。另一方面，Marvin Minsky 还认为，思想是大脑运作的原因。
20世纪生物学的胜利已经破坏了生机主义（vitalism）的案例，这也是哲学立场，即生物的属性不能用物理和化学的一般规律来解释。哥德尔是心理现象（mental phenomena）的活跃分子，心理现象的观点在神经科学知识的现有状态下仍然可以保持一致。
https://cacm.acm.org/news/255113-life-as-a-logician/fulltext赠书福利
AI科技评论本次联合Springer为大家带来5本周志华教授亲笔签名的《Machine Learning》正版新书。
在AI科技评论8月28日头条文章（注意不是本文，仅限AI科技评论微信公众号端）留言区留言，欢迎大家畅所欲言，谈一谈你对本书的看法和期待。在综合留言质量（留言是敷衍还是走心）和留言点赞最高（注：点赞最高的前5不意味着一定会中奖）的读者中选出5位读者获得赠书。获得赠书的读者请联系 AI 科技评论客服（aitechreview）。
由于微信公众号试行乱序推送，您可能不再能准时收到AI科技评论的推送。为了第一时间收到AI科技评论的报道， 请将“AI科技评论”设为星标账号，以及常点文末右下角的“在看”。
