算法|Martin Davis最新访谈：机器学习是一个收敛的过程，背后理论并不高深

文章插图

编译 | 陈彩娴
近日，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）是一回事。