數(shù)學(xué)科普資料：谷歌如何從網(wǎng)絡(luò)的大海里撈到針

1、谷歌如何從網(wǎng)絡(luò)的大海里撈到針david austin關(guān)鍵詞： 谷歌，搜索，隨機(jī)矩陣，特征值想象一個含有250億份文件，卻沒有集屮管理機(jī)構(gòu)和館員的圖書館，而11任何人都可 以在任何時間添加新的文件而不需要通知其他人。一方面你可以確定，這龐大的文件 堆中有一份文件含有對你至關(guān)重要的信息，而另一方面，你又像我們中的大多數(shù)人那 樣沒有耐心，想要在幾秒鐘之內(nèi)就找到這條信息。你有什么辦法呢？擺在你面前的這個難題看起來似乎無法解決。而這個文件堆跟萬維網(wǎng)(world wide web)其實相差無幾，后者就是一個超大的、高度混亂的以各種形式存放的文件堆。當(dāng)然，從萬維網(wǎng)中找信息我們有辦法解決，因為我們對搜索引擎非

2、常熟悉(或許你就 是通過搜索找到這篇文章的)。本文將介紹谷歌的網(wǎng)頁排序算法(pagerank algorithm),以及它如何從250億份網(wǎng)頁中撈到與你的搜索條件匹配的結(jié)果。它的 匹配效果如此之好，以至于“谷歌”(google )今天己經(jīng)成為一個被廣泛使用的動詞 了。包括谷歌在內(nèi)，多數(shù)搜索引擎都是不斷地運行計算機(jī)程序群，來檢索網(wǎng)絡(luò)上的網(wǎng)頁、 搜索每份文件中的詞語并r將相關(guān)信息以高效的形式進(jìn)行存儲。每當(dāng)用戶檢索一個短 語，例如“搜索引擎”，搜索引擎就將找出所有含有被檢索短語的網(wǎng)頁。(或許，類 似“搜索”與“引擎”之間的距離這樣的額外信息都被會考慮在內(nèi)。)但問題是，谷 歌現(xiàn)在需要檢索250億個頁面

3、，而這些頁面上大約95%的文本僅由大約一萬個單詞組 成。也就是說，對于大多數(shù)搜索而言，將會有超級多的網(wǎng)頁含有搜索短語中的單詞。我們所需要的其實是這樣一種辦法，它能夠?qū)⑦@些符合搜索條件的網(wǎng)頁按照重要程度 進(jìn)行排序，這樣才能夠?qū)⒆钪匾捻撁媾旁谧钌厦?。確定網(wǎng)頁重要性的一個方法是使用人為排序。例如，你或許見過這樣一些網(wǎng)頁，他們 包含了大量的鏈接，后者連接到某個特定興趣領(lǐng)域的其他資源。假定維護(hù)這個網(wǎng)頁的 人是可靠的，那么他推薦的網(wǎng)頁在很大程度上就可能有用。當(dāng)然，這種做法也有其局 限性，比如這個列表可能很快就過期了，也可能維護(hù)這個列表的人會無意或因某種未 知的偏見而遺漏掉一些重要的網(wǎng)頁。谷歌的網(wǎng)頁排序算

4、法則不借助人為的內(nèi)容評估來確定網(wǎng)頁的重要性。事實上，谷歌發(fā) 現(xiàn)，它的服務(wù)的價值很大程度上是它能夠提供給用戶無偏見的搜索結(jié)果。谷歌聲稱，“我們軟件的核心就是網(wǎng)頁排序(pagerank)?！闭缥覀儗⒁吹降?技巧就是 讓網(wǎng)頁自身按照重要性進(jìn)行排序。如何辨別誰重要如果你曾建立過一個網(wǎng)頁，你應(yīng)該會列入一些你感興趣的鏈接，它們很容易使你點擊 到其它含有重要、可靠信息的網(wǎng)頁。這樣就相當(dāng)于你肯定了你所鏈接頁面的重要性。 谷歌的網(wǎng)頁排序算法每月在所有網(wǎng)頁中進(jìn)行一次受歡迎程度的評估，以確定哪些網(wǎng)頁 最重要。網(wǎng)頁排序算法的提出者，謝爾蓋布林(sergey brin)和拉里佩奇(lawrence page)的基本

5、想法是：一個網(wǎng)頁的重要性是由鏈接到它的其他網(wǎng)頁的數(shù)量及其重要性 來決定。我們對任意一個網(wǎng)頁p 以/(p)來表述其重要性，并稱之為網(wǎng)頁的網(wǎng)頁排序。在很多 網(wǎng)站，你可以找到一個近似的網(wǎng)頁排序值。(例如，美國數(shù)學(xué)會的首頁目前的網(wǎng)頁排 序值為8,最高分是10。你可以試試找到一個網(wǎng)頁排序值為10的網(wǎng)頁嗎？)這個網(wǎng) 頁排序值僅是一個近似值，因為谷歌拒絕提供真實的網(wǎng)頁排序值，以阻止那些試圖干 擾排序的行為。網(wǎng)頁排序是這樣確定的。假定網(wǎng)頁厲有"個鏈接。如果這些鏈接中的一個鏈接到網(wǎng)頁 pi,那么網(wǎng)頁巴將會將其重要性的1/"賦給網(wǎng)頁p的重要性就是所有指向這個網(wǎng) 頁的其他網(wǎng)頁所貢獻(xiàn)的重要性的加和

6、。換言之，如果我們記鏈接到網(wǎng)頁p的網(wǎng)頁集合 為bi,那么kp滬遲 pjwbii(pj)lj.這或許讓你想起“先有雞還是先有蛋”的問題：為了確定一個網(wǎng)頁的重要性，我們首 先得知道所有指向它的其他網(wǎng)頁的重耍性。然而，我們可將這個問題改寫為一個更數(shù) 學(xué)化的問題。首先建立一個矩陣，稱為超鏈矩陣(hyperlink matrix) , h=h“,其屮第，行第j 列的元素為hi尸口 口0如果pjwbi上述條件不成立.注意到h有一些特殊的性質(zhì)。首先，它所有的元都是非負(fù)的。其次，除非對應(yīng)這一列 的網(wǎng)頁沒有任何鏈接，它的每一列的和為1。所有元均非負(fù)且列和為1的矩陣稱為隨 機(jī)矩陣，隨機(jī)矩陣將在下述內(nèi)容中起到重要作

7、用。我們還需要定義向量i=li(pi)v它的元素為所有網(wǎng)頁的網(wǎng)頁排序重要性的排序值。 前面定義的網(wǎng)頁排序可以表述為z=h7.換言之，向量/是矩陣h對應(yīng)特征值1的特征向量。我們也稱之為矩陣h的平穩(wěn)向量 (stationary vector)。讓我們來看一個例子。下圖所示為一個網(wǎng)頁集合(8個)，箭頭表示鏈接。0000001/31/2101/211/30001/2000000h =0100000001/211/3001/30001/311/3r0000001/30000001/311/3其相應(yīng)的矩陣為0 0.0600 '00.067500.03000其平穩(wěn)向量為/=0.067500.0975

8、/20.2025/20.180000.2950 這說明網(wǎng)頁8的受歡迎程度最高。下圖是陰影化的圖，其中網(wǎng)頁排序值越高的網(wǎng)頁陰 影越淺。計算平穩(wěn)向量i有很多方法可以找到一個方陣的特征向量。然而，我們面對的是一個特殊的挑戰(zhàn)，因 為矩陣h是一個這樣的方陣，它的每一列都對應(yīng)谷歌檢索到的一個網(wǎng)頁。也就是說， h大約有n二250億行和列。不過其中大多數(shù)的元都是0；事實上，研究表明每個網(wǎng)頁 平均約有10個鏈接，換言之，平均而言，每一列中除了 10個元外全是0。我們將選 擇被稱為幕法(power method)的方法來找到矩陣h的平穩(wěn)向量/。幕法如何實現(xiàn)呢？首先選擇/的備選向量/0,進(jìn)而按下式產(chǎn)生向量序列以ik

9、-wik 1,2,這個方法是建立在如下的一般原理上:一般原理：序列*將收斂到平穩(wěn)向量人我們首先用個例子驗證上面的結(jié)論。/0/i72/3z4 /60/6110000.0278 0.060.0606670.0833 0.06750.067500.5000 0.030.0300667 0.06750.0675000.250.16670.1111 0.09750.09750000.250.1806 0.20250.20250000.08330.0972 0.180.180000.08330.3333 0.2950.295一個自然的問題是，這些數(shù)字有什么含義。當(dāng)然

10、，關(guān)于一個網(wǎng)頁的重要性，可能沒有 絕對的度量，而僅有比較兩個網(wǎng)頁的重要性的比例度量，如“網(wǎng)頁a的重要性是網(wǎng)頁 b的兩倍?！被谶@一原因，我們可以用一個固定量去同乘以所有的重要性排序值， 這并不會影響我們能獲得的信息。這樣，我們總是假定所有受歡迎程度值(popularity)的和為1,原因稍后解釋。三個重要的問題自然而然產(chǎn)生的三個問題是:序列*總是收斂嗎？(即運算多次后，以和加1幾乎是一樣的)收斂后的平穩(wěn)向量是否和初始向量/o的選取沒有關(guān)系？重要性排序值是否包含了我們想要的信息？對冃前的方法而言，上述三個的答案都是否定的！下面，我們將看看如何改進(jìn)我們的 方法，使得改進(jìn)后的算法滿足上述三個要求。先

11、看個非常簡單的例子?？紤]如下包含兩個網(wǎng)頁的小網(wǎng)絡(luò)，其中一個鏈接到另一個:其矩陣為h =下例展示了算法的運行過程:/0172h=i10000100在這個例子中，兩個網(wǎng)頁的重要性排序值均為0,這樣我們無法獲知兩個網(wǎng)頁之間的 相對重要性信息。問題在于網(wǎng)頁尸2沒有任何鏈接。因此，在每個迭代步驟中，它從 網(wǎng)頁p獲取了一些重要性，但卻沒有賦給其他任何網(wǎng)頁。這樣將耗盡網(wǎng)絡(luò)中的所有 重要性。沒有任何鏈接的網(wǎng)頁稱為懸掛點(dangling nodos)，顯然在我們要研究的 實際網(wǎng)絡(luò)中存在很多這樣的點。稍后我們將看到如何處理這樣的點，在此之前我們先 考慮一種新的理解矩陣h和平穩(wěn)向量/的思路。h的概率化解釋想象我們

12、隨機(jī)地在網(wǎng)上跳轉(zhuǎn)網(wǎng)頁；也就是說，當(dāng)我們訪問一個網(wǎng)頁時，一秒鐘后我們 隨機(jī)地選擇當(dāng)前網(wǎng)頁的一個鏈接到達(dá)另一個網(wǎng)頁。例如，我們正訪問含有”個鏈接的 網(wǎng)頁p/,其屮一個鏈接引導(dǎo)我們訪問了網(wǎng)頁pi,那么下一步轉(zhuǎn)到網(wǎng)頁p,的概率就是 1/6。由于跳轉(zhuǎn)網(wǎng)頁是隨機(jī)的，我們用乃表示停留在網(wǎng)頁巴上的時間。那么我們從網(wǎng)頁乃 轉(zhuǎn)到網(wǎng)頁r的時間為乃/“。如果我們轉(zhuǎn)到了網(wǎng)頁那么我們必然是從一個指向它的 網(wǎng)頁而來。這意味著ti=pj&bitjlj其中求和是對所有鏈接到b的網(wǎng)頁b進(jìn)行的。注意到這個方程與定義網(wǎng)頁排序值的 方程相同，因此i(pi)=tio那么一個網(wǎng)頁的網(wǎng)頁排序值可以解釋為隨機(jī)跳轉(zhuǎn)時花在這個 網(wǎng)頁上的時

13、間。如果你曾經(jīng)上網(wǎng)瀏覽過某個你不熟悉的話題的相關(guān)信息時，你會有這 種感覺：按照鏈接跳轉(zhuǎn)網(wǎng)頁，過一會你會發(fā)現(xiàn)，相較于其他網(wǎng)頁，你會更頻繁地回到 某一部分網(wǎng)頁。正如諺語所說“條條大路通羅馬，”這部分網(wǎng)頁顯然是更重要的網(wǎng)頁。 基于這個解釋，很自然地可以要求網(wǎng)頁排序向量/的所有元之和為1。當(dāng)然，這種表述屮還存在一個問題：如果我們隨機(jī)地跳轉(zhuǎn)網(wǎng)頁，在某種程度上，我們 肯定會被困在某個懸掛點上，這個網(wǎng)頁沒有給出任何鏈接。為了能夠繼續(xù)進(jìn)行，我們 需要隨機(jī)地選取下一個網(wǎng)頁；也就是說，我們假定懸掛點可以鏈接到其他任何一個網(wǎng) 頁。這個效果相當(dāng)于將超鏈矩陣h做如下修止：將其屮所有元都為0的列替換為所有 元均為1/n的

14、列，前者就對應(yīng)于網(wǎng)頁中的懸掛點。這樣修正后懸掛點就不存在了。我 們稱修正后的新矩陣為so我們之前的例子，現(xiàn)在就變成了對應(yīng)矩陣s=1/21/2i及特征向量換言之，網(wǎng)頁p2的重要性是網(wǎng)頁p的兩倍，符合你的直觀認(rèn)知了。矩陣s有一個很好的性質(zhì)，即其所有元均非負(fù)且每列的和均為1。換言之，s為隨機(jī) 矩陣。隨機(jī)矩陣具有一些很有用的性質(zhì)。例如，隨機(jī)矩陣總是存在平穩(wěn)向量。為了稍后的應(yīng)用，我們要注意到s是由h通過一個簡單的修正得到。定義矩陣a如下： 對應(yīng)于懸掛點的列的每個元均為1/n,其余各元均為0。則s=h+a。幕法如何實現(xiàn)？一般而言，珮法是尋找矩陣對應(yīng)于絕對值最大的特征值的特征向量。就我們而言，我 們要尋找矩

15、陣s對應(yīng)于特征值1的特征向量。首先要說到的是最好的情形。在這種情 形下，其他特征值的絕對值都小于1；也就是說，矩陣s的其它特征值都滿足|a|<k 我們假定矩陣s的特征值為力ii1=ai>|a2|>|a3|>->|a,；|,對矩陣s,假設(shè)對應(yīng)于特征值力的特征向量存在一個基向量刃。這一假設(shè)在一般情況 下并不一定要成立，但如果成立可以幫助我們更容易地理解幕法如何實現(xiàn)。將初始向 量a）寫成如下形式/o=cl vl+c2v2+-+cnvn.那么/1=s/o=c1 vi 4-c,2a2v2+-+c?7x/?v/?,/2=s/1=c1 v1+c2x22v24- +cwa2hv/

16、7, ik=sik=c vhc2xk2v2+ "+cidknvn.當(dāng).左2時，因為所有特征值的絕對值小于1,因此這是akj->oo從而 s'八,后者是 對應(yīng)于特征值1的一個特征向量。需要指出的是，“t/的速度由悶確定。當(dāng)悶比較接近于0時，那么加to會相當(dāng)快。 例如，考慮下述矩陣s=o.65o.35o.35o,65這個矩陣的特征值為久1=1及久2=0.3。下圖左可以看出用紅色標(biāo)記的向量收斂到用綠 色標(biāo)記的平穩(wěn)向量io0.50.5再考慮矩陣s=0.85其特征值為久1=1及久2=0.7。從上圖右可以看出，本例中向量“收斂到平穩(wěn)向量/的速度要慢很多，因為

17、它的第二個特征值較大。不順之時在上述討論屮，我們假定矩陣s需要滿足久1=1且|；2|<lo然而，我們可能會發(fā)現(xiàn)，這 一點并不總成立。假定網(wǎng)絡(luò)關(guān)系如下：在這種情形下，矩陣s為s=j 0100000100000100000110000 那么我們可以得到7o172100010001000000/3/415001000000100010在這種情況下，向量序列"不再收斂。這是為什么？注意到矩陣s的第二個特征值滿 足i久2|=1,因此前述幕法的前提不再成立。為了保證|a2|<1,我們需要矩陣s為本原(primitive)矩陣。這意味著，對某個m, s加的所有元均為正。換言之，若給定兩

18、個網(wǎng)頁，那么從第一個網(wǎng)頁經(jīng)過m個鏈接后可以到達(dá)笫二個網(wǎng)頁。顯然，上述最后的這個例子并不滿足這個條件。稍后，我們將看 到如何修止矩陣s以獲得一個本原隨機(jī)矩陣，從而滿足|a2|<1o下面說明我們的方法行不通的另一個例子?？紤]如下圖所示的網(wǎng)絡(luò)在此例中，矩陣s為000000001/201/2.1/300001/20000000s =01000000001/21/3001 / 2l00001z 311/3001/200001/3001/2100001/311. 20對應(yīng)平穩(wěn)向量 1 =注意到前四個網(wǎng)頁的網(wǎng)頁排序值均為0。這使我們感覺不太對：每個頁面都有其它網(wǎng) 頁鏈接到它，顯然總有人喜歡這些網(wǎng)頁！

19、一般來說，我們希望所有網(wǎng)頁的重要性排序 值均為正。這個例子的問題在于，它包含了一個小網(wǎng)絡(luò)，即下圖中藍(lán)色方框部分。在這個方框中，有鏈接進(jìn)入到藍(lán)色方框，但沒有鏈接轉(zhuǎn)到外部。正如前述中關(guān)于懸掛 點的例子一樣，這些網(wǎng)頁構(gòu)成了一個“重要性水槽”，其他四個網(wǎng)頁的重要性都被“排” 到這個“水槽”中。這種情形發(fā)生在矩陣s為可約(reducible)時；也即，s可以寫 成如下的塊形式s=*0*實際上，我們可以證明：如果矩陣s不可約，則一定存在一個所有元均為正的平穩(wěn)向 量。對一個網(wǎng)絡(luò)，如果任意給定兩個網(wǎng)頁，一定存在一條山鏈接構(gòu)成的路使得我們可以從 第一個網(wǎng)頁轉(zhuǎn)到第二個網(wǎng)頁，那么稱這個網(wǎng)絡(luò)是強(qiáng)連通的(strongl

20、y connected)。 顯然，上面最后的這個例子不是強(qiáng)連通的。而強(qiáng)連通的網(wǎng)絡(luò)對應(yīng)的矩陣s是不可約的。 簡言之，矩陣s是隨機(jī)矩陣，即意味著它有一個平穩(wěn)向量。然而，我們同時還需要s 滿足(a)本原，從而|22|<1； (b)不可約，從而平穩(wěn)向量的所有元均為正。后一個修正為得到一個本原且不可約的矩陣，我們將修正隨機(jī)跳轉(zhuǎn)網(wǎng)頁的方式。就日前來看，我 們的隨機(jī)跳轉(zhuǎn)模式由矩陣s確定：或者是從當(dāng)前網(wǎng)頁上的鏈接中選擇一個，或者是對 沒有任何鏈接的網(wǎng)頁，隨機(jī)地選取其他網(wǎng)頁中的任意一個。為了做出修正，首先選擇 一個介于0到1之間的參數(shù)弘 然后假定隨機(jī)跳轉(zhuǎn)的方式略作變動。具體是，遵循矩 陣s的方式跳轉(zhuǎn)的概率

21、為a,而隨機(jī)地選擇下一個頁面的概率是l-«o若記所有元均為1的矩陣為j,那么我們就可以得到谷歌矩陣(google matrix)：g=as+( 1-«) 1j注意到g為隨機(jī)矩陣，因為它是隨機(jī)矩陣的組合。進(jìn)而，矩陣g的所有元均為正， 因此g為本原r不可約。從而，g存在唯一的平穩(wěn)向量i,后者可以通過幕法獲得。 參數(shù)a的作用是一個重要因素。若。=1，則g=so這意味著我們面對的是原始的網(wǎng)絡(luò) 超鏈結(jié)構(gòu)。然而，若0,則g=l/nj0也即我們面對的是一個任意兩個網(wǎng)頁z間都有 連接的網(wǎng)絡(luò)，它已經(jīng)喪失了原始的網(wǎng)絡(luò)超鏈結(jié)構(gòu)。顯然，我們將會把g的值取得接近 于1,從而保證網(wǎng)絡(luò)的超鏈結(jié)構(gòu)在計算中

22、的權(quán)重更大。然而，還有另外一個問題。請記住，幕法的收斂速度是山第二個特征值的幅值|勿決定 的。而對谷歌矩陣，已經(jīng)證明了第二個特征值的幅值為|壯|=弘這意味著當(dāng)a接近于1 吋，幕法的收斂速度將會很慢。作為這個矛盾的折中方案，網(wǎng)頁排序算法的提出者謝 爾蓋布林和拉里佩奇選擇0=0.85。計算排序向量i到目前為止，我們所討論的看起來是一個很棒的理論，然而要知道，我們需要將這個方法應(yīng)用到一個維數(shù)n約為250億的矩陣！事實上，幕法特別適用于這種情形。回想隨機(jī)矩陣s可以寫成下述形式s=h+a.從而谷歌矩陣有如下形式g=gh+ga+ 1 -an其屮j是元素全為1的矩陣，從而g1 -anjik.現(xiàn)在注意到，矩陣

23、h的絕大部分元都是0；平均而言，一列中只有10個元是非零數(shù)。 從而，求ha的每個元時，只需要知道10個項即可。而且，和矩陣j 一樣，矩陣a的 行元素都是相同的。從而，求aa與j%相當(dāng)于添加懸掛點或者所有網(wǎng)頁的當(dāng)前重要性 排序值。而這只需要一次即可完成。當(dāng)a取值接近于0.85,布林和佩奇指出，需要50到100次迭代來獲得對向量i的一 個足夠好的近似。計算到這個最優(yōu)值需要幾天才能完成。當(dāng)然，網(wǎng)絡(luò)是不斷變化的。首先，網(wǎng)頁的內(nèi)容，尤其是新聞內(nèi)容，變動頻繁。其次， 網(wǎng)絡(luò)的隱含超鏈結(jié)構(gòu)在網(wǎng)頁或鏈接被加入或被刪除時也要相應(yīng)變動。有傳聞?wù)f，谷歌 大約1個月就要重新計算一次網(wǎng)頁排序向量i。由于在此期間可以看到網(wǎng)

24、頁排序值會 有一個明顯的波動，一些人便將其稱為谷歌舞會(google dance)。(在2002年， 谷歌舉辦了一次谷歌舞會！)總結(jié)布林和佩奇在1998年創(chuàng)建了谷歌，正值網(wǎng)絡(luò)的增長步伐已經(jīng)超過當(dāng)時搜索引擎的能 力范圍。在那個時代，大多數(shù)的搜索引擎都是山那些沒興趣發(fā)布其產(chǎn)品運作細(xì)節(jié)的企 業(yè)研發(fā)的。在發(fā)展谷歌的過程中，布林和佩奇希望“推動學(xué)術(shù)領(lǐng)域更多的發(fā)展和認(rèn)識。” 換言之，他們首先希望，將搜索引擎引入一個更開放的、更學(xué)術(shù)化的環(huán)境，來改進(jìn)搜 索引擎的設(shè)計。其次，他們感到其搜索引擎產(chǎn)牛的統(tǒng)計數(shù)據(jù)能夠為學(xué)術(shù)研究提供很多 的有趣信息?？磥?，聯(lián)邦政府最近試圖獲得谷歌的一些統(tǒng)計數(shù)據(jù)，也是同樣的想法。還有一些

25、其他使用網(wǎng)絡(luò)的超鏈結(jié)構(gòu)來進(jìn)行網(wǎng)頁排序的算法。值得一提的例子是hits 算法，由喬恩克萊因伯格(jon klcinborg)提出，它是tcoma搜索引擎的基礎(chǔ)。 事實上，一個有意思的事情是比較一下不同搜索引擎獲得的搜索結(jié)果，這也可以幫助 我們理解為什么有人會抱怨谷歌寡頭(googlcopoly) o 參考文獻(xiàn)michael berry, murray browne, understanding search engines: mathematical modeling and text retrieval. second edition, siam, philadelphia. 2005.sergey brin, law re nee page, the antaomy of a large-scale hypertextual web search engine, computer networks and isdn systems, 33: 107-17, 1998. also available online at /pub/papers/google.pdfkurt bryan, tanya leise, the $25,000,000,000 eigenvector. the linear algebra behi