断熱ページランクアルゴリズム
この記事の概要Google 行列ページ間リンク反復計算によるページランクベクトルの計算ぶら下がりページ(dangling nodes)の扱い方可約グラフがある場合とGoogle行列断熱量子計算ハミルトニアンとエネルギーギャップハミルトニアンエネルギーギャップとアニーリング時間古典と比較してどのくらい高速化したのか？結言参考文献文責
この記事の概要
GoogleのWebサイト検索は、今や生活に欠かせないものになっています。今回はその技術に用いられているページランクアルゴリズムを、断熱計算を用いて高速に求める手法についてメモしました。
Google 行列
ページ間リンク
上図ように、ページ1からはページ2, 3, 4へのリンク、ページ2からはページ4へのリンク、ページ3からはページ1, 4へのリンク、そしてページ4からはページ1, 3へのリンクがそれぞれ貼られているとします。このときどのページが重要度が高いでしょうか、というのがページランクアルゴリズムで求めたい答えです。
このとき
- 頂点1は(1, 2), (1, 3), (1, 4)の3本をエッジとしてもつ →
- 頂点2は(2, 4)の1本をエッジとしてもつ →
- 頂点3は(3, 1), (3, 4)の2本をエッジとしてもつ →
- 頂点4は(4, 1), (4, 3)の2本をエッジとしてもつ →
より、このリンク情報を以下のように(ページ数) x (ページ数)の隣接行列で表現しましょう。
より一般化して記述すると、は以下のようになります。
反復計算によるページランクベクトルの計算
初期に全てのページの重要度が等しくとしましょう。これをページランクベクトルと呼びます。ここに隣接行列をかけることで、そのページがどの程度他のページと関わりがあり重要であるかがわかります。これを繰り返し作用させることで値が収束し、最終的なページ重要度を得ることができます。
ここでは行列の転置を表します。実際に上の例でこれを計算すると以下のように値が収束していきます。
| 反復計算回数\ページ | 1 | 2 | 3 | 4 |
| 0 | 0.25 | 0.25 | 0.25 | 0.25 |
| 5 | 0.299 | 0.10 | 0.267 | 0.332 |
| 10 | 0.3 | 0.1 | 0.266 | 0.333 |
よってこの例ではページ4が最も重要であることがわかります。これは他のページに比べて、ページ4に入ってくるリンクの数が3つで一番多いことに起因しています。
ぶら下がりページ(dangling nodes)の扱い方
下図のページ4のように、他のページからリンクが貼られていてもそこから先にはページが貼られていないようなページのことをぶら下がりページと呼びます。
先程の議論からこのグラフの隣接行列は
となります。これを用いて(3)式の反復計算を行ってみましょう。すると
| 反復計算回数\ページ | 1 | 2 | 3 | 4 |
| 0 | 0.25 | 0.25 | 0.25 | 0.25 |
| 5 | 0.001 | 0.001 | 0.001 | 0.004 |
のように全ての成分が0に収束するようになり、正しくページランクベクトルを計算することができません。よってこれを回避するために、ある行の成分が全て0の場合はページ数分の1、すなわちを代わりに入力します。この行列をとすると
のようになります。これを用いて
を計算し、値の収束を見てみましょう。すると
| 反復計算回数\ページ | 1 | 2 | 3 | 4 |
| 0 | 0.25 | 0.25 | 0.25 | 0.25 |
| 5 | 0.200 | 0.178 | 0.178 | 0.442 |
| 30 | 0.2 | 0.177 | 0.177 | 0.444 |
のようになりました。このことから3ページからリンクが貼られているページ4が最も重要であることがわかります。
可約グラフがある場合とGoogle行列
下図のようなページ間リンクの場合を考えましょう。
このとき、リンク情報を表す隣接行列は
しかし実際のこれを使って(6)式の反復計算を行うと、次のようになります。
| 反復計算回数\ページ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 0 | 0.125 | 0.125 | 0.125 | 0.125 | 0.125 | 0.125 | 0.125 | 0.125 |
| 30 | 0.000 | 0.000 | 0.000 | 0.000 | 0.102 | 0.364 | 0.273 | 0.182 |
のように、1~4までの重要度が0に収束します。元のグラフをみてみると、ページ4はページ1, 2, 3からリンクされているため、本来ならば0でない重要度が求まってほしいところです。この例は、実は可約グラフ(reducible graph)*1になっており、このままではページランクベクトルを正しく計算することはできません。そこでBrin & Page, 1998では、以下のように隣接行列に修正を加え、これをGoogle行列と定義しました。
ここでです。は"Personalization vector"と呼ばれ、確率分布を表します。よく用いられるのは、全ての分布を等しくとしたものです。は全ての要素が1のベクトルです。は、グラフにしたがって別のページへと遷移する確率を表すパラメータです。すなわちこの式はの確率分布にしたがって、程度はランダムなページ遷移を許容することを意味します(Googleが用いている値は)。
(7)式から(8)式のGoogle行列を計算すると
これを用いて
を実際に計算してみると、以下のようになります。
| 反復計算回数\ページ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 0 | 0.125 | 0.125 | 0.125 | 0.125 | 0.125 | 0.125 | 0.125 | 0.125 |
| 30 | 0.030 | 0.054 | 0.027 | 0.062 | 0.162 | 0.284 | 0.242 | 0.139 |
今度はちゃんと全てがゼロでない有限の値に収束しました。
断熱量子計算
これまでの計算手法は、Google行列を求めたのちに、反復計算からページランクを求めるというものでした。今度はこれを断熱量子計算で解くことを考えましょう。
ハミルトニアンとエネルギーギャップ
ハミルトニアン
量子アニーリング終状態のハミルトニアンをとし、これを以下のように定めます。
のようになります。ここで、最終的に求めたいページランクベクトルを思い出しましょう。はその導出方法から、の固有値1の固有ベクトルであることがわかります。よって、求める終状態はのように書くことができます。
(11)式と同じ形で、量子アニーリング開始時のハミルトニアンを
のように定義します。ここでは、先程のページ間リンクを全結合グラフにした場合のGoogle行列です。この場合、全てのページ重要度は等しくなるはずなので、量子アニーリングの初期状態として準備するの基底状態は
となります。ここでここではページがページ重要度1の状態です。
これらを用いて、量子アニーリングを行う際に用いるハミルトニアンは、時間発展を表すを用いて
と書けます。
エネルギーギャップとアニーリング時間
Garnerone et al., 2012では、を生成するモデルとしてBarabasi & Albert, 1999やBollobas et al., 2001の"Preferential attachment model"とKleinberg et al., 1999の"Copying model"の両方をインスタンスとして、エネルギーギャップをハイパフォーマンスコンピューティングで計算しました。その結果が下図です。
縦軸にエネルギーギャップの逆数、横軸にとしています。上図がPreferential attachment model, 下図がCopying modelでの結果です。この結果からエネルギーギャップがとわかります。このことと断熱定理より、求めたい終状態へ到達するためにかかるアニーリング時間は
となります。ここで、は小さな正の整数です。
古典と比較してどのくらい高速化したのか？
古典アルゴリズムでこの問題を解く場合、最速であるのはMarkov Chain Monte Carlo(MCMC)法です。この方法を用いるとページランクベクトルを算出するのにかかるステップ数はであることが知られています。このアルゴリズムではのランダムウォーカーが各ページから出発します(すなわち、総ウォーカー数は)。各ステップ毎に隣あうページ間で情報のやりとりをするためにビットが必要です。ステップ後に、各ページにウォーカーが何名訪れたかを計算することで、それがページランクとなります。よって古典アルゴリズムでこの問題を解くのに必要なコストはであることがわかります。
(15)式と比較すると、量子アニーリングによるページランクアルゴリズムの方が高速化されていることがわかります。
結言
日本人が生活する上で欠かせない技術となったGoogle検索、その背景にある検索エンジンのページランク付けアルゴリズムを概観しました。そして、それを断熱量子計算で高速化できるということをご紹介しました。
参考文献
文責
中村翔、株式会社Jij
Sho NAKAMURA, Jij Inc.
※疑問点や間違いなどございましたら、お気軽にお尋ねください。
*1: 可約グラフとは、可約行列が作るようなグラフのことです。可約行列は
のように、ある巨大な行列のなかに零行列が存在するようなものを指します。これに関連して、ある行列が作るグラフが強連結である時、その行列を既約行列(irreducible)と呼びます。既約でない行列を可約と呼びます。さらに補足すると、強連結とは下図のグラフのように任意の2点間に有向路が存在するようなグラフです。
