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