編譯 西岸
丹尼爾?斯皮爾曼已在計算機科學領域取得一系列突破性成果
丹尼爾?斯皮爾曼(Daniel Spielman)的辦公室坐落在以穹頂和尖塔聞名的耶魯大學校園里,他的書架上擺滿了高高的黑色筆記本,那是他幾十年的手寫筆記,靠墻放著一張舒適的大沙發,看起來經常被使用。
“我天生喜歡靜坐沉思?!彼f。
在宏偉古典的哥特式校園中,他思考的卻是一個比較現代的話題:計算機科學。在斯皮爾曼的職業生涯中,他創造了許多有影響力的成果,但他卻告訴我們,失敗對他來說是家常便飯?!瓣P鍵是你要享受工作的過程,” 他說,“只要享受過程,那就沒問題——偶爾成功一兩次就行?!?/p>
斯皮爾曼最初是在耶魯大學讀本科,然后在麻省理工學院讀研究生,并于 1995 年獲得博士學位,2005年回到耶魯大學任教。在麻省理工,他研究了保護通信免受干擾的方法,其中包括所謂的糾錯碼。羅伯特?加拉格(Robert Gallager) 在 1963 年展示了如何用圖(Graph)構建這些編碼,圖指由線(邊)連接的點(頂點)組成的數學對象。但在斯皮爾曼的時代,這種方法很大程度上被遺忘了。斯皮爾曼和他的導師邁克爾?西普塞(Michael Sipser) 是為數不多的幾個重新啟用該方法的人,他們利用被稱為擴展圖(expander graphs)的特殊圖來創建新的編碼。他們發明的編碼方式為后來編碼理論的許多研究奠定了基礎,包括最近的一項重大突破。
在麻省理工期間,斯皮爾曼遇到了現在在南加州大學的研究員滕尚華(Shang-Hua Teng),此后兩人的職業生涯交織在一起。他們最富有成果的一項合作是解釋了一種被廣泛使用的稱為單純形法(simplex method)的算法,并因此獲得了哥德爾獎,這是一項理論計算機科學領域的年度杰出工作獎。
這對搭檔后來又因為提出了能夠快速求解大型簡單線性方程組的算法而獲得了第二個哥德爾獎??茖W家們為簡單的物理系統(如熱流或電流)建模時,需要用到這類方程,所以兩人的算法具有非常重要的實用性。
2010 年, 斯皮爾曼被授予內萬林納獎(Rolf Nevanlinna Prize,該獎項已更名為 IMU 算盤獎章),該獎項每四年頒發一次,授予一位 40 歲以下的杰出信息科學家。
斯皮爾曼曾獲得兩次哥德爾獎和一次內萬林納獎,這些是他所在領域的最高榮譽
最近, 斯皮爾曼開始把注意力轉向支撐現代醫學研究的隨機對照試驗背后的數學問題。這些試驗的組織者試圖將受試者隨機分為兩組,一組接受實驗性治療,另一組不接受。然而,數量有限的群體總會在某些方面出現不平衡,比如年齡、體重或血壓。斯皮爾曼和他的研究小組一起致力于尋找實現更好平衡的算法。盡管起步緩慢,但這個項目的進展比斯皮爾曼預期的要好?!拔覀冞€沒有宣告項目失敗?!彼f。
《量子雜志》記者在斯皮爾曼的辦公室里,和他聊了一些話題,思考的力量,是什么成就了成功的合作,以及研究有時就像賭博。為了清晰起見,采訪內容經過了剪輯。
“對于我解決過的大多數問題,我都記得想出答案的那個瞬間,那是因為我在這上面花了太多時間?!彼蛊柭f
中學的時候,圖書館里有一本關于計算機編程的書,里面的內容對我來說幾乎是有史以來最神奇的東西。那本書介紹了如何給機器人編程——解釋如何給所有這些基本任務編程,然后想出某種組織方式。從那一刻起,我特別想要一臺電腦。有一天我的父母發現一個工程師在賣一臺舊的電腦。很棒的是,我們不僅買到了電腦,還拿到了這個工程師所有的雜志和書籍。我花了大量時間閱讀這些材料并學習編程。
我喜歡克服困難搞定一切。我年輕的時候真的很喜歡思考,但直到我有了那臺電腦,我的思考才有了用武之地。我對某些事物很著迷,我喜歡為一件事努力的感覺。有時確實會沮喪,但這并不能阻止我。
另一個讓我堅持下去的動力,可能和一個賭徒堅持下去的想法是一樣的。我會覺得我有一個絕妙的主意,我會覺得我解決了一些問題。我會因此興奮,睡不著覺。我的妻子總是說:“ 去睡覺吧,明早你就會發現你高興得太早了?!彼?,幾乎每次我以為自己解決了什么問題的時候,都是錯覺。不過當你認為你解決了一些問題的時候,你會不由自主心生愜意。即便最后發現自己錯了,這種興奮的感覺也是一種激勵。
我的導師曾建議我試著更好地理解概率可校驗證明( probabilistically checkable proofs)——這是當時理論計算機科學的主要研究之一。我有了將它們和擴展圖聯系起來的想法,結果證明這實際上沒什么用——但我意識到它們對編寫糾錯碼很有用。我們本來想研究的問題沒能得到解決,開發出來的東西卻在其他方面很有用。擴展碼( expander codes)就是我們無心插柳的產物。
我的很多研究都是這樣。很多時候我本來打算解決某個問題,最后沒有成功。但我對知識領域有足夠的了解,知道研究出來的東西可以做點別的什么。
“我的記性真的很差,當我需要想什么東西的時候,讀筆記更容易喚醒我的記憶?!彼蛊柭f
那是一個漫長的項目,至少當時感覺是這樣。中間有些時候,尚華直接住在我們公寓里。平滑分析確實來自我和尚華之前做過的另外一個研究項目,那個項目失敗了。
進行研究時,斯皮爾曼會使用多種方法,比如紙筆計算、電腦實驗和靜坐思考
有很多東西在實踐中很管用,卻沒有一個好的理論來解釋為什么。我們當時正試圖理解一種叫作單純形法的常用算法,每個人都知道它存在缺陷,但它仍然在實踐中被廣泛應用。我們一直在想怎么解釋這個現象。最終得出的結論是單純形法之所以有效,是因為其理論上不適用的場合在現實中很難出現。
我們給所有這些例子編碼,然后發現,如果我們不太在意數值的精確度,那么突然之間,單純形法本該出錯的那些地方不再出錯。所以這就是我們的想法,如果輸入數據加一點隨機性,單純形法就會很完美。我們能夠證明這一點。這個想法頗具影響力,因為它能夠讓人們理解為什么單純形法有效,而且人們已經用這個想法和概念去理解為什么許多其他算法有效。
圖在現代計算機科學中是必不可少的,在斯皮爾曼的大部分工作中也是如此
我在麻省理工學院讀研究生的時候,他是那里的老師。從那時起,我們就開始一起做研究,而且我們的工作風格非常合拍。你可以看到我辦公室里有個沙發。我在麻省理工學院的辦公室里有兩個沙發。這意味著我和尚華可以一起躺著工作,一整天都躺著思考問題,有想法的時候就站起來討論。他很樂意花費大量時間思考和談論問題。和我一樣,他也樂于研究那些我們可能解決不了的超級難題。失敗是我們研究問題的標準結果,即使我們為之花費了很多年。不過沒關系。
這樣想吧。如果我給你一枚硬幣,你拋 10 次,看看結果,即使結果是隨機產生的,我們也能看到一些特定組合,比如可能會連續出現四個正面。如果你要我根據年齡和性別,把 100 個人隨機分組,那么其中某組可能會表現出明顯差異。完全隨機幾乎從來都不是正確的做法。
我們稱之為「藝術隨機」。我們將其描述為在完全隨機和平衡你所關心的因素之間的權衡。如果你所衡量的因素(如年齡或性別)對結果有影響,哪怕很小的影響,也最好平衡一下。我最初以為我們需要平衡所有因素,但事實證明,只需要一點點的平衡和大量的隨機性。但這是最近的一個進展。大多數結果只是告訴你存在好的劃分,但沒有告訴你如何找到它們。 尼基爾?班塞爾(Nikhil Bansal) 在 2009 年的一個突破性成果為我們提供了高效的算法。在我們的工作中,我們借助理論計算機科學的成果,用有效的算法,來實現這些平衡的劃分。以前人們從沒想過用這些。
這是一場賭博。如果我能解決一些特別難的課題,我會很開心地到處去演講,這是我的原動力。我通常不研究缺少難度的問題,對它們提不起興趣,不愿在上面花時間。我還有一種感覺,就是所有的研究都很困難——至少對我來說是這樣。即使看起來很簡單的問題,我仍然認為很難解決。所以,既然已經要去做一件很難的事情,為什么不做那些影響很大的事情,或者其他人也認為很難的事情呢 ?
資料來源Quanta Magazine