Lecture 11 PageRank and Ridge Regression

Lecture 11: PageRank and Ridge Regression

1. PageRank

PageRank

Google PageRank

Google原始论文

Imagine surfing web by randomly clicking links. This is called a “random walk” over graph. If you do this long enough eventually reach “steady state” where Probability that you are at site $i = \pi_i$

让$\tilde A$ 表示这个图的邻近矩阵，其中：

$\tilde A = \begin{cases} 1, & \text{if links from j to i},\\ 0, & otherwise \end{cases}\tag{1}$

具体地有：

$\tilde A = \left[\begin{array}{r} 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 1 & 0 &0 & 0 \\ 1 & 0 & 1& 0 \\ \end{array} \right]\tag{2}$

接下来，让$A = \tilde A $ column-normalized version.

$\tilde A = \left[\begin{array}{r} 0 & 1 & \frac {1}{3} & \frac {1}{2}\\ 0 & 0 & \frac {1}{3} & \frac {1}{2} \\ \frac {1}{2} & 0 &0 & 0 \\ \frac {1}{2} & 0 & \frac {1}{3}& 0 \\ \end{array} \right]\tag{3}$

定义：$e_{i} = i^{th}$单位矩阵$I$的第$i$列。

那么，

$Ae_3 =\left[\begin{array}{r} 0 & 1 & \frac {1}{3} & \frac {1}{2}\\ 0 & 0 & \frac {1}{3} & \frac {1}{2} \\ \frac {1}{2} & 0 &0 & 0 \\ \frac {1}{2} & 0 & \frac {1}{3}& 0 \\ \end{array} \right] \left[\begin{array}{r} 0 \\ 0 \\ 1\\ 0 \end{array} \right]=\left[\begin{array}{r} \frac {1}{3} \\ \frac {1}{3} \\ 0\\ \frac {1}{3} \end{array} \right]\tag{4}$ $Ae_4 =\left[\begin{array}{r} 0 & 1 & \frac {1}{3} & \frac {1}{2}\\ 0 & 0 & \frac {1}{3} & \frac {1}{2} \\ \frac {1}{2} & 0 &0 & 0 \\ \frac {1}{2} & 0 & \frac {1}{3}& 0 \\ \end{array} \right] \left[\begin{array}{r} 0 \\ 0 \\ 0\\ 1 \end{array} \right]=\left[\begin{array}{r} \frac {1}{2} \\ \frac {1}{2} \\ 0\\ 0 \end{array} \right]\tag{5}$

$A_ij= Pro(\text{go to site i }| \text{ at site j})$.我们从$j$到$i$的可能性。

令：

$\underline{\pi}= \left[\begin{array}{r} \pi_{1} \\ \pi_{2} \\ \pi_{3} \\ \pi_{4} \end{array} \right]\tag{6}$

$\underline{\pi} $是到下一个网站的可能性，而且有：

$A\underline{\pi} =\underline{\pi}$

目标是找到 $\underline{\pi}$ 。

$\begin{align} &\underline{\pi} 是 \ A \ 的特征向量，令 A的特征向量\ \boldsymbol{v}_k \ 且\ \lVert \boldsymbol{v}_k\rVert_{2}=1\ 。如果\ A\boldsymbol{v}_k = \lambda_k \boldsymbol{v}_{k} , \\&对一些标量\ \lambda_k\ 成立。其中\ \lambda_k \ 叫作特征值。 \end{align}$

令 $V = [v_1, v_2, \cdots, v_n]$ 是 $A$ 的特征向量。

$AV=A[v_1, v_2, \cdots, v_n]=[\lambda_1v_1, \lambda_2v_2, \cdots, \lambda_nv_n]\\ = V\begin{bmatrix} \lambda_1 & 0 & \cdots & 0 \\ 0 & \lambda_2 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \lambda_n \end{bmatrix}=V\Lambda$

对于：

$X \in \mathbb{R}^{n \times p}, A = X^TX \in \mathbb{p \times p}.若 X= U \Sigma V^T, \ \ 那么 A = U \Sigma V^TU\Sigma V^T \Rightarrow A = V\Sigma^2 V^T \Rightarrow AV=V\Sigma^2$

$X$的$\sigma$的平方就是$A$的特征值。$X$右奇异向量就是$A$的特征向量。

PageRank 矩阵$A$有$\lambda_1=1 > \lambda_2 \ge\lambda_3 \ge \cdots\ge \lambda_n$.

算法流程

算法流程

$Let \ \ \underline{\Pi}^{0} \ \ be \ initial \ guess \ of \ \underline{\Pi} \ \ for \ k=1, 2, \cdots \\ \underline{\Pi}^{k} = \frac {A\underline{\Pi}^{(k-1)}}{\lVert A\underline{\Pi}^{(k-1)}\rVert_{2}}$ $if \ \lVert \underline{\Pi}^{(k)} - \underline{\Pi}^{(k-1)}\rVert_{2}< \epsilon, \ \ then \ stop$

又有：

$\begin{aligned} \underline{\Pi}^{1} &\propto A \ \underline{\Pi}^{0} \\ \underline{\Pi}^{2}& \propto A \ \underline{\Pi}^{1} \propto A^2 \ \underline{\Pi}^{0}\\ \vdots &\\ \underline{\Pi}^{k} &\propto A^k \ \underline{\Pi}^{0}\\ \end{aligned}\tag{7}$

和

$\begin{aligned} A &= V\Lambda V^T\\ A^2 &= V\Lambda V^T V\Lambda V^T = V\Lambda\Lambda V^T\\ \vdots &\\ A^k &= V\Lambda^{k} V^T \end{aligned}\tag{8}$

接下来证明算法为什么会有效？

假定特征向量是orthonormal($V^TV=VV^T=I$)。

相应地：

$\underline{\Pi}^{O} = c_1v_1 + c2v_2 +\cdots+c_nv_n \ \text{for} \ c_1, c_2, \cdots,c_n.assume c_1 \ne 0.\tag{9}$

其中，$v_1就等于\underline{\Pi}$.那么，

$\underline{\Pi}^{k} \propto A^k \underline{\Pi}^{0}=V\Lambda^k V^T( c_1v_1 + c2v_2 +\cdots+c_nv_n)\tag{10}$

而

$V^Tv_i =\left[\begin{array}{ll} - &\boldsymbol{v}_{1}^{\top}&- \\ - & \boldsymbol{v}_{2}^{\top}&- \\ - & \vdots &- \\ - & \boldsymbol{v}^T_{n}&- \end{array}\right]v_i=\boldsymbol{e}_{i}, Ve_i=v_i\tag{11}$

那么式10等于：

$\underline{\Pi}^{k} \propto A^k \underline{\Pi}^{0} = V(\lambda^kc_1e_1+ \cdots + \lambda^nc_ne_n)= \lambda^k_1c_1(v_1 + \frac{\lambda^k_2c_2}{\lambda_1^kc_1}v_2+\cdots+ \frac{\lambda^k_nc_n}{\lambda_1^kc_1}v_n)\tag{12}$

当$k \to \infty$,$\frac{\lambda^k_i}{\lambda_1^k} \to 0 \ for \ i \ne 1$，那么

$当 k \to \infty, \lambda^k_1c_1(v_1 + \frac{\lambda^k_2c_2}{\lambda_1^kc_1}v_2+\cdots+ \frac{\lambda^k_nc_n}{\lambda_1^kc_1}v_n) \to \lambda^k_1c_1v_1\tag{13}$

那么式12等于

$\frac{\lambda^k_1c_1v_1}{|\lambda^k_1c_1|\lVert \boldsymbol{v}_1\rVert} \to \boldsymbol{v}_1 = \Pi \tag{14}$

Wiki证明版本