編譯 西岸

丹尼爾?斯皮爾曼已在計(jì)算機(jī)科學(xué)領(lǐng)域取得一系列突破性成果

丹尼爾?斯皮爾曼（Daniel Spielman）的辦公室坐落在以穹頂和尖塔聞名的耶魯大學(xué)校園里，他的書架上擺滿了高高的黑色筆記本，那是他幾十年的手寫筆記，靠墻放著一張舒適的大沙發(fā)，看起來經(jīng)常被使用。

“我天生喜歡靜坐沉思。”他說。

在宏偉古典的哥特式校園中，他思考的卻是一個(gè)比較現(xiàn)代的話題：計(jì)算機(jī)科學(xué)。在斯皮爾曼的職業(yè)生涯中，他創(chuàng)造了許多有影響力的成果，但他卻告訴我們，失敗對(duì)他來說是家常便飯?！瓣P(guān)鍵是你要享受工作的過程，” 他說，“只要享受過程，那就沒問題——偶爾成功一兩次就行?！?/p>

斯皮爾曼最初是在耶魯大學(xué)讀本科，然后在麻省理工學(xué)院讀研究生，并于 1995 年獲得博士學(xué)位，2005年回到耶魯大學(xué)任教。在麻省理工，他研究了保護(hù)通信免受干擾的方法，其中包括所謂的糾錯(cuò)碼。羅伯特?加拉格（Robert Gallager） 在 1963 年展示了如何用圖（Graph）構(gòu)建這些編碼，圖指由線（邊）連接的點(diǎn)（頂點(diǎn)）組成的數(shù)學(xué)對(duì)象。但在斯皮爾曼的時(shí)代，這種方法很大程度上被遺忘了。斯皮爾曼和他的導(dǎo)師邁克爾?西普塞（Michael Sipser） 是為數(shù)不多的幾個(gè)重新啟用該方法的人，他們利用被稱為擴(kuò)展圖（expander graphs）的特殊圖來創(chuàng)建新的編碼。他們發(fā)明的編碼方式為后來編碼理論的許多研究奠定了基礎(chǔ)，包括最近的一項(xiàng)重大突破。

在麻省理工期間，斯皮爾曼遇到了現(xiàn)在在南加州大學(xué)的研究員滕尚華（Shang-Hua Teng），此后兩人的職業(yè)生涯交織在一起。他們最富有成果的一項(xiàng)合作是解釋了一種被廣泛使用的稱為單純形法（simplex method）的算法，并因此獲得了哥德爾獎(jiǎng)，這是一項(xiàng)理論計(jì)算機(jī)科學(xué)領(lǐng)域的年度杰出工作獎(jiǎng)。

這對(duì)搭檔后來又因?yàn)樘岢隽四軌蚩焖偾蠼獯笮秃?jiǎn)單線性方程組的算法而獲得了第二個(gè)哥德爾獎(jiǎng)。科學(xué)家們?yōu)楹?jiǎn)單的物理系統(tǒng)（如熱流或電流）建模時(shí)，需要用到這類方程，所以兩人的算法具有非常重要的實(shí)用性。

2010 年， 斯皮爾曼被授予內(nèi)萬(wàn)林納獎(jiǎng)（Rolf Nevanlinna Prize，該獎(jiǎng)項(xiàng)已更名為 IMU 算盤獎(jiǎng)?wù)拢?，該?jiǎng)項(xiàng)每四年頒發(fā)一次，授予一位 40 歲以下的杰出信息科學(xué)家。

斯皮爾曼曾獲得兩次哥德爾獎(jiǎng)和一次內(nèi)萬(wàn)林納獎(jiǎng)，這些是他所在領(lǐng)域的最高榮譽(yù)

最近， 斯皮爾曼開始把注意力轉(zhuǎn)向支撐現(xiàn)代醫(yī)學(xué)研究的隨機(jī)對(duì)照試驗(yàn)背后的數(shù)學(xué)問題。這些試驗(yàn)的組織者試圖將受試者隨機(jī)分為兩組，一組接受實(shí)驗(yàn)性治療，另一組不接受。然而，數(shù)量有限的群體總會(huì)在某些方面出現(xiàn)不平衡，比如年齡、體重或血壓。斯皮爾曼和他的研究小組一起致力于尋找實(shí)現(xiàn)更好平衡的算法。盡管起步緩慢，但這個(gè)項(xiàng)目的進(jìn)展比斯皮爾曼預(yù)期的要好?！拔覀冞€沒有宣告項(xiàng)目失敗?！彼f。

《量子雜志》記者在斯皮爾曼的辦公室里，和他聊了一些話題，思考的力量，是什么成就了成功的合作，以及研究有時(shí)就像賭博。為了清晰起見，采訪內(nèi)容經(jīng)過了剪輯。

“對(duì)于我解決過的大多數(shù)問題，我都記得想出答案的那個(gè)瞬間，那是因?yàn)槲以谶@上面花了太多時(shí)間?！彼蛊柭f

您是如何開始學(xué)習(xí)計(jì)算機(jī)科學(xué)的 ?

中學(xué)的時(shí)候，圖書館里有一本關(guān)于計(jì)算機(jī)編程的書，里面的內(nèi)容對(duì)我來說幾乎是有史以來最神奇的東西。那本書介紹了如何給機(jī)器人編程——解釋如何給所有這些基本任務(wù)編程，然后想出某種組織方式。從那一刻起，我特別想要一臺(tái)電腦。有一天我的父母發(fā)現(xiàn)一個(gè)工程師在賣一臺(tái)舊的電腦。很棒的是，我們不僅買到了電腦，還拿到了這個(gè)工程師所有的雜志和書籍。我花了大量時(shí)間閱讀這些材料并學(xué)習(xí)編程。

在孩童時(shí)代獨(dú)自看書聽起來很困難，你是怎么熬過來的 ?

我喜歡克服困難搞定一切。我年輕的時(shí)候真的很喜歡思考，但直到我有了那臺(tái)電腦，我的思考才有了用武之地。我對(duì)某些事物很著迷，我喜歡為一件事努力的感覺。有時(shí)確實(shí)會(huì)沮喪，但這并不能阻止我。

另一個(gè)讓我堅(jiān)持下去的動(dòng)力，可能和一個(gè)賭徒堅(jiān)持下去的想法是一樣的。我會(huì)覺得我有一個(gè)絕妙的主意，我會(huì)覺得我解決了一些問題。我會(huì)因此興奮，睡不著覺。我的妻子總是說：“ 去睡覺吧，明早你就會(huì)發(fā)現(xiàn)你高興得太早了?！彼?，幾乎每次我以為自己解決了什么問題的時(shí)候，都是錯(cuò)覺。不過當(dāng)你認(rèn)為你解決了一些問題的時(shí)候，你會(huì)不由自主心生愜意。即便最后發(fā)現(xiàn)自己錯(cuò)了，這種興奮的感覺也是一種激勵(lì)。

是什么讓你開始了自己的第一個(gè)大項(xiàng)目（即糾錯(cuò)碼）?

我的導(dǎo)師曾建議我試著更好地理解概率可校驗(yàn)證明（ probabilistically checkable proofs）——這是當(dāng)時(shí)理論計(jì)算機(jī)科學(xué)的主要研究之一。我有了將它們和擴(kuò)展圖聯(lián)系起來的想法，結(jié)果證明這實(shí)際上沒什么用——但我意識(shí)到它們對(duì)編寫糾錯(cuò)碼很有用。我們本來想研究的問題沒能得到解決，開發(fā)出來的東西卻在其他方面很有用。擴(kuò)展碼（ expander codes）就是我們無(wú)心插柳的產(chǎn)物。

我的很多研究都是這樣。很多時(shí)候我本來打算解決某個(gè)問題，最后沒有成功。但我對(duì)知識(shí)領(lǐng)域有足夠的了解，知道研究出來的東西可以做點(diǎn)別的什么。

“我的記性真的很差，當(dāng)我需要想什么東西的時(shí)候，讀筆記更容易喚醒我的記憶。”斯皮爾曼說

與滕尚華教授合作的平滑分析理論也是這樣誕生的嗎 ?

那是一個(gè)漫長(zhǎng)的項(xiàng)目，至少當(dāng)時(shí)感覺是這樣。中間有些時(shí)候，尚華直接住在我們公寓里。平滑分析確實(shí)來自我和尚華之前做過的另外一個(gè)研究項(xiàng)目，那個(gè)項(xiàng)目失敗了。

你是如何開始平滑分析理論研究的 ?

進(jìn)行研究時(shí)，斯皮爾曼會(huì)使用多種方法，比如紙筆計(jì)算、電腦實(shí)驗(yàn)和靜坐思考

有很多東西在實(shí)踐中很管用，卻沒有一個(gè)好的理論來解釋為什么。我們當(dāng)時(shí)正試圖理解一種叫作單純形法的常用算法，每個(gè)人都知道它存在缺陷，但它仍然在實(shí)踐中被廣泛應(yīng)用。我們一直在想怎么解釋這個(gè)現(xiàn)象。最終得出的結(jié)論是單純形法之所以有效，是因?yàn)槠淅碚撋喜贿m用的場(chǎng)合在現(xiàn)實(shí)中很難出現(xiàn)。

我們給所有這些例子編碼，然后發(fā)現(xiàn)，如果我們不太在意數(shù)值的精確度，那么突然之間，單純形法本該出錯(cuò)的那些地方不再出錯(cuò)。所以這就是我們的想法，如果輸入數(shù)據(jù)加一點(diǎn)隨機(jī)性，單純形法就會(huì)很完美。我們能夠證明這一點(diǎn)。這個(gè)想法頗具影響力，因?yàn)樗軌蜃屓藗兝斫鉃槭裁磫渭冃畏ㄓ行?，而且人們已?jīng)用這個(gè)想法和概念去理解為什么許多其他算法有效。

圖在現(xiàn)代計(jì)算機(jī)科學(xué)中是必不可少的，在斯皮爾曼的大部分工作中也是如此

為什么你認(rèn)為與滕尚華的合作很成功?

我在麻省理工學(xué)院讀研究生的時(shí)候，他是那里的老師。從那時(shí)起，我們就開始一起做研究，而且我們的工作風(fēng)格非常合拍。你可以看到我辦公室里有個(gè)沙發(fā)。我在麻省理工學(xué)院的辦公室里有兩個(gè)沙發(fā)。這意味著我和尚華可以一起躺著工作，一整天都躺著思考問題，有想法的時(shí)候就站起來討論。他很樂意花費(fèi)大量時(shí)間思考和談?wù)搯栴}。和我一樣，他也樂于研究那些我們可能解決不了的超級(jí)難題。失敗是我們研究問題的標(biāo)準(zhǔn)結(jié)果，即使我們?yōu)橹ㄙM(fèi)了很多年。不過沒關(guān)系。

乍一看，有關(guān)對(duì)照試驗(yàn)的課題比其他課題簡(jiǎn)單，把人分成幾個(gè)小組有什么難的 ?

這樣想吧。如果我給你一枚硬幣，你拋 10 次，看看結(jié)果，即使結(jié)果是隨機(jī)產(chǎn)生的，我們也能看到一些特定組合，比如可能會(huì)連續(xù)出現(xiàn)四個(gè)正面。如果你要我根據(jù)年齡和性別，把 100 個(gè)人隨機(jī)分組，那么其中某組可能會(huì)表現(xiàn)出明顯差異。完全隨機(jī)幾乎從來都不是正確的做法。

所以你想要走鋼絲一樣的隨機(jī)嗎 ?

我們稱之為「藝術(shù)隨機(jī)」。我們將其描述為在完全隨機(jī)和平衡你所關(guān)心的因素之間的權(quán)衡。如果你所衡量的因素（如年齡或性別）對(duì)結(jié)果有影響，哪怕很小的影響，也最好平衡一下。我最初以為我們需要平衡所有因素，但事實(shí)證明，只需要一點(diǎn)點(diǎn)的平衡和大量的隨機(jī)性。但這是最近的一個(gè)進(jìn)展。大多數(shù)結(jié)果只是告訴你存在好的劃分，但沒有告訴你如何找到它們。 尼基爾?班塞爾（Nikhil Bansal） 在 2009 年的一個(gè)突破性成果為我們提供了高效的算法。在我們的工作中，我們借助理論計(jì)算機(jī)科學(xué)的成果，用有效的算法，來實(shí)現(xiàn)這些平衡的劃分。以前人們從沒想過用這些。

最后一個(gè)問題，既然失敗如此頻繁，為什么還要致力于特別難的課題？

這是一場(chǎng)賭博。如果我能解決一些特別難的課題，我會(huì)很開心地到處去演講，這是我的原動(dòng)力。我通常不研究缺少難度的問題，對(duì)它們提不起興趣，不愿在上面花時(shí)間。我還有一種感覺，就是所有的研究都很困難——至少對(duì)我來說是這樣。即使看起來很簡(jiǎn)單的問題，我仍然認(rèn)為很難解決。所以，既然已經(jīng)要去做一件很難的事情，為什么不做那些影響很大的事情，或者其他人也認(rèn)為很難的事情呢 ?

資料來源Quanta Magazine