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