他山之石,可以攻玉——丹尼尔 · 斯皮尔曼的解决问题之道。

14.1

丹尼尔 · 斯皮尔曼已在计算机科学领域取得一系列突破性成果

丹尼尔 · 斯皮尔曼(Daniel Spielman)的办公室坐落在以穹顶和尖塔闻名的耶鲁大学校园里,他的书架上摆满了高高的黑色笔记本,那是他几十年的手写笔记,靠墙放着一张舒适的大沙发,看起来经常被使用。

“我天生喜欢静坐沉思。”他说。

在宏伟古典的哥特式校园中,他思考的却是一个比较现代的话题:计算机科学。在斯皮尔曼的职业生涯中,他创造了许多有影响力的成果,但他却告诉我们,失败对他来说是家常便饭。“关键是你要享受工作的过程,” 他说,“只要享受过程,那就没问题——偶尔成功一两次就行。”

斯皮尔曼最初是在耶鲁大学读本科,然后在麻省理工学院读研究生,并于 1995 年获得博士学位,2005年回到耶鲁大学任教。在麻省理工,他研究了保护通信免受干扰的方法,其中包括所谓的纠错码。罗伯特 · 加拉格(Robert Gallager) 在 1963 年展示了如何用图(Graph)构建这些编码,图指由线(边)连接的点(顶点)组成的数学对象。但在斯皮尔曼的时代,这种方法很大程度上被遗忘了。斯皮尔曼和他的导师迈克尔 · 西普塞(Michael Sipser) 是为数不多的几个重新启用该方法的人,他们利用被称为扩展图(expander graphs)的特殊图来创建新的编码。他们发明的编码方式为后来编码理论的许多研究奠定了基础,包括最近的一项重大突破。

在麻省理工期间,斯皮尔曼遇到了现在在南加州大学的研究员滕尚华(Shang-Hua Teng),此后两人的职业生涯交织在一起。他们最富有成果的一项合作是解释了一种被广泛使用的称为单纯形法(simplex method)的算法,并因此获得了哥德尔奖,这是一项理论计算机科学领域的年度杰出工作奖。

这对搭档后来又因为提出了能够快速求解大型简单线性方程组的算法而获得了第二个哥德尔奖。科学家们为简单的物理系统(如热流或电流)建模时,需要用到这类方程,所以两人的算法具有非常重要的实用性。

2010 年, 斯皮尔曼被授予内万林纳奖(Rolf Nevanlinna Prize,该奖项已更名为 IMU 算盘奖章),该奖项每四年颁发一次,授予一位 40 岁以下的杰出信息科学家。

14.2

斯皮尔曼曾获得两次哥德尔奖和一次内万林纳奖,这些是他所在领域的最高荣誉

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

《量子杂志》记者在斯皮尔曼的办公室里,和他聊了一些话题,思考的力量,是什么成就了成功的合作,以及研究有时就像赌博。为了清晰起见,采访内容经过了剪辑。

14.3

“对于我解决过的大多数问题,我都记得想出答案的那个瞬间,那是因为我在这上面花了太多时间。”斯皮尔曼说

您是如何开始学习计算机科学的 ?

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

在孩童时代独自看书听起来很困难,你是怎么熬过来的 ?

我喜欢克服困难搞定一切。我年轻的时候真的很喜欢思考,但直到我有了那台电脑,我的思考才有了用武之地。我对某些事物很着迷,我喜欢为一件事努力的感觉。有时确实会沮丧,但这并不能阻止我。

另一个让我坚持下去的动力,可能和一个赌徒坚持下去的想法是一样的。我会觉得我有一个绝妙的主意,我会觉得我解决了一些问题。我会因此兴奋,睡不着觉。我的妻子总是说:“ 去睡觉吧,明早你就会发现你高兴得太早了。” 她知道,几乎每次我以为自己解决了什么问题的时候,都是错觉。不过当你认为你解决了一些问题的时候,你会不由自主心生惬意。即便最后发现自己错了,这种兴奋的感觉也是一种激励。

是什么让你开始了自己的第一个大项目(即纠错码)?

我的导师曾建议我试着更好地理解概率可校验证明( probabilistically checkable proofs)——这是当时理论计算机科学的主要研究之一。我有了将它们和扩展图联系起来的想法,结果证明这实际上没什么用——但我意识到它们对编写纠错码很有用。我们本来想研究的问题没能得到解决,开发出来的东西却在其他方面很有用。扩展码( expander codes)就是我们无心插柳的产物。

我的很多研究都是这样。很多时候我本来打算解决某个问题,最后没有成功。但我对知识领域有足够的了解,知道研究出来的东西可以做点别的什么。

14.4

“我的记性真的很差,当我需要想什么东西的时候,读笔记更容易唤醒我的记忆。”斯皮尔曼说

与滕尚华教授合作的平滑分析理论也是这样诞生的吗 ?

那是一个漫长的项目,至少当时感觉是这样。中间有些时候,尚华直接住在我们公寓里。平滑分析确实来自我和尚华之前做过的另外一个研究项目,那个项目失败了。

你是如何开始平滑分析理论研究的 ?

有很多东西在实践中很管用,却没有一个好的理论来解释为什么。我们当时正试图理解一种叫作单纯形法的常用算法,每个人都知道它存在缺陷,但它仍然在实践中被广泛应用。我们一直在想怎么解释这个现象。最终得出的结论是单纯形法之所以有效,是因为其理论上不适用的场合在现实中很难出现。

14.5

进行研究时,斯皮尔曼会使用多种方法,比如纸笔计算、电脑实验和静坐思考

我们给所有这些例子编码,然后发现,如果我们不太在意数值的精确度,那么突然之间,单纯形法本该出错的那些地方不再出错。所以这就是我们的想法,如果输入数据加一点随机性,单纯形法就会很完美。我们能够证明这一点。这个想法颇具影响力,因为它能够让人们理解为什么单纯形法有效,而且人们已经用这个想法和概念去理解为什么许多其他算法有效。

14.6

图在现代计算机科学中是必不可少的,在斯皮尔曼的大部分工作中也是如此

为什么你认为与滕尚华的合作很成功?

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

乍一看,有关对照试验的课题比其他课题简单,把人分成几个小组有什么难的 ?

这样想吧。如果我给你一枚硬币,你抛 10 次,看看结果,即使结果是随机产生的,我们也能看到一些特定组合,比如可能会连续出现四个正面。如果你要我根据年龄和性别,把 100 个人随机分组,那么其中某组可能会表现出明显差异。完全随机几乎从来都不是正确的做法。

所以你想要走钢丝一样的随机吗 ?

我们称之为「艺术随机」。我们将其描述为在完全随机和平衡你所关心的因素之间的权衡。如果你所衡量的因素(如年龄或性别)对结果有影响,哪怕很小的影响,也最好平衡一下。我最初以为我们需要平衡所有因素,但事实证明,只需要一点点的平衡和大量的随机性。但这是最近的一个进展。大多数结果只是告诉你存在好的划分,但没有告诉你如何找到它们。 尼基尔 · 班塞尔(Nikhil Bansal) 在 2009 年的一个突破性成果为我们提供了高效的算法。在我们的工作中,我们借助理论计算机科学的成果,用有效的算法,来实现这些平衡的划分。以前人们从没想过用这些。

最后一个问题,既然失败如此频繁,为什么还要致力于特别难的课题?

这是一场赌博。如果我能解决一些特别难的课题,我会很开心地到处去演讲,这是我的原动力。我通常不研究缺少难度的问题,对它们提不起兴趣,不愿在上面花时间。我还有一种感觉,就是所有的研究都很困难——至少对我来说是这样。即使看起来很简单的问题,我仍然认为很难解决。所以,既然已经要去做一件很难的事情,为什么不做那些影响很大的事情,或者其他人也认为很难的事情呢 ?

资料来源Quanta Magazine

————————

本文作者莫迪凯·罗维格(Mordechai Rorvig)是《量子杂志》签约作家,主攻计算机科学领域。