|
原文鏈接:
David Austin 關(guān)鍵詞： 谷歌，搜索，隨機(jī)矩陣，特征值 想象一個(gè)含有250億份文件，卻沒有集中管理機(jī)構(gòu)和館員的圖書館，而且任何人都可以在任何時(shí)間添加新的文件而不需要通知其他人。一方面你可以確定，這龐大的文件堆中有一份文件含有對(duì)你至關(guān)重要的信息，而另一方面，你又像我們中的大多數(shù)人那樣沒有耐心，想要在幾秒鐘之內(nèi)就找到這條信息。你有什么辦法呢？ 擺在你面前的這個(gè)難題看起來似乎無法解決。而這個(gè)文件堆跟萬維網(wǎng)（World Wide Web）其實(shí)相差無幾，后者就是一個(gè)超大的、高度混亂的以各種形式存放的文件堆。當(dāng)然，從萬維網(wǎng)中找信息我們有辦法解決，因?yàn)槲覀儗?duì)搜索引擎非常熟悉（或許你就是通過搜索找到這篇文章的）。本文將介紹谷歌的網(wǎng)頁排序算法（PageRank Algorithm），以及它如何從250億份網(wǎng)頁中撈到與你的搜索條件匹配的結(jié)果。它的匹配效果如此之好，以至于“谷歌”（google）今天已經(jīng)成為一個(gè)被廣泛使用的動(dòng)詞了。 包括谷歌在內(nèi)，多數(shù)搜索引擎都是不斷地運(yùn)行計(jì)算機(jī)程序群，來檢索網(wǎng)絡(luò)上的網(wǎng)頁、搜索每份文件中的詞語并且將相關(guān)信息以高效的形式進(jìn)行存儲(chǔ)。每當(dāng)用戶檢索一個(gè)短語，例如“搜索引擎”，搜索引擎就將找出所有含有被檢索短語的網(wǎng)頁。（或許，類似“搜索”與“引擎”之間的距離這樣的額外信息都被會(huì)考慮在內(nèi)。）但問題是，谷歌現(xiàn)在需要檢索250億個(gè)頁面，而這些頁面上大約95%的文本僅由大約一萬個(gè)單詞組成。也就是說，對(duì)于大多數(shù)搜索而言，將會(huì)有超級(jí)多的網(wǎng)頁含有搜索短語中的單詞。我們所需要的其實(shí)是這樣一種辦法，它能夠?qū)⑦@些符合搜索條件的網(wǎng)頁按照重要程度進(jìn)行排序，這樣才能夠?qū)⒆钪匾捻撁媾旁谧钌厦妗?/SPAN> 確定網(wǎng)頁重要性的一個(gè)方法是使用人為排序。例如，你或許見過這樣一些網(wǎng)頁，他們包含了大量的鏈接，后者連接到某個(gè)特定興趣領(lǐng)域的其他資源。假定維護(hù)這個(gè)網(wǎng)頁的人是可靠的，那么他推薦的網(wǎng)頁在很大程度上就可能有用。當(dāng)然，這種做法也有其局限性，比如這個(gè)列表可能很快就過期了，也可能維護(hù)這個(gè)列表的人會(huì)無意或因某種未知的偏見而遺漏掉一些重要的網(wǎng)頁。 谷歌的網(wǎng)頁排序算法則不借助人為的內(nèi)容評(píng)估來確定網(wǎng)頁的重要性。事實(shí)上，谷歌發(fā)現(xiàn)，它的服務(wù)的價(jià)值很大程度上是它能夠提供給用戶無偏見的搜索結(jié)果。谷歌聲稱，“我們軟件的核心就是網(wǎng)頁排序（PageRank）。” 正如我們將要看到的，技巧就是讓網(wǎng)頁自身按照重要性進(jìn)行排序。 如何辨別誰重要 如果你曾建立過一個(gè)網(wǎng)頁，你應(yīng)該會(huì)列入一些你感興趣的鏈接，它們很容易使你點(diǎn)擊到其它含有重要、可靠信息的網(wǎng)頁。這樣就相當(dāng)于你肯定了你所鏈接頁面的重要性。谷歌的網(wǎng)頁排序算法每月在所有網(wǎng)頁中進(jìn)行一次受歡迎程度的評(píng)估，以確定哪些網(wǎng)頁最重要。網(wǎng)頁排序算法的提出者，謝爾蓋?布林(Sergey Brin)和拉里?佩奇(Lawrence Page)的基本想法是：一個(gè)網(wǎng)頁的重要性是由鏈接到它的其他網(wǎng)頁的數(shù)量及其重要性來決定。 我們對(duì)任意一個(gè)網(wǎng)頁P
取值接近于0.85，布林和佩奇指出，需要50到100次迭代來獲得對(duì)向量I的一個(gè)足夠好的近似。計(jì)算到這個(gè)最優(yōu)值需要幾天才能完成。 當(dāng)然，網(wǎng)絡(luò)是不斷變化的。首先，網(wǎng)頁的內(nèi)容，尤其是新聞內(nèi)容，變動(dòng)頻繁。其次，網(wǎng)絡(luò)的隱含超鏈結(jié)構(gòu)在網(wǎng)頁或鏈接被加入或被刪除時(shí)也要相應(yīng)變動(dòng)。有傳聞?wù)f，谷歌大約1個(gè)月就要重新計(jì)算一次網(wǎng)頁排序向量I。由于在此期間可以看到網(wǎng)頁排序值會(huì)有一個(gè)明顯的波動(dòng)，一些人便將其稱為谷歌舞會(huì)（Google Dance）。（在2002年，谷歌舉辦了一次谷歌舞會(huì)！） 總結(jié) 布林和佩奇在1998年創(chuàng)建了谷歌，正值網(wǎng)絡(luò)的增長步伐已經(jīng)超過當(dāng)時(shí)搜索引擎的能力范圍。在那個(gè)時(shí)代，大多數(shù)的搜索引擎都是由那些沒興趣發(fā)布其產(chǎn)品運(yùn)作細(xì)節(jié)的企業(yè)研發(fā)的。在發(fā)展谷歌的過程中，布林和佩奇希望“推動(dòng)學(xué)術(shù)領(lǐng)域更多的發(fā)展和認(rèn)識(shí)。”換言之，他們首先希望，將搜索引擎引入一個(gè)更開放的、更學(xué)術(shù)化的環(huán)境，來改進(jìn)搜索引擎的設(shè)計(jì)。其次，他們感到其搜索引擎產(chǎn)生的統(tǒng)計(jì)數(shù)據(jù)能夠?yàn)閷W(xué)術(shù)研究提供很多的有趣信息。看來，聯(lián)邦政府最近試圖獲得谷歌的一些統(tǒng)計(jì)數(shù)據(jù)，也是同樣的想法。 還有一些其他使用網(wǎng)絡(luò)的超鏈結(jié)構(gòu)來進(jìn)行網(wǎng)頁排序的算法。值得一提的例子是HITS算法，由喬恩·克萊因伯格（Jon Kleinberg）提出，它是Teoma搜索引擎的基礎(chǔ)。事實(shí)上，一個(gè)有意思的事情是比較一下不同搜索引擎獲得的搜索結(jié)果，這也可以幫助我們理解為什么有人會(huì)抱怨谷歌寡頭（Googleopoly）。 參考文獻(xiàn) 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./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.
|
|
|
