数式処理group work-4(Google page rank)

file:/~/python/doing_math_with_python/group_works_4.ipynb
cc by Shigeto R. Nishitani 2009-2018

目的:Google page rankと線形代数

Googleの躍進の土台となったPageRankは線形代数の計算です. 線形代数のコマンドを実際に使いながら,その中身を理解して行くことを 目的としています.

解説

Google page rank

Googleのpage rankは非常に単純な仮定

「多くの良質なページからリンクされているページはやはり良質なページである」

から成り立っている.博士論文のテーマを探していたスタンフォード大学院コンピュータサイエンス学部時代のラリー・ペイジ(Larry Page)が考案しました.

『そのアルゴリズムはペイジの名をとって「ページランク(Page Rank)」と呼ばれたが, 特定のサイトに入るリンクの数と,リンクしたサイトのそれぞれに入るリンクの数の, その両方を考慮に入れる. これは学術論文の引用の度数計算の方法を手本にしており、予想通りに機能した』 (『ザ・サーチ グーグルが世界を変えた』ジョン・バッテル著、中谷和男訳,2005年日経BP社) 

詳しい解説はhttp://ja.wikipedia.org/wiki/ページランク にある.

ランクの計算手順

つぎのようなリンクが張られたページ群を考える. Drawing

まずは,リンクを再現する隣接行列を作る.ページに番号をつけて,その間が結ばれている$i-j$要素を1,そうでない要素を0とする. 上の例では,

1 2 3 4 5 6 7
---
0 1 1 1 1 0 1
1 0 0 0 0 0 0
1 1 0 0 0 0 0
0 1 1 0 1 0 0
1 0 1 1 0 1 0
1 0 0 0 1 0 0
0 0 0 0 1 0 0

となる.

  1. この隣接行列を転置する.これはページランクが「どれだけリンクしているか」ではなく,「どれだけリンクされているか」を評価するためである.
  2. 転置した隣接行列tMのそれぞれの列ベクトルの総和が1となるように規格化して「推移確率行列」をつくる.(ヒント参照)
  3. 初期ベクトルとして,すべての要素が同じ値で,足して1になるような長さ7の列ベクトルを用意する.
  4. 初期ベクトルに何度か(例えば10回,あるいは収束するまで)推移確率行列を掛ける.この操作は,行列の最大固有値に属する固有ベクトルを見つけることに相当する.
  5. 得られたベクトルの各要素が対応するページの得点とみなせ,得点順にランクが高くなる.

演習

Page Rankの手順の確認

うえの手順にしたがって,「推移確率行列(transition probability matrix)」trans_matを作り,初期ベクトル(init_v)に5回ほど作用させて数字の変化を観察せよ.ページランクはどうなるか.

ヒント

手順2,3に於いて,和を取って規格化する代わりに, 以下のようにして作成した対角(diagonal)行列VAを, 転置した隣接行列tMに右からかければ推移確率行列が得られる.

> V = [1/5,1,1/2,1/3,1/4,1/2,1]
> diag(*V)

ヒント

pythonでMatrixでvectorを作ろうとすると行ベクトルになります. 右から掛けるときには転置(transpose)操作が必要です.

ヒント

はじめに

init_printing()

をいれておくと,固有値ベクトルとかの表示が綺麗.

解答例

In [1]:
from sympy import *
init_printing()
M = Matrix([[0, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 0, 0],
[1, 1, 0, 0, 0, 0, 0],
[0, 1, 1, 0, 1, 0, 0],
[1, 0, 1, 1, 0, 1, 0],
[1, 0, 0, 0, 1, 0, 0],
[0, 0, 0, 0, 1, 0, 0]])
M
Out[1]:
$$\left[\begin{matrix}0 & 1 & 1 & 1 & 1 & 0 & 1\\1 & 0 & 0 & 0 & 0 & 0 & 0\\1 & 1 & 0 & 0 & 0 & 0 & 0\\0 & 1 & 1 & 0 & 1 & 0 & 0\\1 & 0 & 1 & 1 & 0 & 1 & 0\\1 & 0 & 0 & 0 & 1 & 0 & 0\\0 & 0 & 0 & 0 & 1 & 0 & 0\end{matrix}\right]$$
In [2]:
Mt = M.T
Mt
Out[2]:
$$\left[\begin{matrix}0 & 1 & 1 & 0 & 1 & 1 & 0\\1 & 0 & 1 & 1 & 0 & 0 & 0\\1 & 0 & 0 & 1 & 1 & 0 & 0\\1 & 0 & 0 & 0 & 1 & 0 & 0\\1 & 0 & 0 & 1 & 0 & 1 & 1\\0 & 0 & 0 & 0 & 1 & 0 & 0\\1 & 0 & 0 & 0 & 0 & 0 & 0\end{matrix}\right]$$
In [3]:
V = [1/5,1,1/2,1/3,1/4,1/2,1]
V = [Rational(1,5),1,Rational(1,2),Rational(1,3),Rational(1,4),Rational(1,2),1]
VA = diag(*V)
VA
Out[3]:
$$\left[\begin{matrix}\frac{1}{5} & 0 & 0 & 0 & 0 & 0 & 0\\0 & 1 & 0 & 0 & 0 & 0 & 0\\0 & 0 & \frac{1}{2} & 0 & 0 & 0 & 0\\0 & 0 & 0 & \frac{1}{3} & 0 & 0 & 0\\0 & 0 & 0 & 0 & \frac{1}{4} & 0 & 0\\0 & 0 & 0 & 0 & 0 & \frac{1}{2} & 0\\0 & 0 & 0 & 0 & 0 & 0 & 1\end{matrix}\right]$$
In [4]:
trans_mat = Mt*VA
trans_mat
Out[4]:
$$\left[\begin{matrix}0 & 1 & \frac{1}{2} & 0 & \frac{1}{4} & \frac{1}{2} & 0\\\frac{1}{5} & 0 & \frac{1}{2} & \frac{1}{3} & 0 & 0 & 0\\\frac{1}{5} & 0 & 0 & \frac{1}{3} & \frac{1}{4} & 0 & 0\\\frac{1}{5} & 0 & 0 & 0 & \frac{1}{4} & 0 & 0\\\frac{1}{5} & 0 & 0 & \frac{1}{3} & 0 & \frac{1}{2} & 1\\0 & 0 & 0 & 0 & \frac{1}{4} & 0 & 0\\\frac{1}{5} & 0 & 0 & 0 & 0 & 0 & 0\end{matrix}\right]$$
In [5]:
v_init = Matrix([[1/7,1/7,1/7,1/7,1/7,1/7,1/7]])
v_init.shape
Out[5]:
$$\left ( 1, \quad 7\right )$$
In [6]:
trans_mat* v_init.T
Out[6]:
$$\left[\begin{matrix}0.321428571428571\\0.147619047619048\\0.111904761904762\\0.0642857142857143\\0.29047619047619\\0.0357142857142857\\0.0285714285714286\end{matrix}\right]$$
In [7]:
trans_mat* trans_mat* trans_mat* trans_mat* trans_mat* trans_mat* v_init.T
Out[7]:
$$\left[\begin{matrix}0.30766724537037\\0.164527033730159\\0.139831762566138\\0.104824983465608\\0.178323991402116\\0.0460308366402116\\0.0587941468253968\end{matrix}\right]$$

ページランクは1->5->2->3->4->7->6となる

初期ベクトルがちがうと...

初期ベクトルを

> v_init=Matrix([100,0,0,0,0,0,0])

として,推移確率行列に右から掛け,それに伴うベクトルの各要素の変化を観察し,前問と比較せよ.その結果から,推移確率行列を掛けることによってどのように状態が推移していくか,漸近していく様子を記述せよ.

解答例

In [9]:
v_init=Matrix([100,0,0,0,0,0,0])
trans_mat * trans_mat * trans_mat * trans_mat * trans_mat * v_init
Out[9]:
$$\left[\begin{matrix}\frac{2311}{72}\\\frac{11189}{720}\\\frac{2521}{180}\\\frac{3947}{360}\\\frac{3943}{240}\\\frac{191}{36}\\\frac{679}{120}\end{matrix}\right]$$

要素のそれぞれの値は初期値が違うので,異なっている.しかし,何度かかけた後のページランク(順位)は先ほどの等確率の初期値を使った場合と同じである.初期値がどうであろうと,つまりどこから入ったとしても,いくつかリンクをたどった後は同じサイトに行き着く.ステップを繰り返すと定常状態になることが期待される.これがPage Rankの値の安定性を保証し,ランクの信頼性につながっている.

固有ベクトルから確認

推移確率行列の固有値・固有ベクトルをもとめ,最大固有値に対応する固有ベクトルを取り出せ. 前問までに得られた結果と比較し,一致していることを確かめよ. ただし,固有ベクトルの大きさは任意であるため,norm()で規格化しておくと比較しやすい.

解答例

In [10]:
# trans_mat.eigenvects(error_when_incomplete=False)
trans_mat.eigenvects()
Out[10]:
$$\left [ \left ( 0, \quad 1, \quad \left [ \left[\begin{matrix}0\\1\\0\\0\\0\\-2\\1\end{matrix}\right]\right ]\right ), \quad \left ( 1, \quad 1, \quad \left [ \left[\begin{matrix}5\\\frac{52}{19}\\\frac{44}{19}\\\frac{33}{19}\\\frac{56}{19}\\\frac{14}{19}\\1\end{matrix}\right]\right ]\right )\right ]$$

my mac上ではうまく行くが,大学PC上ではエラーが出る場合がある.versionの違いによるらしい.eigenvectorsをerror_when_incomplete=Falseのオプションをつけてやると通る.その場合,初めの推移確率行列の値を単に分数で与えるのでなく,Rationalとして与える必要がある.(挙動の細かいところは不明なので,sympyのversionによるかもしれない.要確認19/5/24)

In [11]:
v = Matrix(trans_mat.eigenvects()[1][2])
In [12]:
v/v.norm()*100
Out[12]:
$$\left[\begin{matrix}\frac{9500 \sqrt{18447}}{18447}\\\frac{400 \sqrt{18447}}{1419}\\\frac{400 \sqrt{18447}}{1677}\\\frac{100 \sqrt{18447}}{559}\\\frac{5600 \sqrt{18447}}{18447}\\\frac{1400 \sqrt{18447}}{18447}\\\frac{1900 \sqrt{18447}}{18447}\end{matrix}\right]$$

Page Rankが最大固有値の固有ベクトルと一致することが,どのような初期値であろうと最終状態のベクトルが安定することを保証している.この導出は,la_eigen_vectors.ipynbの4節に示した.

In [ ]:

In [ ]: