哈佛大學教授獲2010年圖靈獎

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