原文鏈接:
David Austin
關(guān)鍵詞： 谷歌，搜索，隨機矩陣，特征值
想象一個(gè)含有250億份文件，卻沒(méi)有集中管理機構和館員的圖書(shū)館，而且任何人都可以在任何時(shí)間添加新的文件而不需要通知其他人。一方面你可以確定，這龐大的文件堆中有一份文件含有對你至關(guān)重要的信息，而另一方面，你又像我們中的大多數人那樣沒(méi)有耐心，想要在幾秒鐘之內就找到這條信息。你有什么辦法呢？
擺在你面前的這個(gè)難題看起來(lái)似乎無(wú)法解決。而這個(gè)文件堆跟萬(wàn)維網(wǎng)（World Wide Web）其實(shí)相差無(wú)幾，后者就是一個(gè)超大的、高度混亂的以各種形式存放的文件堆。當然，從萬(wàn)維網(wǎng)中找信息我們有辦法解決，因為我們對搜索引擎非常熟悉（或許你就是通過(guò)搜索找到這篇文章的）。本文將介紹谷歌的網(wǎng)頁(yè)排序算法（PageRank Algorithm），以及它如何從250億份網(wǎng)頁(yè)中撈到與你的搜索條件匹配的結果。它的匹配效果如此之好，以至于“谷歌”（google）今天已經(jīng)成為一個(gè)被廣泛使用的動(dòng)詞了。
包括谷歌在內，多數搜索引擎都是不斷地運行計算機程序群，來(lái)檢索網(wǎng)絡(luò )上的網(wǎng)頁(yè)、搜索每份文件中的詞語(yǔ)并且將相關(guān)信息以高效的形式進(jìn)行存儲。每當用戶(hù)檢索一個(gè)短語(yǔ)，例如“搜索引擎”，搜索引擎就將找出所有含有被檢索短語(yǔ)的網(wǎng)頁(yè)。（或許，類(lèi)似“搜索”與“引擎”之間的距離這樣的額外信息都被會(huì )考慮在內。）但問(wèn)題是，谷歌現在需要檢索250億個(gè)頁(yè)面，而這些頁(yè)面上大約95%的文本僅由大約一萬(wàn)個(gè)單詞組成。也就是說(shuō)，對于大多數搜索而言，將會(huì )有超級多的網(wǎng)頁(yè)含有搜索短語(yǔ)中的單詞。我們所需要的其實(shí)是這樣一種辦法，它能夠將這些符合搜索條件的網(wǎng)頁(yè)按照重要程度進(jìn)行排序，這樣才能夠將最重要的頁(yè)面排在最上面。
確定網(wǎng)頁(yè)重要性的一個(gè)方法是使用人為排序。例如，你或許見(jiàn)過(guò)這樣一些網(wǎng)頁(yè)，他們包含了大量的鏈接，后者連接到某個(gè)特定興趣領(lǐng)域的其他資源。假定維護這個(gè)網(wǎng)頁(yè)的人是可靠的，那么他推薦的網(wǎng)頁(yè)在很大程度上就可能有用。當然，這種做法也有其局限性，比如這個(gè)列表可能很快就過(guò)期了，也可能維護這個(gè)列表的人會(huì )無(wú)意或因某種未知的偏見(jiàn)而遺漏掉一些重要的網(wǎng)頁(yè)。
谷歌的網(wǎng)頁(yè)排序算法則不借助人為的內容評估來(lái)確定網(wǎng)頁(yè)的重要性。事實(shí)上，谷歌發(fā)現，它的服務(wù)的價(jià)值很大程度上是它能夠提供給用戶(hù)無(wú)偏見(jiàn)的搜索結果。谷歌聲稱(chēng)，“我們軟件的核心就是網(wǎng)頁(yè)排序（PageRank）?！?/span> 正如我們將要看到的，技巧就是讓網(wǎng)頁(yè)自身按照重要性進(jìn)行排序。
如何辨別誰(shuí)重要
如果你曾建立過(guò)一個(gè)網(wǎng)頁(yè)，你應該會(huì )列入一些你感興趣的鏈接，它們很容易使你點(diǎn)擊到其它含有重要、可靠信息的網(wǎng)頁(yè)。這樣就相當于你肯定了你所鏈接頁(yè)面的重要性。谷歌的網(wǎng)頁(yè)排序算法每月在所有網(wǎng)頁(yè)中進(jìn)行一次受歡迎程度的評估，以確定哪些網(wǎng)頁(yè)最重要。網(wǎng)頁(yè)排序算法的提出者，謝爾蓋?布林(Sergey Brin)和拉里?佩奇(Lawrence Page)的基本想法是：一個(gè)網(wǎng)頁(yè)的重要性是由鏈接到它的其他網(wǎng)頁(yè)的數量及其重要性來(lái)決定。
我們對任意一個(gè)網(wǎng)頁(yè)P 取值接近于0.85，布林和佩奇指出，需要50到100次迭代來(lái)獲得對向量I的一個(gè)足夠好的近似。計算到這個(gè)最優(yōu)值需要幾天才能完成。
當然，網(wǎng)絡(luò )是不斷變化的。首先，網(wǎng)頁(yè)的內容，尤其是新聞內容，變動(dòng)頻繁。其次，網(wǎng)絡(luò )的隱含超鏈結構在網(wǎng)頁(yè)或鏈接被加入或被刪除時(shí)也要相應變動(dòng)。有傳聞?wù)f(shuō)，谷歌大約1個(gè)月就要重新計算一次網(wǎng)頁(yè)排序向量I。由于在此期間可以看到網(wǎng)頁(yè)排序值會(huì )有一個(gè)明顯的波動(dòng)，一些人便將其稱(chēng)為谷歌舞會(huì )（Google Dance）。（在2002年，谷歌舉辦了一次谷歌舞會(huì )?。?/span>
總結
布林和佩奇在1998年創(chuàng )建了谷歌，正值網(wǎng)絡(luò )的增長(cháng)步伐已經(jīng)超過(guò)當時(shí)搜索引擎的能力范圍。在那個(gè)時(shí)代，大多數的搜索引擎都是由那些沒(méi)興趣發(fā)布其產(chǎn)品運作細節的企業(yè)研發(fā)的。在發(fā)展谷歌的過(guò)程中，布林和佩奇希望“推動(dòng)學(xué)術(shù)領(lǐng)域更多的發(fā)展和認識?！睋Q言之，他們首先希望，將搜索引擎引入一個(gè)更開(kāi)放的、更學(xué)術(shù)化的環(huán)境，來(lái)改進(jìn)搜索引擎的設計。其次，他們感到其搜索引擎產(chǎn)生的統計數據能夠為學(xué)術(shù)研究提供很多的有趣信息?？磥?lái)，聯(lián)邦政府最近試圖獲得谷歌的一些統計數據，也是同樣的想法。
還有一些其他使用網(wǎng)絡(luò )的超鏈結構來(lái)進(jìn)行網(wǎng)頁(yè)排序的算法。值得一提的例子是HITS算法，由喬恩·克萊因伯格（Jon Kleinberg）提出，它是Teoma搜索引擎的基礎。事實(shí)上，一個(gè)有意思的事情是比較一下不同搜索引擎獲得的搜索結果，這也可以幫助我們理解為什么有人會(huì )抱怨谷歌寡頭（Googleopoly）。
參考文獻
Michael Berry, Murray Browne, Understanding Search Engines: Mathematical Modeling and Text Retrieval. Second Edition,
Sergey Brin, Lawrence Page, The antaomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, 33: 107-17, 1998. Also available online at http://infolab.stanford.edu/pub/papers/google.pdf
Kurt Bryan, Tanya Leise, The $25,000,000,000 eigenvector. The linear algebra behind Google.
Google Corporate Information: Technology.
Taher Haveliwala, Sepandar Kamvar, The second eigenvalue of the Google matrix.
Amy Langville, Carl Meyer, Google's PageRank and Beyond: The Science of Search Engine Rankings.
This is an informative, accessible book, written in an engaging style. Besides providing the relevant mathematical background and details of PageRank and its implementation (as well as Kleinberg's HITS algorithm), this book contains many interesting "Asides" that give trivia illuminating the context of search engine design.
原文鏈接: | |
作 者: | David Austin，Grand Valley State University |
翻 譯: | 沈棟，中科院數學(xué)與系統科學(xué)研究院博士，北京化工大學(xué)副教授 |
校 對: | 湯濤，香港浸會(huì )大學(xué)數學(xué)講座教授 |
聯(lián)系客服
