いまさら学ぶ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)$ となります。

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%の確率でテレポートされます。