0
| 本文作者： 我在思考中 | 2022-06-20 10:14 |
作者 | Mordechai Rorvig
編譯 | 王玥
Daniel Spielman在耶魯大學(xué)的辦公室十分簡約，他的書架上擺滿了黑色筆記本，里面寫滿了幾十年來寫下的筆記。
“我生來就愛靜坐沉思。”他說。
在這樣宏偉的哥特式校園中，他思考的卻是一個較為現(xiàn)代的話題：計算機科學(xué)。在Spielman的職業(yè)生涯中，他創(chuàng)造了許多成果，影響力斐然，但也正如他所講述的研究故事一樣，失敗對他來說是家常便飯。“關(guān)鍵是，要享受工作的過程，”他說，“只要享受工作過程，那就沒問題——只要偶爾成功一兩次就行?！?/span>
Daniel Spielman最初是在耶魯大學(xué)讀本科，后在麻省理工學(xué)院讀研究生，并于1995年獲得MIT博士學(xué)位。他在MIT研究了保護通信免受干擾的方法，其中包括所謂的糾錯碼（error-correcting codes）。Robert Gallager在1963年展示了如何用圖（圖指由線（邊）連接的點（頂點）組成的數(shù)學(xué)對象）構(gòu)建這些代碼，但在Daniel Spielman的時代，這種方法在很大程度上被遺忘了。Daniel Spielman和他的顧問Michael Sipser是為數(shù)不多的幾個重新啟用了該方法的人，他們利用名叫擴展圖（expander graphs）的特殊圖來創(chuàng)建新的代碼。他們發(fā)明的代碼為后來編碼理論的許多研究奠定了基礎(chǔ)。
圖注：Daniel Spielman獲得了兩項哥德爾獎和內(nèi)萬林納獎，兩個獎項均為他所在領(lǐng)域的最高榮譽。
在MIT期間，Daniel Spielman遇到了現(xiàn)在南加州大學(xué)的研究員滕尚華，從此兩人的職業(yè)生涯開始交織在一起。他們最卓有成效的一項合作是解釋了一種被廣泛使用的算法，叫做「單純形法（simplex method）」，并因此研究獲得了獎勵理論計算機科學(xué)領(lǐng)域杰出工作的哥德爾獎。
由于這對搭檔提出了可以快速求解大型簡單線性方程組的算法，他們隨后又獲得了第二個哥德爾獎。當(dāng)科學(xué)家們?yōu)楹唵蔚奈锢硐到y(tǒng)（如熱流或電流）建模時，就需要用到這些方程式，這使得這對搭檔的算法具有非常重要的實際意義。
為表彰其研究結(jié)果，2010年，Daniel Spielman被授予內(nèi)瓦林納獎（Rolf Nevanlinna Prize），該獎項每四年頒發(fā)一次，授予一位不到40歲的杰出信息科學(xué)家（該獎項后來更名為IMU算盤獎?wù)拢?/span>
最近，Daniel Spielman把注意力轉(zhuǎn)向了支撐現(xiàn)代醫(yī)學(xué)研究的隨機對照試驗背后的數(shù)學(xué)。這些試驗的組織者嘗試將研究對象隨機分為接受試驗性治療的實驗組和不接受試驗性治療的對照組。然而，有限的人群總會在某些方面出現(xiàn)不平衡，比如年齡、體重或血壓。Spielman及其研究小組一起努力尋找實現(xiàn)更好平衡的算法。盡管起步緩慢，但這個項目的進展比他預(yù)期的要好?！拔覀冞€沒有宣告項目失敗?！彼f。
圖注：“對于我解決過的大多數(shù)問題，我都能精準(zhǔn)說出當(dāng)時我是如何想到答案的，”Daniel Spielman說道， “但這不過是因為我在這上面花了太多時間?！?/span>
以下是Quanta雜志與 Spielman的對話，內(nèi)容有所編輯。
QuantaMagazine：您是如何開始學(xué)習(xí)計算機科學(xué)的?
Daniel Spielman：中學(xué)的時候，圖書館里有一本關(guān)于計算機編程的書。我讀過那本書，書的內(nèi)容對我來說幾乎是有史以來最神奇的東西。那本書介紹了如何給機器人編程，也就是解釋了如何對機器人的所有基本任務(wù)編程，然后想出某種組織方式把這些基本任務(wù)給組合起來。從那一刻起，我就想要一臺電腦。有一天我的父母發(fā)現(xiàn)一個工程師在賣一臺舊的Commodore電腦。而且我們不僅買到了電腦，還得到了這個工程師所有的雜志和書籍。我花了大量的時間閱讀這些材料并學(xué)習(xí)編程。
QuantaMagazine：在孩童時代獨自看書是一件挺困難的事，您是怎么熬過來的?
Daniel Spielman：我喜歡思考一切事情。我年輕的時候真的很喜歡思考，直到我有了一臺電腦，我才有了可以花那么多時間思考的東西。我猜你會說，我是一個容易對事物著迷的人。其實是我喜歡為一件事努力的感覺。有時我確實會感到沮喪，但這并不能阻止我的興趣。
另一件讓我堅持下去的東西，可能和讓一個賭徒堅持下去的東西是一樣的。我會覺得自己的主意棒極了，我會覺得我解決了一些問題。我會因此感到非常興奮，甚至無法入睡。通常這種情況下我妻子會告訴我：“去睡覺吧，明早你就會發(fā)現(xiàn)bug了?！彼?，幾乎每次我以為自己解決了什么問題的時候，其實我根本就沒解決。但當(dāng)人自覺已經(jīng)解決了一些問題時，就會有一種內(nèi)啡肽激增的感覺。所以即便是我們錯了，這種興奮的感覺也是一種激勵。
圖注：“我的記性真的很差，”Daniel Spielman說， “當(dāng)我需要記憶的時候，讀筆記能讓我記得更牢。”
QuantaMagazine：是什么讓您開始了自己的第一個大項目（即糾錯碼）?
Daniel Spielman：我的導(dǎo)師建議我試著更好地理解概率可檢測證明（ probabilistically checkable proofs）——這是當(dāng)時理論計算機科學(xué)的主要研究之一。
文章“計算機科學(xué)家如何學(xué)會讓證明以新面目示人（How Computer Scientists Learned to Reinvent the Proof）”中便對概率可檢測證明進行了介紹。
論文鏈接：https://www.quantamagazine.org/how-computer-scientists-learned-to-reinvent-the-proof-20220523/
文中稱，假設(shè)一百萬個計算機科學(xué)家一起吃晚飯，在支付巨額賬單的時候，如果其中一個人想檢查賬單是否正確，那么檢查的過程會顯得十分乏味而簡單：他們必須檢查賬單并將所有內(nèi)容加起來，一次檢查一行，而這張賬單會超級長。
但在 1992 年，六位計算機科學(xué)家在兩篇論文中證明了存在一條檢查賬單的「捷徑」。這兩篇論文分別為：“證明的概率檢驗；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
這六位計算機科學(xué)家認(rèn)為，我們可以做到只需幾個查詢即可對這張超長的賬單進行檢查，只要用一種方法將這張賬單重新格式化即可。更重要的是，他們發(fā)現(xiàn)任何計算，甚至任何數(shù)學(xué)證明都是如此，因為這兩者都有自己的「收據(jù)」。而這種非常簡潔的格式便被稱為概率可檢測證明（PCP）。
我有了將概率可檢測證明與擴展圖聯(lián)系起來的想法，結(jié)果證明這實際上沒什么用——但我意識到概率可檢測證明對編寫糾錯碼很有用。我們本來想要研究的問題沒能解決，卻意外在其他地方做出了成果。擴展器代碼（ Expander codes）就是我們無心插柳得到的成果。
我的很多研究都是如此。很多時候我本來是打算解決別的問題，但卻沒有成功。不過我對知識領(lǐng)域有足夠的了解，知道我可以用手上的材料研究出點別的什么。
QuantaMagazine：同樣的情況也發(fā)生在了和滕尚華教授合作的平滑分析理論研究中嗎?
Daniel Spielman：平滑分析是一個耗時很長的項目，至少當(dāng)時感覺是這樣的。有些時候尚華幾乎就住在我們的公寓里。平滑分析確實來自于我和尚華之前做過的另一個研究項目，那個項目失敗了，卻意外開啟了平滑分析的研究。
QuantaMagazine：您是如何開始平滑分析理論研究的?
Daniel Spielman：人們在實踐中做了很多他們認(rèn)為對自己有用的事情，但沒有一個理論能解釋這是為什么。我們試圖理解其中一種算法，這個叫做單純形法的算法得到了廣泛使用。每個人都知道單純形法有失敗的例子，但單純形法仍然在實踐中運用地非常成功。我們試圖解釋這一現(xiàn)象。最終得出的結(jié)論是單純形法是可行的，因為其失敗的所有例子似乎都非常非常脆弱。
圖注：進行研究時，Daniel Spielman會使用了種方法，比如紙筆計算、電腦實驗和靜坐思考。
部分原因是我們一直在給這些例子編碼。我們注意到，當(dāng)我們不注意數(shù)值的精確性時，突然之間，那些本應(yīng)該破壞單純形法的東西并沒有造成破壞。這就是我們的想法，如果輸入中有一點隨機性，這個方法會很好。我們能夠證明這一點。這個想法頗具影響力，因為其能夠讓人們理解為什么這個算法有效，人們也通過這個想法和概念去發(fā)散理解為什么許多其他的算法有效。
QuantaMagazine：您認(rèn)為自己和滕尚華的合作為何如此成功?
Daniel Spielman：我在麻省理工學(xué)院讀研究生的時候，他是那里的老師。我們從那時起就開始一起做研究解決問題，而且我們的工作風(fēng)格非常合契。你可以看到我辦公室里有個沙發(fā)。我在麻省理工學(xué)院的辦公室里有兩個沙發(fā)。這意味著我和尚華都可以躺著工作，一整天都躺著思考問題，有想法的時候就站起來討論。他很樂意花很多時間思考和談?wù)搯栴}。和我一樣，他也樂于研究那些我們可能解決不了的異常困難的問題。失敗是我們研究問題的標(biāo)準(zhǔn)結(jié)果，即使我們已經(jīng)致力于這項研究好幾年了也可能失敗。不過沒關(guān)系。
圖注：圖（Graph）在現(xiàn)代計算機科學(xué)中是必不可少的，在Spielman的許多研究中也是如此。
QuantaMagazine：這個問題有關(guān)對照試驗：請問把人分成幾個小組有什么難的?
Daniel Spielman：這樣想吧。給你一枚硬幣，拋10次看結(jié)果，即使結(jié)果是隨機產(chǎn)生的，但我們也會看到其中的模式，比如可能會連續(xù)出現(xiàn)四個正面。如果只給我?guī)讉€量來測量，比如年齡和性別，然后在100個人中隨機分組，那么其中一個組的量就會有明顯差異。完全隨機幾乎從來都不是正確的做法。
QuantaMagazine：所以您想要隨機地走鋼絲嗎?
Daniel Spielman：我們稱之為「藝術(shù)隨機」。我們將藝術(shù)隨機描述為在「完全隨機和平衡你所關(guān)心的量之間的權(quán)衡」。如果你所衡量的因素（如年齡或性別）對結(jié)果有影響，哪怕是很小的影響，也最好需要對這些因素進行平衡。我最初認(rèn)為我們需要平衡所有因素，但事實證明只需要一點點平衡和大量隨機性。但這是最近研究得出的結(jié)論。大多數(shù)結(jié)果只是告訴我們存在好的劃分，但沒有告訴我們?nèi)绾螌崿F(xiàn)這些劃分。而Nikhil Bansal在2009年的一個突破性成果為我們提供了有效的算法。在我們的工作中，我們正在利用理論計算機科學(xué)的結(jié)果，用有效的算法來實現(xiàn)這些平衡的劃分。人們以前沒想過用這些。
QuantaMagazine：考慮到失敗似乎經(jīng)常發(fā)生，那您為什么一開始就要解決這些困難的問題？
Daniel Spielman：這是一場賭博。如果我能解決這些問題，我就會非常積極地去做研究，并且會滿懷激情地四處演講。如果不是這樣的問題，我就不想為之投入精力。我沒有動力花時間在其他的問題上面。我也覺得所有的研究都很困難——至少對我來說是這樣。即使看起來很簡單的問題，我仍然認(rèn)為很難解決。所以，既然已經(jīng)要去做一件很難的事情，為什么不做一些影響很大的事情，或者其他人也認(rèn)為很難的事情呢?
原文鏈接：
雷峰網(wǎng)(公眾號：雷峰網(wǎng))雷峰網(wǎng)
雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
