手機(jī)版|
二維碼|
Since: Thu Feb 1 18:22:44 JST 2001
Last Refreshed: Sat Jan 24 18:30:35 JST 2004
★(2007/1/5) 本文的中文版由ROCK翻譯制作完成。
★(2003/7/1) 拙著『Namazu系統(tǒng)的構(gòu)筑和活用』已作修訂。 詳情請(qǐng)看 介紹頁(yè)面 。
★(2001/2/28) Namazu 的索引中使用的計(jì)算 PageRank 的 Perl 腳本 prnmz-1.0.tar.gz 公開下載。
下一頁(yè)
最近，搜索引擎 Google (http://www.google.com/)非常引人注目。Google 是基于現(xiàn)擔(dān)任 CEO 的 Larry Page 和擔(dān)任總經(jīng)理的 Sergey Brin (2001年2月)在就讀于美斯坦福大學(xué)研究生院時(shí)所開發(fā)的搜索引擎的一種檢索服務(wù)。Google 從1998年9月開始服務(wù),但 Netscape Communications 在 Google 的測(cè)試階段就開始與其合作，美國(guó) Yahoo! 公司也從2000年6月起將默認(rèn)搜索引擎(美國(guó) Yahoo! 不能檢索時(shí)作為增補(bǔ)的搜索引擎)由原先合作的 Inktomi 轉(zhuǎn)換為了 Google。日語(yǔ)版 Google 在2000年9月正式登場(chǎng),現(xiàn)已被 BIGLOBE(NEC)所采用。 (注:2001年4月 Yahoo! JAPAN 和 @NIFTY，7月索尼，2002年1月 Excite 也相繼與 Google 建立了協(xié)作關(guān)系)。
Google 被評(píng)價(jià)的優(yōu)點(diǎn)不僅僅在于去除無用的(廣告)標(biāo)語(yǔ)構(gòu)成單一頁(yè)面的功能、獨(dú)自的 Cache 系統(tǒng)、動(dòng)態(tài)制成摘要信息、為實(shí)現(xiàn)高速檢索而設(shè)置的分散系統(tǒng)(數(shù)千臺(tái)規(guī)模的Linux群集器)等，而其中最大的優(yōu)點(diǎn)正是它檢索結(jié)果的正確性。一種能夠自動(dòng)判斷網(wǎng)頁(yè)重要性的技術(shù)「PageRank是(網(wǎng)頁(yè)等級(jí))」就是為此而設(shè)計(jì)的一種技術(shù)。 本文的目的就是以盡可能淺顯易懂的語(yǔ)言來說明 PageRank 系統(tǒng)的概要和原理。
以下是 PageRank 的一篇基礎(chǔ)文章。
Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, 'The PageRank Citation Ranking: Bringing Order to the Web', 1998, http://www-db.stanford.edu/~backrub/pageranksub.ps為了更高效地計(jì)算 PageRank,以下是改良以后的一篇論文。
Taher H. Haveliwala, 'Efficient Computation of PageRank', Stanford Technical Report, 1999,http://dbpubs.stanford.edu:8090/pub/1999-31
另外，以下是 PageRank 的演示用資料(PowerPoint)。
Larry Page, 'PageRank: Bringing Order to the Web',http://hci.stanford.edu/~page/papers/pagerank/ （已失效）
接下來就對(duì)這兩篇文章(另加一篇資料)進(jìn)行基本說明。 首先，用簡(jiǎn)單的例子來解說 PageRank 的概念，再歸結(jié)到使用超鏈接關(guān)系的排序系統(tǒng)來解決大規(guī)模疏松疏矩陣的特性值的問題。然后我們會(huì)接觸一些在現(xiàn)實(shí)世界中應(yīng)用基本模型時(shí)出現(xiàn)的問題和對(duì)應(yīng)方法。接下來，為了探討是否能夠作為「?jìng)€(gè)人化 PageRank」使用，進(jìn)行對(duì)免費(fèi)全文檢索系統(tǒng) Namazu 的安裝實(shí)驗(yàn)并對(duì)其結(jié)果進(jìn)行闡述。最后發(fā)表我對(duì) PageRank 的個(gè)人見解。
另外，為了能夠理解以下的說明內(nèi)容，需要大學(xué)基礎(chǔ)課程程度的數(shù)學(xué)知識(shí)(尤其是線形代數(shù))。然而為使文科生也能夠順利讀下去，盡可能地不用算式來說明問題，同時(shí)，為了加入筆者個(gè)人的見解，沒有加入像原文那么多的算法和數(shù)字，也存在許多不夠嚴(yán)密和欠正確的地方，事先在次聲明。具體內(nèi)容請(qǐng)參照原文。
PageRank(TM) 是美國(guó) Google 公司的登記注冊(cè)商標(biāo)。
上一頁(yè) | 下一頁(yè)
2. PageRank 的基本概念PageRank 是基于「從許多優(yōu)質(zhì)的網(wǎng)頁(yè)鏈接過來的網(wǎng)頁(yè)，必定還是優(yōu)質(zhì)網(wǎng)頁(yè)」的回歸關(guān)系，來判定所有網(wǎng)頁(yè)的重要性。
在以下冗長(zhǎng)的說明中，許多部分大量地使用了專業(yè)用語(yǔ)，會(huì)造成理解上的困難。這一章雖然準(zhǔn)備集中于定性而簡(jiǎn)單的解說,但是，即使如此也會(huì)有怎么也不明白的時(shí)候，此時(shí)只要能夠理解「從許多優(yōu)質(zhì)的網(wǎng)頁(yè)鏈接過來的網(wǎng)頁(yè)，必定還是優(yōu)質(zhì)網(wǎng)頁(yè)」這一思考方法也就非常得可貴了。因?yàn)樵谒袔讉€(gè)要點(diǎn)中，這個(gè)是最重要的思考方法。
來自于 Google 自己的介紹「Google的受歡迎的秘密(http://www.google.co.jp/intl/ja/why_use.html)」 是象以下一樣解說的。
關(guān)于PageRank
PageRank，有效地利用了 Web 所擁有的龐大鏈接構(gòu)造的特性。
從網(wǎng)頁(yè)A導(dǎo)向網(wǎng)頁(yè)B的鏈接被看作是對(duì)頁(yè)面A對(duì)頁(yè)面B的支持投票，Google根據(jù)這個(gè)投票數(shù)來判斷頁(yè)面的重要性?？墒?Google
不單單只看投票數(shù)(即鏈接數(shù))，對(duì)投票的頁(yè)面也進(jìn)行分析。「重要性」高的頁(yè)面所投的票的評(píng)價(jià)會(huì)更高，因?yàn)榻邮苓@個(gè)投票頁(yè)面會(huì)被理解為「重要的物品」。
根據(jù)這樣的分析,得到了高評(píng)價(jià)的重要頁(yè)面會(huì)被給予較高的
Page Rank(網(wǎng)頁(yè)等級(jí))，在檢索結(jié)果內(nèi)的名次也會(huì)提高。PageRank 是 Google
中表示網(wǎng)頁(yè)重要性的綜合性指標(biāo)，而且不會(huì)受到各種檢索(引擎)的影響。倒不如說，PageRank
就是基于對(duì)"使用復(fù)雜的算法而得到的鏈接構(gòu)造"的分析，從而得出的各網(wǎng)頁(yè)本身的特性。
當(dāng)然，重要性高的頁(yè)面如果和檢索詞句沒有關(guān)聯(lián)同樣也沒有任何意義。為此
Google 使用了精練后的文本匹配技術(shù)，使得能夠檢索出重要而且正確的頁(yè)面。
通過下面的圖我們來具體地看一下剛才所闡述的算法。具體的算法是，將某個(gè)頁(yè)面的 PageRank
除以存在于這個(gè)頁(yè)面的正向鏈接,由此得到的值分別和正向鏈接所指向的頁(yè)面的 PageRank 相加，即得到了被鏈接的頁(yè)面的 PageRank。
反向鏈接數(shù) (單純的意義上的受歡迎度指標(biāo))
反向鏈接是否來自推薦度高的頁(yè)面 (有根據(jù)的受歡迎指標(biāo))
反向鏈接源頁(yè)面的鏈接數(shù) (被選中的幾率指標(biāo))
首先最基本的是，被許多頁(yè)面鏈接會(huì)使得推薦度提高。也就是說「(被許多頁(yè)面鏈接的)受歡迎的頁(yè)面，必定是優(yōu)質(zhì)的頁(yè)面」。所以以反向鏈接數(shù)作為受歡迎度的一個(gè)指標(biāo)是很自然的想法。這是因?yàn)?，“鏈接”是一種被看作「可以看看這個(gè)頁(yè)面/這個(gè)頁(yè)會(huì)有用」的推薦行為。但是，值得驕傲的是 PageRank 的思考方法并沒有停留在這個(gè)地方。
也就是說，不僅僅是通過反向鏈接數(shù)的多少，還給推薦度較高頁(yè)面的反向鏈接以較高的評(píng)價(jià)。同時(shí)，對(duì)來自總鏈接數(shù)少頁(yè)面的鏈接給予較高的評(píng)價(jià)，而來自總鏈接數(shù)多的頁(yè)面的鏈接給予較低的評(píng)價(jià)。 換句話說「(匯集著許多推薦的)好的頁(yè)面所推薦的頁(yè)面，必定也是同樣好的頁(yè)面」和「與感覺在被胡亂鏈接的鏈接相比，被少數(shù)挑選出的鏈接肯定是優(yōu)質(zhì)的鏈接」這兩種判斷同時(shí)進(jìn)行著。一方面，來自他人高水平網(wǎng)頁(yè)的正規(guī)鏈接將會(huì)被明確重視，另一方面，來自張貼有沒有關(guān)聯(lián)性的類似于書簽的網(wǎng)頁(yè)的鏈接會(huì)作為「幾乎沒有什么價(jià)值(雖然比起不被鏈接來說好一些)」而被輕視。
因此，如果從類似于 Yahoo! 那樣的 PageRank 非常高的站點(diǎn)被鏈接的話，僅此網(wǎng)頁(yè)的 PageRank 也會(huì)一下子上升；相反地，無論有多少反向鏈接數(shù)，如果全都是從那些沒有多大意義的頁(yè)面鏈接過來的話，PageRank 也不會(huì)輕易上升。不僅是 Yahoo!, 在某個(gè)領(lǐng)域中可以被稱為是有權(quán)威的(或者說固定的)頁(yè)面來的反向鏈接是非常有益的。但是，只是一個(gè)勁地在自己一些同伴之間制作的鏈接，比如像「單純的內(nèi)部照顧」這樣的做法很難看出有什么價(jià)值。也就是說，從注目于全世界所有網(wǎng)頁(yè)的視點(diǎn)來判斷(你的網(wǎng)頁(yè))是否真正具有價(jià)值。
綜合性地分析這些指標(biāo)，最終形成了將評(píng)價(jià)較高的頁(yè)面顯示在檢索結(jié)果的相對(duì)靠前處的搜索結(jié)構(gòu)。
以往的做法只是單純地使用反向鏈接數(shù)來評(píng)價(jià)頁(yè)面的重要性，但 PageRank 所采用方式的優(yōu)點(diǎn)是能夠不受機(jī)械生成的鏈接的影響。 也就是說，為了提高 PageRank 需要有優(yōu)質(zhì)頁(yè)面的反向鏈接。 譬如如果委托 Yahoo! 登陸自己的網(wǎng)站，就會(huì)使得 PageRank 驟然上升。但是為此必須致力于制作(網(wǎng)頁(yè)的)充實(shí)的內(nèi)容。這樣一來，就使得基本上沒有提高 PageRank 的近路(或后門)。不只限于PageRank (Clever 和 HITS 等也同樣)，在利用鏈接構(gòu)造的排序系統(tǒng)中，以前單純的 SPAM 手法將不再通用。這是最大的一個(gè)優(yōu)點(diǎn)，也是 Google 方便于使用的最大理由。(雖然是最大的理由,但并不是唯工一的理由。)
在這里請(qǐng)注意，PageRank 自身是由 Google 定量，而與用戶檢索內(nèi)容的表達(dá)式無關(guān)。就像后邊即將闡述的一樣，檢索語(yǔ)句不會(huì)呈現(xiàn)在 PageRank 自己的計(jì)算式上。不管得到多少的檢索語(yǔ)句，PageRank 也是一定的、文件固有的評(píng)分量。
PageRank 的定性說明大致就是這樣一些。但是，為了實(shí)際計(jì)算排列次序、比較等級(jí)，需要更定量性的討論。以下一章將做詳細(xì)的說明。
上一頁(yè) | 下一頁(yè)
3.怎樣求得 PageRank我們感興趣的是，在有像超級(jí)鏈接構(gòu)造那樣的互相參照關(guān)系的時(shí)候，定量地知道哪一個(gè)頁(yè)面是最「重要」的。換句話大膽地說，這個(gè)也就是嚴(yán)密計(jì)算「應(yīng)該從哪一頁(yè)開始讀取」這個(gè)指標(biāo)的過程。就算從誰(shuí)都不看的小頁(yè)面開始讀取也沒有辦法。
那么，一般地說為了使得像 Web 那樣的超級(jí)鏈接構(gòu)造能夠反映在在排列次序上，需要在計(jì)算機(jī)上建立超級(jí)鏈接構(gòu)造的數(shù)字模型。 怎么模型化需要取決于安裝者的方針?biāo)砸桓哦摚侨绻麘?yīng)用圖表理論來觀察超級(jí)鏈接構(gòu)造的話，最終常?；氐骄€形代數(shù)考慮方法上去。這對(duì)于 PageRank 也是一樣的。
計(jì)算方法的原理作為最基本的考慮方法，就是用行列陣的形式來表達(dá)鏈接關(guān)系。從頁(yè)面 i 鏈接到另一張頁(yè)面 j 的時(shí)，將其成分定義為1，反之則定義為 0 。即，行列陣 A 的成分 aij 可以用，
aij＝1 if (從頁(yè)面 i 向頁(yè)面 j 「 有 」 鏈接的情況) 0 if (從頁(yè)面 i 向頁(yè)面 j 「沒有」鏈接的情況)
來表示。文件數(shù)用 N 來表示的話，這個(gè)行列陣就成為 N×N 的方陣。這個(gè)相當(dāng)于在圖表理論中的「鄰接行列」。也就是說，Web 的鏈接關(guān)系可以看做是采用了鄰接關(guān)系有向圖表 S?？偠灾?，只要建立了鏈接，就應(yīng)該有鄰接關(guān)系。
(*注)由點(diǎn)和點(diǎn)連接的線構(gòu)成的圖形被稱為「圖表(graph)」。這些點(diǎn)被稱為「頂點(diǎn)(vertex)」或者「節(jié)點(diǎn)(node)」；這些線被稱為「邊(edge)」或者「弧(arc)」。圖表分為兩類，“邊”沒有方向的圖表被稱為「無向圖表(undirected graph)」，“邊”帶有方向的圖表被稱為「有向圖表(directed graph)」。把有向圖表想像成單向通行的道路就可以了。 圖表能用各種的方法來表示,但一般用在數(shù)據(jù)結(jié)構(gòu)上的是「鄰接行列(adjacency matrix)」和「鄰接列表(adjacency list)」。需要注意的是，如果是無向圖表，鄰接行列 A 就成為了對(duì)稱行列,而如果是有向圖表，A 就會(huì)成為不對(duì)稱行列。
以下是用位圖表示的 Apache
的在線手冊(cè)(共128頁(yè))的鄰接行列。當(dāng)黑點(diǎn)呈橫向排列時(shí)，表示這個(gè)頁(yè)面有很多正向鏈接(即向外導(dǎo)出的鏈接)；反之，當(dāng)黑店呈縱向排列時(shí)，表示這個(gè)頁(yè)面有很多反向鏈接。
鄰接行列的例子(采用了Apache 的在線手冊(cè))
PageRank 的行列陣是把這個(gè)鄰接行列倒置后(行和列互換)，為了將各列(column)矢量的總和變成 1 (全概率), 把各個(gè)列矢量除以各自的鏈接數(shù)(非零要素?cái)?shù))。這樣作成的行列被稱為「推移概率行列」，含有 N 個(gè)概率變量，各個(gè)行矢量表示狀態(tài)之間的推移概率。倒置的理由是，PageRank 并非重視「鏈接到多少地方」而是重視「被多少地方鏈接」。
PageRank 的計(jì)算，就是求屬于這個(gè)推移概率行列最大特性值的固有矢量(優(yōu)固有矢量)。
這是因?yàn)?，?dāng)線性變換系 t→∞ 漸近時(shí)，我們能夠根據(jù)變換行列的"絕對(duì)價(jià)值最大的特性值"和"屬于它的固有矢量"將其從根本上記述下來。換句話說，用推移概率行列表示的概率過程，是反復(fù)對(duì)這個(gè)行列進(jìn)行乘法運(yùn)算的一個(gè)過程，并且能夠計(jì)算出前方狀態(tài)的概率。
再者，雖然聽起來很難,但是求特性值和固有矢量的值是能夠嚴(yán)密分析的一種基礎(chǔ)的數(shù)學(xué)手段。我們能夠自由地給矢量的初始值賦值，但是因?yàn)椴粩嗟貙⑿辛邢喑?，得到的矢量卻會(huì)集中在一些特定數(shù)值的組合中。我們把那些穩(wěn)定的數(shù)值的組合稱為固有矢量，把固有矢量中特征性的標(biāo)量(scalar)稱為特性值，把這樣的計(jì)算方法總稱為分解特性值，把解特性值的問題稱為特性值問題。
(*注) 對(duì) N 次的正方行列 A 把滿足 Ax =λx 的數(shù) λ 稱為 A 的特性值，稱 x 為屬于 λ 的固有矢量。如果你怎么也不能適應(yīng)行列的概念的話，你也可以考慮 N×N 的二元排列就可以了。同時(shí)，也可以把矢量考慮成為長(zhǎng)度為 N 的普通的(一元)排列就可以了。 簡(jiǎn)單的例子
讓我們用簡(jiǎn)單的例子來試著逐次計(jì)算 PageRank 。首先考慮一下有像下圖表示那樣的鏈接關(guān)系的7個(gè)HTML文件。并且，這些HTML文件間的鏈接關(guān)系只是閉合于這1-7的文件中。也就是說，除了這些文檔以外沒有其他任何鏈接的出入。另外請(qǐng)注意，所有的頁(yè)面都有正向和反向鏈接(即沒有終點(diǎn))，這也是后面將提出的一個(gè)重要假定,在此暫且不深入探討。
表示頁(yè)面間互相鏈接關(guān)系的推移圖
首先，把這張推移圖圖表構(gòu)造的鄰接列表表示為排列式，就有以下式子。即，根據(jù)各個(gè)鏈接源ID列舉鏈接目標(biāo)的ID。
鏈接源I D 鏈接目標(biāo) ID 1 2,3 ,4,5, 7 3 1,2 4 2,3,5 5 1,3,4,6 6 1,5 7 5
以這個(gè)鄰接列表中所表示的鏈接關(guān)系的鄰接行列 A 是以下這樣的 7×7 的正方行列。一個(gè)僅有要素 0 和 1 位圖行列(bitmap matrix)。橫向查看第 i 行表示從文件 i 正向鏈接的文件ID。
A = [ 0, 1, 1, 1, 1, 0, 1; 1, 0, 0, 0, 0, 0, 0; 1, 1, 0, 0, 0, 0, 0; 0, 1, 1, 0, 1, 0, 0; 1, 0, 1, 1, 0, 1, 0; 1, 0, 0, 0, 1, 0, 0; 0, 0, 0, 0, 1, 0, 0; ]
PageRank 式的推移概率行列 M ，是將 A 倒置后將各個(gè)數(shù)值除以各自的非零要素后得到的。即以下這個(gè) 7×7 的正方行列。橫向查看第 i 行非零要素表示有指向文件 i 鏈接的文件ID(文件 i 的反向鏈接源)。請(qǐng)注意，各縱列的值相加的和為 1(全概率)。
M = [ 0, 1, 1/2, 0, 1/4, 1/2, 0; 1/5, 0, 1/2, 1/3, 0, 0, 0; 1/5, 0, 0, 1/3, 1/4, 0, 0; 1/5, 0, 0, 0, 1/4, 0, 0; 1/5, 0, 0, 1/3, 0, 1/2, 1; 0, 0, 0, 0, 1/4, 0, 0; 1/5, 0, 0, 0, 0, 0, 0; ]
表示 PageRank 的矢量 R (各個(gè)的頁(yè)面的等級(jí)數(shù)的隊(duì)列)，存在著 R = cMR 的關(guān)系(c 為定量)。在這種情況下，R 相當(dāng)于線形代數(shù)中的固有矢量，c 相當(dāng)于對(duì)應(yīng)特性值的倒數(shù)。為了求得 R ，只要對(duì)這個(gè)正方行列 M 作特性值分解就可以了。
在分解特性值時(shí)有相應(yīng)的各種各樣的數(shù)值分析法,但是本文將不在這里對(duì)各種方法詳細(xì)說明，請(qǐng)讀者自己去閱讀一本恰當(dāng)?shù)慕炭茣?在你的暑假里一定有這么一本被埋沒的教科書)。在此，我們就暫且使用決 GNU Octave 這個(gè)計(jì)算程序?qū)嶋H計(jì)算一下特性值和固有矢量。
(*注) GNU Octave ，是支持?jǐn)?shù)值計(jì)算，類似于描述性出色的 MATLAB 的編程語(yǔ)言。擴(kuò)展后的處理語(yǔ)言更適合于行列演算,但基本上和C語(yǔ)言的語(yǔ)風(fēng)相像，因此可讀性很高。詳細(xì)請(qǐng)參照 http://www.octave.org/。 當(dāng)然，除了Octave以外 MATLAB 和 Scilab 也是非常不錯(cuò)的語(yǔ)言，但是根據(jù) GPL, Octave 是最容易得到的。
下面我們舉一個(gè)實(shí)際例子。如果不太明白以下例子在做什么的話，只要認(rèn)為我們能夠使用 Octave 這個(gè)程序來解特性值問題即可。
首先，使用恰當(dāng)?shù)木庉嬈髦谱饕韵?Octave 腳本。(在行尾加上分號(hào)就能消去多余的結(jié)果輸出，不過，此次為了說明特意去掉了。)
% cat pagerank.m #!/usr/bin/octave ## pagerank.m - 計(jì)算 PageRank(TM) 用的簡(jiǎn)單的 GNU Octave 腳本 ##設(shè)置計(jì)時(shí)器。 tic(); ## 根據(jù)PageRank 的定義，將從文件 i 鏈接到文件 j 的鏈接狀態(tài)的推移概率行列定義為 M(i,j) M = [ 0, 1, 1/2, 0, 1/4, 1/2 , 0; 1/5, 0, 1/2, 1/3, 0, 0, 0; 1/5, 0, 0, 1/3, 1/4, 0, 0; 1/5, 0, 0, 0, 1/4, 0, 0; 1/5, 0, 0, 1/3, 0, 1/2, 1; 0, 0, 0, 0, 1/4, 0, 0; 1/5, 0, 0, 0, 0, 0, 0; ##計(jì)算 全部 M 的特性值和固有矢量列的組合。 [V，D]= eig(M) ## 保存與絕對(duì)價(jià)值最大的特性值對(duì)應(yīng)的固有矢量到EigenVector。 EigenVector = V(:, find(abs(diag(D))==max(abs(diag(D))))) ## PageRank 是將 EigenVector 在概率矢量上標(biāo)準(zhǔn)化后得到的值。 PageRank = EigenVector．/ norm(EigenVector,1) ## 輸出計(jì)算時(shí)間。 elapsed_time = toc()
(2003/7/23: 修正上述腳本的錯(cuò)誤。)
誤: EigenVector = V(:, find(max(abs(diag(D)))) ) 正: EigenVector = V(:, find(abs(diag(D))== max(abs(diag(D)))))
用 Octave 運(yùn)行這個(gè) pagerank.m 腳本后在標(biāo)準(zhǔn)輸出中得到以下結(jié)果。
% octave pagerank.m GNU Octave, version 2.0.16 (i586-redhat-linux-gnu). Copyright (C) 1996, 1997, 1998, 1999, 2000 John W. Eaton. This is free software with ABSOLUTELY NO WARRANTY. For details, type `warranty'.
0.00000 1.00000 0.50000 0.00000 0.25000 0.50000 0.00000 0.20000 0.00000 0.50000 0.33333 0.00000 0.00000 0.00000 0.20000 0.00000 0.00000 0.33333 0.25000 0.00000 0.00000 0.20000 0.00000 0.00000 0.00000 0.25000 0.00000 0.00000 0.20000 0.00000 0.00000 0.33333 0.00000 0.50000 1.00000 0.00000 0.00000 0.00000 0.00000 0.25000 0.00000 0.00000 0.20000 0.00000 0.00000 0.00000 0.00000 0.00000 0.00000 Columns 1 through 3: 0.69946 + 0.00000i 0.63140 + 0.00000i 0.63140 + 0.00000i 0.38286 + 0.00000i -0.28715 + 0.15402i -0.28715 - 0.15402i 0.32396 + 0.00000i -0.07422 - 0.10512i -0.07422 + 0.10512i 0.24297 + 0.00000i 0.00707 - 0.24933i 0.00707 + 0.24933i 0.41231 + 0.00000i -0.28417 + 0.44976i -0.28417 - 0.44976i 0.10308 + 0.00000i 0.22951 - 0.13211i 0.22951+ 0.13211i 0.13989 + 0.00000i -0.22243 - 0.11722i -0.22243 + 0.11722i Columns 4 through 6: 0.56600 + 0.00000i 0.56600 + 0.00000i -0.32958 + 0.00000i 0.26420 - 0.05040i 0.26420 + 0.05040i 0.14584 + 0.00000i -0.10267 + 0.14787i -0.10267- 0.14787i 0.24608 + 0.00000i -0.11643 + 0.02319i -0.11643 - 0.02319i -0.24398+ 0.00000i -0.49468 - 0.14385i -0.49468 + 0.14385i 0.42562 + 0.00000i -0.14749+ 0.38066i -0.14749 - 0.38066i -0.64118 + 0.00000i 0.03106 - 0.35747i 0.03106+ 0.35747i 0.39720 + 0.00000i Column 7: 0.00000 + 0.00000i -0.40825 + 0.00000i -0.00000 + 0.00000i 0.00000 + 0.00000i -0.00000 + 0.00000i 0.81650 + 0.00000i -0.40825 + 0.00000i Columns 1 through 3: 1.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i -0.44433 + 0.23415i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i -0.44433 - 0.23415i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i Columns 4 through 6: 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.02731 + 0.31430i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.02731 - 0.31430i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i -0.16595 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i Column 7: 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i 0.00000 + 0.00000i -0.00000 + 0.00000i EigenVector = 0.69946 0.38286 0.32396 0.24297 0.41231 0.10308 0.13989 PageRank = 0.303514 0.166134 0.140575 0.105431 0.178914 0.044728 0.060703 elapsed_time = 0.063995
Octave 的輸出中，特性值被表示為對(duì)角行列 D 的對(duì)角成分，各個(gè)特性值相對(duì)應(yīng)的固有矢量被表示為行列 V 對(duì)應(yīng)列的列矢量。也就是說 M * V = D * M 成立。 如果包含復(fù)數(shù)特性值的話這里的特性值有7個(gè),其中絕對(duì)價(jià)值最大的特性值 λ 是λ=1。與之相對(duì)應(yīng)的固有矢量為實(shí)矢量：
EigenVector = 0.69946 0.38286 0.32396 0.24297 0.41231 0.10308 0.13989
即行列 V 的第1列。請(qǐng)注意，這個(gè)求得的固有矢量中概率矢量(要素的和等于1的 N 次元非負(fù)矢量)沒有被標(biāo)準(zhǔn)化，只是矢量的「大小」等于 1。 用算式來表達(dá)就是，Σpi ≠1 ，Σ(pi)2＝1。 在這里，對(duì)概率矢量進(jìn)行標(biāo)準(zhǔn)化
PageRank = 0.303514 0.166134 0.140575 0.105431 0.178914 0.044728 0.060703
PageRank 就是排位了。 注意，全部相加的和為 1。 計(jì)算只用了0.064秒。
求得的 PageRank 的評(píng)價(jià)將 PageRank 的評(píng)價(jià)按順序排列 (PageRank 小數(shù)點(diǎn)3位四舍五入)。
名次 PageRank 文件ID 發(fā)出鏈接ID 被鏈接ID 1 0.304 1 2,3,4,5,7 2,3,5,6 2 0.179 5 1,3,4,6 1,4,6,7 3 0.166 2 1 1,3,4 4 0.141 3 1,2 1,4,5 5 0.105 4 2,3,5 1,5 6 0.061 7 5 1 7 0.045 6 1,5 5
首先應(yīng)該關(guān)注的是，PageRank 的名次和反向鏈接的數(shù)目是基本一致的。無論鏈接多少正向鏈接都幾乎不會(huì)影響 PageRank，相反地有多少反向鏈接卻是從根本上決定 PageRank 的大小。但是，僅僅這些并不能說明第1位和第2位之間的顯著差別(同樣地、第3位和第4位，第6位和第7位之間的差別)?？傊?，絕妙之處在于 PageRank 并不只是通過反向鏈接數(shù)來決定的。
讓我們?cè)敿?xì)地看一下。ID=1 的文件的 PageRank 是0.304，占據(jù)全體的三分之一，成為了第1位。特別需要說明的是，起到相當(dāng)大效果的是從排在第3位的 ID=2 頁(yè)面中得到了所有的 PageRank(0.166)數(shù)。ID=2頁(yè)面有從3個(gè)地方過來的反向鏈接，而只有面向 ID=1頁(yè)面的一個(gè)鏈接，因此(面向ID=1頁(yè)面的)鏈接就得到了所有的 PageRank 數(shù)。不過，就因?yàn)? ID=1頁(yè)面是正向鏈接和反向鏈接最多的頁(yè)面，也可以理解它是最受歡迎的頁(yè)面吧。
反過來，最后一名的 ID=6 頁(yè)面只有 ID=1 的15％的微弱評(píng)價(jià),這可以理解為是因?yàn)闆]有來自 PageRank 很高的 ID=1 的鏈接而使其有很大地影響。 總之，即使有同樣的反向鏈接的數(shù)目，鏈接源頁(yè)面評(píng)價(jià)的高低也影響 PageRank 的高低。
表示頁(yè)面互相的鏈接關(guān)系的推移圖(加入了PageRank)
實(shí)際地試著計(jì)算一下PageRank的收支。因?yàn)棣?1所以計(jì)算很簡(jiǎn)單，只要將自各頁(yè)的流入量單純相加即可。譬如 ID=1 的流入量為，
流入量＝(ID=2發(fā)出的Rank)+(ID=3發(fā)出的Rank)+(ID=5發(fā)出的Rank)+(ID=6發(fā)出的Rank) = 0.166+0.141/2+0.179/4+0.045/2 = 0.30375
在誤差范圍內(nèi)PageRank的收支相符合。其他頁(yè)面ID的情況也一樣。以上的 PageRank 推移圖正表示了這個(gè)收支。沿著各自的鏈接發(fā)出的PageRank等于此頁(yè)面原有的PageRank除以發(fā)出鏈接數(shù)的值，而且和各自的頁(yè)面的PageRank收支相平衡。
不過，這樣絕妙均衡的本身，對(duì)理解線形代數(shù)的人來說當(dāng)然不會(huì)是讓人驚訝的事情。因?yàn)檫@正是「特性值和固有矢量的性質(zhì)」，總之這樣被選的數(shù)值的組就是固有矢量。但即使是這樣，實(shí)際試著確認(rèn)一下的話，已經(jīng)能夠很好地使用PageRank的方法來考慮了。
以上就是 PageRank 的基本原理。 Google 做的就是大規(guī)模地處理這樣的非常特性值問題。
上一頁(yè) | 下一頁(yè)
4.實(shí)際應(yīng)用時(shí)的問題PageRank 的基本考慮方法并不是很難的東西。實(shí)用效果中的巨大成分并不是復(fù)雜離奇的算法，而是進(jìn)行簡(jiǎn)單的線性變換，倒不如都屬于簡(jiǎn)明直觀的類別吧。但是，實(shí)際使用 Web 超級(jí)鏈接構(gòu)造來計(jì)算 PageRank 的話，不是簡(jiǎn)單地能夠用嘴巴來說明的東西。主要的困難主要有二個(gè)。一、由來于純粹假設(shè)的數(shù)值模型和現(xiàn)實(shí)世界的不同；二，在實(shí)際數(shù)值計(jì)算上(專門技術(shù)的)困難。
準(zhǔn)備:數(shù)學(xué)用語(yǔ)(主要概率過程)的解說推移概率行列和概率過程上的馬爾可夫過程存在很深的關(guān)系。本章先離開與 PageRank 本身的說明，預(yù)先說明幾個(gè)呈現(xiàn)在概率過程上的數(shù)學(xué)用語(yǔ)。因?yàn)闀?huì)設(shè)計(jì)相當(dāng)難的部分，如果不能夠理解也可以跳過這里。(也可能是我的說明方法不好) 同時(shí)，請(qǐng)注意這里幾乎沒有證明就直接使用了。詳細(xì)的解說請(qǐng)閱讀教科書。
從有向圖表S的狀態(tài) i 出發(fā)，將有限時(shí)間之后再次回復(fù)到狀態(tài) i 的概率作為 1 時(shí)，也就是說，當(dāng)沿著(有向)圖表的方向前進(jìn)能夠回到原來位置的路徑存在的時(shí)候，i 就被成為「回歸」。不能回歸的狀態(tài)被稱為「非回歸」。從狀態(tài) i 出發(fā)，當(dāng)通過有限次數(shù)的推移達(dá)到狀態(tài) j 的概率非負(fù)的時(shí)候，我們就說「從狀態(tài) i 到達(dá)狀態(tài) j 是可能的」。當(dāng)反方向也可能到達(dá)的時(shí)候，我們稱「i 和 j 互相可能到達(dá)」。從狀態(tài) i 不能到達(dá)其他任何狀態(tài)的時(shí)候，稱 i 為「吸收狀態(tài)」。
從鄰接行列 A 所決定的圖表(graph)的任意頂點(diǎn)出發(fā)，指向其他任意的頂點(diǎn)圖表的路徑能夠像箭頭那樣到達(dá)時(shí)被稱為「強(qiáng)聯(lián)結(jié)」( 也被稱為「分解不能」)。強(qiáng)聯(lián)結(jié)，等價(jià)于從任意狀態(tài)到任意狀態(tài)可以互相到達(dá)。鄰接行列 A 的成分中有很多 0 時(shí)，強(qiáng)聯(lián)結(jié)性就會(huì)有問題。注意，如果全部成分都為 aij ≠0 的話，則都屬于強(qiáng)聯(lián)結(jié)。因?yàn)?，?duì)應(yīng)的 馬爾可夫鏈的樣本路徑表示 S 的任意兩點(diǎn)間以正的概率來往通行。
我們可以把全體狀態(tài)以等價(jià)類(或者回歸類)來劃分。在這里，回歸類是指鏈接所圍成的范圍。屬于一個(gè)等價(jià)類的狀態(tài)可以互相到達(dá)。從一個(gè)類出發(fā)以正的概率進(jìn)入到其他的類的可能性也是存在的?？墒呛苊黠@，在這種情況下不可能回復(fù)到原來的類。不然的話，這兩個(gè)類就歸于等價(jià)類了。下圖表示了，當(dāng) T 作為非回歸性的等價(jià)類、R 作為回歸性等價(jià)類時(shí),雖然存在 馬爾可夫鏈 既不來自回歸類，也不來自非回歸類的情況，但如果一旦來自前兩者的話，就不再會(huì)回到非回歸類中了。
回歸、非回歸示意圖(修改了小谷(1997)的圖11.1)
這個(gè)等價(jià)關(guān)系中只有一個(gè)回歸類的時(shí)候，那個(gè) 馬爾可夫鏈就被稱為「最簡(jiǎn)」。換句話說，全部的狀態(tài)之間互相可以到達(dá)時(shí)就被稱為最簡(jiǎn)。最簡(jiǎn)時(shí)都是強(qiáng)聯(lián)結(jié)。
互相沒有關(guān)聯(lián)的鄰接行列(或推移概率行列)，乘以恰當(dāng)?shù)闹脫Q行列(掉換行和列)以后得到
P = | P1 0 | | 0 P2 |
這樣的關(guān)系。這表示回歸類 P1 和 P2 間不存在直接的鏈接關(guān)系。
回歸類、非回歸類摻雜在一起的鄰接行列(或推移概率行列)，乘以恰當(dāng)?shù)闹脫Q行列后得到，
P = | P1 0 | | Q P2 |
這樣的關(guān)系(Q≠0)。此時(shí)，P1是非回歸類，P2是回歸類。
推移概率行列有時(shí)也被稱作馬爾可夫行列。稱馬爾可夫過程的試驗(yàn)行列的觀測(cè)結(jié)果為馬爾可夫鏈(Markov chain)。 當(dāng)經(jīng)過相當(dāng)?shù)臅r(shí)間后馬爾可夫鏈會(huì)趨向某種平衡狀態(tài)。對(duì)任意的狀態(tài) i, 如果 j 是非回歸狀態(tài)，則 Pij(n)→0。相反，當(dāng) i 為非回歸、j 為回歸時(shí)，停留在狀態(tài) i 上著的概率是0。如果 i，j 屬于同樣的非周期性回歸類的話，Pij(n)→Pj≥0。
定理:若 P 是有限馬爾可夫行列的話，P 的特性值 1 的重復(fù)度等于 P 決定的回歸類的數(shù)目。(證明太長(zhǎng)，省略)。
跟隨著推移概率行列的有向圖表的最大強(qiáng)聯(lián)結(jié)成分(與之對(duì)應(yīng)的狀態(tài)的集合)被稱為Ergodic部分(歷遍部分)，此外的強(qiáng)聯(lián)結(jié)成分被稱為消散部分。因?yàn)闊o論從怎樣的初期狀態(tài)概率 x(0)開始，經(jīng)過時(shí)間 n 后 x(n) = P(n)x(0)，所以屬于消散部分的狀態(tài)概率幾乎接近于0。關(guān)于EllGoth部分，連同與各聯(lián)結(jié)成分對(duì)應(yīng)狀態(tài)的類、像獨(dú)立的最簡(jiǎn)的馬爾可夫鏈一樣行動(dòng)，其中，各類中的狀態(tài)概率(即從過去開始的平均值)的值和初期狀態(tài)概率無關(guān)，換言之，是近似于與對(duì)應(yīng) P 的最簡(jiǎn)成分的固有矢量成比例的東西。在類之間概率的分配依存于初期狀態(tài)的概率。
離散時(shí)間型馬爾可夫鏈的不變分布是屬于極限分布，從那個(gè)分布開始已經(jīng)不是在分布意義上的隨時(shí)間的變化了。狀態(tài)的概率分布在時(shí)間變化時(shí)也不會(huì)變化時(shí)被稱為固定分布。PageRank 用馬爾可夫過程來說就是，PageRank就是以一定時(shí)間內(nèi)用戶隨機(jī)地沿著(網(wǎng)頁(yè))鏈接前進(jìn)時(shí)對(duì)各個(gè)頁(yè)面訪問的固定分布。
假想模型和現(xiàn)實(shí)世界的不同那么，讓我們將概率過程(即圖表原理)的考慮方法和實(shí)際的網(wǎng)頁(yè)鏈接構(gòu)造合起來看一看。
對(duì)于剛才舉例的假想網(wǎng)頁(yè)群來說，只要相互順著鏈接前進(jìn)則在彼此頁(yè)面間必定有相互鏈接的關(guān)系。即，有向圖表是強(qiáng)聯(lián)結(jié)的行列既是回歸又是最簡(jiǎn)。像上面舉的很多的概率過程的教科書一樣，許多證明都是把回歸和最簡(jiǎn)作為前提來證明的，如果是最簡(jiǎn)的話，各種各樣的性質(zhì)就變得容易說了。
但是現(xiàn)實(shí)的網(wǎng)頁(yè)并不是強(qiáng)聯(lián)結(jié)。也就是說鄰接行列不是最簡(jiǎn)的。具體來說，順著鏈接前進(jìn)的話，有時(shí)會(huì)走到?jīng)]有向外鏈接的網(wǎng)頁(yè)。通常這樣的情況，只有利用 web 瀏覽器的「返回」功能了。如果人們只是瀏覽而已的話，一切就到此結(jié)束了，然而 PageRank 的計(jì)算卻不能到此結(jié)束。因?yàn)镻ageRank 一旦被引入以后是不能返回的。Pagerank 稱這種頁(yè)面為為「dangling page」。同樣道理，只有向外的鏈接而沒有反向鏈接的頁(yè)面也是存在的。但 Pagerank 并不考慮這樣的頁(yè)面,因?yàn)闆]有流入的 PageRank 而只流出的 PageRank，從對(duì)稱性來考慮的話必定是很奇怪的。
同時(shí)，有時(shí)候也有鏈接只在一個(gè)集合內(nèi)部旋轉(zhuǎn)而不向外界鏈接的現(xiàn)象。這是非周期性的回歸類多重存在時(shí)可能出現(xiàn)的問題。(請(qǐng)讀者考慮一下陷入上圖中一個(gè) R 中而不能移動(dòng)到別的 R 和 T 的情況)。 Pagerank 稱之為「rank sink」。在現(xiàn)實(shí)中的頁(yè)面，無論怎樣順著鏈接前進(jìn)，僅僅順著鏈接是絕對(duì)不能進(jìn)入的頁(yè)面群總歸存在，也就是說，這些頁(yè)面群是從互相沒有關(guān)聯(lián)的多數(shù)的同值類(回歸類)形成的。
總之，由現(xiàn)實(shí)的 Web 頁(yè)組成的推移概率行列大部分都不是最簡(jiǎn)的。當(dāng)不是最簡(jiǎn)時(shí)，最大特性值(即1)是重復(fù)的，并且不能避免優(yōu)固有矢量多數(shù)存在的問題。換句話說，PageRank 并不是從一個(gè)意義上來決定的。
在此，Pagerank 為了解決這樣的問題，考慮了一種「用戶雖然在許多場(chǎng)合都順著當(dāng)前頁(yè)面中的鏈接前進(jìn),但時(shí)常會(huì)跳躍到無關(guān)的頁(yè)面里」,這樣的瀏覽模型。再者，將「時(shí)?！构潭? 15％ 來計(jì)算。用戶在 85％ 的情況下沿著鏈接前進(jìn),但在 15％ 的情況下會(huì)突然跳躍到無關(guān)的頁(yè)面中去。(注:Pagerank 的原始手法是各自87％(＝1/1.15 )和13％(＝0.15/1.15)。)
將此用算式來表示的話得到以下公式。
M'= c*M +(1-c)*[1/N]
其中，[1/N]是所有要素為 1/N 的 N次正方行列，c =0.85(=1-0.15)。M'當(dāng)然也同樣是推移概率行列了。也就是說，根據(jù) Pagerank 的變形，原先求行列 M 的特性值問題變成了求行列 M'的優(yōu)固有矢量特性值問題。M 是固定無記憶信息源(i.i.d.)時(shí)，M'被稱為「混合信息源」，這也就是固定但非ellGoth信息源的典型例子。
如果從數(shù)學(xué)角度看，「把非最簡(jiǎn)的推移行列最簡(jiǎn)化」操作的另外一種說法就是「把不是強(qiáng)聯(lián)結(jié)的圖表變成強(qiáng)聯(lián)結(jié)」的變換操作。所謂對(duì)全部的要素都考慮0.15的遷移概率，就是意味著將原本非最簡(jiǎn)的推移概率行列轉(zhuǎn)換為最簡(jiǎn)并回歸的（當(dāng)然非負(fù)的情況也存在）推移概率行列。針對(duì)原本的推移概率行列，進(jìn)行這樣的變換操作的話，就能從一個(gè)意義上定義 PageRank、也就是說能保證最大特性值的重復(fù)度為1。如果考慮了這樣的變換操作的話，因?yàn)橥埔聘怕市辛械幕貧w類的數(shù)目變成 1 的同時(shí)也最簡(jiǎn)化，根據(jù)前面的定理，優(yōu)固有矢量(即 PageRank)就被從一個(gè)意義上定義了。
數(shù)值計(jì)算上的問題點(diǎn)(其1)在此，只要大概明白 PageRank 的概念就可以了，不需要很深的陷入數(shù)值計(jì)算上的技術(shù)的問題中(其實(shí)，筆者自己即使有自信也說不清楚)。但是，因?yàn)樘匦灾捣治龊吐?lián)立一次方程式分析一樣，是利用在各種的統(tǒng)計(jì)分析中重要的數(shù)值計(jì)算手法的一中，所以這里我們簡(jiǎn)單的觸及一些分析方法。
主記憶領(lǐng)域的問題是在數(shù)值計(jì)算上的問題之一。
假設(shè) N 是 104 的 order。通常，數(shù)值計(jì)算程序內(nèi)部行列和矢量是用雙精度記錄的，N 次正方行列 A 的記憶領(lǐng)域?yàn)? sizeof(double)* N * N =8 *104 * 104＝800MB。 800MB 的主記憶領(lǐng)域不是那種經(jīng)常會(huì)擁有的東西, 雖然這么說也非那種不可能的數(shù)字。但是，N 如果變成 105 或106 的話，各自就變成80GB,8TB。這樣的話不用說內(nèi)存就連硬盤也已經(jīng)很困難了。 Google 從處理著10億以上的頁(yè)面(2001年時(shí))以來，就知道這種規(guī)矩的做法已經(jīng)不適用了。
不過，A 只是稀疏(sparse)行列。因?yàn)榧词褂幸徊糠值捻?yè)面拼命地進(jìn)行鏈接，但是向整個(gè)Web展開鏈接的頁(yè)面是沒有的，即使有也是極為稀少的。平均一下，每一張頁(yè)面有10-20個(gè)左右的鏈接(根據(jù) IBM Almaden 研究所'Graph structure in the web' 的統(tǒng)計(jì)，平均在16.1個(gè)左右)。因此，我們可以采用恰當(dāng)?shù)膲嚎s方法來壓縮 A 。 N 即使是 106 時(shí)，如果平均鏈接數(shù)是10，最終的記憶領(lǐng)域只要 80MB，從規(guī)模上來說可以收納到合理的數(shù)字里。
稀疏行列的容納方式當(dāng)今已經(jīng)被充分地研究(有限要素法的解法等)，在恰當(dāng)?shù)臄?shù)值計(jì)算的專業(yè)書中就可以學(xué)到。雖然這么說，因?yàn)橄喈?dāng)?shù)仉y解還是需要很復(fù)雜的手法。但想指出的是如果可以很好的解決的話，并列化的高速計(jì)算(也許)就變得可能了。因?yàn)楸绕鹪鯓优帕胁⑷菁{非零要素來說，計(jì)算性能和并列性能對(duì)其的影響會(huì)更大。 數(shù)值計(jì)算上的問題點(diǎn)(其2)
另一個(gè)是收斂問題。
固定方程式
xi＝ΣAijxi
是 N 元的聯(lián)立一次方程式，一般地不能得到分析解，所以只能解其數(shù)值。剛才舉的例子中為了求特性值和固有矢量，使用了 Octave 的 eig()函數(shù), 不過，這個(gè)在問題小的時(shí)候不能適用。說起來，并不需要計(jì)算全部的特性值/固有矢量。
求最大特性值和屬于它的固有矢量(優(yōu)固有矢量)的數(shù)值計(jì)算手法中，一般使用「冪乘法」(也叫反復(fù)法)。這是指，取適當(dāng)初期矢量 x0 ，當(dāng) x(n+1) = A y(n) (其中 y(n) = x(n) / c(n) )中的 n →∞ 時(shí)，x 向擁有最大特性值的固有矢量收斂的同時(shí) c 向此最大特性值收斂的利用線形代數(shù)性質(zhì)的計(jì)算方法(證明請(qǐng)參照線形代數(shù)的教科書)。冪乘法(反復(fù)法)的特長(zhǎng)與逐次反復(fù)計(jì)算的近似法比，能夠改善解矢量的問題。它的優(yōu)點(diǎn)是，因?yàn)橹灰磸?fù)對(duì)行列和矢量進(jìn)行適當(dāng)次數(shù)的乘法運(yùn)算，所以只要通過程序就能夠簡(jiǎn)單地解決，并且還可以進(jìn)行由于受到內(nèi)存和硬盤的限制通過直接法不能解決的大規(guī)模分析。這是許多的實(shí)用算法的出發(fā)點(diǎn)。
在這里，請(qǐng)注意從線形代數(shù)的簡(jiǎn)單定理(Peron-Frobenius定理)得到推移概率行列的絕對(duì)價(jià)值的最大特性值是1。如果采用了這個(gè)，就會(huì)使得反復(fù)法的 PageRank 的計(jì)算變得更容易。即，因?yàn)樽畲筇匦灾凳羌戎模绕鹎鬂M足 Ax=x 的矢量 x來說 ，變成更加簡(jiǎn)單的問題了。這雖然是很細(xì)小的地方但是很重要。首先，可以去掉比較花費(fèi)成本的除法計(jì)算 (y(n)=x(n)/c(n))不用完成。如果是反復(fù)法的話，不能得到很高的精確度，并且如果搞錯(cuò)了加速方法的話，計(jì)算出的不是是最大特性值而是第二大特性值和屬于它的固有矢量(雖然這種情況很少，但是說不定就是從根本上錯(cuò)誤的值)。但如果知道了最大特性值，就可以進(jìn)行核對(duì)了。在 Pagerank 的第一篇論文中他們似乎沒有注意到這個(gè)事情,但在 Haveliwala 的第二論文中增加了關(guān)于此的修正。
反復(fù)的次數(shù)取決于想要求的精度。也就是說,想要求的精度越高，反復(fù)的次數(shù)就越多?？墒牵瑑绯朔?反復(fù)法)的誤差的收斂比與系數(shù)行列的譜段特性(特性值的絕對(duì)值分布)有很強(qiáng)的依存關(guān)系。具體地說，絕對(duì)值最大的特性值用λ1表示，第二位用 λ2 表示，優(yōu)越率(收斂率 probability of dominance)為 d =λ1/λ2 話，可以知道d離1越近收斂就變得越慢。在 N 很大的情況時(shí)d當(dāng)然離1很近。這是因?yàn)?，絕對(duì)值最大的特性值是1，而其他所有的 N-1 個(gè)特性值的絕對(duì)值都比1小。但是，N-1個(gè)特性值之間非常的擁擠，所以λ1和λ2 之間幾乎沒有差別。因此一般來說，收斂會(huì)變慢。
所謂收斂變慢，嚴(yán)密地說，就是無論經(jīng)過多少時(shí)間也完成不了的計(jì)算。對(duì)此，為了使收斂加快的適當(dāng)?shù)募铀俜椒ㄒ彩谴嬖诘模瑧?yīng)用這些方法時(shí)，需要對(duì)數(shù)值計(jì)算技術(shù)有十二分的理解，因此如果不是數(shù)值計(jì)算的專家就很難引入。
上一頁(yè) | 下一頁(yè)
5. Namazu 上的實(shí)際安裝實(shí)驗(yàn)為了使更簡(jiǎn)單地推測(cè)上文描述的問題，PageRank 并不是非世界所有的web頁(yè)面而不能使用的考慮方法，即使是個(gè)人的利用方法也能實(shí)現(xiàn)。為了實(shí)現(xiàn)「Personalized PageRank」，針對(duì)在各種 UNIX 和 Windows 上運(yùn)作的中小規(guī)模網(wǎng)站適用的全文檢索系統(tǒng) Namazu 進(jìn)行了實(shí)際安裝實(shí)驗(yàn)。(關(guān)于Namazu可參考 日語(yǔ)全文檢索引擎軟件列表。)
由于實(shí)驗(yàn)?zāi)芎?jiǎn)單地控制內(nèi)存的使用量，并將最大特性值用1來考慮，所以將 Have liwala(1999)的想法做為基本的考慮方法。但是對(duì) dangling pages 的處理有少許不同。固有矢量的計(jì)算內(nèi)核使用了數(shù)值計(jì)算腳本 GNU Octave。所以基本的代碼編寫自己只用了一天就解決了。另外，從用 mknmz 編寫的索引不能直接計(jì)算 PageRank，而要事前準(zhǔn)備表示鄰接關(guān)系的索引(鄰接列表)。這個(gè)也有可能被編入檢索者(Indexer)的主要部分。
以下表示了實(shí)際計(jì)算時(shí)間(單位：秒)。運(yùn)行機(jī)器的配置為 PentiumII 400MHz x 2,內(nèi)存512MB，Kondara MNU/Linux 1.2的(kernel-2.2 .17-15ksmp)，Octave-2.0.16(一般狀態(tài)分發(fā)物)。收斂精度(剩余差矢量的L1規(guī)范)取了到1.0e-10,也許有些過分精確了。
文書數(shù)N mknmz時(shí)間 準(zhǔn)備時(shí)間 PageRank計(jì)算時(shí)間 ============================================================ 128 58 2 6 2,301 1, 575 46 214 49,604 15,975 478 5,872
因?yàn)闆]用一些巨大的web頁(yè)群來做測(cè)試，所以實(shí)驗(yàn)只停留在小規(guī)模的基礎(chǔ)上。雖然有這個(gè)難點(diǎn),但從基本上可以了解與索引所花的時(shí)間相比，在很短的時(shí)間里就可以計(jì)算 PageRank 的傾向吧。
因?yàn)?Namazu 自身中也有很多難題，所以并不寄予很大的奢望，但至少使用 105 程度(盡可能 106)規(guī)模的web頁(yè)面群來實(shí)驗(yàn)。從趨勢(shì)來看可以預(yù)想 N=106 的計(jì)算時(shí)間恐怕會(huì)發(fā)散開去，所以在 N=106 時(shí)，若是能夠討論把mknmz時(shí)間變成和comparable一樣的加速方法的話，對(duì)于Personalized PageRank 來說就十分實(shí)用了。作為參考，根據(jù)Page et al.(1998)，Google 對(duì)7500萬的URL的實(shí)際 PageRank 計(jì)算時(shí)間約是5小時(shí)。(2001年2月現(xiàn)在不明)。從這個(gè)角度來說，研究更加高效的加速法的余地就十分得必要了吧。
計(jì)算實(shí)際運(yùn)行時(shí)的使用內(nèi)存最大也是10幾MB左右。如果是Haveliwala (1999)那樣的「吝嗇地作戰(zhàn)」的話，最大只有O(3N+2)左右的內(nèi)存使用量就做完了,不過 N 是 104-5 程度和內(nèi)存的使用量連 N2 也放不進(jìn)的話，其他的也只能勉強(qiáng)調(diào)諧了，所以以 O(5N+α) (α是疏松行列的非零成分?jǐn)?shù)字，典型的是5-20N左右) 程度來編寫代碼。另外 N 是103 左右時(shí)，可以確認(rèn)不壓縮疏松行列就在內(nèi)存上使用冪乘法來計(jì)算，從速度面上來說是非常有利的。實(shí)測(cè)時(shí)速度為上述數(shù)字的6-7倍左右的。但遺憾的是，這個(gè)方法從內(nèi)存的限制來看，盡可能地只使用2-3千頁(yè)以內(nèi)。
此次我們使用了 Octave 分發(fā)附屬的「Tsurushi」,不過，正像大家知道的那樣，如果把 Octave 調(diào)諧的好的話，會(huì)戲劇性地提高完成的速度。Octave-2.1.x 和 ATLAS 的組合有時(shí)候根據(jù)情況甚至?xí)勾笠?guī)模行列乘法的運(yùn)算速度提高10倍以上。
實(shí)驗(yàn)的詳細(xì)結(jié)果請(qǐng)參照prnmz-1.0.tar.gz 中的文檔。
Personalized PageRank 的基本性質(zhì)人們經(jīng)常會(huì)利用 MHonArc、latex2html 或者 PowerPoint 這樣的工具將文檔變成 HTML，針對(duì)這樣的人工制作的HTML鏈接群求 PageRank 的話，大部分頁(yè)面的得分幾乎都是一樣的(～1/N)。如果考慮鄰接行列，則大部分的成分是1，或者對(duì)角成分附近全部是1。因?yàn)檫@樣的推移概率行列的固有矢量成為(1,1,…,1)。
或是象 sitemap.html 一樣變成樹狀的情況下，分?jǐn)?shù)會(huì)集中在sitemap.html中。就算占據(jù)全體的9成也不算新奇。
從現(xiàn)在起能說的是，為了計(jì)算有意義的 PageRank，要盡可能地排除機(jī)械生成的鏈接關(guān)系。如果把鏈接關(guān)系看做是推薦關(guān)系的話更加容易認(rèn)同了吧。
上一頁(yè) | 下一頁(yè)
6.對(duì) PageRank 的個(gè)人的見解(讀者)應(yīng)該沒有余地去懷疑象 PageRank 那樣利用超級(jí)鏈接來決定排列次序有效手法吧。
不過，閱讀了這些論文以后筆者自身也考慮了許多問題。在這里，列舉幾個(gè)對(duì) PageRank 的個(gè)人見解。雖是見解,說到底就是方法論，也許會(huì)有很多錯(cuò)誤的地方。 關(guān)于 dangling page，不相反考慮的原因是什么？
只是因?yàn)榭紤]一定的變異概率時(shí)「偶然」會(huì)變成最簡(jiǎn)才不予考慮嗎？還是有時(shí)看漏了什么嗎？稍微有點(diǎn)不太明白。
改善推移概率行列的可能性說起來，為了保證 PageRank 的單一意義的性質(zhì)(一意)，只要保證推移概率行列是最簡(jiǎn)(有向圖表是強(qiáng)聯(lián)結(jié))就行了，沒有必要所有的要素 aij 都是非零要素。事實(shí)上，像在web上瀏覽 Toyota 汽車網(wǎng)站后緊接著跳向色情網(wǎng)站，接著又繼續(xù)跳到白宮網(wǎng)站瀏覽的怪異的人應(yīng)該是不存在的吧。(請(qǐng)注意這里是指在隨時(shí)間變化連續(xù)的形式)。因此，從實(shí)用的意義上來說，區(qū)別于改善多少的使用方便程度，應(yīng)該留下對(duì)算法改良的余地。
考慮「逗留概率」會(huì)怎樣根據(jù) PageRank 的考慮方法，在一定的時(shí)間后必定順著鏈接前進(jìn)到其他的頁(yè)面，或者突然怪異的、歪曲的跳到其他頁(yè)面。但是如果對(duì)照現(xiàn)實(shí)的web瀏覽模型，也要考慮一定的逗留概率。具體地說，就是推移概率行列的對(duì)角成分中只取( 1-c)/N 的話取得過小了。在原本所有變遷概率都一定的情況下，更加進(jìn)一步分析會(huì)怎樣？因?yàn)閷?duì)于無聊的頁(yè)面(瀏覽者)必定會(huì)想都不想就轉(zhuǎn)到另外的頁(yè)面，反過來對(duì)于重要的頁(yè)面卻會(huì)停留較長(zhǎng)的時(shí)間。
如果考慮概率論應(yīng)用的話必定會(huì)考慮其他許多問題即使是將實(shí)現(xiàn)性置之度外，我們也再來試著進(jìn)一步考慮這個(gè)想法。概率論中，存在著一種叫消滅概率或叫固定概率的概率。比起 PageRank 的單純而同樣考慮方法，導(dǎo)入這種考慮方法會(huì)得到更期望的結(jié)果，所以理所當(dāng)然被大家所期待。大家都知道馬爾可夫鏈中的分枝過程的考慮方法。這是考慮遺傳基因突變時(shí)的一個(gè)模型，即，說明經(jīng)過一定的時(shí)間而產(chǎn)生淘汰的可能性的模型。很多人認(rèn)為這個(gè)考慮方法或許會(huì)被采用。那么導(dǎo)入帶有限制的概率(禁忌概率)又會(huì)怎么樣呢？ 即，相當(dāng)于導(dǎo)入通過 n 次的推移從狀態(tài) i 移動(dòng)到狀態(tài) j 時(shí)，不經(jīng)過狀態(tài) k 的概率。如果考慮到web瀏覽的性質(zhì)的話，不是也能理所當(dāng)然地成為假定嗎？
不能作為非馬爾可夫過程(或者說 m次的多重馬爾可夫過程)來考慮嗎所謂馬爾可夫過程，就是與過去的經(jīng)歷無關(guān)，只從現(xiàn)在的狀態(tài)來確定未來的概率法則的概率過程。 馬爾可夫過程只依存于1步之前的過程。這個(gè)過程和沒有對(duì)過去的記憶，沒有依存于過去經(jīng)歷的要素。 PageRank 是在單純馬爾可夫過程隨時(shí)間變化而固定的狀態(tài)下計(jì)算時(shí)候所求得的結(jié)果。但是，人類的理性行動(dòng)必須以非馬爾可夫過程來表現(xiàn)。復(fù)雜的過程總是以一些形式和過去有著牽連。因此，不僅僅單一地分析從哪個(gè)頁(yè)面連接來，而要分析沿著怎樣的路徑連接而來的。這樣的分析才會(huì)使其有可能成為更有用的排序系統(tǒng)。在能抑制住計(jì)算量爆炸的范圍內(nèi)，試著引入非馬爾可夫過程來研究說不定也很有趣。
在考慮到和看到的許許多多中，有像實(shí)際安裝那樣不太難的東西，也有因?yàn)橹皇亲焐险f說而不知道怎樣實(shí)際安裝的東西，不管怎樣，定量地評(píng)價(jià)它的效果是極為困難的。難道真的是不能實(shí)現(xiàn)的東西嗎？ PageRank 的技術(shù)有多少
即使只是采用評(píng)價(jià)很高的 PageRank 技術(shù)，作為基本的想法也只是使用了枯竭的數(shù)值分析的手法來實(shí)現(xiàn)的。但是，象我在這里說明的事情，如果從專業(yè)的研究者來看是理所當(dāng)然的事情了。只是克服規(guī)模這一點(diǎn)就能建立一個(gè)專業(yè)的研究領(lǐng)域吧。 也可以認(rèn)為專業(yè)領(lǐng)域的內(nèi)部并沒有那么深的盡頭。事實(shí)上，我做事，充其量只是表示了「如果是極其小規(guī)模的問題，即使是教科書的手法也能大約地得到滿足計(jì)算量的結(jié)果」。
盡管是這樣，充其量只觸及了概要的表面就在嘴邊說「沒什么嘛，原來是程度這么簡(jiǎn)單的技術(shù)呀」 的那種不懂裝懂的人也是有的。在這里事先強(qiáng)調(diào)：這種淺薄的看法是從根本上錯(cuò)誤的。
當(dāng)然，PageRank 技巧的非常好的地方是「從許多優(yōu)質(zhì)的頁(yè)面連接過來的頁(yè)面是還是優(yōu)質(zhì)的頁(yè)面」，如果明白了就會(huì)覺得是簡(jiǎn)單的想法。但更進(jìn)一步說，真正絕妙的地方是，不僅僅只是想到一個(gè)主意，而是將想法用固定狀態(tài)變遷的概率分布來定式化，為了實(shí)證其有效性而實(shí)際地進(jìn)行安裝實(shí)驗(yàn)，并證明其在現(xiàn)實(shí)領(lǐng)域也能很好地運(yùn)作的過程。在所有的這些階段都成功了才是真正值得被稱贊的。
的確，不僅有斬新而且巧妙的想法，再加上結(jié)合教科書的手法，也有可能制造出能和 Google 匹敵(或是凌駕)的搜索引擎。也可以說實(shí)際上 Google 自己也在這么做著。但是，實(shí)際完成的人卻是少得驚人。假想模型中的「肯定能夠完成」的東西和實(shí)際運(yùn)作的東西之間有著天差地別。在實(shí)際問題上，處理大規(guī)模疏松行列本身，通過一般的手法也是相當(dāng)?shù)睦щy，需要高度的專業(yè)技術(shù)。應(yīng)該銘記在頭腦中總覺得能夠理解的事和實(shí)現(xiàn)中能夠做的事之間絕對(duì)會(huì)有不能填埋的差距。不可過分輕率地考慮。
上一頁(yè) | 下一頁(yè)
7.參考文獻(xiàn)以下列舉了除了在「前言」中介紹的基本論文以外的關(guān)聯(lián)論文。(譯者去掉了許多無用的連接)
S. Brin, L. Page, 'The Anatomy of a Large-Scale Hypertextual Web Search Engine', http://www-db.stanford.edu/~backrub/google.html 山名早人，近藤秀和，「解說:搜索引擎Google」(概要) , 信息處理42卷8號(hào)(2001年8月), pp.775-780 (PDF) 原田昌紀(jì)，「路標(biāo):WWW搜索引擎的建立方法」(概要), 信息處理41卷11號(hào)(2000年11月), pp.1280-1283 原田昌紀(jì)，「搜索引擎檢索結(jié)果的排序」,bit 2000年8月號(hào)(Vol.32), pp.8-14 美國(guó) Clever Project，「聰明地使用超級(jí)鏈接」 (概要) ,日經(jīng)科學(xué) 1999年9月號(hào), pp.28-35 Dell Zhang, Yisheng Dong, 'An Efficient Algorithm to Rank Web Resources', http://www9.org/w9cdrom/251/251.html Jon M. Kleinberg, 'Authoritative sources in a hyperlinked environment', Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. http://www.cs.cornell.edu/home/kleinber/auth.ps IBM Almaden Research Center, 'CLEVER Searching', http://www.almaden.ibm.com/cs/k53/clever.html以下列舉數(shù)學(xué)關(guān)聯(lián)的參考書籍。
S．卡琳 著，佐藤健一，佐藤由身子譯，『概率過程講義』(數(shù)理分析與周邊3),1974年，產(chǎn)業(yè)圖書 巖堀信子著，『圖表和概率過程』 (與數(shù)理分析與周邊4),1974年，產(chǎn)業(yè)圖書 伊藤升 他著，『經(jīng)濟(jì)系、工學(xué)系的行列及應(yīng)用』, 1987年，紀(jì)伊國(guó)屋書店, ISBN4-314-00477-0 L.V.Atokinson, P.J.哈里, J.D.赫德森 共著，神谷紀(jì)生，大野信忠，佐脅豐，北榮輔 合譯，『數(shù)值計(jì)算及其應(yīng)用- FORTRAN77-』, 1993年，Science公司，ISBN4-7819-0690-7 宮澤政清著，『概率和概率過程』(現(xiàn)代數(shù)學(xué)研究小組17),1993年，近代科學(xué)社， ISBN4-7649-1034-9 伊理正夫著，『線形代數(shù)II』(巖波講座應(yīng)用數(shù)學(xué)11) ,1994年，巖波書店, ISBN4-00-010521-3 韓太舜，小林欣吾著，『信息和符號(hào)化數(shù)理』(巖波講座應(yīng)用數(shù)學(xué)13) ,1994年，巖波書店, ISBN4-00-010523-X 小國(guó)力著，『MATLAB及其實(shí)際利用-現(xiàn)代應(yīng)用數(shù)學(xué)和CG -』( Information Computing=86),1995年，Science公司， ISBN4-7819-0763-6 長(zhǎng)谷川里美，長(zhǎng)谷川秀彥，藤野清次譯，『反復(fù)法 Templates』(應(yīng)用數(shù)值計(jì)算Library),1996年，朝倉(cāng)書店, ISBN4-254-11401-X 小谷真一著，『測(cè)每次和概率2』(巖波講座現(xiàn)代數(shù)學(xué)基礎(chǔ)10 ),1997年，巖波書店, ISBN4-00-010640-6 藤野清次著，『數(shù)值計(jì)算之基礎(chǔ)-以數(shù)值解法做為中心』(Library新信息工程之基礎(chǔ)9),1998年，Science公司，ISBN4-7819-0861-6與有關(guān) Google 的在線新聞報(bào)道(日語(yǔ)新聞)已經(jīng)分離到其另一張頁(yè)面(googlenews.html) 。(2003/5/20)
其他，特別列出幾個(gè)認(rèn)為有關(guān)聯(lián)的頁(yè)面。
Interview with Google's Sergey Brin(翻譯報(bào)道) (LinuxGazette) Web搜索引擎的商務(wù)模型和檢索技術(shù)動(dòng)向-以Google為例- (JCOT報(bào)告) 聰明地分開使用吧! 21世紀(jì)的搜索引擎(InternetWatch) Web的「地圖」的研究成果公布。10％沒有被鏈接 (InternetWatch) 站點(diǎn)研究結(jié)果「搜索引擎之檢索到了一部分」 (HotWired Japan) 檢索引擎的檢索結(jié)果不平等 (HotWired Japan) Google --停住時(shí)代，你是美麗的--(yomoyomo 氏族) Google Weblog (Japanese Version) Patent Death Pending (the cluetrain weblog) Google's PageRank: Calculator (Web Workshop)感謝轉(zhuǎn)載！其他許多的個(gè)人站點(diǎn)和BBS都介紹了此文。
ZDNet China中文 如何提高網(wǎng)站在Google中的排名(2003/1/6報(bào)道) 。讀不了... :-) ZDNet China 如何評(píng)價(jià)一個(gè)網(wǎng)站的人氣(2002/8/5報(bào)道) 還是中文。讀不懂... :-) 中村正三郎「BRAVO! Linux」Linux Japan 2001年5月號(hào) InternetWatch Watcher選出的今天的站點(diǎn)2001年3月16日號(hào) InternetWatch 摘要新聞2001年2月26日號(hào) Google World Japanese 計(jì)算機(jī) 因特網(wǎng) WWW 主頁(yè)檢索 目錄 Lycos /計(jì)算機(jī)、因特網(wǎng)/因特網(wǎng)/站點(diǎn)的檢索、鏈接集/搜索引擎/機(jī)器人檢索/ Google 目錄 Yahoo! JAPAN 商務(wù)經(jīng)濟(jì) 企業(yè) 因特網(wǎng)服務(wù) 企業(yè)間交易(BtoB) 檢索，導(dǎo)航 Google 目錄上一頁(yè) | 下一頁(yè)
8.附錄:「guguru？/ goguru?」英語(yǔ)(美式英語(yǔ))中是不可能把 Google 念成「goguru」的。和沒有人把拉面的 noodle 發(fā)音或標(biāo)記為「nodoru」一樣，如果硬要用片假名來表示的話應(yīng)該寫成「グーグル」。
不過，有oo 這個(gè)拼寫的英文單詞有以下這些。
book, bool, cook, cool, food, good, hook, look, loop, loose, mood, moon, noon, pool, roof, soon, tool, wood, zoo, ...
這些都是簡(jiǎn)單的一般的英文單詞,但不論取哪個(gè)都有「u:」這個(gè)發(fā)音。至少，對(duì)許多的典型的日本人來說聽起來是這樣的吧。英語(yǔ)(美式英語(yǔ))，oo 的拼寫基本讀成「u」。當(dāng)然，goo就讀成「gu:」。 廣末涼子不也在中古車信息雜志的電視廣告中說「如果要說車，gu―」嗎？另外，游泳時(shí)使用游泳眼鏡的拼寫是 goggle。
當(dāng)然，如果 Google 不是英語(yǔ)(美式英語(yǔ))話那就另當(dāng)別論了。但是，Google 名字的由來是從表示10的100次方的英文單詞「googol」而來的，也許還是英語(yǔ)發(fā)音比較適合(google)吧。不用說，googol 的發(fā)音也是「guguru」吧。
另外，創(chuàng)業(yè)者之一是 Sergey Brin，從他的名字就能明白他是俄羅斯出身，也有可能是他的英語(yǔ)發(fā)音帶有自己的方言。如果扯到那里的話，已經(jīng)是牽強(qiáng)附會(huì)了。而且，我也不太清楚Google 用俄羅斯的地方口音怎么發(fā)音。如果有識(shí)之士在的話，請(qǐng)一定告訴我。
補(bǔ)充(2001/4): 給Google的支持中心發(fā)了「是goguru,還是guguru？」的詢問信的一位讀者，熱情地給我轉(zhuǎn)發(fā)了這封郵件。對(duì)方說雖然 Google 自己本身的發(fā)音是「guguru」,不過，你以你自己喜歡的叫法稱呼也決不會(huì)介意的哦。
Date: Wed,31 Jan 200116:12:01-0800
From:”GoogleTech” googletech＠google.com
Subject: RE:{Google#034-917 } pronunciation
To:轉(zhuǎn)送郵件者(Thanks)!
We go by:”GU Gul”
But you are welcome to say whichever you prefer!
Regards，
The Google Team
補(bǔ)充2(2001/10/29):請(qǐng)看Google的頁(yè)面 ”Google”怎么發(fā)音 。
上一頁(yè) | 回到目錄
