# 李宏毅_Linear Algebra Lecture 28: PageRank
###### tags: `Hung-yi Lee` `NTU` `Linear Algebra Lecture`
[課程撥放清單](https://www.youtube.com/playlist?list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW)
## Linear Algebra Lecture 28: PageRank
[課程連結](https://www.youtube.com/watch?v=pSg9TG_U_fY&list=PLJV_el3uVTsNmr39gwbyV-0KjULUsN7fW&index=28)

### PageRank

* PageRank較高的的網頁，搜尋的時候就會排較前面
* PageRank依靠的並不是網頁本身的內容，而是整個網路的結構
* 當Page-A設置一個超連結到Page-B的時候，代表Page-B會得到較高的分數

### Importance

這是一個示意圖，每一個笑臉代表一個網路，箭頭則代表每一個網頁之間的超連結。

藍色、黃色網頁被很多超連結連到，這意味著它們的PageRank會比較大。另一個情況是，當你的網頁被PageRank比較大的網頁連結的時候，那你的網頁也會有較高的PageRank，像右上紅色網頁就是被黃色網頁這個非常重要的網頁給連到，因此它也跟著水漲船高。
### PageRank

這是當初google創辦人的論文
### Importance - Formulas

這邊說明PageRank的計算。假設網路上只有四個網頁，網頁之間設有超連結。每個網頁都有分數，以$x_1 \cdots x_4$表示。每個網頁的分數都會是指向它的網頁的總合：
* $x_1 = x_3 + \dfrac{1}{2}x_4$
* $x_4$的分數會乘上$\dfrac{1}{2}$是因為$x_4$的指向有兩個，因此它的分數就會被分流
* $x_2 = \dfrac{1}{3}x_1$
* $x_3 = \dfrac{1}{3}x_1 + \dfrac{1}{2}x_2 + \dfrac{1}{2}x_4$
* $x_4 = \dfrac{1}{3}x_1 + \dfrac{1}{2}x_2$

你可以這樣看式子，這一刻有$x_3 + \dfrac{1}{2}x_4$的人在看網頁，下一刻會往$x_1$去，這也可以看成一個機率，目前在看網頁2的人，在下一刻有各$\dfrac{1}{2}$的機率往網頁3、4去。
### Importance - Formulas

整個關係可以看成$Ax = x$，而$x$就是$A$的eigenvector，而它對應的eigenvalue=1。我們要找的解就是對應eigenvalue=1的eigenvector。

整個網頁世界可以看成是matrix-$A$，而matrix-$A$裡面的每一個數值可以看成是網頁之間的關係。接下來只要找eigenvalue=1的eigenvector，就是PageRank的數值。
### Importance - Formulas

舉例來說，12、4、9、6就可以是這個PageRank。
### Eigenvalue = 1

這邊有一個特性說明，後續有機會課程上會證明。只要matrix內的columns的合都是1，那它就會有$\lambda=1$的eigenvalue。

而matrix-$A$的每一個column代表每一個網頁link到其它網頁的權重值，第一個column就是網頁1連接到網頁2、3、4的值，因此加總必定為1。也因此，必定有一個$\lambda=1$的eigenvalue。

但要注意的是，如果有某一個網頁它並沒有對其它網頁的超連結，而你把它考慮進來，那就會出現某一個column的值皆為0，這時候就會產生問題，因此不考慮這種狀況。
### Unique Ranking?

剛才我們計算得到PageRank，現在要討論的是，這個解是否為唯一。

事實上，當matrix-$A$的eigenvalue=1，並且其eigenspace的dimension=1，那它就會是唯一，也就是只會有一種排序方式。
### Unique Ranking?

但eigenvalue=1的eigenspace的dimension是有可能大於1的。

以上圖中的matrix-$A$為例，它的column的合皆為1，因此符合$\lambda=1$，但它的eigenspace的dimension會是2。

因此，這說明了並不是所有的eigenvalue=1的eigenspace的dimension都會是1，這種情況下的排序就不會是唯一。
### Unique Ranking?

整個PageRank的完整寫法為$M=(1 - m)A+mS$：
* $m$是一個接近0的值
* $s$是一個矩陣，所有的值皆為$\dfrac{1}{n}$，也就是如果$A$是一個3x3的矩陣，那$S$就會是3x3的矩陣，且值皆為$\dfrac{1}{3}$
* $(1 - m)A$就是使用者會依著link去其它的網頁
* $S$就是使用者也不一定會依著link去下一個網頁，而是隨機跳去某一個網頁，因此大家的機率都是平均的

在$m=0.15$的情況下，假設有一個使用者正在看網頁3，那它有85%的機率會去網頁4，但也有15%的機率去其它的網頁。

值得注意的是，$S$裡面的值並不一定都是平均分配的，如果你有花錢買廣告，也許你的機率就會高一點。

現在，我們求的不再是$A$，而是$Mx=\lambda x$，其中$\lambda=1$，因此為$Mx=x$
### Unique Ranking?

這個$M$會有幾個特性：
1. 是唯一的排序
2. eigenvalue=1，且其eigenspace的dimension=1
### Power method

假設網路世界中有1億個網頁，那matrix-$M$就會是1億x1億。計算它的RREF太瘋狂了。因此，實務上會用Power method：
* 假設要找一個vector-$x^*$，它是$\lambda=1$的eigenvalue的eigenvector，也因此$x^* = Mx^*$，並且限制$\Vert x^* \Vert_1$長度為1
* $\Vert x^* \Vert_1$，意味著向量長度以1-norm來計算
* 隨機生成一個vector-$x_0$，只要它的合是1就可以，$\Vert x_0 \Vert_1 = 1$
* 初始值並不影響結果，最後收斂都是一樣的
* 接下來，$x_1 = Mx_0$，$x_2 = Mx_1 \cdots x_k = Mx_{k-1}$
* 當$k$為無窮大的時候，$x_k = x^*$

實際上，你並不需要跑個上百萬次，只需要數十次就會收斂，收斂的意思就是$x_k$與$x_{k-1}$的值差異就會很小。