Extrapolation Methods for Accelerating PageRank Computations
-
Sepandar D. Kamvar, Taher H. Haveliwala, Christopher D. Manning, Gene H. Golub
-
WWW 2003
概要
-
PageRankのためのPower methodの高速化
-
25--300%速くなった
-
メモ:イントロで…
-
Dangling nodesからは一様に飛ぶとしている
Aitken Extrapolation
-
$$ x^{(k-2)} $$が上位2つの固有ベクトルの線形結合で表せるとする
-
$$ x^{(k-2)}, x^{(k-1)}, x^{(k)} $$を使って$u_1$を求めたい!
-
$$ x^{(k-2)} = u_1 + \alpha_2 u_2 $$
-
$$ x^{(k-1)} = u_1 + \alpha_2 \lambda_2 u_2 $$
-
$$ x^{(k )} = u_1 + \alpha_2 \lambda_2^2 u_2 $$
-
$$ g_i = (x_i^{(k-1)} - x_i^{(k-2)})^2 = \alpha_2^2(\lambda_2-1)^2(u_2)^2_i $$
-
$$ h_i = x_i^{(k)}-2x_i^{(k-1)}+x_i^{(k-2)} = \alpha_2(\lambda_2-1)^2(u_2)_i $$
-
$$ f_i = g_i/h_i = \alpha_2 (u_2)_i $$
-
だから,$$ f = \alpha_2 u_2 $$
-
$$ u_1 = x^{(k-2)}-f $$
-
実際には,仮定が近似なので,u1も近似
-
でも,u2の係数は小さくなる(なりそう?)
Epsilon Extrapolation
-
$$ g_i = (x_i^{(k-1)} - x_i^{(k-2)}) (x_i^{(k)} - x_i^{(k-1)}) $$とすると,
-
$$ u_1 = x^{(k-1)} - \alpha_2 \lambda_2 u_2 = x^{(k-1)} - (g_i / h_i)_i $$
Quadratic Extrapolation
-
$$ x^{(k-3)} = u_1 + \alpha_2 u_2 + \alpha_3 u_3 $$として,
-
$$ x^{(k-2)}, x^{(k-1)}, x^{(k)} $$を使って頑張る(式が超長いので省略)
実験
-
「テレポーテーションが少ない=αが大きい」とPower methodはどんどん遅くなる
-
Quadratic Extrapolationはぼちぼち耐えている
-
ただし,α=0.9ではほぼ同じ
-
現在主流の0.85ではほとんど差がつかないのかな?
収束の尺度
-
唐突だけど,$$ \delta_k = \| Ax^{(k)}-x^{(k)} \| $$って良いの?
-
KDist :=
-
Ax^(k)基準では$$ u \preceq v $$なのに,
-
x^(k)基準では$$ v \preceq u $$なペア(u,v)の個数(割合)
-
KDistもKmin(既存の何か)もL_1も大体同じ(?!)
PageRank PageRank計算 Personalized PageRank WWW
2015/07/27 17:03
最終更新:2016年12月05日 23:23