| 從谷歌的“佩奇排名”到最新提出的“瀏覽排名”，中國科學院院士馬志明講述了數(shù)學為網(wǎng)絡(luò)建立新秩序的真實故事 5月16日上午，中國科學院數(shù)學與系統(tǒng)科學院公眾科學日院士論壇現(xiàn)場，中國數(shù)學會理事長、中國科學院院士馬志明發(fā)表了演講。 大屏幕上出現(xiàn)了谷歌的網(wǎng)頁，搜索框中的關(guān)鍵詞是：數(shù)學與系統(tǒng)科學院。在排列著含有這個關(guān)鍵詞的各種網(wǎng)頁中，中國科學院數(shù)學與系統(tǒng)科學研究院的網(wǎng)頁位居第一…… 在搜索框下，馬志明用紅筆圈了兩句話：一句是“約有1860000項符合……的查詢結(jié)果”，另一句是“搜索時間0.2秒”。然后他問聽眾：“我們每天都在上網(wǎng)，但什么是互聯(lián)網(wǎng)信息檢索呢？大家看，這里的關(guān)鍵詞是‘數(shù)學與系統(tǒng)科學院’，谷歌只用0.2秒就查出186萬多項相關(guān)網(wǎng)頁。我的問題是：如果將這186萬項信息平鋪在你面前，你會得到什么信息呢？” 短暫的停頓后，他自己回答：“你什么都得不到，但對這些網(wǎng)頁進行排序后，你知道了什么是最重要的或人們最感興趣的網(wǎng)頁。那么，計算機是如何在0.2秒的時間里就查出這些網(wǎng)頁并將它們按序列排出來，而且排得這么好呢？” 用這樣的開場白，馬志明牽出了自己的演講題目——數(shù)學在互聯(lián)網(wǎng)信息檢索中的應(yīng)用。 “希望能給大家講懂?！瘪R志明說。 在整個演講中，從谷歌的“佩奇排名”到最新提出的“瀏覽排名”概念，馬志明向聽眾講述了十多年間數(shù)學為網(wǎng)絡(luò)建立新秩序的真實故事。 數(shù)學博士生和計算機教授 世界上第一個網(wǎng)站是英國計算機專家蒂姆·伯納斯-李于1991年8月6日創(chuàng)立的，它解釋互聯(lián)網(wǎng)是什么，如何使用網(wǎng)頁瀏覽器和如何建立一個網(wǎng)頁服務(wù)器。 到1995年，網(wǎng)絡(luò)文件總數(shù)據(jù)估計已達1000萬張，但對互聯(lián)網(wǎng)上網(wǎng)頁的排名，人們幾乎沒有什么辦法?！爱敃r，也有一些搜索引擎公司希望為用戶服務(wù)，輸入關(guān)鍵詞后，就會有相關(guān)網(wǎng)頁排出來。但是，人們的做法是將頁面讀懂，再根據(jù)頁面內(nèi)容來決定它的重要性和排序。”馬志明說。 “但大家想想，這么多的頁面，怎么能在很短的時間內(nèi)讀出來呢？而且，頁面的內(nèi)容重要還是不重要，也是見仁見智的事，沒有統(tǒng)一標準。所以在那段時期，這個問題很混亂，不知道該怎么辦，直至1998‘鏈接分析法’的出現(xiàn)。其中，最著名的算法就是佩奇排名和HITS算法，才革命性地改變了網(wǎng)絡(luò)世界?！?br> 實際上，網(wǎng)絡(luò)研究的學術(shù)革命開始于1995年。這一年春天，在斯坦福大學校園，計算機科學院的新博士生拉里·佩奇遇見了博士二年級的謝爾蓋·布林。 佩奇大學畢業(yè)于密歇根大學安娜堡分校，他的父親是密歇根州立大學的計算機專業(yè)教授。 佩奇從父親那里了解到，博士論文可以成為一個人學術(shù)生涯的基礎(chǔ)。在斯坦福大學的第一年，他選擇用戶界面研究先驅(qū)特里·威諾格做他的導師，開始尋找一個有研究價值的博士論文題目。 最初，佩奇只是因網(wǎng)絡(luò)的數(shù)學特征而對網(wǎng)絡(luò)產(chǎn)生了興趣。他發(fā)現(xiàn)每臺計算機都是一個節(jié)點，網(wǎng)頁上的每一條鏈接就是這些節(jié)點間的聯(lián)系，這樣就構(gòu)成了一個經(jīng)典的圖結(jié)構(gòu)?！坝嬎銠C科學家最喜歡圖”，他認為互聯(lián)網(wǎng)很可能是有史以來人類創(chuàng)造出的最大的圖，這張圖的節(jié)點中隱藏著很多啟示，他決定探索互聯(lián)網(wǎng)中的數(shù)學特征。而導師威諾格鼓勵他這樣做。 佩奇后來回憶說：“這是我得到的最好的建議。” 佩奇開始思索網(wǎng)絡(luò)中鏈接結(jié)構(gòu)的奧妙，他發(fā)現(xiàn)盡管跟著鏈接可以從一張網(wǎng)頁轉(zhuǎn)到另一張網(wǎng)頁，但沿著這些鏈接往回走就不行了。他想找到一種方法，可以讓各個網(wǎng)頁能輕松找出并說明指向它們的鏈接。 美國文獻引用分析之父加菲爾德的學術(shù)思想給了他啟發(fā)。 加菲爾德認為，發(fā)表論文是研究人員最重要的工作之一，基本上每篇論文的結(jié)論都建立在謹慎構(gòu)建的引文基礎(chǔ)上，而每篇新論文也可能成為新的文獻被他人引用，因此，文獻的引用和被引用體現(xiàn)了學術(shù)發(fā)展的邏輯性結(jié)構(gòu)；一篇論文的重要性可以根據(jù)有多少篇論文通過引用而同它建立聯(lián)系來確定，這個體系為已出版的論文提供了一種等級評定的方法。 正是基于這種引用和被引用的思想，蒂姆·伯納斯-李在計算機上通過技術(shù)和超文本鏈接發(fā)明了萬維網(wǎng)。佩奇則發(fā)現(xiàn)，鏈接就是萬維網(wǎng)上的引用和被引用，整個網(wǎng)絡(luò)就是由引用和注評構(gòu)成的松散體系，而早期的網(wǎng)絡(luò)超鏈接文本有一個缺陷：不能反向追蹤鏈接。佩奇想，如果能找到一種方法來計算反向鏈接的數(shù)量并衡量它的質(zhì)量，那么，“網(wǎng)絡(luò)就會成為一個更有價值的地方”。 佩奇將自己的研究項目命名為“反向鏈接”（BackRub），這個項目的宗旨是追蹤并發(fā)現(xiàn)網(wǎng)絡(luò)中的鏈接，存儲它們并進行分析，然后在網(wǎng)絡(luò)上重新發(fā)布它們。佩奇估計，當時網(wǎng)絡(luò)文件的數(shù)量大約為10000萬張，而它們的鏈接數(shù)量則可能達1億。這個項目的復雜性和規(guī)模吸引了還在確定論文選題的布林，于是他加入這個項目，從此，兩人開始合作。 在完成網(wǎng)絡(luò)搜索并存儲了鏈接圖之后，還需要找到評定等級的方法。這時，佩奇發(fā)現(xiàn)，對所有指向某網(wǎng)頁的鏈接數(shù)量的計算對于確定該網(wǎng)頁的等級具有指導意義，這種方法帶來了新的挑戰(zhàn)——困難而復雜的遞歸性數(shù)學運算。布林的數(shù)學天賦提供了幫助。他們發(fā)明了一種新算法，基于重要的來源鏈接來評價網(wǎng)頁的重要性，這種算法以佩奇的姓（Page）命名，因此叫佩奇排名（PageRank）。 當佩奇和布林在斯坦福的校園埋頭研究網(wǎng)頁排名的算法時，在IBM位于圣何塞市的阿爾馬登研究中心，來自康奈爾大學的計算機教授喬恩·克萊因伯格正在這里做訪問科學家，他也在研究網(wǎng)絡(luò)評級方法，他提出了中心網(wǎng)頁和權(quán)威網(wǎng)頁的評級系統(tǒng)，并完成了創(chuàng)造性著作《權(quán)威性來源》的草稿。 1998年革命性的論文 一本記錄谷歌公司成長的書《搜》中，作者約翰·巴利特說，“PageRank促成谷歌建立神秘技術(shù)配方……盡管當時佩奇和布林還不知道，但他們早期的評級系統(tǒng)為一個全新網(wǎng)絡(luò)生態(tài)環(huán)境的形成開辟了道路?！?br> 在佩奇和布林發(fā)明了PageRank算法后，他們編寫了一個PageRank搜索工具，然后用PageRank來為結(jié)果的相關(guān)性排序。他們發(fā)現(xiàn)，網(wǎng)絡(luò)越大，鏈接越多，這個引擎提供的結(jié)果就越準確，于是，他們將新引擎命名為Google，這是Googol的變體，Googol是一個數(shù)字名詞，表示10的100次方。1996年8月，他們在斯坦福的網(wǎng)站上發(fā)布了第一個Google版本。 1997年夏天，克萊因伯格在斯坦福會見了佩奇，交換了關(guān)于搜索的觀點和各自的工作，克萊因伯格鼓勵佩奇發(fā)表一篇關(guān)于PageRank的論文，但佩奇“擔心有人竊取他的思想”，因此對發(fā)表論文的態(tài)度很謹慎。最后，學術(shù)名聲戰(zhàn)勝了產(chǎn)權(quán)保護的沖擊，雙方同意在彼此的論文中相互引用。 克萊因伯格的論文《超鏈接環(huán)境下權(quán)威來源》發(fā)表在1998年出版的《第九屆ACM-SIAM離散算法會刊》上。他在這篇文章中提出的中心網(wǎng)頁和權(quán)威網(wǎng)頁的評價系統(tǒng)，被巴利特評價為“最著名的網(wǎng)絡(luò)評級方式”。巴利特說，“在學術(shù)性網(wǎng)絡(luò)研究這個自成一體的世界里，這篇文章的影響僅次于佩奇和布林介紹谷歌的論文?！?br> 1998年初，佩奇將他的第一篇論文，也就是對PageRank算法的總結(jié)介紹，提交給美國計算機學會（ACM）信息提取特別興趣組，但論文被拒絕了。一位評審專家的意見是：“論文的整體結(jié)構(gòu)缺乏連貫性……文章應(yīng)側(cè)重于信息的提取而不是網(wǎng)絡(luò)分析?！迸迤鎴猿滞陡澹詈?，這篇論文作為斯坦福大學數(shù)字圖書館項目的一部分被發(fā)表了。 不久后，佩奇和布林聯(lián)合發(fā)表了一篇關(guān)于谷歌的論文——《大規(guī)模超文本網(wǎng)絡(luò)搜索引擎剖析》，如今，這篇論文已經(jīng)成為目前世界上被引用最廣泛的搜索類文獻。 1998年底，佩奇和布林決定要開辦一家公司，當?shù)谝晃煌顿Y人準備為他們開支票時，兩人還沒有想好公司的名字，這位投資人建議他們就用這項搜索服務(wù)的名字Google，兩人同意了。幾分鐘后，他們得到了一張10萬美元的支票。 2001年9月，PageRank被授予美國專利，專利被正式頒發(fā)給斯坦福大學，佩奇作為發(fā)明人列于文件中；2006年，國際數(shù)學聯(lián)盟將“奈望林納獎”授予克萊因伯格，以表彰他在計算機科學的數(shù)學方面的杰出貢獻。 馬志明說，1998年后，信息檢索領(lǐng)域出現(xiàn)了“鏈接分析法”，PageRank和HITS是其中最著名的算法，實際上，這兩個算法就是用數(shù)學原理在對網(wǎng)頁進行排序。他說：“一個看似很困難的實際問題，用一個巧妙的數(shù)學方法就解決了，所以，數(shù)學的用處有時真是不可估量?！?br> 讓用戶為頁面重要性投票 馬志明指出了PageRank在網(wǎng)頁排序中的局限性。 “從1998年到現(xiàn)在，PageRank經(jīng)過11年運轉(zhuǎn)，取得了巨大成功，同時它的缺點也暴露出來了。因為它對網(wǎng)頁的排序是靜態(tài)的，只考慮頁面在整個互聯(lián)網(wǎng)中的拓撲結(jié)構(gòu)，所以，有人可以作弊，通過多做一些超級鏈接來顯示頁面的重要性，因此有這樣的公司，自己搞個服務(wù)器，讓許多頁面互相鏈接，如果對方給錢，公司就將你的頁面鏈接上去，從而惡意提高頁面排序。誰能控制超級鏈，誰就能控制頁面的重要性。但這不符合實際情況?！?br> “實際情況是，我們在上網(wǎng)時會有自己的感情，當我們觀察一個頁面時，如果這個頁面重要，我們會靜下心來仔細閱讀它；如果這個頁面不重要，我們很快就會離開它，所以，用戶才是判斷頁面重要性真正的標準。但用戶的感情、上網(wǎng)時間因素在PageRank中是沒有的，這是它的缺點，許多搜索引擎公司也都在想辦法克服這個缺點?！?br> 2008年7月，在新加坡召開的第31屆國際信息檢索大會上，一位年輕人報告了他們的論文——《瀏覽排序：讓因特網(wǎng)用戶為頁面重要性投票》，論文獲得了會議設(shè)立的唯一最佳學生論文獎。 這位年輕人就是馬志明的博士生劉玉婷，那時她正在微軟亞洲研究院做實習生。 論文的基本思想是，利用大量用戶訪問網(wǎng)頁的信息來估計網(wǎng)頁的重要性。每個搜索引擎公司都有大量的不含隱私的用戶上網(wǎng)記錄?！安煌娜藢τ谟脩羯暇W(wǎng)記錄有不同的解讀”，馬志明說。 據(jù)馬志明介紹，他本人是研究隨機過程的，他從用戶上網(wǎng)記錄中看到了一個真實的過程。這個過程是一個隨機過程，可以稱為瀏覽過程（Browsing Process）。這個過程在不同的網(wǎng)頁之間跳來跳去，從數(shù)學上可以將其歸類為跳過程，或者隨機點過程（把網(wǎng)頁看作點）。數(shù)學家對于隨機點過程有許多研究，已經(jīng)有豐富的研究成果。 馬志明分析：當用戶瀏覽一個網(wǎng)頁時，他下一步跳轉(zhuǎn)到哪一個網(wǎng)頁，停留多長時間跳轉(zhuǎn)，大概只依賴于當前的狀態(tài)，而與他瀏覽網(wǎng)頁的過去歷史無關(guān)。因此從數(shù)學上，這應(yīng)該是一個馬氏過程（給定現(xiàn)在，將來與過去無關(guān)）。 再有，用戶在一個網(wǎng)頁的停留時間，以及他下一步跳轉(zhuǎn)到哪一個網(wǎng)頁，都只與他正在瀏覽的網(wǎng)頁內(nèi)容以及網(wǎng)頁的超級鏈接有關(guān)，大概與他在什么時間點（8點或9點，上午或下午）瀏覽此網(wǎng)頁無關(guān)。因此，這個馬氏過程應(yīng)該是時間可推移的，或者說是時間齊次的。再加上瀏覽過程的狀態(tài)是有限的（網(wǎng)頁的總數(shù)是有限），因此，瀏覽過程很可能是一個有限狀態(tài)時間齊次馬氏過程，即Q過程。 對于中國的概率學家而言，Q過程是一個熟悉的數(shù)學對象，中國學者在這個方向有世界領(lǐng)先的研究成果。當然，實踐是檢驗真理的唯一標準，瀏覽過程是否時間齊次馬氏過程，還需要用實際數(shù)據(jù)作統(tǒng)計檢驗。一個可行的檢驗方法，是驗證用戶在網(wǎng)頁上的停留時間是否服從負指數(shù)分布。因為根據(jù)數(shù)學理論，Q過程在每個狀態(tài)的停留時間必然服從負指數(shù)分布。 由劉玉婷設(shè)計算法，微軟亞洲研究院的相關(guān)研究組用真實數(shù)據(jù)作了大量實驗模擬，發(fā)現(xiàn)用戶在網(wǎng)頁的停留時間基本服從負指數(shù)分布。通過反復論證，確信隨機過程中的Q過程理論可以很好地對這個問題進行建模。Q過程的平穩(wěn)分布，也就是在時間趨于無窮時的極限分布，在理論上正好是用戶在某頁面平均停留時間與再次回訪此頁面平均間隔時間之比。網(wǎng)頁越重要，平均停留時間就越長，該網(wǎng)頁的平穩(wěn)分布值就越大；網(wǎng)頁越重要，再次回訪此網(wǎng)頁的平均間隔時間就越短，該網(wǎng)頁的平穩(wěn)分布值就越大。因此，瀏覽過程的平穩(wěn)分布可以作為衡量網(wǎng)頁重要性的指標。這個瀏覽過程的平穩(wěn)分布，就是我們所說的瀏覽排序（Browse Rank）。 當然，要設(shè)計一套可行的算法真正計算出瀏覽排序，并非易事。微軟亞洲研究院的相關(guān)課題組克服了重重困難，每一步都在課題組內(nèi)反復論證，深入探討，反復模擬實驗。這里含有許多奇思構(gòu)想和巧妙的數(shù)學。微軟亞洲研究院從產(chǎn)品部門調(diào)來大量數(shù)據(jù)，做了大規(guī)模模擬實驗。 據(jù)馬志明介紹，在新加坡獲獎的這篇論文，從第一版寫出來以后，在微軟的課題組內(nèi)反復修改了81次才成為最終稿。 新加坡會議后，“瀏覽排序”成了業(yè)內(nèi)熱門話題，在互聯(lián)網(wǎng)搜索工業(yè)界引起廣泛關(guān)注和討論。 馬志明強調(diào)，“作為一個數(shù)學工作者，我認為Browsing Process（瀏覽過程）的重要性應(yīng)該不亞于Browse Rank。這是第一個刻畫真實的用戶上網(wǎng)行為的數(shù)學框架。我相信今后人們在研究用戶上網(wǎng)行為時，一定會想到Browsing Process，應(yīng)用并發(fā)展Browsing Process的理論和實踐。在這一方向還有許多課題需要進一步研究?！?br> 最后，馬志明希望學生們能把這個網(wǎng)頁排序的故事講給自己的親朋好友，讓他們知道“數(shù)學非常好用”。 |
