淺談 Google 的 PageRank 算則

之前報讀了 Udacity 的 CS101: Building a Search Engine，開課後才發現它比想象中淺得多，大多數時候，與其說該課程教人建構搜尋器，不如說它是 Introduction to the Python Programming Language，不過課程終段的確牽涉到 Google 的搜尋結果排名算法，只是也許為了遷就學生的程度，避談了本來可以用數學來解釋得清清楚楚的部份。這裏我就不妨補充一下。

Google 的搜尋結果排名法，稱為 PageRank。經過多年發展，現時 PageRank 算法的內容已經不為人知，不過 Larry Page 與 Sergey Brin （Google 兩位創辦人）起初是有將描述此算則的論文擺上網的，有興趣的讀者不妨看一看。

簡單來說，早期的 PageRank 是一個投票機制，每引用一個網頁，就等於投了該網頁一票。舉例說，假設下圖十一個方格都是提及動畫 Steins;Gate 的網頁，其中每個箭咀代表一項連結，亦即是 a 網頁有一道連向 A 網頁的連結，而 c 網頁內有三道連向三個不同網頁的連結等等。由於 b, c 各得三票，a 網頁卻無票（無人引用），驟眼看來，b, c 兩網頁理應比 a 網頁更權威。

然而，若純粹以票數多寡來作排名指標，會引起明顯問題。譬如：

• 儘管圖中 A, B 兩個網頁都各得一票，但 B 網頁應該比 A 網頁重要，原因是投票給 B 的 b 網頁有人引用，投票給 A 的 a 網頁卻無。投票者較權威，得票者亦應該更權威。
• 儘管 B, C 均各得一票，但 B 的排名應該比 C 高，原因是投票給它們的 b, c 兩個網頁同樣權威，但是 b 網頁將票全投給 B，而 c 網頁卻投了三個網頁，所以 C 網頁未必如 B 網頁那麼有用。

以上兩點，第一點其實是說我們不應只考慮得票多寡，還要考慮投票者本身的重要性（即排名），而第二點就是說，除了要考慮得票多寡（即有幾多條 incoming links）之外，亦要考慮投票者的投票若干（即投票者有幾多條 outgoing links）。要解決這兩點，可以用以下做法。假設整個整個互聯網中，有 $n$ 個網頁提及 Steins;Gate 動畫，而我們以符號 $p_i$ 來代表等 $j$ 個網頁的排名分數，分數愈高則名次愈高。那麼，我們可將 $p_j$ 定義為下列方程式的解：
$$p_i = \sum_{\textrm{page } j \textrm{ has link to page } i} \frac{p_j}{\textrm{no. of out-links of page } j}.$$
根據以上方程，若 $j$ 網頁投了票給 $i$ 網頁，那麼 $j$ 網頁本身的分數 $p_j$，亦反映在 $p_i$ 的計算之中，因此顧及了上面提到的第一點。此外，等式右邊的分母是投票者所投的票數。若 $j$ 網頁引用了許多網頁，而 $i$ 網頁只是其中之一，那麼這個大分母會將分數拉低，因而解決了上面提到的第二點。

Google 最初期的 PageRank，其實還有另一步 ── 它實際上將 $p_i$ 定義為
$$p_i = \frac{1-d}{n} + d\left(\sum_{\textrm{page } j \textrm{ has link to page } i} \frac{p_j}{\textrm{no. of out-links of page } j}\right).$$
換句話來說，除了前述的排名方法之外，PageRank 還考慮了另一個排名方法，就是各網頁皆有同等名次。將一票分給 $n$ 個網頁，每個網頁就有 $\frac{1}{n}$ 票。將兩種票數以權數 $d$ 來作加權平均，才是真正得票。Page and Brin 將這個權數 $d$ 稱為 damping factor。他們起初所用的數值為 $d=0.85$。

至於何以要作加權平均，他們含糊其詞，說 PageRank 可以視為搜尋用戶的行為的數學模型，而上式 $\frac{1}{n}$ 的部份，可視作當一名用戶厭倦了點擊網頁的連結以後，隨機探訪網上一個任意網頁。他們於另一篇文章又提到這樣可以給每個網頁一些內在價值，有助避免某單一網頁有過大影響云云，不過我感覺他們當時其實並無一套清楚的理論，解釋加權的原因，只是單純覺得這樣做有助改善搜尋器的表現而已。讀者切勿誤會，以為我看扁他們，實情剛剛相反。儘管我以為他們並無一套理論解釋何以要加權，但就正正因為如此，才顯出他們是上等的工程師，有靈敏的直覺。

PageRank 的加權平均方法，其實是有理論基礎的。假設 $C_j$ 代表網頁 $j$ 有幾多條 out-links，而 $g_{ij}$ 代表「網頁 $j$ 引用了網頁 $i$」的布林值，亦即當網頁 $j$ 引用了網頁 $i$ 的時候，$g_{ij}$ 為 $1$，否則為 $0$。於是我們可以將 $p_i$ 的定義以矩陣形式寫成
$$\begin{eqnarray}
\mathbf{p} &=& \left[\frac{1-d}{n}
\begin{pmatrix}1&\ldots&1\\\vdots&&\vdots\\1&\ldots&1\end{pmatrix}
+ d\mathbf{G}\begin{pmatrix}\frac{1}{C_1}\\&\ddots&\\&&\frac{1}{C_n}\end{pmatrix}\right] \mathbf{p}\\
&=& \mathbf{A}\mathbf{p} \quad\textrm{ (say)}.
\end{eqnarray}$$
我們要問的問題有三個。第一，$\mathbf{p}=\mathbf{A}\mathbf{p}$ 此方程是否有解？第二，若它有解，又是否只有獨一的解？若有多個解，豈非說一個網頁有多個排名？當然，若 $\mathbf{p}$ 是方程式的解，將 $\mathbf{p}$ 乘上任意一個實數 $\lambda$，亦將是一個解，因此我們必須將方程式的解正規化 (normalized)。由於 $p_i$ 可以理解為「$i$ 網頁乃有用的搜尋結果」的機會率，所以我們要求 $\sum_i p_i=1$。第三，亦由於我們將 $p_i$ 視為機會率，故此亦要求 $p_i\ge0$。所以，綜合起來，我們要問的，就是：

方程式 $\mathbf{p}=\mathbf{A}\mathbf{p}\quad (p_i\ge0,\ \sum_ip_i=1)$ 是否有獨一的解？

不難驗證，$\mathbf{A}$ 是一個非負 (entrywise nonnegative) 矩陣，且每列元素總和為 1 (column sum = 1)。數學上，這樣的矩陣稱為隨機矩陣 (stochastic matrix)。矩陣理論中，有一條與隨機矩陣相關的定理，稱為 Perron-Frobenius Theorem，內容是說，若 $\mathbf{A}$ 是一個元素為正的隨機矩陣，那麼它會剛好有一個特徵值 (eigenvalue) 為 1，而且所有其他特徵值的絕對值皆小於 1；此外，撇除放大與縮小 $\mathbf{p}$，方程 $\mathbf{p}=\mathbf{A}\mathbf{p}$ 有獨一的解，兼且此解的所有元素為正數。

有了這條定理，PageRank 算則之中權數 $d$ 的功用就呼之欲出了 ── 若不取加權平均（或等價地將權數設為 $1$)，$\mathbf{A}$ 只是個非負矩陣，而非正矩陣，因此不能保證 $\mathbf{p}=\mathbf{A}\mathbf{p}$ 有獨一的解，亦即可能存在多種排名次序，結果要用其他方法解決排名問題。然而，一旦有 $0\le d<1$，我們即可確保 Google 大神分得出排名先後。

回說 Udacity 的 CS101。主講的 Prof. Evans 避談數學，將 PageRank 以迭代方式定義為 $\mathbf{p}_t =\mathbf{A}\mathbf{p}_{t-1}$。這其實於數學上稱為 power method，是一種計算特徵向量的方法。Brin and Page 的文章說他們用了某種 simple iterative algorithm 來計算 PageRank，所指似乎就是 power method。此方法的名稱，源自 $\mathbf{p}_t =\mathbf{A}\mathbf{p}_{t-1} = \mathbf{A}^2\mathbf{p}_{t-2} = \ldots = \mathbf{A}^t \mathbf{p}_0$，亦即利用 $\mathbf{A}$ 的 power 去計算特徵向量 $\mathbf{p}$。這個方法的好處是容易理解、實作簡單，缺點是當 $\mathbf{A}$ 最大和第二大的特徵值相當接近的時候，power method 會收斂得非常慢。一般而言，power method 並非尋找特徵向量的好方法，不過做網頁排名的話，$\mathbf{A}$ 是一個超巨大的稀疏矩陣 (sparse matrix)，兼且由於 web crawler 會不時更新矩陣內容，因此簡單的方法可能更有利。實際情況如何，就在我知識範圍以外了。

上文是我將多年前的舊文略為變更而成，目的是以最少的線性代數解釋早期 PageRank 的數學原理。美國數學學會 (American Mathematical Society) 另有一篇 feature column 做類似的事，但遠較本文詳盡，有興趣的讀者不妨一看。本文並未參考 AMS 的文章。