PageRankの仕組 林晋.

Presentation on theme: "PageRankの仕組 林晋."— Presentation transcript:

1 PageRankの仕組 林晋

2 グーグル の検索方式 2 グーグル検索では、まず、WEB上の「すべて」のページに PageRank （ページランク）という数値を与える。
ただし，これは原理的な話. 実際には，検索者がどの国にいるか，などの情報も「ランク」の判定に使われている．だから，世界のどこで検索するか, どの言語のグーグル検索のページを使うかなどで順位が変わる． また、「すべてのページ」が実際にグーグルのデータセンター上にあるわけではない。「「すべて」の意味は大幅に割り引いて見たほうがよい。 キーワードが含まれる１万件くらいのページが見つかるのは珍しくないので，より重要な情報が，より前に表示されるかどうか，つまり，PageRank が「ユーザーの期待」にどれだけ合致しているかで検索エンジンの良し悪しが決まることに注意。 グーグル検索は，登場当初，この「ユーザーの期待への合致度」が，他の検索に比べて，遥かに良かったため、それがグーグルが現在のように成長した一つの原因と言われる。 3/20/2017

3 グーグル の PageRanking 創業者 Larry Page（ラリー・ページ）, Sergey Brin （セルゲイ・ブリン）が, スタンフォード大学 CS (Computer Science Department) の大学院生だったころに書いた共著論文(1,2)のアイデアである)ペイジ・ランク PageRank の有効性を確かめるために始めたサービス.　ペイジ・ランクの「ペイジ」は，頁ではなくて Page という姓から来ているということになっている． 最初は スタンフォード大のサーバーを使う実験的サービスだったが，会社を設立後，驚異的な成長をとげ，2004年には，同じ スタンフォード大 CS の学生が設立した Yahoo を時価総額で追い抜いた。 3/20/2017

4 Page の PageRank formula
ページ x の PageRank を R(x)とする. ページ u にリンクを張っている page の集合を Buとし，そのメンバーとなる page v から伸びているリンクの総数を Nvとし，R(u)を次のように計算する(Page, Brin の論文より）： 3/20/2017

5 PageRank の算出法 信用のおける重要なページには，大きな PageRank が与えられるようにしておき，すべての page u に大して，前頁の式が成り立つように，PageRank の計算を何度も繰り返す（正確にいうと，page の数だけの行と列を持つ行列の固有値計算というものを行う. ） これは大学初年級レベルの数学だが，行列の大きさが膨大な場合は難しいテクニックが必要となる. 3/20/2017

6 社会テクノロジー PageRank その結果は，それ以前のどの検索エンジンをも，はるかに凌ぐ的中率を示した.
Google以前の検索エンジンは，あるページが検索キーワードに関係が強いか否かを，そのページの「構造」だけから判定していた．あるいは，Yahoo のように，人間（検索会社の社員）が，一つ一つのページをブラウズして分類，ランク付けしていた． 一方でペイジ・ランクを使う Google 検索は，WEB という現実社会の「像」から関係性を全自動で算出している．つまり，ひとつの文章（ページ）の構造でなく, その文章が置かれている社会的位置により，そのページが理解される．また，その計算が機械により行われ，それを分類しランク付けする「賢い社員」の知的労働を必要としなかった． つまり，ペイジ・ランクというテクノロジーは，人間の判断・社会の判断を反映する「社会テクノロジー」であり，それ故に「的中率」が飛躍的に向上した．そして，同時に学生2名だけでも，多数のコンピュータという「労働者」があれば運用できるものだった． 3/20/2017

7 リンクはだれが「生産」するのか？ 「PageRankの原料」ともいえる，個々のリンクは誰が作ったのか？個々のリンクは，個人あるいは団体が，自らの目的のために作ったものでグーグル検索のために作られたわけではない． Googleはある意味では他人の家に土足で入ってきているようなもの．ページがその持ち主の意思で公開されていることから，この表現は強すぎるが，「道に面した商店に何も買わない人がやってきて商品の写真を写して出て行く，あるいは店頭にならべられた商品のリストを作って『ありがとう』も言わずにでていく」，この状況に例えることが出来る． 実際，グーグルが無名だった頃，「自分のページに勝手にグーグルのクローラがアクセスして情報を持っていった」という抗議がグーグルに寄せられていた時期があった。 現在は，逆で，グーグルがあるページを無視すれば「グーグル八分」としてグーグルが非難され、訴訟になりかねない。