學好線性代數，成為億萬富翁不是夢

線性代數課聽得暈暈乎乎，你是不是也在想：這線代到底能幹啥使啊？今天，AI就給你們講一個特別激動人心的例子——線性代數有可能讓你成為億萬富翁！

當人們在使用搜索引擎時，總會對搜索結果排名靠前的網頁更信任。

在大多數人的直覺里，最重要的、可信度高的網頁應該排在前面。可是，怎樣判斷一個網頁的重要性？一個很自然的想法是：一個網頁獲得鏈接越多，可信度就越高，那麼它的排名就越高。

這個看似簡單的想法，正是谷歌PageRank網頁排名演算法的核心思想。

圖 | Pixabay

1

光看網頁鏈接數，靠譜嗎？

不過，演算法實際上要複雜的多。比如，你想呀，把每個網頁獲得的鏈接從多到少排名一下可以嗎？好像也不行，光是想想龐大的網路水軍就知道，這樣排名的注水量一定能淹了龍王廟。這很容易作弊不說，也不能反映不同網頁內容和領域的差異。

假如，你是學校的招生老師，看推薦信，是看誰的信多誰厲害嗎？當然不是，還要看寫信的人是誰。同樣的道理，我們應該看一下鏈過去的網頁到底有多厲害。如果一個網頁被很多其他網頁所鏈接，由於有的網頁重要，而有的網頁很水，我們當然要對來自不同網頁的鏈接區別對待。因而，在判斷一個網頁的重要性時，對那些重要網頁的鏈接應該給予大的權重，而權重又取決於它們的重要程度——被鏈接的次數……

這樣，問題就來了。和單向的推薦信不同，所有的網頁都是連在一起的，你鏈我、我鏈她、她鏈他，他鏈我，構成了一個死循環。而你評估必須要有一個起點，但是，用任何網頁作為起點都不公平，怎麼辦？

PageRank的解決辦法是：先同時把所有網站作為起點，也就是先假定所有的網頁一樣重要、排名相同。然後，進行迭代。

2

看線代怎麼解決演算法難題

同時起點又該怎麼做？這時候，就是線性代數非出場不可的時候了。

1996年，谷歌的創始人拉里·佩奇（Larry Page）和謝爾蓋·布林（Sergey Brin）在斯坦福大學開發出PageRank。「Page」一語雙關，既有網頁的意思，也是佩奇的名字。當時，佩奇和布林把整個互聯網當做一個整體來看待，他們認為「整個互聯網就像一張大的圖，每個網站就像一個節點，而每個網頁的鏈接就像一個弧」[1]。於是，佩奇就想用一個圖或者線性代數的矩陣來描述互聯網。而布林把無從下手的網頁相連問題變成了一個二維矩陣相乘的問題，並通過迭代，算出了網頁排名。

圖1 | 四個網頁之間的鏈接情況

【前方高能，可以不愛線代，但請不要傷害！】

布林先假定所有網頁的排名是一樣的：一共n個網頁的話，那每個網頁的最初排名都是1/n。假設一共4個網頁（見圖1），那每個網頁的初始排名都是1/4，當我們用一個向量r來保存所有網頁的排名時，r的初始值就如下所示：

r的初始值，即所有網頁的初始網頁排名

然後，我們把一個網頁的鏈接情況看作是一個向量，那麼，根據圖1，網頁A的鏈接情況

以此類推

這樣，我們就能把所有網頁之間的鏈接情況用一個矩陣L表示：

列：指向外部的鏈接數，行：指向自己的鏈接數，例如，第一列表示從A指出的鏈接數，第一行表示箭頭指向A的鏈接數。

我們已經知道，一個網頁的重要程度，要看它被多少網頁所鏈接；同時，對於不同的鏈接網頁，根據它們的網頁排名，我們給予不同的權重。所以，網頁A的排名應該等於所有指向網頁A的其他網頁的權重之和。而我們現在既知道所有網頁的鏈接數——矩陣L，也知道所有網頁的排名——向量r，那麼，就可以算出一個網頁的排名，比如網頁A的排名：

j表示第幾個網頁

接著，就開始迭代。當所有網頁的最初排名都一樣的時候，我們可以算出每個網頁的第一次迭代排名。網頁A、B、C、D的第一次迭代排名計算如下：

網頁BCD的第一次迭代排名依次為0.2083、 0.2083、 0.4583。

有了第一次迭代排名，我們又能算出第二次迭代排名……最終，排名r會收斂，不再變化。一般只要10次左右的迭代基本上就收斂了。而且，這種演算法不需要任何人工干預。如下圖，經過多次迭代，紅框內的數值，就是這四個網頁的最終排名：D排最前面，中間是B和C，排在最後的是A。

圖 | coursera.org- Imperial College London, Mathematics for Machine Learning: Linear Algebra

3

算出來的網頁排名是真實的嗎？

迭代計算的結果會收斂到網頁排名的真實值嗎？打比方的話，網頁之間的鏈接關係，有點類似動物之間的食物鏈關係。而網頁排名結果通過多次迭代、最終收斂，就有些類似於常見的兔子數量問題，在一個自然的生態環境里，不管兔子最開始的數量是多少，最終它們的數量都會達到一個穩定的值。關於網頁排名計算的迭代收斂，佩奇和布林從理論上證明了不論初始值如何選取，這種演算法都能保證網頁排名的估計值能收斂到排名的真實值[1]。

隨著迭代次數的增加，與上一次迭代結果的總差異在變小

簡言之，網頁排名的的計算主要是矩陣相乘。但是，在實際運用中，這些運算其實非常複雜。另外，實際的網頁數量多得驚人，巨大的矩陣相乘需要的計算量也就無法估計，而這也難不過科技大牛們，佩奇和布林又利用稀疏矩陣計算的技巧解決了龐大計算量這一問題。但是現在，對一個網頁重要性的衡量是全方位的，除了要看PageRank，還要看別的數據，比如網頁的內容權威性……

谷歌PageRank網頁排名演算法，讓谷歌搜索引擎從同時代的搜索引擎中脫穎而出，也讓兩位創始人成為了億萬富翁。

現在，媽媽再也不用擔心我不知道線性代數能幹啥使了……

作者:Cloud

編輯：Ent、東風

參考文獻：

[1].吳軍. 數學之美[M]. 人民郵電出版社, 2012.

[2].https://www.coursera.org/lecture/linear-algebra-machine-learning/introduction-to-pagerank-hExUC

[3].Page L, Brin S, Motwani R, et al. The PageRank citation ranking: Bringing order to the web[R]. Stanford InfoLab, 1999.

[4].Brin S, Page L. The anatomy of a large-scale hypertextual web search engine[J]. Computer networks and ISDN systems, 1998, 30(1-7): 107-117.

[5].https://en.wikipedia.org/wiki/PageRank

一個AI

同樣都在學線代，你看看人家？

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！