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