上世紀我向朋友講過，linear regression（線性迴歸）真是史上一大發明，事關今時今日有許多人凡見數據，即（亂）做一番 regression，得出一些似是而非的結論，然後用來出新聞稿或者寫論文，所以 linear regression 真是養活了唔少人。
近日電視那輯「XX愛作戰」也一樣。這套真人 show，我一集都無睇過，但是今日行經便利店，驚覺所有八卦雜誌都是拿當中幾位女角做封面。加埋報紙與電台，此劇真是有非常正面的經濟功能呀。（唔係諷刺，我係認真的。）
2012年4月22日星期日
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 網頁更權威。
然而，若純粹以票數多寡來作排名指標，會引起明顯問題。譬如：
$$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$。所以，綜合起來，我們要問的，就是：
有了這條定理，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 的文章。
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 網頁那麼有用。
$$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 的文章。
Label(s)：
不學無術
憑弔你的老味 II 之翻一翻舊賬
事發不過幾日，領匯已聲稱為「免影響社會和諧」，決定讓臉皮「薄起來」，終止它這個偽善的「尋味時光」活動。今次事件引起不少網民討論，其中《船山筆記》 的 SF 先生很細心，指出根據當年《香港經濟日報》報道，鄭經翰當時反對的並非變賣，而是賤賣領匯。這與在下的記憶有點出入，不過記憶從來都不是百分百可靠的東西。唯有翻舊賬，方能拼出較全面景象。
搜尋一番之後，結果如下：
最後，雖然累贅，但也得聲明：本文目的，並非在於將鄭經翰塑造為一位為民請命的正義天使。當然，我是認為當年鄭經翰的立場乃非常正確的，但這不表示我們同意他所有的見解。例如政改一役，鄭事後說自己當初應該支持通過政改方案，不應被民主派捆綁云云，在下就不敢苟同了。又譬如領匯上市，當年工聯會是反對的，可是民建聯卻支持。我不知讀者如何看待工聯會的決定，但我就只覺得它與民建聯扯貓尾。
註：
[1] 據立法會解釋，倘若議員希望在立法會席上提出某一問題進行辯論，但不欲以明確字眼擬訂議案，則可動議一項休會待續的議案進行辯論，讓議員可就有關問題發表意見及探求政府的回應。
伸延閱讀：
搜尋一番之後，結果如下：
- 鄭經翰當年似乎並無斬釘截鐵地以「加租」為反對領匯上市的主要理由，不過他確有表示過領匯上市會造成亂加租的惡果。根據《文匯報》2004年11月28日報道：
發起公屋商場及領匯租戶大聯盟的議員鄭經翰則稱，房委會急於滅赤、套現，對領匯的資產估值過低，將商場全面分拆是殺雞取卵的做法：「上市可以套現二百幾億，但實際上只要拆幾個商場和停車場出售，例如樂富、何文田、龍翔中心，已經夠了，其他的還可以留下來繼續收租。」他又稱，商場在上市後會以商業形式運作，租金調整無人管理，整個董事局也缺乏監管。在這些細節問題都未能解決時，領匯不應倉促上市，故他已與其他立法會議員聯署，致函立法會內委會主席，要求在大會上討論押後領匯上市日期。
- 然而，擔心領匯加租，是由鄭經翰支持的盧少蘭婆婆當年入稟司法覆核的理據。見盧少蘭與馬基召訴香港房屋委員會 (HCAL 154/2004)。
- 至於鄭經翰本人所持的主力反對理由，如前述的經濟日報報道，乃認為房委會其時的上市安排，是賤賣港人資產。話說當年領匯的上市說明書估計，領匯上市後一年，股東可獲 6.7 厘的回報，非常吸引，房委會卻安排 90% 的領匯股票售予國際投資者，因而招致鄭經翰質疑。
- 2004年12月1日，鄭經翰於立法會提出休會辯論[1]，議案為：
「就政府當局及房屋委員會漠視立法會房屋事務委員會於本年11月22日的特別會議上通過要求在領匯與租戶達成共識前房屋委員會應擱置領匯基金上市安排的議案， 表達對領匯基金招股上市、資產估值及一切有關分拆出售公屋零售和停車場設施的意見。」
儘管隱晦，但議案本身確有反映對領匯加租的憂慮。此外，據《文匯報》12月2日報道，鄭經翰於會上表示：現時屋邨商場及停車場因管理不善，令估值較低；他認為政府可以先進行私有化，令經營改善及價值上升，才進行上市。他又擔心領匯上市後以商業經營為原則，最終會將小商戶趕離屋邨商場，故希望先擱置上市，與商戶商討。
最後，雖然累贅，但也得聲明：本文目的，並非在於將鄭經翰塑造為一位為民請命的正義天使。當然，我是認為當年鄭經翰的立場乃非常正確的，但這不表示我們同意他所有的見解。例如政改一役，鄭事後說自己當初應該支持通過政改方案，不應被民主派捆綁云云，在下就不敢苟同了。又譬如領匯上市，當年工聯會是反對的，可是民建聯卻支持。我不知讀者如何看待工聯會的決定，但我就只覺得它與民建聯扯貓尾。
註：
[1] 據立法會解釋，倘若議員希望在立法會席上提出某一問題進行辯論，但不欲以明確字眼擬訂議案，則可動議一項休會待續的議案進行辯論，讓議員可就有關問題發表意見及探求政府的回應。
伸延閱讀：
- 宋小莊，領匯官司查找不足，《文匯報》，2004-12-27。
2012年4月10日星期二
憑弔你的老味
二○○三年，房委會以解決財政困難為由，計劃將轄下商場及停車場分拆上市，時稱「房地產信託基金」，也就是後來的「領匯」。
二○○四年十二月，基金首次招股。同月，公屋居民盧少蘭對房委會的措施提出司法覆核，但敗訴。由於盧少蘭仍未向終審法院上訴，為免法律風險，房委會決定暫擱上市計劃。一時間，盧少蘭與支持她的鄭經翰議員，遭媒體與政黨大肆攻擊，被譏為「阻人發達」。律師林炳昌更報案，指鄭經翰違反《普通法》中的「包攬訴訟罪」，要求警方徹查。
二○○五年六月一日，陳偉業議員於立法會提出不具約束力的「要求擱置私有化」議案（立法會CB(3)688/04-05 號文件）。分組點票結果，無論是功能組別抑或地方組別，議案均大約以二比一的比例遭否決。支持議案的議員共十四位，包括陳偉業、鄭經翰、張超雄、李卓人、梁耀忠、劉千石、劉慧卿、馮檢基、郭家麒、何鍾泰、李鳳英、王國興、鄺志堅、陳婉嫻。民建聯、自由黨與民主黨均反對擱置，公民黨就棄權。
二○○五年七月，終審法院駁回盧少蘭的上訴。同年十一月，基金易名為「領匯房地產投資信託基金」，於港交所掛牌上市。領匯上市後，如一般人所料大幅加租，並不斷淘汰小商戶，引入大集團連鎖店。
上月，領匯於 Facebook 推出「我們的尋味時光」活動，聲稱「讓大家重拾舊時獨有的人情味與滋味」云云。
伸延閱讀：
二○○四年十二月，基金首次招股。同月，公屋居民盧少蘭對房委會的措施提出司法覆核，但敗訴。由於盧少蘭仍未向終審法院上訴，為免法律風險，房委會決定暫擱上市計劃。一時間，盧少蘭與支持她的鄭經翰議員，遭媒體與政黨大肆攻擊，被譏為「阻人發達」。律師林炳昌更報案，指鄭經翰違反《普通法》中的「包攬訴訟罪」，要求警方徹查。
二○○五年六月一日，陳偉業議員於立法會提出不具約束力的「要求擱置私有化」議案（立法會CB(3)688/04-05 號文件）。分組點票結果，無論是功能組別抑或地方組別，議案均大約以二比一的比例遭否決。支持議案的議員共十四位，包括陳偉業、鄭經翰、張超雄、李卓人、梁耀忠、劉千石、劉慧卿、馮檢基、郭家麒、何鍾泰、李鳳英、王國興、鄺志堅、陳婉嫻。民建聯、自由黨與民主黨均反對擱置，公民黨就棄權。
二○○五年七月，終審法院駁回盧少蘭的上訴。同年十一月，基金易名為「領匯房地產投資信託基金」，於港交所掛牌上市。領匯上市後，如一般人所料大幅加租，並不斷淘汰小商戶，引入大集團連鎖店。
上月，領匯於 Facebook 推出「我們的尋味時光」活動，聲稱「讓大家重拾舊時獨有的人情味與滋味」云云。
伸延閱讀：
- 鄭經翰：那些年，他們一起支持領匯上市
- tommyjonk: 誰吊起了我們的老味
- 林忌：支持領匯上市－－歷史不會忘記
2012年4月8日星期日
2012年4月3日星期二
The Elements of Statistical Learning
A free version is available for download. See the official website.
訂閱：
文章 (Atom)