seri::diary

プログラミングのこととかポエムとか

PageRankについて調べてみた

この記事はトレタ Advent Calendar 2016の2日目です。
1日目は弊社iOSエンジニアのhorimislimeによるリリース自動化だけじゃないfastlane活用方法でした。恥ずかしながらfastlane初めて知ったんですが便利ですね。あと関係ない話ですがなぜか弊社のiOSエンジニアは普通にruby書けるのでビビります…

概要

PageRankについて

PageRankが生まれた時代背景

  • Googleの前身であるBackRubが開発された1996年当時、他の商用検索エンジン転置インデックスを用いた全文検索を主な検索の手段としていたケースが多かった(AltaVistaなど)
  • しかし、それらの商用検索エンジンは、人間から見て実用的な検索結果を表示することが非常に困難な状態にあった。単純に検索クエリとページに含まれるキーワードの一致数などを使って表示順序を決定していたため、そのページに価値があるかどうかを評価することができなかった。
  • また、特定のタグに同じキーワードを沢山いれるなどするだけで簡単に任意のページの検索ランキングを操作することができ、スパマーの攻撃の的にされるという問題も抱えており、ますます実用性からはかけ離れていた。*1
  • その一方で、webサイト上のリンクのつながりから自律的にページの重要度を学習するBuckRubは、検索結果の表示順序を決定する際にPageRankによって算出された「ページの重要度」を用いていたため、他の商用エンジンと比べ「実用的な」検索結果を表示することができた。
  • 2016年8月現在においてもGoogle内部でページランクが「ページの重要度」を評価するために用いられていると公表されている

基本的なアイデア

PageRankの基本的なアイデアは下記がベースとなっている(後述するが実用的なスコアを算出するためには若干の調整が必要になるので単純に実際のリンク数だけで決定している訳ではない)

  • 沢山のページからリンクを貼られているサイトほど重要(以後本記事ではこのリンクを 入リンク と呼称)
  • 他のページにリンクを貼る時、重要なサイトから貼られたリンクの方が価値がある(以後本記事ではこのリンクを 出リンク と呼称)
  • 出リンク の価値は1つのサイトから貼られている 出リンク の数に反比例する

webサイトのPageRankスコアを計算してみる

以下のように6つのページが互いにリンクを貼っている状況を考える(それぞれのノードが1つのWebサイト) f:id:serihiro:20161118160538p:plain

Lawrence Page とSergey Brinは、当初下記の計算式によりPageRankスコアを求めた。*2

 \displaystyle
  \mathrm r(P_{i}) = \sum_{ P_{j} \in B_{P_{i}} } \frac { \mathrm r(P_{j}) } { \mathrm |P_{j}| }

ここで

  •  \displaystyle r(P_{j}) : ページPjのPageRank
  •  \displaystyle P : 全ページの集合
  •  \displaystyle B_{P} : 入リンクの集合*3
  •  \displaystyle \mathrm |P_{j}| : ページPjの出リンク数の総数

この数式を反復法で繰り返し計算することでPageRankのスコアを求めることができると考え、k+1回目の繰り返しで求められるスコアを

 \displaystyle
   r_{k+1}(P_{i})

とすると

 \displaystyle
  \mathrm r_{k+1}(P_{i}) = \sum_{ P_{j} \in B_{P_{i}} } \frac { \mathrm r_{k}(P_{j}) } { \mathrm |P_{j}| }

となる。

ここで、当然ながらk=0の時の値(つまり初期値)を何の値とするかという問題が発生するが、Lawrence Page とSergey Brinは初期値として集合Pに含まれるページ数の逆数を用いたとされる。今回の例で言えば、Pにはページが6個含まれるので、k=0の時は一律で 1/6 となる。

単純なアプローチによるスコア計算

上記の数式を用いて実際にスコアを計算してみる。*4
 \displaystyle r_{1}(P) から計算してみる。

 \displaystyle
  \mathrm r_{1}(P_{1}) = \frac { \mathrm r_{0}(P_{3}) } { \mathrm |P_{3}| } = \frac 1 6 / 3 = \frac 1 {18}
 \displaystyle
  \mathrm r_{1}(P_{2}) = \frac { \mathrm r_{0}(P_{1}) } { \mathrm |P_{1}| } + \frac { \mathrm r_{0}(P_{3}) } { \mathrm |P_{3}| }  = \frac 1 6 / 2 +  \frac 1 6 / 3 +  = \frac {5} {36}
 \displaystyle
  \mathrm r_{1}(P_{3}) = \frac { \mathrm r_{0}(P_{1}) } { \mathrm |P_{1}| } = \frac 1 6 / 2 = \frac {1} {12}
 \displaystyle
  \mathrm r_{1}(P_{4}) = \frac { \mathrm r_{0}(P_{5}) } { \mathrm |P_{5}| }  + \frac { \mathrm r_{0}(P_{5}) } { \mathrm |P_{6}| }  = \frac 1 6 / 2 + \frac 1 6 / 1 = \frac {1} {4}
 \displaystyle
  \mathrm r_{1}(P_{5}) = \frac { \mathrm r_{0}(P_{3}) } { \mathrm |P_{3}| } + \frac { \mathrm r_{0}(P_{4}) } { \mathrm |P_{4}| }  = \frac 1 6 / 3 +  \frac 1 6 / 2 +  = \frac {5} {36}
 \displaystyle
  \mathrm r_{1}(P_{6}) = \frac { \mathrm r_{0}(P_{4}) } { \mathrm |P_{4}| } + \frac { \mathrm r_{0}(P_{5}) } { \mathrm |P_{5}| }  = \frac 1 6 / 2 +  \frac 1 6 / 2 = \frac {1} {6}

つづいてk=1の時のスコアを使ってk=2のスコアを反復的に求めてみる。texで書くのがめんどくさくなってきたので細かい計算は省略する。

 \displaystyle
  \mathrm r_{2}(P_{1}) = \frac { \mathrm r_{1}(P_{3}) } { \mathrm |P_{3}| } = \frac 1 {36}
 \displaystyle
  \mathrm r_{2}(P_{2}) = \frac { \mathrm r_{1}(P_{1}) } { \mathrm |P_{1}| } + \frac { \mathrm r_{1}(P_{3}) } { \mathrm |P_{3}| }  = \frac 1 {18}
 \displaystyle
  \mathrm r_{2}(P_{3}) = \frac { \mathrm r_{1}(P_{1}) } { \mathrm |P_{1}| } = \frac 1 {36}
 \displaystyle
  \mathrm r_{2}(P_{4}) = \frac { \mathrm r_{1}(P_{5}) } { \mathrm |P_{5}| }  + \frac { \mathrm r_{1}(P_{5}) } { \mathrm |P_{6}| }  = \frac {17} {72}
 \displaystyle
  \mathrm r_{2}(P_{5}) = \frac { \mathrm r_{1}(P_{3}) } { \mathrm |P_{3}| } + \frac { \mathrm r_{1}(P_{4}) } { \mathrm |P_{4}| }  = \frac {11} {72}
 \displaystyle
  \mathrm r_{2}(P_{6}) = \frac { \mathrm r_{1}(P_{4}) } { \mathrm |P_{4}| } + \frac { \mathrm r_{1}(P_{5}) } { \mathrm |P_{5}| }  = \frac {14} {72}

k = 2の時点でスコアを降順ソートすると

 \displaystyle
\mathrm r_{2}(P_{4}) > \mathrm r_{2}(P_{6}) > \mathrm r_{2}(P_{5}) > \mathrm r_{2}(P_{2}) > \mathrm r_{2}(P_{1}) = \mathrm r_{2}(P_{3})

となり、6ページ間のランキングが作成できる。*5

総和計算から行列計算に置き換えて考える

ここで、最終的に得られるPageRankのスコアのリストを、n次元ベクトル(nは集合Pに含まれるページ数)と捉えると、上記の計算はn * n行列とn次元ベクトルの積として考えることができる。*6

具体的には、総和式の代わりに以下の行列を導入することで、先に行ったPageRankスコアの計算を単純な行列計算として考えることができる。

 \displaystyle
\begin{equation}
H=
\begin{vmatrix}
0 &\frac {1} {2} &\frac {1} {2} &0 &0 &0 \\
0 &0 &0 &0 &0 &0 \\
\frac {1} {3} &\frac {1} {3} &0 &0 &\frac {1} {3} &0 \\
0 &0 &0 &0 &\frac {1} {2} &\frac {1} {2} \\
0 &0 &0 &\frac {1} {2} &0 &\frac {1} {2} \\
0 &0 &0 &1 &0 &0
\end{vmatrix}
\end{equation}

Hi行の要素は、ページ Pi が持つの出リンクの有無を示す。

例えば H[1] 行においては H[1][2]H[1][3] のみが非0で、それ以外は0になっている。これは、 P1P2P3 に対する出リンクを保持しており、それ以外のページに対してはでリンクを保持していないことを示している。*7

要素の値がそれぞれ 1/2 となっているのは P1 の持つ出リンクの個数で除している為である。これは、先に示した総和式でPageRankスコアを計算した時、各ページのスコアを |Pj| で除した処理に対応した前処理である。

Hj 列の要素は、ページ Pj が持つ入リンクの有無を示す。 例えば H[1] 列においては H[3][1] のみが非0で、それ以外は0になっている。これは、 P1P3 からの入リンクを保持し、それ以外のページからの入リンクを保持していないことを示している。H[3][1] 要素が1/3 なのは、先に説明したとおりP3の出リンクの総数で除されている為である。

この行列Hを用いると、先に掲載した

 \displaystyle
  \mathrm r_{k+1}(P_{i}) = \sum_{ P_{j} \in B_{P_{i}} } \frac { \mathrm r_{k}(P_{j}) } { \mathrm |P_{j}| }

は以下のように書き換える事ができる。

 \displaystyle
  \mathrm r_{k+1}(P_{i}) = \sum_{ j = 1 }^n H_{ji} \times { \mathrm r_{k}(P_{j}) }

ここで、

 \displaystyle
\begin{equation}
\pi^{(k)T}=
\begin{vmatrix}
r_{k}(P_{1}) &\cdots &r_{k}(P_{n})
\end{vmatrix}
\end{equation}

と定義される行ベクトル  \displaystyle \pi^{(k)T} を導入すると、

 \displaystyle
\pi^{(k+1)T} = \pi^{(k)T}H

と置き換えられる。

なお、実際に行列計算をする時は

 \displaystyle
\pi^{(k+1)} = H^{T} \times \pi^{(k)}

として、Hの転置行列に右から列ベクトル  \displaystyle  \pi^{(k)} を乗じる必要がある(と思うのだが、なぜか参考にした書籍ではこの辺のことが記載されていなかった。。そんなもんは数学者の間では常識なんだろうか?)

単純なアプローチをそのまま用いて計算する場合の問題点

しかしこの式には以下のような問題があると参考にした書籍では指摘されている。

  • いつか  \displaystyle \pi^{(k)T} は収束するのか?
  • 計算を繰り返す回数は何回が最適なのか?10回か?20回か?それ以上か?

また、実際、先に掲載した式で  \displaystyle \pi^{(13)T} ぐらいまで求めると `(0 0 0 2/3 1/3 1/5) となり、一部のページにスコアが隔たってしまうという問題もある。

これらの問題を解決するためにLarry PageSergey Brinは以下の調整を行った。以下の調整を行うことで  \displaystyle \pi^{(k)T} がある定常ベクトルに収束することがべき乗法の考え方から収束することが保証される*8

ハイパーリンク行列を調整する

Larry PageSergey Brinが行った調整は下記の2つ。

出リンクを1つも持たないページには他のページに出リンクがあることにする

出リンクがないページに到達したらどっか適当なページに飛ぶじゃろ、という前提で他のページに対する出リンクが同確率で「あること」にする。

例えば P(2) は出リンクを持たないページなので、 H[2] の行において、全ページに対して出リンクを持つことにする。

つまり一定の確率で他のページにジャンプする、という概念を導入することになる。Larry PageSergey Brinの論文では ランダムサーファー と呼称されている。

この調整により先の数式で出てきた行列 H を用いて新たな確率行列 S が定義される。

 \displaystyle
S = H + a(1/ne^{T})

ここで a は出リンクを1つでも持つPは0、ないPを1とする2値ベクトルとする。

全てのページから関係のないページに一定の割合で他のページに出リンクがあることにする

出リンクがあるページを閲覧していたとしても突然関係ないページに飛ぶじゃろ、という前提で、全ページに対する出リンクが同確率で「あること」にする。

その結果、更に調整を行った新たな行列 G が登場する。

 \displaystyle
G = {\alpha}S + (1-\alpha)1/nee^{T} \\
\ \ \ = {\alpha}(H + a(1/ne^{T})) + (1-\alpha)1/nee^{T} \\ 
\ \ \ = {\alpha}H + ({\alpha}a + (1 - {\alpha}e)1/ne^{T} \\

 \displaystyle \alpha は0と1の間のスカラーである。googleでは長い間 0.85 が使われていたらしい。

実際に先に挙げた例で G を計算すると以下のようになる。

 \displaystyle
G = 0.9H + ({0.9}
\begin{vmatrix}
0 \\
1 \\
0 \\
0 \\
0 \\
0
\end{vmatrix}
+ {0.1}
+ \begin{vmatrix}
1 \\
1 \\
1 \\
1 \\
1 \\
1
\end{vmatrix}){1/6}
\begin{vmatrix}
1 &1 &1 &1 &1 &1
\end{vmatrix}

 \displaystyle \pi^{T}はGに対する定常ベクトルで、以下のようになる。参考書籍よりそのまま抜粋。参考書籍掲載のMATLABの参考実装で計算したものらしい。

 \displaystyle
\pi^{(k+1)T} = \begin{vmatrix}
0.03721 &0.05396 &0.04151 &0.3751 &0.206 &0.2862
\end{vmatrix}

参考書籍に掲載されていた参考実装では π(k)Tπ(k-1)Tノルムの差が一定数値以下になるまで計算を繰り返した最後の π(k)T を定常ベクトルとして扱っているらしい。要するに、1回前の計算値と最後の計算値の差が十分小さくなったら収束した、と見なすというアプローチらしい。

 \displaystyle \pi^{T} は以下の固有ベクトル問題を解くことでべき乗法で繰り返し計算しなくても近似的に求める方法があるらしいが、自分の数学力と時間が足りなくて固有値問題についてよく理解できないので誰か教えてほしい…(要勉強)

 \displaystyle
\pi^{T} = {\pi^{T}}G

自分でもrubyで実装してみた

最後に、自分がrubyで実装したpagerankのスコアをべき乗法で求めるコードを掲載しておく。

bitbucket.org

なるべく参考書籍の数式がそのまま動く感じになるように実装した。

実際にべき乗法で繰り返し計算するループは下記のような感じ。本文でも記載しているが、G 行列を転置して列ベクトルである pie を右から乗じて計算している。行列計算においてはrubyMatrixクラスが非常に便利だった。

収束したかを判定する @residual_erorr は参考書籍の参考実装から持ってきた 1e-8 を使っている。

    _transposed_google_matrix = google_matrix.transpose

    loop do
      previous_pie = pie
      pie = _transposed_google_matrix * pie
      if pie.norm - previous_pie.norm < @residual_erorr
        break
      end
    end

まとめ

  • ページランクの概要はざっくり知っていたが、いざ書籍を一冊読んでちゃんと調べると数学的な奥深さが半端なく、その辺のバックグラウンドがない自分には難解でほとんど理解できてないように感じる。実際、参考書籍は前半においてはオリジナルの論文の解説といった感じだが、後半は収束速度とパラメータの数値の調整に関する議論やPageRank以外でのランキングについて記されているのだが、その辺の内容が高度すぎてまだ理解できていない。
  • これをきっかけ確率過程やマルコフ連鎖について勉強していきたいと感じた。実際、確率過程についてはネットで拾った大学講義の資料とかで調べてみたらかなり面白く、自然言語処理機械学習の分野でもこれが理解できないといつか詰みそうな内容だったので、いつか単独でブログネタにしたい。*9
  • トレタ Advent Calendar 20163日目はmasuidriveによる「Railsで新規サービスを作る時に使うべきサービス」です。

参考資料

*1:CCCメディアハウス「グーグル ネット覇者の真実 追われる立場から追う立場へ」より

*2:この数式は書籍 「Google PageRankの数理」に記載されていた通りのものだが、書籍中では出典が明らかになっておらず、また、オリジナルの論文である 「The Anatomy of a Large-Scale Hypertextual Web Search Engine」 にはこの数式は書かれていない。Lawrence Page と Sergey Brin によるもう一つの論文 「PageRank, an Eigenvector based Ranking Approach for Hypertext」 の方に記載があったのかも知れないが、この論文はweb上で本文が見つからなかったため確認できなかった。無念。

*3:Lawrence Page とSergey Brinらが入リンクのことをBacklinkと論文の中で記述していたのでBを使っているのだろう

*4:このあたりから段々tex記法で数式書くのが辛くなってきた…ので段々サボり出しているがはてなブログにおけるmarkdowntex記法の組み合わせが最悪なのでご了承いただきたい

*5:ページ1とページ3のスコアが同値なので、2つのページが同じ検索結果に含まれる場合にどう並べるかという問題に対しては、別の評価パラメータを用いて総合的に優劣を決定しているものと考えられる。

*6:実際は行列と行ベクトルの積は直接計算できないので(懐かしの数Cでやったことを思い出そう)それぞれの転置行列同士の積を取ることになるのだが、アカデミックの世界ではその辺をよしなにやってくれる計算ライブラリを使うのが常識なのかどうかは分からないが「PageRankの数理」においてはその辺の説明を端折っている

*7:ここでtex使わないで書いているのは、同じ行にtex記法で書くとはてなブログが展開してくれないからである。。

*8:なぜ保証されるかは参考書籍を読んでも良く分からんかったが、調整したH行列の固有値を用いることで収束することが証明できるらしい…要勉強

*9:公開されている大学の講義資料にいつも助けられている。機械学習自然言語処理の方で調べ物するときも信頼のおける情報ソースとしていつも使わせていただいている。工学系の学位取ってない自分にとってはホントありがたい。