愛耍酷的Style

七月282008

【SEO】Google 的秘密- PageRank 徹底解說

星期一, 七月 28, 2008 13:06 | 9,332位訪客跟4,694 Bot看過

分類於： Google

No Comments

對 PageRank 的個人的見解

(讀者)應該沒有餘地去懷疑象 PageRank 那樣利用超級鏈接來決定排列次序有效手法吧。

不過，閱讀了這些論文以後筆者自身也考慮了許多問題。在這裡，列舉幾個對 PageRank 的個人見解。雖是見解,說到底就是方法論，也許會有很多錯誤的地方。

關於 dangling page，不相反考慮的原因是什麼？

只是因為考慮一定的變異概率時「偶然」會變成最簡才不予考慮嗎？還是有時看漏了什麼嗎？稍微有點不太明白。

改善推移概率行列的可能性說起來，為了保證 PageRank 的單一意義的性質(一意)，只要保證推移概率行列是最簡(有向圖表是強聯結)就行了，沒有必要所有的要素 a_ij 都是非零要素。事實上，像在web上瀏覽 Toyota 汽車網站後緊接著跳向色情網站，接著又繼續跳到白宮網站瀏覽的怪異的人應該是不存在的吧。(請注意這裡是指在隨時間變化連續的形式)。因此，從實用的意義上來說，區別於改善多少的使用方便程度，應該留下對算法改良的餘地。
考慮「逗留概率」會怎樣

根據 PageRank 的考慮方法，在一定的時間後必定順著鏈接前進到其他的頁面，或者突然怪異的、歪曲的跳到其他頁面。但是如果對照現實的web瀏覽模型，也要考慮一定的逗留概率。具體地說，就是推移概率行列的對角成分中只取( 1-c)/N 的話取得過小了。在原本所有變遷概率都一定的情況下，更加進一步分析會怎樣？因為對於無聊的頁面(瀏覽者)必定會想都不想就轉到另外的頁面，反過來對於重要的頁面卻會停留較長的時間。

如果考慮概率論應用的話必定會考慮其他許多問題

即使是將實現性置之度外，我們也再來試著進一步考慮這個想法。概率論中，存在著一種叫消滅概率或叫固定概率的概率。比起 PageRank 的單純而同樣考慮方法，導入這種考慮方法會得到更期望的結果，所以理所當然被大家所期待。大家都知道馬爾可夫鏈中的分枝過程的考慮方法。這是考慮遺傳基因突變時的一個模型，即，說明經過一定的時間而產生淘汰的可能性的模型。很多人認為這個考慮方法或許會被採用。那麼導入帶有限制的概率(禁忌概率)又會怎麼樣呢？即，相當於導入通過 n 次的推移從狀態 i 移動到狀態 j 時，不經過狀態 k 的概率。如果考慮到web瀏覽的性質的話，不是也能理所當然地成為假定嗎？

不能作為非馬爾可夫過程(或者說 m次的多重馬爾可夫過程)來考慮嗎

所謂馬爾可夫過程，就是與過去的經歷無關，只從現在的狀態來確定未來的概率法則的概率過程。馬爾可夫過程只依存於1步之前的過程。這個過程和沒有對過去的記憶，沒有依存於過去經歷的要素。 PageRank 是在單純馬爾可夫過程隨時間變化而固定的狀態下計算時候所求得的結果。但是，人類的理性行動必須以非馬爾可夫過程來表現。複雜的過程總是以一些形式和過去有著牽連。因此，不僅僅單一地分析從哪個頁面連接來，而要分析沿著怎樣的路徑連接而來的。這樣的分析才會使其有可能成為更有用的排序系統。在能抑制住計算量爆炸的範圍內，試著引入非馬爾可夫過程來研究說不定也很有趣。

在考慮到和看到的許許多多中，有像實際安裝那樣不太難的東西，也有因為只是嘴上說說而不知道怎樣實際安裝的東西，不管怎樣，定量地評價它的效果是極為困難的。難道真的是不能實現的東西嗎？

PageRank 的技術有多少

即使只是採用評價很高的 PageRank 技術，作為基本的想法也只是使用了枯竭的數值分析的手法來實現的。但是，像我在這裡說明的事情，如果從專業的研究者來看完全是理所當然的事情了。只是克服規模這一點就能建立一個專業的研究領域吧。也可以認為專業領域的內部並沒有那麼深的盡頭。事實上，我做事，充其量只是表示了「如果是極其小規模的問題，即使是教科書的手法也能大約地得到滿足計算量的結果」。

儘管是這樣，充其量只觸及了概要的表面就在嘴邊說「沒什麼嘛，原來是程度這麼簡單的技術呀」的那種不懂裝懂的人也是有的。在這裡事先強調：這種淺薄的看法是從根本上完全錯誤的。

當然，PageRank 技巧的非常好的地方是「從許多優質的頁面連接過來的頁面是還是優質的頁面」，如果明白了就會覺得是簡單的想法。但更進一步說，真正絕妙的地方是，不僅僅只是想到一個主意，而是將想法用固定狀態變遷的概率分佈來定式化，為了實證其有效性而實際地進行安裝實驗，並證明其在現實領域也能很好地運作的過程。在所有的這些階段都成功了才是真正值得被稱讚的。

的確，不僅有斬新而且巧妙的想法，再加上結合教科書的手法，也有可能製造出能和 Google 匹敵(或是凌駕)的搜索引擎。也可以說實際上 Google 自己也在這麼做著。但是，實際完成的人卻是少得驚人。假想模型中的「肯定能夠完成」的東西和實際運作的東西之間有著天差地別。在實際問題上，處理大規模疏鬆行列本身，通過一般的手法也是相當的困難，需要高度的專業技術。應該銘記在頭腦中總覺得能夠理解的事和實現中能夠做的事之間絕對會有不能填埋的差距。不可過分輕率地考慮。