PageRankのべき乗法、マルコフ連鎖の凝集
(「Google PageRankの数理」から)

@flashingwind

2010.5.3

2006年度の専攻科ゼミで参考にしたレビュー[1]の著者らによるより詳細な解説が、昨年(日本語版が)出版された[2]である。

PageRankべき乗法の収束回数は高々50〜100

「漸近的な収束の速さ(asymptonic rate of convergence)」:

$\lambda_1 / \lambda_2 ^k \rightarrow0$ の速さ
Gが原始であるから $\lambda_2<1$
$\lambda_2$ はスペクトラム(スペクトル半径？)が

$\begin{displaymath}\sigma(G)={1,\lambda_2,\cdots,\lambda_k}\end{displaymath}$

および

$\begin{displaymath}\sigma(S)={1,\mu_2,\cdots,\mu_k}\end{displaymath}$

であるとき、

$\begin{displaymath}\lambda_k=\alpha\mu_k \quad(k=1,2,3n\cdots,n)\end{displaymath}$

. ただしSは確率的になるよう規格化した隣接行列。

$\begin{displaymath}G=\alpha S+(1-\alpha)/n\bf {e}\bf {e}^T\end{displaymath}$

.
ウェブのリンク構造は可約であることが多いから最悪 $\lambda_2(S)\vert=1$ があり得て、

$\begin{displaymath}\vert\lambda_2(G)\vert\leq\alpha\vert\lambda_2(S)\vert=\alpha\end{displaymath}$
つまり回の繰り返しに対して $\alpha^k\rightarrow 0$ の速さで収束
言い換えると、精度(スコアの桁数)を $\tau$ 桁として、 $-\tau/\log_10\alpha$ 回
$\alpha=0.85$ として2〜3桁なら50回

疎であるので…

リンク変更時の再計算の計算量削減のため。

確率分布をつかう？

$\begin{displaymath}\Phi^T=(\phi_1,\phi_2,\cdots,\phi_m)\end{displaymath}$
G(固有ベクトル $\pi^T$ )より小さい、確率分布C(固有ベクトル $\psi^T$ )を用いる
歴史的には「ほとんど分離された連鎖の定常分布」を評価するのに使われてきた
状態空間Sを、 $S=L\cup L^-$ に分け(Lはリンクが更新された可能性が高いノード)
- これに従ってGを分割できる
- $\Phi^T$ … … $\xi ^T$ … $\omega^T$
(めんどくさいのでp.135参照)

本来は分割統治のためのものである。が、以下などは、リンク構造に関係すると考えられ、クラスタリングのためにに使えないか。指標: $\pi$ と $\pi$ 、 $\omega^T$ と $\pi_2 ^T$ がどの程度近似できているか。

M-行列(ミンコフスキー行列)
- 正方行列がM-行列であるとは、ある行列( $b_{ij}>=0$ )が存在し、を満たす実数 $r>=\rho(B)$ が存在
対角か可能行列のスペクトル定理？
スペクトル射影子？:

$\begin{displaymath}\lim_{k\rightarrow\inf}A^k=G\end{displaymath}$

はR(I-A)沿いのN(I-A)への射影子

1: Amy N.Langville, Carl D.Meyer ``A Survey of Eigenvector Methods for Information Retrieval'', SIAM Review Vol.47 No.1, pp.135-161 (2005).
2: Amy N.Langville, Carl D.Meyer, 岩野和生 (翻訳), 黒川利明 (翻訳), 黒川洋 (翻訳)『Google PageRankの数理―—最強検索エンジンのランキング手法を求めて』共立出版 (2009/10/10).

PageRankのべき乗法、マルコフ連鎖の凝集
(「Google PageRankの数理」から)

この文書はLaTeX2HTML 翻訳プログラム Version 2008 (1.71)

を日本語化したもの( 2008 (1.71) JA patch-2.1beta1.12 版)

を用いて生成されました。

コマンド行は以下の通りでした。:
latex2html seminar-20100503html.tex -split 0 -html_version 4.0 math -antialias.

翻訳は munenori によって 2010-06-04 に実行されました。

munenori 2010-06-04