2001年度情報数学

Googleのページランク
W
• 基本的な仕組は数学的
W 0
グラフの行列による表現

隣接行列（推移行列、遷移行列） S  0
C 0
固有値と固有ベクトル

G  1
S学部
W大学
C学科
G研究室
S C G
1 0 0

0 1 0
0 0 1

1 1 0 
 1 頂点iから頂点 jに辺がある
aij  
０頂点iから頂点 jに辺がない
行列の上と左のW, S, C, Gは注釈
であり行列に含まれない
WEBページのリンクの関係
1
隣接行列を転置する
• 隣接行列 A  (aij ) を転置する
リンクを「出す」側から「受ける」側へ
S学部
C学科
A 
t
W大学
G研究室
WEBページのリンクの関係
0

1
0

0

0
0
1
0
0
0
0
1
1

1
1

0 
2
隣接行列から推移確率行列へ
• 列(column)の総和が１または０になるように調整
ページの評価値をリンク先に渡す
１
S学部
１
1/3
W大学
1/3
C学科
1/3
１
G研究室
M 
0

1

0

0
0 0
0 0
1 0
0 1
1 
3
1 
3
1 
3
0 
WEBページのリンクの関係
3
推移確率行列の固有値と固有ベクトル
• 固有値λと固有ベクトルｒ
M r  r
• 行列 M を掛ける（乗算）ということは、グラフの
辺に沿って（確率的に）推移するということである
• 固有ベクトルの各要素は M を掛けても定数倍
しか変化しない。（安定している）
固有ベクトルの各要素がランクになる
（ただし要素の和が１となるように正規化する）
4
固有ベクトルの具体例
• GNU Octaveを使って計算する。固有値λ＝１が最大
の固有値であり、固有ベクトルは下の左のようになる。
 0.11111


 0.22222
 0.33333


 0.33333


 0.20851


 0.41703
 0.62554


 0.62554


• これを正規化したページランクは上の右である。
2/9
１
１
S学部
1/3
1/9
W大学
1/3
C学科
1/3
1/3
１
G研究室
ページランクを記入した図
1/3
5
Googleにおける工夫
• サイズの大きな
疎(sparse)行列の
固有ベクトルの計算
• ユーザがランダムに
ページを渡り歩くと仮定
S学部
W大学
1 N 
N 4
1
 4
1
 4
1
 4
1
 4
1
1
1
1
4
4
4
4
1
1
1
1
4
4
4
4
1 
4
1 
4
1 
4
1 
4
C学科
G研究室
6
Googleにおけるページランク
• 次の行列の固有ベクトルを求めて、要素の和が１に
なるように正規化する。
 4
0.85 M  0.15 1
N 4
 0.0375

 0.8875

0.0375

 0.0375

S学部
W大学
0.0375
0.0375
0.8875
0.0375
0.0375 0.320833

0.0375 0.320833
0.0375 0.320833

0.8875 0.0375 
C学科
 0.12649


 0.23401
 0.32540


 0.31409


G研究室
7
より深く調べるために
• 本資料の例題は簡単にするために４つのサイトに閉じて
いた。
現実のPageRankは早稲田大学（8/10）、理工学部
（6/10）、CS学科（5/10）、後藤研（4/10）。
• 次の資料が参考になる
http://www.kusastro.kyoto-u.ac.jp/~baba/wais/pagerank.html
本資料は上記を参考にした。ただしOctaveのスクリプトは若干改良した。
• Googleの創始者による論文も入手できる。
Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd,
'The PageRank Citation Ranking: Bringing Order to the Web', 1998,
http://www-db.stanford.edu/~backrub/pageranksub.ps
Taher H. Haveliwala, 'Efficient Computation of PageRank', Stanford
Technical Report, 1999,
http://dbpubs.stanford.edu:8090/pub/1999-31
8
特集：情報数学の演習問題
• 200６年度の定期試験問題の解答を解説します。
200７年度の諸君の勉強の参考にして下さい。
• 次の事実に注意してください。
2004年度の金曜日（前半）の担当は上田和紀教
授、2005年度から担当を交代して後藤滋樹です。
• 本日の授業では３題を解説します。残り２題は来
週以降の授業の範囲です。順次解説する予定。
9
問１．集合 X＝{ 1, 2, 3, 4, 5 }, 集合 Y={ 3, 5, 7 }
とするとき、次の(1-1)～(1-6)の集合を外延的に表
現せよ。
(1  1)
X Y
(1  2)
X Y
(1  3)
X Y
(1  4)
X Y
(1  5)
X Y
(1  6) 2  (Y )
Y
• ヒント：記号の意味を覚えておく必要がある
10
問１．解答
(1  1)
(1  2)
X  Y  1, 2, 3, 4, 5, 7}
X  Y   3, 5 
 1,3 , 1,5 , 1,7 , 2,3 , 2,5 , 2,7 , 


(1  3) A  B   3,3 , 3,5 , 3,7 , 4,3 , 4,5 , 4,7 ,


 5,3 , 5,5 , 5,7

(1  4) A  B   0,1 , 0,2 , 0,3 , 0,4 , 0,5 , 1,3 , 1,5 , 1,7
(1  5)
A  B  1, 2, 4 

(1  6) 2 B  ( B )
  , 3, 5, 7, 3,5, 3,7, 5,7, 3,5,7
• ヒント：各集合の要素の数を考えてみる
11
問２．自然数の集合 N は無限集合である。
(2—1) N 2= N×Nに属する要素（元）を３つ
以上具体的に記述せよ。
(2—2) N 2が可算無限集合 (enumerable
set, countable set) であることを示すには、
次の関数 f (x,y) を使えば良い。
f (x,y)={(x+y)2+3x+y}÷2
具体的に、この関数をどのように使うのか説
明せよ。
• ヒント： N 2 という表記法を誤解しないように
12
(2—1) 解答（次は解答の一例である。正解は、
これに限らない。）
<0,0>, <0,1>, <1,0>.
(2—2) 解答
関数 f(x,y)はNからN2への全単射である。
よってNとN2とは対等で同じ濃度を持つ。集合Nが
可算無限集合であるから、集合N2も可算無限集
合である。
13
問３．次の(3—1)～(3—4)で定義する各々の二項
関係は、（a）反対称律、（r）反射律、（s）対称律、
（t）推移律のどれを満たすか？
(3—1)～(3—4)の各々について、満たす性質すべ
てを記号（a, r, s, t）で答えよ。
(3—1) A は2次元平面上のすべての直線の集合
で、関係 R は「直線 x と直線 y が平行である」と
定義される。
14
(3—2) A は自然数の集合で、関係Rは「自然数 x
は自然数 yよりも小さい、または xとyは等しい」
と定義される。
(3—3) A は2次元平面上のすべての点の集合で、
関係 R は「点 x は点 y よりも原点より遠くない」
と定義される。
(3—4) 有限集合 A={0, 1, 2, 3, 4} の上でRは
R={<0,0>,<1,1,>,<2,2>,<3,3>,<4,4>}という
グラフで定義される。
15
問3．解答
(3—1) r, s, t
(3—2) a, r, t
(3—3) r, t
(3—4) a, r, s, t
16
補足
(3—4) 有限集合 A={0, 1, 2, 3, 4} の上でRは
R={<0,0>,<1,1,>,<2,2>,<3,3>,<4,4>}というグラフ
で定義される。
Rが推移律を満たすかどうかを検討する
xRy ∧ yRz が成立つ <x,z> は必ず x=z となる。
つまり xRz を満たす。
注意１）xRy は x=y と書ける。
注意２）xRy ∧ yRz が成立たない<x,y>,<y,z>につい
ては、xとzの間に何の関係がなくても良い
17
レポートの提出方法
(200７年度後藤担当）
• レポート用紙を下記のURLからプリントする
http://www.goto.info.waseda.ac.jp/~goto/infomath.html
１班 (奇数班), と２班 (偶数班) で用紙が異なる
• 提出場所は、60号館2階の
CS学科事務所の中の
レポートBOX
• 締切厳守のこと
提出期間は、200７年６月１１日(月)～１５日(金)の間
18
ＣＳ連絡事務室開室時間
• 月曜日から金曜日の 9：00～17：15
• 12：30～13：30は昼休みのため閉室
• 土曜は休日
19
問１集合と非順序対
• 集合 A={u, v, w}, 集合 B={1, 2, 3}と
するとき、次のように内包的に定義される集
合 C を考える。
{ {{a},{a, b}} | a  A, b  B}
すなわち、Cの要素は集合{{a},{a,b}}で
ある。
• この集合Cの要素をすべて示せ。ただし集合
として同じものを重複して掲げないこと。また
集合Cの要素の数を答えよ。
20
問２関数とグラフ
(2—1) 有限集合 B={t, f} を考える。B3 という
集合を直積と考えて、B3の要素を列挙せよ。
(2—2) 3を自然数の集合 {0, 1, 2}と考えると、
B3 は集合3から集合 Bへの関数の全体となる。
このように考えた場合には、B3の各要素は個々
の関数となる。B3の各要素を関数のグラフとし
て表現せよ。
ヒント：要素を列挙するため、解答が相当の分量になるのでは
ないか、と懸念するかもしれない。実際には要素の数は多くない。
21
問３集合の濃度（可算集合）
• 自然数の集合 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) f(x,y) が全単射であることを、全単射の定
義に照らして丁寧に説明せよ。
22
問４二項関係
集合Aは、２次元平面上の点の集合である。
(4—1)Aの上の関係Rが次のように定義されているとき、
この関係Rが反射率を満たすか否かを解答せよ。
 x, y  R  u , v  
x2  y2  u 2  v2
(4—2) 関係Rが推移律を満たすか否かを解答せよ。
(4—3) Aの上の関係Dが次のように定義されているとき、
この関係Dが同値関係であるか否かを解答せよ。
 x, y  D  u , v   x  y  u  v
2
2
2
2
23

Download Report