Googleの躍進の土台となったPageRankは線形代数の計算です. 線形代数のコマンドを実際に使いながら,その中身を理解して行くことを 目的としています.
Googleのpage rankは非常に単純な仮定
「多くの良質なページからリンクされているページはやはり良質なページである」
から成り立っている.博士論文のテーマを探していたスタンフォード大学院コンピュータサイエンス学部時代のラリー・ペイジ(Larry Page)が考案しました.
『そのアルゴリズムはペイジの名をとって「ページランク(Page Rank)」と呼ばれたが, 特定のサイトに入るリンクの数と,リンクしたサイトのそれぞれに入るリンクの数の, その両方を考慮に入れる. これは学術論文の引用の度数計算の方法を手本にしており、予想通りに機能した』 (『ザ・サーチ グーグルが世界を変えた』ジョン・バッテル著、中谷和男訳,2005年日経BP社)
詳しい解説はhttp://ja.wikipedia.org/wiki/%E3%83%9A%E3%83%BC%E3%82%B8%E3%83%A9%E3%83%B3%E3%82%AF にある.
つぎのようなリンクが張られたページ群を考える.
まずは,リンクを再現する隣接行列を作る.ページに番号をつけて,その間が結ばれている$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
となる.
うえの手順にしたがって,「推移確率行列(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)
はじめに
init_printing()
をいれておくと,固有値ベクトルとかの表示が綺麗.
ページランクは1->5->2->3->4->7->6となる
初期ベクトルを
> v_init=Matrix([100,0,0,0,0,0,0])
として,推移確率行列に右から掛け,それに伴うベクトルの各要素の変化を観察し,前問と比較せよ.その結果から,推移確率行列を掛けることによってどのように状態が推移していくか,漸近していく様子を記述せよ.
要素のそれぞれの値は初期値が違うので,異なっている.しかし,何度かかけた後のページランク(順位)は先ほどの等確率の初期値を使った場合と同じである.初期値がどうであろうと,つまりどこから入ったとしても,いくつかリンクをたどった後は同じサイトに行き着く.ステップを繰り返すと定常状態になることが期待される.これがPage Rankの値の安定性を保証し,ランクの信頼性につながっている.
推移確率行列の固有値・固有ベクトルをもとめ,最大固有値に対応する固有ベクトルを取り出せ. 前問までに得られた結果と比較し,一致していることを確かめよ. ただし,固有ベクトルの大きさは任意であるため,norm()で規格化しておくと比較しやすい.
Page Rankが最大固有値の固有ベクトルと一致することが,どのような初期値であろうと最終状態のベクトルが安定することを保証している.この導出は,la_eigen_vectors.ipynbの3節に示した.
my mac上ではうまく行くが,大学PC上ではエラーが出る場合がある.versionの違いによるらしい.eigenvectsをerror_when_incomplete=Falseのオプションをつけてやると通る.その場合,初めの推移確率行列の値を単に分数で与えるのでなく,Rationalとして与える必要がある.(挙動の細かいところは不明なので,sympyのversionによるかもしれない.要確認19/5/24,つけないと私のでも動かなくなった20/10/29.)
最後の固有値を求めるeigenvectsで失敗するかもしれません. これはsympyのversionによるようです.1.6.1ではダメです. それまでのは行けそうです.
上の方で,対角ベクトルを与えるところで, Rationalを使うとちゃんと求めてくれます.
#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]
これに関する問い合わせと開発者の反応はGithubのissue の通りです. この辺りがOSS開発ソフトで時々おこる問題です. そういうものだということを覚悟して, いくつかのライブラリや他のソフトで結果をクロス検証することを心がけてください.
<2020-11-02 月>