第533章 ri-Vf公式

  在如今這個互聯網時代，有一家家喻戶曉的公司，它自 1998 年問世以來，在極短的時間內就聲譽鵲起，不僅超越了所有競爭對手，而且徹底改觀了整個互聯網的生態。這家公司就是當今互聯網上的第一搜索引擎：穀歌(Google)。


  在這樣一家顯赫的公司背後，自然有許許多多商戰故事，也有許許多多成功因素。但與普通商戰故事不同的是，在穀歌的成功背後起著最關鍵作用的卻是一個數學因素。


  穀歌作為一個搜索引擎，它的核心功能顧名思義，就是網頁搜索。說到搜索，我們都不陌生，因為那是凡地球人都會的技能。我們在字典裏查個生字，在圖書館裏找本圖書，甚至在商店裏尋一種商品等，都是搜索。如果我們稍稍推究一下的話，就會發現那些搜索之所以可能，並且人人都會，在很大程度上得益於以下三條：


  1.搜索對象的數量較小——比如一本字典收錄的字通常隻有一兩萬個，一家圖書館收錄的不重複圖書通常不超過幾十萬種，一家商店的商品通常不超過幾萬種等。


  2.搜索對象具有良好的分類或排序——比如字典裏的字按拚音排序，圖書館裏的圖書按主題分類，商店裏的商品按品種或用途分類等。


  3.搜索結果的重複度較低——比如字典裏的同音字通常不超過幾十個，圖書館裏的同名圖書和商店裏的同種商品通常也不超過幾十種。


  但互聯網的鮮明特點卻是以上三條無一滿足。事實上，即便在穀歌問世之前，互聯網上的網頁總數就已超過了諸如圖書館藏書數量之類傳統搜索對象的數目。而且這還隻是冰山一角，因為與搜索圖書時單純的書名搜索不同，互聯網上的搜索往往是對網頁內容的直接搜索，這相當於將圖書內的每一個字都變成了搜索對象，由此導致的數量才是真正驚人的，它不僅直接破壞了上述第一條，而且連帶破壞了二、三兩條。在互聯網發展的早期，象 Yahoo 那樣的門戶網站曾試圖為網頁建立分類係統，但隨著網頁數量的激增，這種做法很快就“掛一漏萬”了。而搜索結果的重複度更是以快得不能再快的速度走向失控。這其實是可以預料的，因為幾乎所有網頁都離不開幾千個常用詞，因此除非搜索生僻詞，否則出現幾十萬、幾百萬、甚至幾千萬條搜索結果都是不足為奇的。


  互聯網的這些“不良特點”給搜索引擎的設計帶來了極大的挑戰。而在這些挑戰之中，相對來說，對一、二兩條的破壞是比較容易解決的，因為那主要是對搜索引擎的存儲空間和計算能力提出了較高要求，隻要有足夠多的錢來買“裝備”，這些還算是容易解決的。套用電視連續劇《蝸居》中某貪官的台詞來說，“能用錢解決的問題就不是大問題”。但對第三條的破壞卻要了命了，因為無論搜索引擎的硬件如何強大，速度如何快捷，要是搜索結果有幾百萬條，那麽任何用戶想從其中“海選”出自己真正想要的東西都是幾乎不可能的。這一點對早期搜索引擎來說可謂是致命傷，而且它不是用錢就能解決的問題。


  這致命傷該如何治療呢？藥方其實很簡單，那就是對搜索結果進行排序，把用戶最有可能需要的網頁排在最前麵，以確保用戶能很方便地找到它們。但問題是：網頁的水平千差萬別，用戶的喜好更是萬別千差，互聯網上有一句流行語叫做：“在互聯網上，沒人知道你是一條狗”(Oe， nobody knows you"re a dog)。連用戶是人是狗都“沒人知道”，搜索引擎又怎能知道哪些搜索結果是用戶最有可能需要的，並對它們進行排序呢？

  在穀歌主導互聯網搜索之前，多數搜索引擎采用的排序方法，是以被搜索詞語在網頁中的出現次數來決定排序，出現次數越多的網頁排在越前麵。這個判據不能說毫無道理，因為用戶搜索一個詞語，通常表明對該詞語感興趣。既然如此，那該詞語在網頁中的出現次數越多，就越有可能表示該網頁是用戶所需要的。可惜的是，這個貌似合理的方法實際上卻行不大通。因為按照這種方法，任何一個象祥林嫂一樣翻來複去倒騰某些關鍵詞的網頁，無論水平多爛，一旦被搜索到，都立刻會“金榜題名”，這簡直就是廣告及垃圾網頁製造者的天堂。事實上，當時幾乎沒有一個搜索引擎不被“祥林嫂”們所困擾，其中最具諷刺意味的是：堪稱互聯網巨子的當年四大搜索引擎在搜索自己公司的名字時，居然隻有一個能使之出現在搜索結果的前十名內，其餘全被“祥林嫂”們擠跑了。


  就是在這種情況下， 1996 年初，穀歌公司的創始人，當時還是美國斯坦福大學(Stanford Uy)研究生的佩奇(Larry Page)和布林(Sergey Brin)開始了對網頁排序問題的研究。這兩位小夥子之所以研究網頁排序問題，一來是導師的建議(佩奇後來稱該建議為“我有生以來得到過的最好建議”)，二來則是因為他們對這一問題背後的數學產生了興趣。


  網頁排序問題的背後有什麽樣的數學呢？這得從佩奇和布林看待這一問題的思路說起。在佩奇和布林看來，網頁的排序是不能靠每個網頁自己來標榜的，無論把關鍵詞重複多少次，垃圾網頁依然是垃圾網頁。那麽，究竟什麽才是網頁排序的可靠依據呢？出生於書香門第的佩奇和布林(兩人的父親都是大學教授)想到了學術界評判學術論文重要性的通用方法，那就是看論文的引用次數。在互聯網上，與論文引用相類似的是顯然是網頁鏈接。因此，佩奇和布林萌生了一個網頁排序的思路，那就是通過研究網頁間的相互鏈接來確定排序。具體地說，一個網頁被其它網頁鏈接得越多，它的排序就越靠前。不僅如此，佩奇和布林還進一步提出，一個網頁越是被排序靠前的網頁所鏈接，它的排序就也應該越靠前。這一條的意義也是不言而喻的，就好比一篇論文被諾貝爾獎得主所引用，顯然要比被普通研究者所引用更說明其價值。依照這個思路，網頁排序問題就跟整個互聯網的鏈接結構產生了關係，正是這一關係使它成為了一個不折不扣的數學問題。


  思路雖然有了，具體計算卻並非易事，因為按照這種思路，想要知道一個網頁 Wi 的排序，不僅要知道有多少網頁鏈接了它，而且還得知道那些網頁各自的排序——因為來自排序靠前網頁的鏈接更“值錢”。但作為互聯網大家庭的一員， Wi 本身對其它網頁的排序也是有貢獻的，而且基於來自排序靠前網頁的鏈接更“值錢”的原則，這種貢獻與 Wi 的排序有關。這樣一來，我們就陷入了一個“先有雞還是先有蛋”的循環之中：想要知道 Wi 的排序，就得知道與它鏈接的其它網頁的排序，而想要知道那些網頁的排序，卻又首先得知道 Wi 的排序。


  為了打破這個循環，佩奇和布林采用了一個很巧妙的思路，即分析一個虛擬用戶在互聯網上的漫遊過程。他們假定：虛擬用戶一旦訪問了一個網頁後，下一步將有相同的幾率訪問被該網頁所鏈接的任何一個其它網頁。換句話說，如果網頁 Wi 有 Ni 個對外鏈接，則虛擬用戶在訪問了 Wi 之後，下一步點擊這些鏈接中任何一個的幾率均為 1/Ni。初看起來，這一假設並不合理，因為任何用戶都有偏好，怎麽可能以相同的幾率訪問一個網頁的所有鏈接呢？但如果我們考慮到佩奇和布林的虛擬用戶實際上是對互聯網上全體用戶的一種平均意義上的代表，這條假設就不象初看起來那麽不合理了。那麽網頁的排序由什麽來決定呢？是由該用戶在漫遊了很長時間(理論上為無窮長時間)後訪問各網頁的幾率分布來決定，訪問幾率越大的網頁排序就越靠前。


  為了將這一分析數學化，我們用 pi(n)表示虛擬用戶在進行第 n 次瀏覽時訪問網頁 Wi 的幾率。顯然，上述假設可以表述為(請讀者自行證明)：pi(n+1)=Σj pj(n)pj→i/Nj

  這裏 pj→i 是一個描述互聯網鏈接結構的指標函數(indicator )，其定義是：如果網頁 Wj 有鏈接指向網頁 Wi，則 pj→i 取值為 1，反之則為 0。顯然，這條假設所體現的正是前麵提到的佩奇和布林的排序原則，因為右端求和式的存在表明與 Wi 有鏈接的所有網頁 Wj 都對 Wi 的排名有貢獻，而求和式中的每一項都正比於 pj，則表明來自那些網頁的貢獻與它們的自身排序有關，自身排序越靠前(即 pj 越大)，貢獻就越大。


  為符號簡潔起見，我們將虛擬用戶第 n 次瀏覽時訪問各網頁的幾率合並為一個列向量 pn，它的第 i 個分量為 pi(n)，並引進一個隻與互聯網結構有關的矩陣 H，它的第 i 行 j 列的矩陣元為 Hij = pj→i/Nj，則上述公式可以改寫為：pn+1 = Hpn

  這就是計算網頁排序的公式。


  熟悉隨機過程理論的讀者想必看出來了，上述公式描述的是一種馬爾可夫過程(Markov process)，而且是其中最簡單的一類，即所謂的平穩馬爾可夫過程(stationary Markov process)[注一]，而 H 則是描述轉移概率的所謂轉移矩陣(transition matrix)。不過普通馬爾可夫過程中的轉移矩陣通常是隨機矩陣(stochastic matrix)，即每一列的矩陣元之和都為 1 的矩陣(請讀者想一想，這一特點的“物理意義”是什麽？)[注二]。而我們的矩陣 H 卻可能有一些列是零向量，從而矩陣元之和為 0，它們對應於那些沒有對外鏈接的網頁，即所謂的“懸掛網頁”(dangling page)。


  上述公式的求解是簡單得不能再簡單的事情，即：pn = Hnp0

  其中 p0 為虛擬讀者初次瀏覽時訪問各網頁的幾率分布(在佩奇和布林的原始論文中，這一幾率分布被假定為是均勻分布)。


  如前所述，佩奇和布林是用虛擬用戶在經過很長(理論上為無窮長)時間的漫遊後訪問各網頁的幾率分布，即 limn→∞pn，來確定網頁排序的。這個定義要想管用，顯然要解決三個問題：

  1.極限 limn→∞pn 是否存在？


  2.如果極限存在，它是否與 p0 的選取無關？

  3.如果極限存在，並且與 p0 的選取無關，它作為網頁排序的依據是否真的合理？


  如果這三個問題的答案都是肯定的，那麽網頁排序問題就算解決了。反之，哪怕隻有一個問題的答案是否定的，網頁排序問題也就不能算是得到滿意的解決。那麽實際答案如何呢？很遺憾，是後一種，而且是其中最糟糕的情形，即三個問題的答案全都是否定的。這可以由一些簡單的例子看出。比方說，在隻包含兩個相互鏈接網頁的迷你型互聯網上，如果 p0 =(1， 0)T，極限就不存在(因為幾率分布將在(1， 0)T和(0， 1)T 之間無窮振蕩)。而存在幾個互不連通(即互不鏈接)區域的互聯網則會使極限——即便存在——與 p0 的選取有關(因為把 p0 選在不同區域內顯然會導致不同極限)。至於極限存在，並且與 p0 的選取無關時它作為網頁排序的依據是否真的合理的問題，雖然不是數學問題，答案卻也是否定的，因為任何一個“懸掛網頁”都能象黑洞一樣，把其它網頁的幾率“吸收”到自己身上(因為虛擬用戶一旦進入那樣的網頁，就會由於沒有對外鏈接而永遠停留在那裏)，這顯然是不合理的。這種不合理效應是如此顯著，以至於在一個連通性良好的互聯網上，哪怕隻有一個“懸掛網頁”，也足以使整個互聯網的網頁排序失效，可謂是“一粒老鼠屎壞了一鍋粥”。


  為了解決這些問題，佩奇和布林對虛擬用戶的行為進行了修正。首先，他們意識到無論真實用戶還是虛擬用戶，當他們訪問到“懸掛網頁”時，都不可能也不應該“在一棵樹上吊死”，而是會自行訪問其它網頁。對於真實用戶來說，自行訪問的網頁顯然與各人的興趣有關，但對於在平均意義上代表真實用戶的虛擬用戶來說，佩奇和布林假定它將會在整個互聯網上隨機選取一個網頁進行訪問。用數學語言來說，這相當於是把 H 的列向量中所有的零向量都換成 e/N (其中 e 是所有分量都為 1 的列向量， N 為互聯網上的網頁總數)。如果我們引進一個描述“懸掛網頁”的指標向量(indicator vector) a，它的第 i 個分量的取值視 Wi 是否為“懸掛網頁”而定，如果是“懸掛網頁”，取值為 1，否則為零，並用 S 表示修正後的矩陣，則：S = H + aeT/N

  顯然，這樣定義的 S 矩陣的每一列的矩陣元之和都是 1，從而是一個不折不扣的隨機矩陣。這一修正因此而被稱為隨機性修正(stochasticity adjustment)。這一修正相當於剔除了“懸掛網頁”，從而可以給上述第三個問題帶來肯定回答(當然，這一回答沒有絕對標準，可以不斷改進)。不過，這一修正解決不了前兩個問題。為了解決那兩個問題，佩奇和布林引進了第二個修正。他們假定，虛擬用戶雖然是虛擬的，但多少也有一些“性格”，不會完全死板地隻訪問當前網頁所提供的鏈接。具體地說，他們假定虛擬用戶在每一步都有一個小於 1 的幾率α訪問當前網頁所提供的鏈接，同時卻也有一個幾率 1-α不受那些鏈接所限，隨機訪問互聯網上的任何一個網站。用數學語言來說(請讀者自行證明)，這相當於是把上述 S 矩陣變成了一個新的矩陣 G：G =αS +(1-α)eeT/N

  這個矩陣不僅是一個隨機矩陣，而且由於第二項的加盟，它有了一個新的特點，即所有矩陣元都為正(請讀者想一想，這一特點的“物理意義”是什麽？)，這樣的矩陣是所謂的素矩陣(primitive matrix)[注四]。這一修正因此而被稱為素性修正(primitivity adjustment)。


  經過這兩類修正，網頁排序的計算方法就變成了：pn = Gnp0

  這個算法能給上述問題提供肯定答案嗎？是的，它能。因為隨機過程理論中有一個所謂的馬爾可夫鏈基本定理(Fual Theorem of Markov s)，它表明在一個馬爾可夫過程中，如果轉移矩陣是素矩陣，那麽上述前兩個問題的答案就是肯定的。而隨機性修正已經解決了上述第三個問題，因此所有問題就都解決了。如果我們用 p 表示 pn 的極限，則 p 給出的就是整個互聯網的網頁排序——它的每一個分量就是相應網頁的訪問幾率，幾率越大，排序就越靠前。


  這樣，佩奇和布林就找到了一個不僅含義合理，而且數學上嚴謹的網頁排序算法，他們把這個算法稱為 PageRank，不過要注意的是，雖然這個名稱的直譯恰好是“網頁排序”，但它實際上指的是“佩奇排序”，因為其中的“Page”不是指網頁，而是佩奇的名字。這個算法就是穀歌排序的數學基礎，而其中的矩陣 G 則被稱為穀歌矩陣(Google matrix)。


  細心的讀者可能注意到了，我們還遺漏了一樣東西，那就是穀歌矩陣中描述虛擬用戶“性格”的那個α參數。那個參數的數值是多少呢？從理論上講，它應該來自於對真實用戶平均行為的分析，不過實際上另有一個因素對它的選取產生了很大影響，那就是 Gnp0 收斂於 p 的快慢程度。由於 G 是一個 N×N 矩陣，而 N 為互聯網上——確切地說是被穀歌所收錄的——網頁的總數，在穀歌成立之初為幾千萬，目前為幾百億，是一個極其巨大的數字。因此 G 是一個超大型矩陣，甚至很可能是人類有史以來處理過的最龐大的矩陣。對於這樣的矩陣， Gnp0 收斂速度的快慢是關係到算法是否實用的重要因素，而這個因素恰恰與α有關。可以證明，α越小， Gnp0 的收斂速度就越快。但α也不能太小，因為太小的話，“佩奇排序”中最精華的部分，即以網頁間的彼此鏈接為基礎的排序思路就被弱化了(因為這部分的貢獻正比於α)，這顯然是得不償失的。因此，在α的選取上有很多折衷的考慮要做，佩奇和布林最終選擇的數值是α= 0.85。


  以上就是穀歌背後最重要的數學奧秘。與以往那種憑借關鍵詞出現次數所作的排序不同，這種由所有網頁的相互鏈接所確定的排序是不那麽容易做假的，因為做假者再是把自己的網頁吹得天花亂墜，如果沒有真正吸引人的內容，別人不鏈接它，一切就還是枉然[注六]。而且“佩奇排序”還有一個重要特點，那就是它隻與互聯網的結構有關，而與用戶具體搜索的東西無關。這意味著排序計算可以單獨進行，而無需在用戶鍵入搜索指令後才臨時進行。穀歌搜索的速度之所以快捷，在很大程度上得益於此。


  穀歌成立之初跟其它一些“發跡於地下室”(one-man-in-basement)的 IT 公司一樣寒酸：雇員隻有一位(兩位老板不算)，工作場所則是一位朋友的車庫。但它出類拔萃的排序算法很快為它贏得了聲譽。公司成立僅僅三個月，《PC Magzine》雜誌就把穀歌列為了年度最佳搜索引擎。 2001 年，佩奇為“佩奇排序”申請到了專利，專利的發明人為佩奇，擁有者則是他和布林的母校斯坦福大學。 2004年8月，穀歌成為了一家初始市值約 17 億美元的上市公司。不僅公司高管在一夜間成為了億萬富翁，就連當初給過他們幾十美元“讚助費”的某些同事和朋友也得到了足夠終身養老所用的股票回報。作為公司搖籃的斯坦福大學則因擁有“佩奇排序”的專利而獲得了 180 萬股穀歌股票。 2005 年 12 月，斯坦福大學通過賣掉那些股票獲得了 3.36 億美元的巨額收益，成為美國高校因支持技術研發而獲得的有史以來最巨額的收益之一。


  穀歌在短短數年間就橫掃整個互聯網，成為搜索引擎業的新一代霸主，佩奇和布林的那個排序算法無疑居功至偉，可以說，是數學成就了穀歌。當然，這麽多年過去了，穀歌作為 IT 界研發能力最強的公司之一，它的網頁排序方法早已有了巨大的改進，由當年單純依靠“佩奇排序”演變為了由兩百多種來自不同渠道的信息(其中包括與網頁訪問量有關的統計數據)綜合而成的更加可靠的方法。而當年曾給佩奇和布林帶來過啟示的學術界，則反過來從穀歌的成功中借鑒了經驗，如今一些學術機構對論文影響因子(impact factor)的計算已采用了類似“佩奇排序”的算法。


  在本文的最後，還有一件事情在這裏提一下，那就是與佩奇和布林研究排序算法幾乎同時，有另外幾人也相互獨立地沿著類似的思路從事著研究。他們中有一位是當時在美國新澤西州工作的中國人，他的算法後來也成就了一家公司——一家中國公司。此人的名字叫做李彥宏(Robin Li)，他所成就的那家公司就是百度。這些新公司的發展極好地印證了培根(Francis Ba)的一句名言：知識就是力量。