け日記

最近はPythonでいろいろやってます

いまさら学ぶPageRankアルゴリズム

情報検索 (IR) のみならず、いろいろな分野で応用されているPageRankアルゴリズムについてまとめます。

PageRank

PageRankはリンク分析 (link analysis) に分類されるアルゴリズムで、1998年に提案されました (提案論文PDF) 。以下の特徴を持ってます。

  • リンク構造が明確なコンテンツに向いている
    • 最初はWebの検索エンジンに適用された
      • クローリングで取得したhtmlファイルのリンクタグを抽出するだけで良いため
    • 現在はソーシャルネットワークや自然言語処理などでも応用されてます
    • Python: LexRankで日本語の記事を要約する - け日記で紹介した要約アルゴリズムもPageRankから着想を得てます
  • コンテンツの解析だけでランキング化ができる
    • 検索結果に対してこのページはクリックされた/されなかった、などのフィードバックが不要

アルゴリズムを大雑把に捉えると、ランダムサーファーを仮定したマルコフ連鎖モデルを作り、定常状態の遷移確率を求めることでランキングを作るものです。

ランダムサーファー

PageRankでは以下の仮定を置いてモデル化します。ランダムサーファーと呼ばれます。

  • 仮定1. 全ての人は、最初のページをランダムに選択してスタートする
  • 仮定2. あるページに滞在している人は、次のタイムスライスで、別のページへ遷移します
    • 遷移先のページは、現在滞在しているページからリンクされているページの中から等確率で選択される (リンク遷移)
      • 滞在しているページから別のページへのリンクが無い場合、(今滞在しているページ以外の) 全ページの中からランダムに選択される (テレポート)
  • 仮定3. 滞在確率が高いページが有用なページであるとして、ランキング化する

ページ数4で図示するとこんな感じです。例えばページ1から2の遷移確率は1/2です。

マルコフ連鎖モデルによる計算

上の図でマルコフ連鎖モデルに落とし込むことができます。遷移行列Pの各要素  p_{i,j} はページiからjへの遷移確率を表します。

$$ P= \begin{pmatrix} 0 & 1/2 & 1/2 & 0 \\ 1/2 & 0 & 0 & 1/2 \\ 1/2 & 1/2 & 0 & 0 \\ 1/3 & 1/3 & 1/3 & 0 \end{pmatrix} $$

タイムスライスtにおける各ページでの滞在確率を  \vec{x}_t とします。仮定1.に基づくと、最初はページ1〜4に滞在する確率は等確率なので  \vec{x}_0=(1/4, 1/4, 1/4, 1/4) となります。

次のタイムスライスではこの滞在確率はどうなるでしょうか?  \vec{x}_1=\vec{x}_0P で計算できます。

$$ \vec{x}_0 P= \begin{pmatrix} 1/4 & 1/4 & 1/4 & 1/4 \end{pmatrix} \begin{pmatrix} 0 & 1/2 & 1/2 & 0 \\ 1/2 & 0 & 0 & 1/2 \\ 1/2 & 1/2 & 0 & 0 \\ 1/3 & 1/3 & 1/3 & 0 \end{pmatrix} = \begin{pmatrix} 1/3 & 1/3 & 5/24 & 1/8 \end{pmatrix} $$

次は  \vec{x}_2=\vec{x}_1P 、その次は  \vec{x}_3=\vec{x}_2P ... と無限に繰り返すことができます。
そうしていくと、滞在確率はほぼ変化しなくなります。この  \vec{x}_{t+1} \risingdotseq \vec{x}_t のときの  \vec{x}_t が最終的な滞在確率となり、この順番でランク付けします。

マルコフ連鎖における  \vec{x}_{t}=\vec{x}_tP は定常状態と呼ばれます。定常状態の \vec{x}  \vec{\pi} (定常確率) とすると、この  \vec{\pi} は簡単に計算できます。  \vec{x}_{t}=\vec{x}_tP であるため、以下の連立方程式を解きます。

  •  x_{1}=\frac{1}{2}x_{2}+\frac{1}{2}x_{3}+\frac{1}{3}x_{4}
  •  x_{2}=\frac{1}{2}x_{1}+\frac{1}{2}x_{3}+\frac{1}{3}x_{4}
  •  x_{3}=\frac{1}{2}x_{1}+\frac{1}{3}x_{4}
  •  x_{4}=\frac{1}{2}x_{2}

 x_{4}=a として解くと、 \vec{\pi}=(2a, 2a, 4a/3, a) となります。合計は1なので、a=3/19で、  \vec{\pi}=(6/19, 6/19, 4/19, 3/19) となります。

ランキング

 \vec{\pi}=(6/19, 6/19, 4/19, 3/19) であるため、ページ1 = ページ2 > ページ3 > ページ4 の順番のランキングになります。

PageRankのバリエーション

ここまでが純粋なPageRankでしたが、いくつかバリエーションがあります。

リンクが有る場合でも一定確率でテレポートする

リンクが有る場合は常にそのリンクで遷移していました (仮定2.) 。
実はこの仮定を厳密に守ると、例えば下図のページ2と4のように、外へのリンクが無く、かつ、閉路を構成していると、そこから抜け出せなくなります (ページ1と3は定常確率が0になります) 。

この対策として、リンクが有る場合でも一定確率αでテレポートさせるバリエーションがあります。上の図の場合、α=0.1とおくと遷移行列Pは以下で計算できます。これにより閉路を形成している場合でも、抜け出すことができるようになります。

$$ P=0.1 \begin{pmatrix} 0 & 1/3 & 1/3 & 1/3 \\ 1/3 & 0 & 1/3 & 1/3 \\ 1/3 & 1/3 & 0 & 1/3 \\ 1/3 & 1/3 & 1/3 & 0 \end{pmatrix} +(1-0.1) \begin{pmatrix} 0 & 1/2 & 1/2 & 0 \\ 0 & 0 & 0 & 1 \\ 1/2 & 1/2 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix} $$

カテゴリごとにテレポートする確率を変える

純粋なPageRankでは、テレポートするときは全てのページに等確率で遷移していました (仮定2.) 。
通常、この仮定は粗過ぎです。ニュースサイトのユーザをイメージしてみますと、阪神タイガースの試合結果のページを見ていた人が、次に遷移する確率は、スポーツカテゴリのページと芸能カテゴリのページでは異なるはずです。

こうした場合に、前者のカテゴリにテレポートしやすくなるように確率を調整する (一種のパーソナライズ) という方法が考えられます。
ページのカテゴリがスポーツと芸能の2種類のみであると仮定します。また、ある人のページの滞在傾向がスポーツ:芸能で7:3 (スポーツのほうが興味が強い) ということがわかっているとします。
テレポート時には、最初に7:3でカテゴリを振り分け、次にカテゴリ内で等確率に遷移させるようにします。

遷移確率行列は  (1-\alpha)P_{L} + \alpha(0.7P_{S}+0.3P_{G}) で計算できます。ただし  P_{L} はリンクのみの遷移確率行列、  P_{S} はスポーツカテゴリ内でのテレポート時の遷移確率行列、  P_{G} は芸能カテゴリ内でのテレポート時の遷移確率行列です。
α=0.1とすると、スポーツカテゴリのページに7%、芸能カテゴリのページに3%の確率でテレポートされます。

参考文献

こちらの21.2節を参考にしました。

Introduction to Information Retrieval

Introduction to Information Retrieval

  • 作者: Christopher D. Manning,Prabhakar Raghavan,Hinrich Schuetze
  • 出版社/メーカー: Cambridge University Press
  • 発売日: 2008/07/07
  • メディア: ハードカバー
  • 購入: 7人 クリック: 115回
  • この商品を含むブログ (37件) を見る