GoogleのPageRankアルゴリズムにみるイノベーションのパターン
前回の記事、NHKスペシャル「グーグル革命の衝撃」、要約と感想。 - 情報流の流れに身を任せ。で”PageRankの説明が端折りすぎ”、と書いたものの、どのような点を端折ったのかを書いてなかったこと。
あと、PageRankの思想って結構イノベーションに言える共通のパターンがあるような気がしていたので、ちょっとその視点からまとめてみることにします。
PageRankとは
はじめに
PageRankとは、ラリー・ペイジらがスタンフォード大にいたときに開発し、Googleが検索エンジン市場に華々しく登場するきっかけとなった基本的なアルゴリズムであり、Googleの検索結果の上下を決めている指標のことである。
計算方法の概念としてはかなり単純で、まさに発想の転換ともいうべきものなのだが、その他にもいくつかの工夫も凝らされている。*1
Game Start！、得をするのは誰だ。
PageRankの仕組みは論文でも公開され*2、日本語では、http://www.kusastro.kyoto-u.ac.jp/~baba/wais/pagerank.htmlなど、素晴らしく分かりやすく書かれた説明もあるので、本稿では例え話を使って、数式を出さずに説明したいと思う。
（逆に分かりにくくなってしまったら、すみません・・・。）
まず、５人（仮にＡ〜Ｅさんとする。）くらいで行う次のようなゲームを考えてみることにしよう。
モノポリーや人生ゲームの簡単なやつといったイメージで読んでもらえればと思う。
ゲーム開始時のルールは以下のふたつ
- 各自は、所持金として1,000円を持っているとする。
- 各々は仲の良い相手を何人か選んでおく。
だけである。
以下、あなたがＡさんだとして話を進めると、ルール２は例えば、
- ０人（誰も選ばない）
- １人（じゃあ、Ｃさんにする）
- ２人（ＢさんとＣさん）
（中略）
- ４人全員（Ｂさん、Ｃさん、Ｄさん、Ｅさん）
といったバリエーションの中からどれかを選ぶことになる。
そして、ゲームスタートである。
第１ターン
まず、決めた人に対して、持ち金を配る。
- あなた（Ａ）が、もしＣさんのみを選んでいたのなら、Ｃさんに1,000円を渡す。
- もし、ＢさんとＣさんを選んでいたのなら、公平にＢさんとＣさんに500円ずつを支払う。
- もし、全員を選んでいたら、250円ずつＢさんからＥさんにそれぞれ支払う。
といった具合である。
これを全員で一気に行う。
あなたの手元からは1,000円が無くなり、他の人からあなたが選ばれていれば、あなたはその分配金を受け取ることになる。
もし、誰も選んでいなかった場合、その1,000円は全額銀行に没収され、次のターンの始まる前に参加者5人で分け合うことにしよう。*3
配分は、その時持っている各プレーヤーの所持金の比率によって分配される。
もし、２ターン目を始める際、Ｂさんが全プレーヤーの持っているお金の半分を集めていれば、Ｂさんに500円。残りの500円も持ち金比率に従って、分配される。
そして、２ターン目開始。
あなたが比較的多くの人から選ばれていて、合計2,000円を受け取っていたとしよう。
あとは、ルールは同じである。
あなたが、もし、ＢさんとＣさんを選んでいたら、今度は1,000円ずつＢさんとＣさんに支払うことになる。
これをひたすら繰り返す。
すると、”あること”さえ起きなければ、金額はターンが進んでも変化しなくなり一定になる。
金額が変わらなくなったら、ゲームは終了である。
最後に、手持ちのお金を集計し、もっとも儲かった人が優勝、つまり、PageRank一等賞である。
裏ワザ！？
さて、これでゲームは終了なのだが、”あること”が起きると、金額はおかしなことになってしまう。
その”あること”を説明したいと思う。
それは、次のような方法で、ゲームを何回かやれば、すぐに誰かが思いつくだろう。
あなた（Ａ）は、Ｂさんと結託することにする。
あなたは、常にＢさんのみを指名し、Ｂさんもあなたのみを指名する。
そうすれば、ＡかＢが他の人（Ｃ、Ｄ、Ｅ）から指名されていけば、お金は入ってくる。
そして、入ってきたお金はＡとＢの間を動くだけでＣからＥに渡ることは無いので、外部の指名したお金を集めつくすまでは、確実に増える一方となる。
ルール修正！
さて、問題発生である。これではゲームが成立しない。
そこで、ゲームのルールを一部変更することにする。
ターンを開始する際、まず、各自の所持金のうち１５％は、自分以外の４人のプレーヤーに１／４ずつ分配することにする。
そして、残りの８５％を当初のルールどおり、決めた相手に分配することにするのである。
これなら、ＡとＢの間で回しているお金も、それ以外の３人に渡ってしまうため、再現なく増えることは無い。
必勝法はなくなり、ゲームは成立することになり、メデタシメデタシである。
話をWebに戻すと・・・。
さて、話をWebの戻そう。
本家では、「投票」という例えをとっているのだが、ここでは、ちょっと生々しくするために、「お金」を例えに使ってみました。
Webの用語に戻すと、
- この「プレーヤー」というのが、「ホームページ」（特定のURL）。
- 「お金をあげる相手」というのが、そのホームページに載っている「他のホームページへのリンク」
のことである。
このやり方の、いいところは、
- 評価の高いページからリンクされた方が評価が上がる
ことにある。
再び、例え話に話を戻せば、もし、Ａさんを指名した人の中に多額の金額を集める人がいれば、よりＡさんに入る金額は多くなることになる。
誰からのリンクの張られていないページからリンクを張られるよりも、Yahoo!のトップページからリンクを張られた方が、高い評価になるわけである。
PageRankのイノベーション
「うまいこと、考えたな・・・。」
というのが、Googleが出てきて、PageRankの概要を知った時の当時の僕の感想である。
ところが、である。
PageRankとは、それほど画期的な計算方法だったのだろうか？
こう振ったからにはその先は想像がつくと思うが、
実は、この
- 高い評価を得たものから評価された場合、その評価を重く見る。
- その評価の高低も他者の評価から決まる。
といった計算方法の収束点を探すというのは、行列演算でいうところの、固有値・固有ベクトルの演算に過ぎない。
数学のグラフ理論では、「グラフの中心を探す時に固有ベクトル演算を使うと良い」というのは、一般的な話らしいのである。
また、社会ネットワーク学の分野では、真の有力者を探しだすために、
アンケートで、「あなたが重要な相談事をするとしたら誰ですか？」と聞き、それを投票とみなして、固有値を計算することで、有力者ランキングの作成をするといった方法がGoogle以前から知られていた。（中心性尺度のひとつ、ボナチッチ中心性という。）
要は、
「よく相談される人から相談されるということは、その人も相当なもんや。」
という具合である。
では、PageRankの凄さとは何だったのだろうか？
それは、
『Webのハイパーリンク構造をみて、それを一般的なネットワーク（グラフ構造）の一系統に過ぎないと理解し、その分野では一般的な技術を応用したこと』
である。
整理すると、
- 抽象化して、
- 類似のものを他分野みつけ、
- その分野での解決方法を適用する。
といえる。
これが、PageRankという演算方法の一つ目の凄さであり、『イノベーションの多くは、他分野ではごく一般的な技術が応用されることによって起こる』という、どこかで聞いたことのあるような話につながる。
さて、PageRankには、もうひとつの凄さがある。
実は、社会ネットワーク学の「有力者を見つけ出す」方法では、ゲームの例で上げたルール違反が発生した場合の修正ルールに、対応していない。
例えば、ネットワーク計算ソフトで、有力者をみつけるために固有値演算をしようとしたときに、上述のルール違反のような状況（グラフ理論では、「有向グラフで閉路がある。」といった表現が使われる。）が発生すると、「計算の妥当性は怪しいです。」というメッセージが出て、そのまま単純に固有値を計算してしまうのである。
これが、実は、２つ目の凄さである。
すなわち、
単純な応用をした際、概ね良いが部分的に問題があった場合には、
『ひと工夫してみる。』
ことで乗り越えている。
このゲーム内での金額の一部を分散させるやり方は、PageRankでは、ランダムサーファーモデルと呼ばれ、グーグル創業者であるLarry Pageらの独自モデルである。（ちなみに、PageRankとは、Larry PageのPageということらしい*4 ）
イノベーションとは・・・。
最後にまとめると、GoogleのPageRankのイノベーションとは、
- 他分野の技術を、Webに使えると発見し、試したこと。
- うまくいかなかった場合に、ひと工夫を自作でしたこと。
にあり、このパターンと言うのは、割と一般的に言われているイノベーション理論でもいえることなのでは、と思えるのである。*5
補足
分かりやすいので、GoogleもPageRankを投票に例え、僕も、配金ゲームとして例え話を作りましたが、「ランダムサーファーモデル」などの用語から分かるとおり、実際には、
- WebのHTMLを内容を無視して、多くの人がどこかのページを基点として適当にページ内にあるリンクをクリックして次々とページを移動していった場合、長い時間で見て、どこのページを沢山通過したか？（交通量が多いか？）
というのをシミュレートしようとして出来たのが、PageRankです。
ランダムサーファーモデルというのは、閉路への対応という一面をもつ一方、仮説との整合性という意味では、
- Webサーフィンをしている人は、今見ているページのリンクだけではなく、一定の確率でブックマークでどっか適当に飛んでいくこともあるだろう
という意味づけも含んでいます。
PageRankは、数理学では単純マルコフ過程という枠組みの一形態ですので、興味のある方は、そちらとの関連性も調べると、いろいろと面白いと思います。
今回は、計算式としてのPageRankのイノベーションという話にしましたが、勿論、Google自体の強さはそれを広大なWebで本当にやってしまっていることにあります。*6そのほか、新規サーバーの追加、壊れたサーバーの削除でのメンテナンスの負荷の軽減。ルールを微調整すると、大量のサーバーへ伝搬させる仕組みなど、分散システムによるスケールに対する頑健性が一番の凄さでしょうね。
*1:実際には、当時の他の検索エンジンが行っていたアルゴリズム、例えば、キーワードとなる単語の数、html上での文字の大きさなどと組み合わせで評価しており、ハイブリッドモデルといえる。
*2:Page, L.,Brin,S.,Motwani ,R. and Winograd ,T.(1998),"The PageRank Citation Ranking: Bringing Order to the Web. ," Stanford University Technical Report. http://dbpubs.stanford.edu:8090/pub/showDoc.Fulltext?lang=en&doc=1999-66&format=pdf&compression=&name=1999-66.pdf
*3:計算式上では、「正規化」のプロセス
*5:amazon:VEとTRIZや、その他イノベーション論にて。流し読みをして忘れていくので、ソースが少なくてすみません。
*6:3年くらいまえで、80億ページを集めています。
