【SEO】Google 的秘密- PageRank 徹底解說
實際應用時的問題
PageRank 的基本考慮方法並不是很難的東西。實用效果中的巨大成分並不是複雜離奇的算法，而是進行簡單的線性變換，倒不如都屬於簡明直觀的類別吧。但是，實際使用 Web 超級鏈接構造來計算 PageRank 的話，不是簡單地能夠用嘴巴來說明的東西。主要的困難主要有二個。一、由來於純粹假設的數值模型和現實世界的不同；二，在實際數值計算上(專門技術的)困難。
準備:數學用語(主要概率過程)的解說
推移概率行列和概率過程上的馬爾可夫過程存在很深的關係。本章先離開與 PageRank 本身的說明，預先說明幾個呈現在概率過程上的數學用語。因為會設計相當難的部分，如果不能夠理解也可以跳過這裡。(也可能是我的說明方法不好) 同時，請注意這裡幾乎沒有證明就直接使用了。詳細的解說請閱讀教科書。
從有向圖表S的狀態 i 出發，將有限時間之後再次回覆到狀態 i 的概率作為 1 時，也就是說，當沿著(有向)圖表的方向前進能夠回到原來位置的路徑存在的時候，i 就被成為「回歸」。不能回歸的狀態被稱為「非回歸」。從狀態 i 出發，當通過有限次數的推移達到狀態 j 的概率非負的時候，我們就說「從狀態 i 到達狀態 j 是可能的」。當反方向也可能到達的時候，我們稱「i 和 j 互相可能到達」。從狀態 i 不能到達其他任何狀態的時候，稱 i 為「吸收狀態」。
從鄰接行列 A 所決定的圖表(graph)的任意頂點出發，指向其他任意的頂點圖表的路徑能夠像箭頭那樣到達時被稱為「強聯結」( 也被稱為「分解不能」)。強聯結，等價於從任意狀態到任意狀態可以互相到達。鄰接行列 A 的成分中有很多 0 時，強聯結性就會有問題。注意，如果全部成分都為 aij ≠0 的話，則都屬於強聯結。因為，對應的 馬爾可夫鏈的樣本路徑表示 S 的任意兩點間以正的概率來往通行。
我們可以把全體狀態以等價類(或者回歸類)來劃分。在這裡，回歸類是指鏈接所圍成的範圍。屬於一個等價類的狀態可以互相到達。從一個類出發以正的概 率進入到其他的類的可能性也是存在的。可是很明顯，在這種情況下不可能回覆到原來的類。不然的話，這兩個類就歸於等價類了。下圖表示了，當 T 作為非回歸性的等價類、R 作為回歸性等價類時,雖然存在 馬爾可夫鏈 既不來自回歸類，也不來自非回歸類的情況，但如果一旦來自前兩者的話，就不再會回到非回歸類中了。
 |
| 回歸、非回歸示意圖(修改了小谷(1997)的圖11.1) |
這個等價關係中只有一個回歸類的時候，那個 馬爾可夫鏈就被稱為「最簡」。換句話說，全部的狀態之間互相可以到達時就被稱為最簡。最簡時都是強聯結。
互相完全沒有關聯的鄰接行列(或推移概率行列)，乘以恰當的置換行列(掉換行和列)以後得到
P = | P1 0 |
| 0 P2 |
這樣的關係。這表示回歸類 P1 和 P2 間完全不存在直接的鏈接關係。
回歸類、非回歸類摻雜在一起的鄰接行列(或推移概率行列)，乘以恰當的置換行列後得到，
P = | P1 0 |
| Q P2 |
這樣的關係(Q≠0)。此時，P1是非回歸類，P2是回歸類。
推移概率行列有時也被稱作馬爾可夫行列。稱馬爾可夫過程的試驗行列的觀測結果為馬爾可夫鏈(Markov chain)。 當經過相當的時間後馬爾可夫鏈會趨向某種平衡狀態。對任意的狀態 i, 如果 j 是非回歸狀態，則 Pij(n)→0。相反，當 i 為非回歸、j 為回歸時，停留在狀態 i 上著的概率是0。如果 i，j 屬於同樣的非週期性回歸類的話，Pij(n)→Pj≧0。
定理:若 P 是有限馬爾可夫行列的話，P 的特性值 1 的重複度等於 P 決定的回歸類的數目。(證明太長，省略)。
跟隨著推移概率行列的有向圖表的最大強聯結成分(與之對應的狀態的集合)被稱為Ergodic部分(歷遍部分)，此外的強聯結成分被稱為消散部分。因為無論從怎樣的初期狀態概率 x(0)開始，經過時間 n 後 x(n) = P(n)x(0)，所以屬於消散部分的狀態概率幾乎接近於0。關於EllGoth部分，連同與各聯結成分對應狀態的類、像獨立的最簡的馬爾可夫鏈一樣行動，其中，各類中的狀態概率(即從過去開始的平均值)的值和初期狀態概率無關，換言之，是近似於與對應 P 的最簡成分的固有矢量成比例的東西。在類之間概率的分配依存於初期狀態的概率。
離散時間型馬爾可夫鏈的不變分佈是屬於極限分佈，從那個分佈開始已經不是在分佈意義上的隨時間的變化了。狀態的概率分佈在時間變化時也不會變化時被稱為固定分佈。PageRank 用馬爾可夫過程來說就是，PageRank就是以一定時間內用戶隨機地沿著(網頁)鏈接前進時對各個頁面訪問的固定分佈。
假想模型和現實世界的不同
那麼，讓我們將概率過程(即圖表原理)的考慮方法和實際的網頁鏈接構造合起來看一看。
對於剛才舉例的假想網頁群來說，只要相互順著鏈接前進則在彼此頁面間必定有相互鏈接的關係。即，有向圖表是強聯結的行列既是回歸又是最簡。像上面舉 的很多的概率過程的教科書一樣，許多證明都是把回歸和最簡作為前提來證明的，如果是最簡的話，各種各樣的性質就變得容易說了。
但是現實的網頁並不是強聯結。也就是說鄰接行列不是最簡的。具體來說，順著鏈接前進的話，有時會走到完全沒有向外鏈接的網頁。通常這樣的情況，只有利用 web 瀏覽器的「返回」功能了。如果人們只是瀏覽而已的話，一切就到此結束了，然而 PageRank 的計算卻不能到此結束。因為PageRank 一旦被引入以後是不能返回的。Pagerank 稱這種頁面為為「dangling page」。同樣道理，只有向外的鏈接而沒有反向鏈接的頁面也是存在的。但 Pagerank 並不考慮這樣的頁面,因為沒有流入的 PageRank 而只流出的 PageRank，從對稱性來考慮的話必定是很奇怪的。
同時，有時候也有鏈接只在一個集合內部旋轉而不向外界鏈接的現象。這是非週期性的回歸類多重存在時可能出現的問題。(請讀者考慮一下陷入上圖中一個 R 中而不能移動到別的 R 和 T 的情況)。 Pagerank 稱之為「rank sink」。在現實中的頁面，無論怎樣順著鏈接前進，僅僅順著鏈接是絕對不能進入的頁面群總歸存在，也就是說，這些頁面群是從互相沒有關聯的多數的同值類(回歸類)形成的。
總之，由現實的 Web 頁組成的推移概率行列大部分都不是最簡的。當不是最簡時，最大特性值(即1)是重複的，並且不能避免優固有矢量多數存在的問題。換句話說，PageRank 並不是從一個意義上來決定的。
在此，Pagerank 為瞭解決這樣的問題，考慮了一種「用戶雖然在許多場合都順著當前頁面中的鏈接前進,但時常會跳躍到完全無關的頁面裡」,這樣的瀏覽模型。再者，將「時常」固定為 15％ 來計算。用戶在 85％ 的情況下沿著鏈接前進,但在 15％ 的情況下會突然跳躍到無關的頁面中去。(注: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'當然也同樣是推移概率行列了。也就是說，根據 Pagerank 的變形，原先求行列 M 的特性值問題變成了求行列 M'的優固有矢量特性值問題。M 是固定無記憶信息源(i.i.d.)時，M'被稱為「混合信息源」，這也就是固定但非ellGoth信息源的典型例子。
如果從數學角度看，「把非最簡的推移行列最簡化」操作的另外一種說法就是「把不是強聯結的圖表變成強聯結」的變換操作。所謂對全部的要素都考慮 0.15的遷移概率，就是意味著將原本非最簡的推移概率行列轉換為最簡並回歸的（當然非負的情況也存在）推移概率行列。針對原本的推移概率行列，進行這樣 的變換操作的話，就能從一個意義上定義 PageRank、也就是說能保證最大特性值的重複度為1。如果考慮了這樣的變換操作的話，因為推移概率行列的回歸類的數目變成 1 的同時也最簡化，根據前面的定理，優固有矢量(即 PageRank)就被從一個意義上定義了。
數值計算上的問題點(其1)
在此，只要大概明白 PageRank 的概念就可以了，不需要很深的陷入數值計算上的技術的問題中(其實，筆者自己即使有自信也說不清楚)。但是，因為特性值分析和聯立一次方程式分析一樣，是 利用在各種的統計分析中重要的數值計算手法的一中，所以這裡我們簡單的觸及一些分析方法。
主記憶領域的問題是在數值計算上的問題之一。
假設 N 是 104 的 order。通常，數值計算程序內部行列和矢量是用雙精度記錄的，N 次正方行列 A 的記憶領域為 sizeof(double)* N * N =8 *104 * 104＝800MB。 800MB 的主記憶領域不是那種經常會擁有的東西, 雖然這麼說也非那種不可能的數字。但是，N 如果變成 105 或106 的話，各自就變成80GB,8TB。這樣的話不用說內存就連硬盤也已經很困難了。 Google 從處理著10億以上的頁面(2001年時)以來，就知道這種規矩的做法已經完全不適用了。
不過，A 只是稀疏(sparse)行列。因為即使有一部分的頁面拚命地進行鏈接，但是向整個Web展開鏈接的頁面是沒有的，即使有也是極為稀少的。平均一下，每一張頁面有10-20個左右的鏈接(根據 IBM Almaden 研究所'Graph structure in the web' 的統計，平均在16.1個左右)。因此，我們可以採用恰當的壓縮方法來壓縮 A 。 N 即使是 106 時，如果平均鏈接數是10，最終的記憶領域只要 80MB，從規模上來說可以收納到合理的數字裡。
稀疏行列的容納方式當今已經被充分地研究(有限要素法的解法等)，在恰當的數值計算的專業書中就可以學到。雖然這麼說，因為相當地難解還是需要很複 雜的手法。但想指出的是如果可以很好的解決的話，並列化的高速計算(也許)就變得可能了。因為比起怎樣排列並容納非零要素來說，計算性能和並列性能對其的 影響會更大。
數值計算上的問題點(其2)
另一個是收斂問題。
固定方程式
xi＝ΣAijxi
是 N 元的聯立一次方程式，一般地不能得到分析解，所以只能解其數值。剛才舉的例子中為了求特性值和固有矢量，使用了 Octave 的 eig()函數, 不過，這個在問題小的時候不能適用。說起來，並不需要計算全部的特性值/固有矢量。
求最大特性值和屬於它的固有矢量(優固有矢量)的數值計算手法中，一般使用「冪乘法」(也叫反覆法)。這是指，取適當初期矢量 x0 ，當 x(n+1) = A y(n) (其中 y(n) = x(n) / c(n) )中的 n →∞ 時，x 向擁有最大特性值的固有矢量收斂的同時 c 向此最大特性值收斂的利用線形代數性質的計算方法(證明請參照線形代數的教科書)。冪乘法(反覆法)的特長與逐次反覆計算的近似法比，能夠改善解矢量的問 題。它的優點是，因為只要反覆對行列和矢量進行適當次數的乘法運算，所以只要通過程序就能夠簡單地解決，並且還可以進行由於受到內存和硬盤的限制通過直接 法不能解決的大規模分析。這是許多的實用算法的出發點。
在這裡，請注意從線形代數的簡單定理(Peron-Frobenius定理)得到推移概率行列的絕對價值的最大特性值是1。如果採用了這個，就會使得反覆法的 PageRank 的計算變得更容易。即，因為最大特性值是既知的，比起求滿足 Ax=x 的矢量 x來說 ，變成更加簡單的問題了。這雖然是很細小的地方但是很重要。首先，可以去掉比較花費成本的除法計算 (y(n)=x(n)/c(n))不用完成。如果是反覆法的話，不能得到很高的精確度，並且如果搞錯了加速方法的話，計算出的不是是最大特性值而是第二大特性值和屬於它的固有矢量(雖然這種情況很少，但是說不定就是從根本上錯誤的值)。但如果知道了最大特性值，就可以進行核對了。在 Pagerank 的第一篇論文中他們似乎沒有注意到這個事情,但在 Haveliwala 的第二論文中增加了關於此的修正。
反覆的次數取決於想要求的精度。也就是說，想要求的精度越高，反覆的次數就越多。可是，冪乘法(反覆法)的誤差的收斂比與係數行列的譜段特性(特性值的絕對值分佈)有很強的依存關係。具體地說，絕對值最大的特性值用λ1表示，第二位用 λ2 表示，優越率(收斂率 probability of dominance)為 d =λ1/λ2 話，可以知道d離1越近收斂就變得越慢。在 N 很大的情況時d當然離1很近。這是因為，絕對值最大的特性值是1，而其他所有的 N-1 個特性值的絕對值都比1小。但是，N-1個特性值之間非常的擁擠，所以λ1和λ2 之間幾乎沒有差別。因此一般來說，收斂會變慢。
所謂收斂變慢，嚴密地說，就是無論經過多少時間也完成不了的計算。對此，為了使收斂加快的適當的加速方法也是存在的，應用這些方法時，需要對數值計算技術有十二分的理解，因此如果不是數值計算的專家就很難引入。
歷史上的今天
- 【doodle】紀念Beatrix Potter 誕生 - 2008
- 【doodle】祕魯國慶日 - 2008
- 【SEO】Matt Cutts談PR和PR更新 - 2008
