データモデリング Webページの検索とランキング Googleはこんなことをしている

検索の精度を示す指標 適合率(Precision) 再現率(Recall) P = F値 R = F = R P 1 R P 2 検索結果内の正解文書数 検索された文書の数 再現率(Recall) 全文書内の適合文書の数 F値 F = 全文書内の 適合文書の数 （本当の解集合） 検索された 文書の数 P = R P R = 全文書 1 R P + 2 検索結果内の 正解文書数 条件が厳しくなるとPが上がり Rが下がる 条件が緩くなるとPが下がり Rが上がる

キーワードらしさ tf-idf 文章中の特徴的な単語（キーワード）を抽出するためのアルゴリズム 文書の集合 { D1, D2, …., Dn}内の文書 Di を単語の集合 { W1, W2, …, Wm} とみる 個々の単語の評価 tf（Term Frequency）は単語の頻度 繰り返される　単語は評価が高い 文書Dk でのWi の出現数 / Dk　の単語数 Idf(Inverse Document Frequency) Wi は，特定の文書 Di にしか出現しない　なら、評価が高い。逆にWi は，すべての文書に出現するなら、その　評価は低い 文書の集合 { D1, D2, …., Dn}のなかでWi が現れる比の逆数 そのままでは大きすぎるので log をとる 単語の評価 = 頻度・ log (総文書数/出現文書数)

クローリング(Crawling) リンクの自動航行 クローラが収集するもの 一度、訪問したサイトはそこからのリンクを辿らない クローラと呼ばれるプログラムが、インターネット上のWebペー ジのリンクをたどりながら情報を収集 クローラは　スパイダ（蜘蛛）　とも呼ばれる クローラが収集するもの 各ページに含まれる各単語の tf-idf値 を計算 ページごとに文書ベクトル化 　 文書ベクトルDk Dk = (W1 のtf-idf値, W2 のtf-idf値, …, Wn のtf-idf値) 各ページのリンク先を記録（PageRankで利用） 一度、訪問したサイトはそこからのリンクを辿らない クローリングは 定期的 に実施される

空間ベクトル法 ページの文書ベクトル Dk と問合せのベクトルQの類似度で検索を実施 文書「空間ベクトル法」 問合せ（類似度 Web 検索） Dk = (W1 のtf-idf, W2 のtf-idf, …, Wn のtf-idf) Q = (W1 のtf-idf, W2 のtf-idf, …, Wn のtf-idf) 2つのベクトルのコサイン類似度 　　似ているときに１、逆方向の時に-1 文書「空間ベクトル法」 類似度は0.7, Webは0.2, 検索は1.4 問合せ（類似度 Web 検索） 類似度1, Web 1, 検索 1 類似度が高いものを選択 類似度 問合せ 文書 Web 検索

PageRank Algorithm 多くの検索結果を順位づけて並べたい Google 創始者の Larry Page と Sergey Brin が米スタンフォード大学大学院在籍中に開発 論文の評価にヒントを得て考え出された PageRankとは 「多くの良質なページからリンクされているページは、 やはり良質なページである」 という再帰的な関係をもとに、すべてのWebページの重要度を判定したもの PageRank 自体はユーザが検索式に与えた語句とはまったく無関係な、 すでに定まった量

Googleの紹介ページより ページAからページBへのリンクをページAによるページBへの支持投票と みなし、Googleはこの投票数によりそのページの重要性を判断します。 しかしGoogleは単に票数、つまり　リンク数を見るだけではなく、票を投じた ページについても分析します。「重要度」 の高いページによって投じられた票はより高く評価されて、それを受け取ったページ を「重要なもの」 にしていくのです。 PageRankは ページの重要度を示す総合的な指標であり、各検索に影響 されるものではありません

PageRankの意味の図示 あるページの PageRank を、そのページに存在する発リンク数で 割った数が、リンク先のページの PageRank に加算される

数式を使って表現 P(j) P(i) = Σ Oj すべてのWebページの集合を V とし，それらの間のリンクの集合を E とするとWeb空間は G = ( V , E ) 　で表現できる ページの総数を n とし，ページ i のPageRankスコアを P(i)， ページ j からの外向けリンクの数を Oj とすると ただし、(j i) はページ j からページ i へのリンク P(i) = Σ P(j) Oj (j i) ∈ E （式１）

ベクトルと行列で表現 PageRankのスコアを値とする n 次元ベクトルを P, ページ間のリンクを表現する行列を A とすると、 　　先の式は 　　と表される （式2） Oi 1 (i j) ∈ E の場合 ページ i から j にリンクがあれば リンク元ページ i の外向きリンク数の逆数 Ai j ＝ （式3） A は，ページ i から j にリンクがあればリンク元ページ i の外向きリンク数の逆数を 要素 Aij　とする行列 前スライドの∑の式と今スライドのAの式の定義をよく見比べると，リンクの出るページと入るページで i と ｊ が入れ替わっている． ページ i （1≦ i ≦n）からページ j にリンクがある場合に，ページ j　のページランク P(ｊ） は P(j) = A11 P(1) + A21 P(2) +．．．+An1P(n) = (1/o1) P(1) + (1/o2) P(2) +．．．+ (1/on) P(n) となる．これを行列とベクトルの積で表現するには P(i) = A11 P(1) + A12 P(2) +．．．+A1nP(n) となっていて欲しい．どうすればよいか？ i と j をひっくり返せば良い． つまり　転置した行列を用いれば良い． 0 それ以外 （式4）

どうしてAの転置行列　At　なの？ さきの(式1)とAの定義(式3)をよく見比べると，リンクの出るページと入るページで i と j が入れ替わっている． ページ i （1≦ i ≦n）からページ j にリンクがある場合に，ページ j 　のページランク P(j） は p(j) = A11 p (1) + A21 p (2) +．．．+An1p (n) = (1/o1) p(1) + (1/o2) p(2) +．．．+ (1/on) p(n) となる．Aの２つある添字のうち，さきにある添字が増える式になっている．ページランクの計算を，通常の行列とベクトルの積で表現するには p (i) = A11 p (1) + A12 p (2) +．．．+A1n p (n) となって， Aの２つある添字のうち，後にある添字が増える式になって欲しい．どうすればよいか？ i と j をひっくり返せば良い． つまり　転置した行列を用いれば良い．

図による例示 この図を表現する行列 A は A ＝ 0 1/5 1/5 1/5 1/5 0 1/5 1 0 0 0 0 0 0 1/2 1/2 0 0 0 0 0 0 1/3 1/3 0 1/3 0 0 1/4 0 1/4 1/4 0 1/4 0 1/2 0 0 0 1/2 0 0 0 0 0 0 1 0 0 A ＝ この行列 A をページランク p1, p2, …, pn　からなるベクトルPにかけてはいけない． そんなことをしたら 　　　A11 P(1) + A21 P(2) +．．．+An1P(n) になってしまう．これだと，第2項は 　「ページ1からページ２へのリンクがあるときに，ページ1の外向きリンクの逆数を，リンクの先のページランクP(2)にかける」 という意味になってしまう．そうではなく，第2項は 　　「ページ2からページ1へのリンクがあるときに，ページ2の外向きリンクの逆数を，リンクの先のページランクP(１)にかける」 となっていないといけない． 行列　Aを転置すると（A の行と列を入れ替えると），まさしくそうなる． A21だから, ページ2から1へリンクがあるかどうか．

各ページのPageRankは不変な値 | M– λ E | = 0 不変なベクトル P は A をかけても P のまま これは、行列とベクトルの固有値問題 P ≠ 0 が存在するためには これは λ の n 次方程式で、λ の実数解は高々 n 個 この場合 P は固有値 λ = 1 に対応する固有ベクトル 固有値 λ = 1 の存在には特定条件の成立が必要 成立すれば，n 元連立方程式 より， べき乗法で P も計算可能 | M– λ E | = 0

Page と Brin はマルコフモデルに着目 ユーザがリンクを無作為にたどるとすると、ページ遷移はマルコフ遷移モデル 次の条件が満たされると、固有値 λ = 1 が存在 A がマルコフ推移の遷移確率行列である 各行の値を総和すると 1 外部にリンクを持たないページがない グラフが強連結である どのページからも、どのページへも辿り着ける グラフが非周期的である あるページからそこに戻るパスの長さが k (>1) の整数倍であれば周期的,そうでなければ非周期的(すなわち k = 1) このような A が見つかるということは、ユーザがリンクをクリックし続けると、ある特定のページに行き着く確率を計算できることを意味する

Page と Brin のアイデア 要素がすべて1のベクトルが e のとき、遷移確率は 遷移確率行列を修正 外部リンクが無いページからは、各ページに同じ確率で遷移 このページに相当する A の行はすべて 1/n ユーザは確率 d でリンクを辿る（1-dで新ページを検索） 各ページから すべてのページ へのリンク追加（確率は 1- d ） 要素がすべて1のベクトルが e のとき、遷移確率は Page と Brin の論文では d = 0.85 ①について，外部にリンクを持たないページからはn個あるページのどれにでも同じ確率（1/n）で移動する ②について，あるページから出ているリンクをたどる確率は d で，リンクを辿らず無作為に新しいページに移る確率は(1-d)であるとPageとBrinは考えた． 式の中で，(1-d)e　の項はリンクを辿らず無作為に新しいページに移行した時を表し，dAp　の項は現在のページからのリンクを辿った時を表す．

[補助]　PageとBrinは考えた！ ①について，外部にリンクを持たないページからはn個あるページのどれにでも同じ確率（1/n）で移動する．（これでA がマルコフ推移の遷移確率行列になった） ②について，あるページから出ているリンクをたどる確率は d で，リンクを辿らず無作為に新しいページに移る確率は(1-d)である．（これで，どのページへも辿り着けるようになった．また周期ｋが１となったので、周期グラフでもなくなった） 式の中で，(1-d)e　の項はリンクを辿らず無作為に新しいページに移行した時を表し，dATp　の項は現在のページからのリンクを辿った時を表す．

すべてのページの PageRank を計算 不変になるまで遷移確率行列を繰り返し適用 k = 1 do { k = k + 1 ３.２２億個のリンクがある場合、52回の繰り返しで収束 k = 1 do { k = k + 1 } while( 　　　　　　　　　　) return

検索エンジンの概要 クローリング してインデックスと 行列 A を作っておく。 PageRank を計算しておく インデックスは、ページごとの文書ベクトル　Dk Dk = (W1 のtf-idf値, W2 のtf-idf値, …, Wn のtf-idf値) PageRank　を計算しておく ユーザが指定した検索式とインデックスから、類似度を使って検索結果の集合を作成 検索結果の集合の要素を PageRank で整列