Googleのページランク 基本的な仕組は数学的 グラフの行列による表現 隣接行列（推移行列、遷移行列） 固有値と固有ベクトル W大学

Presentation on theme: "Googleのページランク 基本的な仕組は数学的 グラフの行列による表現 隣接行列（推移行列、遷移行列） 固有値と固有ベクトル W大学"— Presentation transcript:

1 Googleのページランク 基本的な仕組は数学的 グラフの行列による表現 隣接行列（推移行列、遷移行列） 固有値と固有ベクトル W大学
基本的な仕組は数学的 グラフの行列による表現 　隣接行列（推移行列、遷移行列） 固有値と固有ベクトル W大学 S学部 C学科 G研究室 WEBページのリンクの関係 行列の上と左のW, S, C, Gは注釈 であり行列に含まれない

2 隣接行列を転置する 隣接行列　　　　　　　を転置する リンクを「出す」側から「受ける」側へ W大学 S学部 C学科 G研究室 WEBページのリンクの関係

3 隣接行列から推移確率行列へ 列(column)の総和が１または０になるように調整 ページの評価値をリンク先に渡す W大学 S学部 C学科
G研究室 WEBページのリンクの関係 １ 1/3

4 推移確率行列の固有値と固有ベクトル 固有値λと固有ベクトルｒ
行列 M を掛ける（乗算）ということは、グラフの 辺に沿って（確率的に）推移するということである 固有ベクトルの各要素は M を掛けても定数倍 しか変化しない。（安定している） 固有ベクトルの各要素がランクになる （ただし要素の和が１となるように正規化する）

5 固有ベクトルの具体例 GNU Octaveを使って計算する。固有値λ＝１が最大の固有値であり、固有ベクトルは下の左のようになる。
これを正規化したページランクは上の右である。 W大学 S学部 C学科 G研究室 １ 1/3 2/9 ページランクを記入した図 1/9

6 Googleにおける工夫 サイズの大きな 疎(sparse)行列の 固有ベクトルの計算 ユーザがランダムにページを渡り歩くと仮定 W大学
C学科 G研究室

7 Googleにおけるページランク 次の行列の固有ベクトルを求めて、要素の和が１になるように正規化する。 W大学 S学部 C学科 G研究室

8 より深く調べるために 本資料の例題は簡単にするために４つのサイトに閉じていた。 現実のPageRankは早稲田大学（8/10）、理工学部（6/10）、CS学科（5/10）、後藤研（4/10）。 次の資料が参考になる 本資料は上記を参考にした。ただしOctaveのスクリプトは若干改良した。 Googleの創始者による論文も入手できる。 Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, 'The PageRank Citation Ranking: Bringing Order to the Web', 1998, Taher H. Haveliwala, 'Efficient Computation of PageRank', Stanford Technical Report, 1999,

9 特集：情報数学の演習問題 2005年度の定期試験問題の解答を解説します。 2006年度の諸君の勉強の参考にして下さい。
次の事実に注意してください。 2004年度の金曜日（前半）の担当は上田和紀教授、2005年度から担当を交代して後藤滋樹です。 本日の授業では３題を解説します。残り２題は来週以降に解説する予定。

10 問１．集合 A＝{ 2, 3, 4, 5 }, 集合 B={ 1, 3, 5, 7 }とするとき、次の(1-1)～(1-6)の集合を外延的に表現せよ。
ヒント：　記号の意味を覚えておく必要がある

11 問１．解答 ヒント：　各集合の要素の数を考えてみる

12 問２．自然数の集合 N は無限集合である。このとき集合 N 2 が可算無限集合 (enumerable set, countable set) であることを示せ。

13 問2．解答 　　　　　　　　は自然数の集合の直積である。 　　　　　の要素<x,y>に自然数 を対応づける関数は全単射である。よって　　と 　　　　　　　　　とは対等で同じ濃度をもつ。 集合　　が可算無限集合であるから　　　も可算 無限集合である。

14 問３．次の(3-1)～(3-3)で定義する各々の二項関係は、（a）反対称律、（r）反射律、（s）対称律、 （t）推移律のどれを満たすか？ (3-1)～(3-3)の各々について、満たす性質すべてを記号（a, r, s, t）で答えよ。

15 問３． (3-1) A は2次元平面上のすべての点の集合で、関係 R は「点 x は点 y よりも原点より遠くない」と定義される。 (3-2) A は2次元平面上のすべての直線の集合で、関係 R は「直線 x と直線 y が平行である」と定義される。 (3-3) 有限集合 A={0, 1, 2, 3, 4} の上でRは 　　R={<0,0>,<1,1,>,<2,2>,<3,3>,<4,4>}というグラフで定義される。

16 問3．解答 (3-1) r, t (3-2) r, s, t (3-3) a, r, s, t

17 レポートの提出方法 (2006年度 後藤担当） レポート用紙を下記のURLからプリントする
レポートの提出方法 (2006年度 後藤担当） レポート用紙を下記のURLからプリントする １班 (奇数班), と２班 (偶数班) で用紙が異なる 提出場所は、60号館2階の CS学科事務所前のBOX BOX番号は掲示による 締切厳守のこと 提出期間は、2006年5月22日(月)～26日(金)の間

18 問１ 集合の要素 次の集合に属するすべての要素を列挙せよ。 例： [1-1] (または P (P (f g )) ) [1-2]
問１　集合の要素 次の集合に属するすべての要素を列挙せよ。 例： [1-1] (または　 P (P (f g )) 　) [1-2] ヒント：　[1-2]では＋の左と右の集合の要素の数を、まず数えてみる。 　　　　　これは有限集合である。

19 問2 関数 次の集合に属する要素を具体的に一つ挙げよ。 N{0,1}×{2,3｝
問2　関数 次の集合に属する要素を具体的に一つ挙げよ。 　　N{0,1}×{2,3｝ ヒント：　まず集合 {0, 1}×{2, 3}　の要素を具体的に書いてみる。

20 問３　集合の濃度（可算集合） 自然数の集合 N={0,1,2,…}の直積 N2=N×Nから N への関数 f(x,y)={(x+y)2+3x+y}÷2 を考える。 (3-1) f(0,0), f(0,1), f(1,0) ,f(0,2), f(1,1), f(2,0)の値を計算せよ。 (3-2) N2は可算集合であることを説明せよ。

21 問４　二項関係の反射推移的閉包 集合A = {p, q, r, s} 上の二項関係 R = {<p, q>, <q, r>, <r, s>, <r,r>} の 反射推移閉包（すなわち R * ）を求めよ． ヒント p q r s R0 R1 R2 R3 R4 p q r r,s s