哥德尔奖得主 Daniel Spielman：实现「躺平」办公，失败乃家常便饭

luyuanhong

哥德尔奖得主 Daniel Spielman：实现「躺平」办公，失败乃家常便饭

撰文 | Mordechai Rorvig

编译 | 王玥

编辑 | 陈彩娴



Daniel Spielman 在耶鲁大学的办公室十分简约，他的书架上摆满了黑色笔记本，里面写满了几十年来写下的笔记。

“我生来就爱静坐沉思。”他说。

在这样宏伟的哥特式校园中，他思考的却是一个较为现代的话题：计算机科学。在 Spielman 的职业生涯中，他创造了许多成果，影响力斐然，但也正如他所讲述的研究故事一样，失败对他来说是家常便饭。“关键是，要享受工作的过程，”他说，“只要享受工作过程，那就没问题——只要偶尔成功一两次就行。”

Daniel Spielman 最初是在耶鲁大学读本科，后在麻省理工学院读研究生，并于 1995 年获得 MIT 博士学位。他在 MIT 研究了保护通信免受干扰的方法，其中包括所谓的纠错码（error-correcting codes）。Robert Gallager 在 1963 年展示了如何用图（图指由线（边）连接的点（顶点）组成的数学对象）构建这些代码，但在 Daniel Spielman 的时代，这种方法在很大程度上被遗忘了。Daniel Spielman 和他的顾问 Michael Sipser 是为数不多的几个重新启用了该方法的人，他们利用名叫扩展图（expander graphs）的特殊图来创建新的代码。他们发明的代码为后来编码理论的许多研究奠定了基础。


图注：Daniel Spielman 获得了两项哥德尔奖和内万林纳奖，两个奖项均为他所在领域的最高荣誉。

在 MIT 期间，Daniel Spielman 遇到了现在南加州大学的研究员滕尚华，从此两人的职业生涯开始交织在一起。他们最卓有成效的一项合作是解释了一种被广泛使用的算法，叫做「单纯形法（simplex method）」，并因此研究获得了奖励理论计算机科学领域杰出工作的哥德尔奖。

由于这对搭档提出了可以快速求解大型简单线性方程组的算法，他们随后又获得了第二个哥德尔奖。当科学家们为简单的物理系统（如热流或电流）建模时，就需要用到这些方程式，这使得这对搭档的算法具有非常重要的实际意义。

为表彰其研究结果，2010 年，Daniel Spielman 被授予内瓦林纳奖（Rolf Nevanlinna Prize），该奖项每四年颁发一次，授予一位不到 40 岁的杰出信息科学家（该奖项后来更名为 IMU 算盘奖章）。

最近，Daniel Spielman 把注意力转向了支撑现代医学研究的随机对照试验背后的数学。这些试验的组织者尝试将研究对象随机分为接受试验性治疗的实验组和不接受试验性治疗的对照组。然而，有限的人群总会在某些方面出现不平衡，比如年龄、体重或血压。Spielman 及其研究小组一起努力寻找实现更好平衡的算法。尽管起步缓慢，但这个项目的进展比他预期的要好。“我们还没有宣告项目失败。”他说。


图注：“对于我解决过的大多数问题，我都能精准说出当时我是如何想到答案的，”Daniel Spielman 说道， “但这不过是因为我在这上面花了太多时间。”

以下是 Quanta 杂志与 Spielman 的对话，内容有所编辑。

1  迈向学术之路

Quanta Magazine：您是如何开始学习计算机科学的？

Daniel Spielman：中学的时候，图书馆里有一本关于计算机编程的书。我读过那本书，书的内容对我来说几乎是有史以来最神奇的东西。那本书介绍了如何给机器人编程，也就是解释了如何对机器人的所有基本任务编程，然后想出某种组织方式把这些基本任务给组合起来。从那一刻起，我就想要一台电脑。有一天我的父母发现一个工程师在卖一台旧的Commodore电脑。而且我们不仅买到了电脑，还得到了这个工程师所有的杂志和书籍。我花了大量的时间阅读这些材料并学习编程。

Quanta Magazine：在孩童时代独自看书是一件挺困难的事，您是怎么熬过来的？

Daniel Spielman：我喜欢思考一切事情。我年轻的时候真的很喜欢思考，直到我有了一台电脑，我才有了可以花那么多时间思考的东西。我猜你会说，我是一个容易对事物着迷的人。其实是我喜欢为一件事努力的感觉。有时我确实会感到沮丧，但这并不能阻止我的兴趣。

另一件让我坚持下去的东西，可能和让一个赌徒坚持下去的东西是一样的。我会觉得自己的主意棒极了，我会觉得我解决了一些问题。我会因此感到非常兴奋，甚至无法入睡。通常这种情况下我妻子会告诉我：“去睡觉吧，明早你就会发现 bug 了。”她知道，几乎每次我以为自己解决了什么问题的时候，其实我根本就没解决。但当人自觉已经解决了一些问题时，就会有一种内啡肽激增的感觉。所以即便是我们错了，这种兴奋的感觉也是一种激励。


图注：“我的记性真的很差，”Daniel Spielman 说， “当我需要记忆的时候，读笔记能让我记得更牢。”

Quanta Magazine：是什么让您开始了自己的第一个大项目（即纠错码）？

Daniel Spielman：我的导师建议我试着更好地理解概率可检测证明（ probabilistically checkable proofs）——这是当时理论计算机科学的主要研究之一。

文章“计算机科学家如何学会让证明以新面目示人（How Computer Scientists Learned to Reinvent the Proof）”中便对概率可检测证明进行了介绍。


论文链接：https://www.quantamagazine.org/h ... the-proof-20220523/

文中称，假设一百万个计算机科学家一起吃晚饭，在支付巨额账单的时候，如果其中一个人想检查账单是否正确，那么检查的过程会显得十分乏味而简单：他们必须检查账单并将所有内容加起来，一次检查一行，而这张账单会超级长。

但在 1992 年，六位计算机科学家在两篇论文中证明了存在一条检查账单的「捷径」。这两篇论文分别为：“证明的概率检验；NP 的一个新表征 （Probabilistic checking of proofs; a new characterization of NP）”和“近似问题的证明验证和难度（Proof verification and hardness of approximation problems）”。


论文地址：https://ieeexplore.ieee.org/document/267824                 https://ieeexplore.ieee.org/document/267823

这六位计算机科学家认为，我们可以做到只需几个查询即可对这张超长的账单进行检查，只要用一种方法将这张账单重新格式化即可。更重要的是，他们发现任何计算，甚至任何数学证明都是如此，因为这两者都有自己的「收据」。而这种非常简洁的格式便被称为概率可检测证明（PCP）。

我有了将概率可检测证明与扩展图联系起来的想法，结果证明这实际上没什么用——但我意识到概率可检测证明对编写纠错码很有用。我们本来想要研究的问题没能解决，却意外在其他地方做出了成果。扩展器代码（ Expander codes）就是我们无心插柳得到的成果。

我的很多研究都是如此。很多时候我本来是打算解决别的问题，但却没有成功。不过我对知识领域有足够的了解，知道我可以用手上的材料研究出点别的什么。

2  学术搭档

Quanta Magazine：同样的情况也发生在了和滕尚华教授合作的平滑分析理论研究中吗？

Daniel Spielman：平滑分析是一个耗时很长的项目，至少当时感觉是这样的。有些时候尚华几乎就住在我们的公寓里。平滑分析确实来自于我和尚华之前做过的另一个研究项目，那个项目失败了，却意外开启了平滑分析的研究。

Quanta Magazine：您是如何开始平滑分析理论研究的？

Daniel Spielman：人们在实践中做了很多他们认为对自己有用的事情，但没有一个理论能解释这是为什么。我们试图理解其中一种算法，这个叫做单纯形法的算法得到了广泛使用。每个人都知道单纯形法有失败的例子，但单纯形法仍然在实践中运用地非常成功。我们试图解释这一现象。最终得出的结论是单纯形法是可行的，因为其失败的所有例子似乎都非常非常脆弱。


图注：进行研究时，Daniel Spielman 会使用各种方法，比如纸笔计算、电脑实验和静坐思考。

部分原因是我们一直在给这些例子编码。我们注意到，当我们不注意数值的精确性时，突然之间，那些本应该破坏单纯形法的东西并没有造成破坏。这就是我们的想法，如果输入中有一点随机性，这个方法会很好。我们能够证明这一点。这个想法颇具影响力，因为其能够让人们理解为什么这个算法有效，人们也通过这个想法和概念去发散理解为什么许多其他的算法有效。

Quanta Magazine：您认为自己和滕尚华的合作为何如此成功？

Daniel Spielman：我在麻省理工学院读研究生的时候，他是那里的老师。我们从那时起就开始一起做研究解决问题，而且我们的工作风格非常合契。你可以看到我办公室里有个沙发。我在麻省理工学院的办公室里有两个沙发。这意味着我和尚华都可以躺着工作，一整天都躺着思考问题，有想法的时候就站起来讨论。他很乐意花很多时间思考和谈论问题。和我一样，他也乐于研究那些我们可能解决不了的异常困难的问题。失败是我们研究问题的标准结果，即使我们已经致力于这项研究好几年了也可能失败。不过没关系。


图注：图（Graph）在现代计算机科学中是必不可少的，在 Spielman 的许多研究中也是如此。

3  学术难题

Quanta Magazine：这个问题有关对照试验：请问把人分成几个小组有什么难的？

Daniel Spielman：这样想吧。给你一枚硬币，抛 10 次看结果，即使结果是随机产生的，但我们也会看到其中的模式，比如可能会连续出现四个正面。如果只给我几个量来测量，比如年龄和性别，然后在 100 个人中随机分组，那么其中一个组的量就会有明显差异。完全随机几乎从来都不是正确的做法。

Quanta Magazine：所以您想要随机地走钢丝吗？

Daniel Spielman：我们称之为「艺术随机」。我们将艺术随机描述为在「完全随机和平衡你所关心的量之间的权衡」。如果你所衡量的因素（如年龄或性别）对结果有影响，哪怕是很小的影响，也最好需要对这些因素进行平衡。我最初认为我们需要平衡所有因素，但事实证明只需要一点点平衡和大量随机性。但这是最近研究得出的结论。大多数结果只是告诉我们存在好的划分，但没有告诉我们如何实现这些划分。而 Nikhil Bansal 在 2009 年的一个突破性成果为我们提供了有效的算法。在我们的工作中，我们正在利用理论计算机科学的结果，用有效的算法来实现这些平衡的划分。人们以前没想过用这些。

Quanta Magazine：考虑到失败似乎经常发生，那您为什么一开始就要解决这些困难的问题？

Daniel Spielman：这是一场赌博。如果我能解决这些问题，我就会非常积极地去做研究，并且会满怀激情地四处演讲。如果不是这样的问题，我就不想为之投入精力。我没有动力花时间在其他的问题上面。我也觉得所有的研究都很困难——至少对我来说是这样。即使看起来很简单的问题，我仍然认为很难解决。所以，既然已经要去做一件很难的事情，为什么不做一些影响很大的事情，或者其他人也认为很难的事情呢?

本文转载自微信公众号“AI科技评论”。

原文链接： https://www.quantamagazine.org/t ... kthroughs-20220613/