2012年4月14日星期六

淺談 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 的文章。

5 則留言:

Chainsaw Riot 說...

可否解釋下為何他們用的 Urank ,一個 graph 所有的 Urank 加埋不會等於 1 ;而 PageRank 卻會等於 1 ?

The suffocated 說...

這純粹因為佢地無 normalize 枝 eigenvector。如果你用 Urank 計算到的 ranking 是 p=(p_1, ..., p_n)^T,那麼將整枝 p 向量除以 p_1+...+p_n,就會得到 PageRank(或者嚴格來說,PageRank 的 approximation)。

要否 normalize p,其實無乜大不了,因為我們最終要求的,是各網頁的相對排名。譬如 n=3,p=(0.7, 0.3, 654.3),這枝 p 的元素加起來並非 1,但我們仍知道三個網頁的排名是 3>1>2。就算你 normalize p,得到 p=(1/655.3)(0.7, 0.3, 654.3),結果仍一樣。

然而,若我們如 Brin and Page 那般,將 p 詮釋成一枝 probability vector 的話,那當然要記得 normalize p。留意,由於我們要有 probability interpretation,因此做 normalization 的時候,分母並非 p 的 norm,而是 p 的 entrywise sum。

我還隱約記得,初期的 Google 列出搜尋結果時,PageRank 也是一併列出的,而且排第一的網頁的 PageRank 好像是 1。因此,若我無記錯的話,它列出 PageRank 時,其實都唔係用 entrywise sum,而是用 sorted 之後的 p_1 (即最大的那個 ranking)來 normalize p 的。

最後,由於電腦計算會有 rounding error,因此一般而言,若要用 power method 去 run 好多個 iterations,最好還是每幾個 iterations 就 normalize 一次,否則那枝 p 會有機會慢慢收斂到 zero vector,不過以一般教學例子來說,大概不會遇到這樣的情況吧。

匿名 說...

I totally agree with you that the intuition and gut feels separate the geniuses from the work mules. It is like comparing Thomas Edison vs. Nicholas Tesla. The former used brute force and dirty business practices to become successful and the latter was just purely a genius who was suppressed and shot down by rivals. Edison said Genius was 1% inspiration and 99% perspiration. That pretty much proved that he was not a true genius because Tesla probably was 99% inspiration and 1% perspiration. If Tesla had gotten funding for his research, the earth would be a different world today.

匿名 說...

I still remembered my first exposure to Google search years ago. I was using MetaCrawler and Yahoo search at the time. I usually had to go through 5 to 10 pages of results to finally find what I was looking for. One day a friend told me to give Google a try. What I sought showed up as No 1 result as if the search engine could read my mind. On that day, I removed my bookmark on MetaCrawler and Yahoo search.

匿名 說...

I think knowing how to rank the pages is one thing. Figuring a way to actually implement the idea is another thing. There are so many webpages on the Internet. How can one distill the world of Internet into some ranking numbers quickly to keep the ranking up to date. I believe MapReduce enabled that. Today, Hadoop is an Open Source version used by many company for other applications.