文章編號：1672-5913(2011)21-0055-03 中圖分類號：G642 文獻標識碼：A
　　
　　ACM委員會于2011年3月10日公布，2010年度圖靈獎授予萊斯利?瓦里安特教授，表彰他在機器學習理論以及計算機科學諸多方面的奠基性貢獻。
　　2011年6月5日，在加州圣荷塞會議中心ACM召開的計算研究聯(lián)合大會FCRC 2011開幕日上，為萊斯利?瓦里安特舉辦了頒獎晚宴，獎金為25萬美元，仍由Intel和Google贊助。
　　1 學術(shù)生平
　　萊斯利?瓦里安特(Leslie Gabriel Valiant) 1949年3月28日生于英國。1970年在劍橋大學國王學院獲數(shù)學學士學位，1973年在倫敦帝國學院獲計算機科學畢業(yè)文憑，1974年獲華威克大學(University of Warwick)計算機科學博士學位。
　　1973年至1974年，萊斯利在卡內(nèi)基-梅隆大學作
　　
　　訪問學者。1974年至1976年在里茲大學、1977年至1982年在愛丁堡大學、1982年至今在哈佛大學任教。從2001年起，擔任哈佛工程與應(yīng)用科學學院計算機科學與應(yīng)用數(shù)學的杰弗遜(T. Jefferson Coolidge)講席教授。他是英國皇家學會會員、美國科學院院士。
　　2 三大貢獻
　　萊斯利的第一個貢獻是在機器學習領(lǐng)域。1984年他在《ACM通訊》上發(fā)表了論文“習能力理論”(A Theory of the Learnable)，在論文中提出了PAC模型，即“概率近似正確”(Probably Approximately Correct)的學習模型。PAC模型使20世紀50年代誕生的機器學習領(lǐng)域第一次有了堅實的數(shù)學基礎(chǔ)，從而清除了學科發(fā)展的障礙，對于機器學習、人工智能和其他計算領(lǐng)域(如自然語言處理、手寫識別、機器視覺等)都產(chǎn)生了重要影響。該模型可解決信息分類問題，為此學習算法會根據(jù)過去的經(jīng)驗而設(shè)計一個概率假設(shè)，并將此假設(shè)作為判斷依據(jù)。PAC模型可最大限度地降低泛化(Over-generalization)帶來的錯誤，這就是為什么它被稱為“概率近似正確”的原因。
　　
　　萊斯利的第二個貢獻是在計算復(fù)雜性領(lǐng)域。1986年萊斯利和瓦茲拉尼在《理論計算機科學》上發(fā)表論文，題目是“NP同檢測唯一解一樣容易”(NP is as easy as detecting unique solutions)，提出了瓦里安特-瓦茲拉尼定理(Valiant–Vazirani theorem)，合作者瓦茲拉尼(Vijay Virkumar Vazirani)是印度裔美國計算機科學家，佐治亞技術(shù)學院教授。
　　該定理可敘述為：UNIQUE-SAT ? P ? NP = RP。其中，SAT表示布爾可滿足性問題(Boolean Satisfiability Problem)，指是否存在一組變量賦值，用來解決給定的布爾方程式。NP是“非確定性的多項式復(fù)雜程度”(Non-deterministic Polynomial)問題。
　　該定理的含義：如果UNIQUE-SAT 存在一個多項式時間算法P(polynomial time algorithm)，那么NP=RP。這里的RP是隨機的多項式時間(randomized polynomial time)，給出問題的復(fù)雜性類。該定理屬于決定性問題，是第一個被證明的NP完備問題。這個特性是概率圖靈機(Probabilistic Turing machine)特有的性質(zhì)，它表明即使可滿足賦值數(shù)很小，SAT這個NP完備問題仍然是很難的問題。
　　萊斯利的第三個貢獻是在計算神經(jīng)學領(lǐng)域。1994年他在牛津大學出版社出版了《思維的電路》(Circuits of the Mind)一書，他為大腦設(shè)計了一個數(shù)學模型，并將它與復(fù)雜的認知功能建立了關(guān)聯(lián)。他在書中描述了一個稱為Neuroids的模型，支持廣泛的、多種多樣的、與記憶、學習、推理、搜索等相關(guān)的計算任務(wù)，不必使用更多資源就可以直接按神經(jīng)系統(tǒng)的方法完成這些任務(wù)。
　　此外，1979年他提出的上下文無關(guān)分析算法，至今仍是最快的算法之一。在并行與分布式計算領(lǐng)域，1990年他提出著名的BSP并行模型，至今仍是這一學科的基本文獻。
　　3 頒獎評語
　　ACM的頒獎詞高度評價了萊斯利?瓦里安特教授30年來對理論計算科學的基礎(chǔ)性工作。鑒于他“對眾多計算理論，包括PAC學習、枚舉復(fù)雜性、代數(shù)計算和并行與分布式計算所做的變革性的貢獻”而獲得2010年計算機科學最高榮譽圖靈獎。
　　他的工作開辟了新領(lǐng)域，給出了獨創(chuàng)的新概念，并提供了許多兼具原創(chuàng)性、深度和優(yōu)美的結(jié)果。他的工作一次又一次地確立或改變了計算科學的面貌。很少有人能像萊斯利那樣同時在廣度和深度上作出如此卓越的工作。他是理論計算機科學領(lǐng)域的真正英雄，他在解決某些懸而未決的科學問題上的勇氣和創(chuàng)造力是人們學習的楷模。圖1為頒獎晚會上的合影，左起為ACM CEO 約翰?懷特(John White)、Intel院士Shekar Borkar、谷歌副總裁Alfred Spector、圖靈獎得主萊斯利?瓦里安特、ACM總裁Alain Chesnais。
　　Intel院士、微處理器技術(shù)實驗室主任Shekar Borkar說：“瓦里安特教授在計算理論方面的研究使機器學習和人工智能發(fā)生了革命性的變化，使機器幾乎可以思維”，“他的研究方式堪與圖靈本人的媲美，從深邃洞察的基礎(chǔ)出發(fā)，建立新穎的公式表述。Intel非常高興支持這個獎項”。
　　谷歌研究與創(chuàng)新副總裁Alfred Spector說：“瓦里安特教授的獨特概念和亮麗研究具有不可思議的廣度，他在機器學習領(lǐng)域完成了創(chuàng)新的發(fā)明，這是一個快速成長的、有許多重要應(yīng)用的領(lǐng)域。我們?yōu)槌蔀锳CM圖靈獎的贊助者感到榮幸，這將激勵并辨別計算領(lǐng)域的巨大進步，給世界帶來美好的憧憬。”
　　4 光輝案例
　　眾所周知，1997年IBM的超級計算機“深藍”擊敗國際象棋大師卡斯帕羅夫，但是要讓計算機理解人類語言、像人類一樣思考就比下棋難多了。萊斯利的學習理論影響了IBM Watson的研制。IBM Watson系統(tǒng)是2006年開始設(shè)計的，它是由90臺IBM 750服務(wù)器組成的群集系統(tǒng)，每臺服務(wù)器采用8核芯片的Power 7處理器，每核有4個線程，因此相當于有2880個核在運行。內(nèi)存16TB。采用的軟件有SUSE Linux Enterprise Server 11操作系統(tǒng)、IBM DeepQA軟件、Apache UIMA (非結(jié)構(gòu)化信息管理體系結(jié)構(gòu))框架等。該系統(tǒng)使用了上百種以上的技術(shù)來分析自然語言、識別資源、尋找并產(chǎn)生假設(shè)、尋找證據(jù)并評分、對假設(shè)進行聚集和分級，因此它是專門設(shè)計的具有學習能力的機器。
　　這個以IBM創(chuàng)始人托馬斯?J?沃森的名字命名的系統(tǒng)，能儲存大量信息，相當于“100萬本書籍和2億頁資料”，還可以從經(jīng)驗中學習如何提高性能，并且使用自然語言回答問題。世界各地的研究人員歷時四年共同完成，其中我國科學家也為該項目做出了貢獻。該系統(tǒng)應(yīng)用前景廣泛，它可以高速分析大量數(shù)據(jù)，用來幫助政府部門解答公眾疑問，幫助醫(yī)生評估藥物療效等。圖2為2011年Jeopardy!競賽。
　　2011年2月14-16日，IBM Watson參加了美國智力競賽電視節(jié)目Jeopardy!(危險邊緣)，該競賽1964年創(chuàng)立，問題涉及地理、政治、歷史、體育、娛樂等。通過難度相當大的考試后才能獲得參賽資格。在兩個回合比賽中，IBM Watson與該節(jié)目史上最出色的選手肯?詹寧斯和布拉德?魯特爾戰(zhàn)成一平一勝。
　　5 研究興趣
　　關(guān)于萊斯利?瓦里安特最近的研究興趣，他談道：計算機科學包括對人工現(xiàn)象和自然現(xiàn)象的研究。前者關(guān)注人造設(shè)備比如計算機；后者涉及大自然中多步驟或者計算的過程，比如腦或者生物進化過程。在大多數(shù)領(lǐng)域，對這些人工或者自然過程的終極局限還沒有很好的理解。計算設(shè)備的潛力目前還遠遠沒有認識清楚，而神經(jīng)科學與演化中基礎(chǔ)性的定量問題也沒有得到解答。他的研究主要將關(guān)注這些基本問題。
　　在計算復(fù)雜性方面，他正在尋求全息(Holographic) 解決方法。在分布式計算方面，他正在研究如何為多核設(shè)備設(shè)計算法，而且能夠?qū)崿F(xiàn)在性能差異很大、不同的體系結(jié)構(gòu)之間保證很好的移植性和效率。在機器學習領(lǐng)域，他提出了健壯邏輯學(Robust logics)試圖彌合統(tǒng)計模型與推理模型之間的鴻溝。此外，他對大腦皮層如此脆弱的系統(tǒng)如何完成復(fù)雜而且大規(guī)模的計算發(fā)生了濃厚興趣，已經(jīng)提出了一些原語。他還在達爾文進化理論的量化研究方面做出了一些嘗試。
　　除圖靈獎外，萊斯利?瓦里安特1986年獲國際數(shù)學聯(lián)盟Nevanlinna獎，1997年獲Knuth獎，2008年獲歐洲理論計算科學協(xié)會EATCS獎。
　　(編輯：白杰)