Google の秘密 - PageRank 徹底解説

評判の高いサーチエンジン Google (グーグル) の中核要素技術の一つである PageRank (ページランク) について、その基本的な概念と求め方の原理を解説する。

INDEX

§1

§2

§3

§4

§5

§6

§7

§8

INDEX

Since: Thu Feb 1 18:22:44 JST 2001
Last Refreshed: Sat Jan 24 18:30:35 JST 2004

★(2004/1/24) Yuan Huanglin氏によって本ページの中国語訳が作成されました。

★(2003/7/1) 拙著『Namazuシステムの構築と活用』を改訂しました。詳しくはサポートページをご覧ください。

★(2003/5/20) Google に関するオンラインニュース記事一覧(日本語記事のみ)を別ページ(googlenews.html) として分離しました。

★(2001/2/28) Namazu のインデックスを用いて PageRank を計算する Perl スクリプト prnmz-1.0.tar.gz を公開しました。

1. はじめに

最近注目を集めるサーチエンジンに Google (グーグル: http://www.google.com/)がある。 CEOの Larry Page と社長の Sergey Brin (2001年2月現在)が米スタンフォード大学大学院在籍中に開発した検索エンジンによるサービスである。 1998年9月にサービスを開始したが、Netscape Communications は Google がまだ試験段階だった頃から提携しており、米 Yahoo! も2000年6月にデフォルト・サーチエンジン(米Yahoo!で検索できない場合に補完する役割のエンジン)として提携関係にあった Inktomi を Google に切り替えている。日本語版は2000年9月に正式に登場したが、すでに BIGLOBE(NEC) が採用している。 (補注: 2001年4月に Yahoo! JAPAN および @NIFTY、7月にソニー、 2002年1月にエキサイトとも相次いで提携)。

Google の評判の良さは、無駄なバナー等を排したシンプルな画面構成や独自のキャッシュシステム、動的に作成する要約、高速検索のための分散システム(数千台規模のLinuxクラスタ)などもさることながら、その検索結果の的確さこそが第一である。そのための技術の一つがページ重要度の自動判定技術である「PageRank (ページランク)」である。このページでは、この PageRank システムに注目し、その概要をできるだけわかりやすい言葉で説明することを目的とする。

PageRank の基本論文は、以下の論文である。

Lawrence Page, Sergey Brin, Rajeev Motwani, Terry Winograd, 'The PageRank Citation Ranking: Bringing Order to the Web', 1998,
http://www-db.stanford.edu/~backrub/pageranksub.ps

PageRank を効率的に計算するために改良を加えた論文が以下である。

Taher H. Haveliwala, 'Efficient Computation of PageRank', Stanford Technical Report, 1999,
http://dbpubs.stanford.edu:8090/pub/1999-31

また、PageRank のプレゼン用資料(PowerPoint)は以下にある。

Larry Page, 'PageRank: Bringing Order to the Web',
http://hci.stanford.edu/~page/papers/pagerank/

以下ではこの2論文(+ 1資料)を基本に説明する。まず、PageRank の基本的な概念を簡単な例を用いて解説し、ハイパーリンク関係を用いたランキングシステムが大規模疎行列の固有値問題を解くことに帰着されることを説明する。次いで、基本モデルを現実世界に適用するときに現れる問題点とその対処法について触れる。さらに「Personalized PageRank」として用いることができるか検討するためにフリーの全文検索システム Namazu での実装実験を行ったのでその結果を述べる。最後に PageRank に対する個人的見解を述べる。

なお以下の説明を理解するには、大学の教養課程程度の数学(特に線形代数)の基礎的知識が必要とおもわれる。しかしながら文科系であっても読み進められるように、できるだけ数式を用いずに説明することを心掛けたことと、筆者個人の見解がところどころに混ざっているため、原論文そのままのアルゴリズムでないばかりか、厳密性ないしは正確性に欠ける部分が多々見られることをあらかじめお断りしておく。詳細は原論文を参照して頂きたい。

PageRank^(TM) は、米 Google 社の登録商標である。

前へ | 次へ

2. PageRank の基本概念

PageRank は、 「多くの良質なページからリンクされているページは、やはり良質なページである」 という再帰的な関係をもとに、全てのページの重要度を判定したものである。

以下に長々と続く説明では、部分的に専門用語も多く現れるから理解に苦しむ部分があるかも知れない。この章では定性的な解説に絞って平易に解説したつもりであるが、それでもどうしてもわからなかった時は、 「多くの良質なページからリンクされているページは、やはり良質なページである」 というアイデアだけでも理解してもらえればありがたい。いくつかあるポイントの中でも、これが一番重要な考え方だからだ。

さて、Google 自身による紹介ページ「Googleの人気の秘密 (http://www.google.co.jp/intl/ja/why_use.html)」では、以下のような解説がなされている。

PageRankについて
PageRankは、ウェブの膨大なリンク構造を用いて、その特性を生かします。ページＡからページＢへのリンクをページAによるページBへの支持投票とみなし、Googleはこの投票数によりそのページの重要性を判断します。しかしGoogleは単に票数、つまりリンク数を見るだけではなく、票を投じたページについても分析します。「重要度」の高いページによって投じられた票はより高く評価されて、それを受け取ったページを「重要なもの」にしていくのです。
こうした分析によって高評価を得た重要なページには高いPageRank（ページ順位）が与えられ、検索結果内の順位も高くなります。PageRankは Googleにおけるページの重要度を示す総合的な指標であり、各検索に影響されるものではありません。むしろ、PageRankは複雑なアルゴリズムにしたがったリンク構造の分析にもとづく、各ウェブページそのものの特性です。
もちろん、重要度が高いページでも検索語句に関連がなければ意味がありません。そのためにGoogleは洗練されたテキストマッチ技術を使って、検索に対し重要でなおかつ、的確なページを探し出します。

このアルゴリズムを具体的に見ると図のようになる。あるページの PageRank を、そのページに存在する発リンク数で割った数が、それぞれ被リンク先の PageRank に加算されるという関係になっている。

PageRank の概念図。 (Page et al. (1998) Figure 2 'Simplified Page Calculation' より引用)

詳しく見てみよう。 PageRank を高くするためのポイントは、大きく分けて３つある。

被リンク数 (単純な意味での人気度の指標)
お勧め度の高いページからのリンクかどうか (裏付けのある人気かどうかの指標)
リンク元ページでのリンク数 (選び抜かれた人気かどうかの指標)

まず基本的に、多くのページからリンクが張られていればお勧め度は高くなる。「(たくさんリンクされるような)人気のあるページは、きっと良いページであるに違いない」ということだ。被リンク数を人気度の指標の一つと見ることは自然な考え方だろう。リンクを張るという行為は、「このページを見るといい／このページは役に立つ」という推薦行為を行っていることとみなせるからだ。だが、PageRank の考え方はそれだけにはとどまっていないところがミソだ。

すなわち、単に被リンク数の多寡だけではなくお勧め度の高いページからのリンクは高く評価する。また同時に、総リンク数が少ないページからのリンクは高く評価し、総リンク数が多いページからのリンクは低く評価する。言い換えれば「(多くの推薦を集めるような)良いページが推薦するページは、同じく良いページであるに違いない」という判断と、「やたらリンクを乱発するインフレ気味なリンクに比べて、選び抜かれたリンクは良質なリンクであるに違いない」という判断を同時に行っている。きちんと人手の入った高い水準のページからの厳選されたリンクは明確に重視する一方で、あれもこれもと関連のないところにリンクを張りまくっているだけの単なるブックマーク的ページからのリンクは、「(全然リンクされないよりはまだマシだが)ほとんど価値がない」として軽視するわけである。

したがって、Yahoo! のような PageRank がとても高いサイトからリンクされれば、それだけで PageRank はグンと上がることになるが、逆に、いくら被リンク数ばかりが多くても、無意味なつまらないページからのリンクばかりでは PageRank はいつまで経っても上がらない。 Yahoo! でなくともその分野での権威(あるいは定番)とも言えるページからリンクされていれば良いわけだが、自分達だけで相対リンクしまくっているだけの低価値なページ同士のリンクは、いわば「単なる内輪びいき」として価値のあるものとは見なされにくい仕組みになっているということでもある。世界中のWebページ全体というグローバルな視点から見て、真に価値があるかどうかを判定していることになる。

こうした指標を総合的に分析した結果、最終的な評価の高かったページは検索の時に上位に表示される仕組みになっている。

従来は、ページの重要度としてそのページの被リンク数だけを単純に用いることがあったが、PageRank 方式だと機械的に生成されたリンクの影響を受けにくいという利点がある。つまり、PageRank を上げるためには良質なページからリンクされる必要がある。たとえば Yahoo! に登録依頼を出して通ればイッキに上がる。だがそのためには内容の充実に努めなければならない。このように、PageRank を上げるための近道 (あるいは裏道)は基本的に無いことになるのである。 PageRank に限らない(Clever や HITS などでも同じことだ)が、リンク構造を利用したランキングシステムには、従来の単純な SPAM 手法は通用しない。これは大きな利点であり、 Google の使い勝手を良くしている最大の理由になっている。 (最大の理由ではあるが、唯一の理由でないことには注意したい。)

ここで、 PageRank 自体はユーザが与えた検索式に与えた語句とは全く無関係な、すでに定まった量であることに注意しよう。後に述べるように、PageRank 自体の計算式には検索語句は現れない。どのような検索語句を与えても一定の、文書固有のスコア量である。

PageRank の定性的な説明はこのようなものでだいたい尽きる。だが、実際にランキングを計算して順位を比較するためにはもっと定量的な議論が必要である。次章以下で詳しく説明しよう。

前へ | 次へ

3. どうやって PageRank を求めるか

我々が興味があるのは、ハイパーリンク構造のような相互参照関係があるときに、どのページがもっとも「重要」であるかを定量的に知りたいということだ。これは「どのページから読み始めるべきか」の指標を厳密に計算する、と大胆に言い換えてみても大きくは違わないだろう。誰も見ないようなマイナーページから読みはじめてもしょうがないからだ。

さて、一般的に言って、Web のようなハイパーリンク構造をランキングに反映させるためには、ハイパーリンク構造を計算機上でモデル化し数値化してやる必要がある。どのようにモデル化するかは実装者の方針によるので一概に言えないが、ハイパーリンク構造をグラフ理論の応用と見た場合、それは線形代数の考え方に帰着されることが多い。 PageRank も同様である。

計算方法の原理

もっとも基本的な考え方として、リンク関係を行列の形で表わしてみよう。あるページ i から別のページ j へリンクが張られている場合にはその成分を 1 とし、そうでない場合を 0 とする。すなわち、行列 A の成分 a_ij は、

  a_ij = 1  if (ページ i からページ j へのリンクが「ある」場合)
        0  if (ページ i からページ j へのリンクが「ない」場合)

で表わされるとしよう。文書数を N とするとこの行列は N×N のN次正方行列になる。これは、グラフ理論で「隣接行列」と呼ばれるものに相当する。すなわち、Web のリンク関係を有向グラフ S と見なし、その隣接関係を取ったものである。要するに、リンクが張られていれば隣接関係があるわけである。

(*註) 点とそれを接続する線から構成されている図形を「グラフ(graph)」と言う。点のことを「頂点(vertex)」とか「節点(node)」と呼び、線のことを「辺(edge)」とか「弧(arc)」と呼ぶ。グラフには２種類あって、辺に向きの無いグラフを「無向グラフ(undirected graph)」といい、辺に向きがあるグラフを「有向グラフ(directed graph)」という。有向グラフは一方通行の道と考えればよい。グラフはいろいろな方法で表すことができるが、一般に用いられるデータ構造は「隣接行列(adjacency matrix)」や「隣接リスト(adjacency list)」である。無向グラフであれば隣接行列 A は対称行列になるが、有向グラフであれば A は非対称行列になることに注意しよう。

以下の図は、Apache のオンラインマニュアル(128ページ)の隣接行列をビットマップで表わしたものである。黒点が横に連なっているページはすなわち外向けのリンクが多いページであることを示し、逆に縦に連なっているページは、たくさんリンクされているページであることを示している。

隣接行列の例 (Apache のオンラインマニュアルを用いたもの)

PageRank の行列は、この隣接行列を転置し(行と列を入れ替えること)、さらにそれぞれの列(column)ベクトルの総和が 1 (全確率)になるようにそれぞれのリンク数(すなわち、非零要素数)で割ったものと言える。作られた行列は「推移確率行列」と呼ばれ、 N 個の確率変数を持ち、各行ベクトルは状態間の推移確率を表わす。転置する理由は、PageRank が「どれだけリンクしているか」ではなく「どれだけリンクされているか」を重視しているからである。

PageRank の計算は、この推移確率行列の最大固有値に属する固有ベクトル(優固有ベクトル)を求めることにほかならない。

なぜなら、線形変換系の t →∞ での漸近挙動は、変換行列の絶対値最大の固有値とそれに属する固有ベクトルによって本質的に記述されることがわかっているからである。言い換えれば、推移確率行列で表わされる確率過程は、この行列の掛け算を繰り返したものを調べることで、行き着く先の状態の確率を計算できると言うことである。

なお、固有値や固有ベクトルを求めると言われても、依然として難しく聞こえるかもしれないが、これは厳密に解析できる基礎的な数学の一手法である。ベクトルの初期値は自由に与えられるが、行列を繰り返し掛けていくことで、与えたベクトルをある一定の値の組に落ち着かせることができる。その安定な数値の組合わせを固有ベクトルと呼び、固有ベクトルに特徴的なあるスカラー量のことを固有値と呼ぶ。このような計算手法全体のことを固有値分解と言い、固有値分解すれば解ける問題のことを固有値問題と言うのである。

(*註) N次正方行列 A に対して Ax = λx を満たす数λをAの固有値といい、 x をλに属する固有ベクトルという。どうしても行列の概念になじみがなければ、サイズが N×N の二次元配列を考えてもらえば良い。また、ベクトルとはサイズ N の通常の(一次元)配列のことと考えれば良い。

簡単な具体例

簡単な具体例を用いて逐次的に PageRank を計算してみよう。以下のようなリンク関係を持つ７つのHTML文書を考えよう。なお、この HTML文書間のリンク関係は 1-7 の文書だけで閉じているものとする。つまり、この文書群以外からのリンクの出入りはないものとする。また全てのページで出入りの両方があることに注意する(行き止まりが無い)。このことは後に重要な仮定になるが、ここでは深くは立ち入らないでおく。

ページ相互のリンク関係を表わした推移図

まず、上の推移図に対応するグラフ構造を表わす隣接リストの配列表現は以下のようになる。すなわち、それぞれのリンク元IDから発するリンク先IDを列挙したものである。

        リンク元ID      リンク先ID
        1               2,3,4,5,7
        2               1
        3               1,2
        4               2,3,5
        5               1,3,4,6
        6               1,5
        7               5

この隣接リストで表現されるリンク関係の隣接行列 A は以下のような7×7の正方行列になる。要素は 0 か 1 だけのビットマップ行列である。 i 行目を横に見れば「文書 i からリンクしている文書ID」を表わしていることになる。

A = [
        0, 1, 1, 1, 1, 0, 1;
        1, 0, 0, 0, 0, 0, 0;
        1, 1, 0, 0, 0, 0, 0;
        0, 1, 1, 0, 1, 0, 0;
        1, 0, 1, 1, 0, 1, 0;
        1, 0, 0, 0, 1, 0, 0;
        0, 0, 0, 0, 1, 0, 0;
]

PageRank 式の推移確率行列 M は、A を転置しそれぞれの列を非零要素数で割った、以下のような7×7の正方行列になる。 i 行目の非零要素を横に見れば「文書 i に対してリンクを張っている文書ID」を表わしていることになる。各列を縦に足し合わせるとすべて 1 (全確率) になっていることに注意しよう。

M = [
        0,   1, 1/2, 0,   1/4, 1/2, 0;
        1/5, 0, 1/2, 1/3, 0,   0,   0;
        1/5, 0, 0,   1/3, 1/4, 0,   0;
        1/5, 0, 0,   0,   1/4, 0,   0;
        1/5, 0, 0,   1/3, 0,   1/2, 1;
        0,   0, 0,   0,   1/4, 0,   0;
        1/5, 0, 0,   0,   0,   0,   0;
]

PageRank のベクトル R (それぞれのページのランクを表わす数値の列)は、 R = cMR という関係で結ばれる(c は定数)。この場合、R は線形代数で言うところの固有ベクトルに相当し、c は対応する固有値の逆数に相当する。そこで、R の組を得るためには、この正方行列 M を固有値分解すれば良いことになる。

固有値分解するにはそれなりの数値解析的なさまざまの手法があるが、その詳細をここで説明するのは本筋ではないので適当な教科書を読んでもらうことにして(優に本棚一つを埋め尽くすだけの教科書が存在する)、ここでは横着をして GNU Octave という計算プログラムを使って固有値と固有ベクトルを実際に計算することとしよう。

(*註) GNU Octave は、数値計算をサポートし記述性に優れる MATLAB に似たプログラミング言語である。処理言語は行列演算に適する様に拡張されているが、基本的にC言語風の言語仕様を持つため可読性が高い。詳しくは http://www.octave.org/ を参照のこと。むろん、Octave でなくとも MATLAB でも Scilab でも良いわけだが、GPL 準拠である Octave が最も入手しやすいだろう。

実行例

以下に実行例を示す。何をやっているか良くわからない人は、なにやら Octave というプログラムを使えばとにかく固有値問題が解けるらしい、ということだけ理解してもらえれば良い。

まず、以下のような Octave スクリプトを適当なエディタで作成する。 (余分な結果出力表示は行末にセミコロンを付ければ消せるのだが、今回は説明のためにわざと外してある。)


% cat pagerank.m
#!/usr/bin/octave
## pagerank.m - PageRank(TM) 計算用の簡単な GNU Octave スクリプト

## タイマーをセット。
tic();

## 文書 i から文書 j へのリンクの状態を示す推移確率行列 M(i,j) を
## PageRank の定義に従って定義。
M = [
     0,   1, 1/2, 0,   1/4, 1/2, 0;
     1/5, 0, 1/2, 1/3, 0,   0,   0;
     1/5, 0, 0,   1/3, 1/4, 0,   0;
     1/5, 0, 0,   0,   1/4, 0,   0;
     1/5, 0, 0,   1/3, 0,   1/2, 1;
     0,   0, 0,   0,   1/4, 0,   0;
     1/5, 0, 0,   0,   0,   0,   0;
]

## M の固有値と固有ベクトル列の組合わせのすべてを計算。
[V,D] = eig(M)

## 絶対値が最大の固有値に対応する固有ベクトルを EigenVector に保存。
EigenVector = V(:, find(abs(diag(D)) == max(abs(diag(D)))))

## PageRank は EigenVector を確率ベクトルに正規化したもの。
PageRank = EigenVector ./ norm(EigenVector, 1)

## かかった計算時間を表示。
elapsed_time = toc()

(2003/7/23: 上記スクリプトにおける誤りを以下のように修正しました。)

  誤: EigenVector = V(:, find(max(abs(diag(D)))))
  正: EigenVector = V(:, find(abs(diag(D)) == max(abs(diag(D)))))

この pagerank.m を、Octave に食わせれば良い。すると、以下のような結果が標準出力に出てくる。


% octave pagerank.m
GNU Octave, version 2.0.16 (i586-redhat-linux-gnu).
Copyright (C) 1996, 1997, 1998, 1999, 2000 John W. Eaton.
This is free software with ABSOLUTELY NO WARRANTY.
For details, type `warranty'.

M =

  0.00000  1.00000  0.50000  0.00000  0.25000  0.50000  0.00000
  0.20000  0.00000  0.50000  0.33333  0.00000  0.00000  0.00000
  0.20000  0.00000  0.00000  0.33333  0.25000  0.00000  0.00000
  0.20000  0.00000  0.00000  0.00000  0.25000  0.00000  0.00000
  0.20000  0.00000  0.00000  0.33333  0.00000  0.50000  1.00000
  0.00000  0.00000  0.00000  0.00000  0.25000  0.00000  0.00000
  0.20000  0.00000  0.00000  0.00000  0.00000  0.00000  0.00000

V =

 Columns 1 through 3:

   0.69946 + 0.00000i   0.63140 + 0.00000i   0.63140 + 0.00000i
   0.38286 + 0.00000i  -0.28715 + 0.15402i  -0.28715 - 0.15402i
   0.32396 + 0.00000i  -0.07422 - 0.10512i  -0.07422 + 0.10512i
   0.24297 + 0.00000i   0.00707 - 0.24933i   0.00707 + 0.24933i
   0.41231 + 0.00000i  -0.28417 + 0.44976i  -0.28417 - 0.44976i
   0.10308 + 0.00000i   0.22951 - 0.13211i   0.22951 + 0.13211i
   0.13989 + 0.00000i  -0.22243 - 0.11722i  -0.22243 + 0.11722i

 Columns 4 through 6:

   0.56600 + 0.00000i   0.56600 + 0.00000i  -0.32958 + 0.00000i
   0.26420 - 0.05040i   0.26420 + 0.05040i   0.14584 + 0.00000i
  -0.10267 + 0.14787i  -0.10267 - 0.14787i   0.24608 + 0.00000i
  -0.11643 + 0.02319i  -0.11643 - 0.02319i  -0.24398 + 0.00000i
  -0.49468 - 0.14385i  -0.49468 + 0.14385i   0.42562 + 0.00000i
  -0.14749 + 0.38066i  -0.14749 - 0.38066i  -0.64118 + 0.00000i
   0.03106 - 0.35747i   0.03106 + 0.35747i   0.39720 + 0.00000i

 Column 7:

   0.00000 + 0.00000i
  -0.40825 + 0.00000i
  -0.00000 + 0.00000i
   0.00000 + 0.00000i
  -0.00000 + 0.00000i
   0.81650 + 0.00000i
  -0.40825 + 0.00000i

D =

 Columns 1 through 3:

   1.00000 + 0.00000i   0.00000 + 0.00000i   0.00000 + 0.00000i
   0.00000 + 0.00000i  -0.44433 + 0.23415i   0.00000 + 0.00000i
   0.00000 + 0.00000i   0.00000 + 0.00000i  -0.44433 - 0.23415i
   0.00000 + 0.00000i   0.00000 + 0.00000i   0.00000 + 0.00000i
   0.00000 + 0.00000i   0.00000 + 0.00000i   0.00000 + 0.00000i
   0.00000 + 0.00000i   0.00000 + 0.00000i   0.00000 + 0.00000i
   0.00000 + 0.00000i   0.00000 + 0.00000i   0.00000 + 0.00000i

 Columns 4 through 6:

   0.00000 + 0.00000i   0.00000 + 0.00000i   0.00000 + 0.00000i
   0.00000 + 0.00000i   0.00000 + 0.00000i   0.00000 + 0.00000i
   0.00000 + 0.00000i   0.00000 + 0.00000i   0.00000 + 0.00000i
   0.02731 + 0.31430i   0.00000 + 0.00000i   0.00000 + 0.00000i
   0.00000 + 0.00000i   0.02731 - 0.31430i   0.00000 + 0.00000i
   0.00000 + 0.00000i   0.00000 + 0.00000i  -0.16595 + 0.00000i
   0.00000 + 0.00000i   0.00000 + 0.00000i   0.00000 + 0.00000i

 Column 7:

   0.00000 + 0.00000i
   0.00000 + 0.00000i
   0.00000 + 0.00000i
   0.00000 + 0.00000i
   0.00000 + 0.00000i
   0.00000 + 0.00000i
  -0.00000 + 0.00000i

EigenVector =

  0.69946
  0.38286
  0.32396
  0.24297
  0.41231
  0.10308
  0.13989

PageRank =

  0.303514
  0.166134
  0.140575
  0.105431
  0.178914
  0.044728
  0.060703

elapsed_time = 0.063995

Octave の出力のうち、固有値は対角行列 D の対角成分として与えられ、それぞれの固有値に対応する固有ベクトルは行列 V の対応する列の列ベクトルとして与えられる。つまり M*V = D*M が成り立つ。固有値は複素数も含めると7つあるが、このうち絶対値最大の固有値λは λ=1 である。これに対応する固有ベクトルは実ベクトルであり、

EigenVector =

   0.69946
   0.38286
   0.32396
   0.24297
   0.41231
   0.10308
   0.13989

である。すなわち、行列 V の第 1 列目である。この求めた固有ベクトルは確率ベクトル (要素の和が 1 に等しいN 次元非負ベクトル)には正規化されておらず、ベクトルの「大きさ」が 1 になっていることに注意しておこう。数式で言えば、Σp_i ≠ 1 だが Σ(p_i)² ＝ 1 である。そこで、確率ベクトルに正規化した

が PageRank のランクということになる。全部足すと 1 になることに注意しよう。この計算はたったの 0.064 秒でできてしまう。

求めた PageRank の評価

PageRank の評価順に並べ替えてみると以下のようになる (PageRank は小数点3位で四捨五入した)。

  順位  PageRank  文書ID  発リンクID  被リンクID
  1     0.304     1       2,3,4,5,7   2,3,5,6
  2     0.179     5       1,3,4,6     1,4,6,7
  3     0.166     2       1           1,3,4
  4     0.141     3       1,2         1,4,5
  5     0.105     4       2,3,5       1,5
  6     0.061     7       5           1
  7     0.045     6       1,5         5

まず注目すべきは、PageRank の順位と被リンク数の多さとが基本的に一致していることである。外に向けてリンクをいくらたくさん張ろうともそれはPageRank にはほとんど影響せず、逆にどれだけ外からリンクを張られているかで PageRank の大きさが一義的に決まることがわかる。だが、単にそれだけでは1位と2位の大差(あるいは 3位と4位や、6位と7位の差) は説明できない。つまり、被リンク数だけで PageRank が決まるわけではないところにその絶妙さがあるのである。

細かく見よう。ID=1 の文書の PageRank は 0.304 で全体の3割を占め 1位になっている。とくに、3位の ID=2 のランク(0.166)を全部もらっていることが大きく効いていることがわかる。 ID=2 は3個所からリンクを張られているが ID=1 に対してしかリンクが張っていないからランクを全部もらうことができるわけである。もっとも、ID=1 はリンクする方もされる方も多いページであり、人気が高いであろうことはだいたい納得がいくだろう。

逆に最下位は ID=6 の文書であり ID=1 の 15% 弱の評価しかないが、これは PageRank の高い ID=1 からのリンクがないことが大きく影響しているものと考えれば納得がいくだろう。つまり、同じリンクを張られるにしても、そのリンク元のページがどれくらい評価されているかによっても影響されることがわかる。

ページ相互のリンク関係を表わした推移図(PageRank入り)

実際に PageRank の収支を計算してみよう。λ=1 だから計算は簡単で、流入量は各ページからの流入量を単純に足し合わせるだけで良い。たとえば ID=1 の場合の流入量は、

  流入量 = (ID=2発ランク) + (ID=3発ランク) + (ID=5発ランク) + (ID=6発ランク)
         = 0.166 + 0.141/2 + 0.179/4 + 0.045/2
         = 0.30375

となり、誤差の範囲内で収支が正しく合っていることがわかる。他の文書 IDの場合でも同様である。このことを表わしたのが上の PageRank 推移図である。それぞれのリンクに沿って出ていく PageRank が、もともと持っていた PageRank を発リンク数で割ったものになっていることと、またそれぞれの文書IDの収支が合っていることを確認して頂きたい。

もっとも、このように絶妙な釣り合いが取れていること自体は、線形代数を理解している人にとっては当たり前のことで驚くに値しない。なぜならそれが「固有値と固有ベクトルの性質そのもの」、つまり、そうなるように選ばれた数値の組が固有ベクトルだからである。だがそれであっても、こうやって実際に確認してみると、PageRank の考え方が良くできたものであることが実感できるだろう。

PageRank の原理は基本的には以上のようなものである。 Google のやっていることは、このような固有値問題を規模を非常に大きくしてやっているということになるのである。

前へ | 次へ

4. 現実に適用する際の問題

PageRank の基本的な考え方自体は難しいものではない。実用的な効果が絶大な割には複雑怪奇なアルゴリズムでもなんでもなく、簡単な線形変換を行うだけであり、むしろ簡明で直感的に理解しやすい部類に属するだろう。だが、実際の Web ハイパーリンク構造を使って PageRank を計算するとなると、さすがに口で言うほどには易しいものではない。その困難は主に二つある。一つには、純粋に仮想的な数値モデルと現実世界との相違に由来するものであり、もう一つは、実際に数値計算する上での(もっぱら技術的な)困難である。

準備：数学用語(主に確率過程)の解説

推移確率行列は、確率過程に現れるマルコフ過程と深い関わりがある。そこでこの節では PageRank 自体の説明とは少し離れて、確率過程に現れる数学用語をいくつか説明しておく。かなり難しい部類に入るとおもうので、良く分からなければ読み飛ばしてもらっても構わない (良くわからなければ説明の仕方が悪いと考えていただいて構わない)。また、ほとんど証明無しに用いているので注意してほしい。詳しい解説は教科書を読んでもらいたい。

有向グラフ S のある状態 i を出発して、有限時間の後で状態 i に再び戻ってくる確率が 1 であるとき、すなわちグラフの路を順方向にたどるだけで元の位置に戻ってこれる経路が存在するとき、i は「再帰」であるという。再帰でない状態は「非再帰」であるという。状態 i から出発して有限回の推移で状態 j に達する確率が 0 ではなく正であるとき、「状態 j が状態 i から到達可能」という。逆方向にも到達可能であるとき、「i と j は相互到達可能」と言う。状態 i から他のどんな状態へも到達できないとき、i を「吸収状態」と呼ぶ。

隣接行列 A の定めるグラフの任意の頂点から出発して、他の任意の頂点へグラフの路を矢印通りに進んで到達できることを「強連結」と言う (「分解不能」と呼ぶこともある)。強連結は、任意の状態から任意の状態へ相互到達可能であることと同値である。強連結性が問題になるのは、隣接行列 A の成分に 0 が多いときである。すべての成分 a_ij ≠ 0 なら常に強連結であることに注意しよう。なぜなら、対応するマルコフ連鎖の標本路がS の任意の二点間を正の確率で往来できることを示しているからである。

状態全体を同値類(あるいは再帰類)に分けることができる。ここで、再帰類とはリンクをたどっていける範囲のことである。一つの同値類に入っている状態は互いに相互到達可能である。一つの類から出発してどれか他の類へ正の確率で入ることもありえる。しかしこの場合は明らかに元の類に戻ることは不可能である。さもなければ、この二つの類は一つの同値類にまとまってしまう。以下の図は、R を再帰的な同値類、T を非再帰的な同値類とすると、マルコフ連鎖は再帰類から出ないし、非再帰類から出ないこともあるが、一度出ると再びその非再帰類に戻ってくることはないことを示している。

再帰・非再帰の関係を表わした図 (小谷(1997) 図11.1 を改変)

この同値関係でただ一つの再帰類しかできないとき、そのマルコフ連鎖は「既約」であるという。言い換えれば、全ての状態が相互到達可能であるとき既約であるという。既約であれば強連結である。

相互にまったく関連のない隣接行列(あるいは推移確率行列)は、適当な置換行列(行や列を入れ替える行列)を掛けると、

    P = | P1  0  |
        | 0   P2 |

のような関係にできる。これは再帰類 P1 と P2 との間に直接のリンク関係がまったく存在しないことを示している。

再帰類・非再帰類がまざっている隣接行列(あるいは推移確率行列)は、適当な置換行列を掛けると、

    P = | P1  0  |
        | Q   P2 |

のような関係にできる(ただし Q ≠ 0)。このとき、P1 が非再帰類、P2 が再帰類である。

推移確率行列はマルコフ行列と呼ばれることもある。マルコフ過程の試行列の観測結果をマルコフ連鎖と呼ぶ。マルコフ連鎖は、時間が十分に経過するとある種の平衡状態に近づく。任意の状態 i に対して j が非再帰状態なら P_ij⁽ⁿ⁾ → 0 である。逆に i が非再帰で j が再帰である場合、状態 i にとどまっていられる確率は 0 である。 i,j が同じ非周期的再帰類に属していれば、 P_ij⁽ⁿ⁾ →π_j ≧ 0 である。

定理：P を有限マルコフ行列とすると、 P の固有値 1 の重複度は P から決まる再帰類の数に等しい。 (証明は長くなるので略する)。

推移確率行列に付随する有向グラフの極大強連結成分 (に対応する状態の集合)をエルゴート部分、それ以外の強連結成分を消散部分と呼ぶ。どのような初期状態確率 x⁽⁰⁾ から始めても、時間 n が経つにしたがって x⁽ⁿ⁾ = P⁽ⁿ⁾ x⁽⁰⁾ であるから、消散部分に属する状態の存在確率は 0 に近づく。エルゴート部分については、各連結成分に対応する状態の類ごとに一つの独立な既約マルコフ連鎖のごとくに振る舞い、各類の中での状態確率 (あるいはその過去からの平均)は初期状態確率によらない値、すなわち対応する P の既約成分の固有ベクトルに比例するものに近づく。類の間での確率の分配は初期状態確率に依存する。

離散時間型マルコフ連鎖の不変分布は極限分布であり、その分布からはもはや分布の意味での時間的発展はない。状態の確率分布が時間を変化させても変わらないとき、定常分布と呼ぶ。 PageRank をマルコフ過程の用語で言い直すならば、 PageRank は、ランダムにリンクをたどって動くユーザが一定の時間のうちにそれぞれのページを訪問する定常分布であるとも言える。

仮想モデルと現実世界との相違

では、確率過程(あるいはグラフ理論)の考え方と現実のWebページのリンク構造とをすり合わせてみよう。

これまでに例として挙げてきた仮想的な Web ページ群はリンクをたどってさえいれば必ず互いのページにたどりつける関係であった。すなわち、有向グラフは強連結であり行列は再帰かつ既約であった。上に挙げたように多くの確率過程の教科書では再帰ないし既約であることを前提にした証明が数多くなされており、既約であればいろいろの性質を言うことができるようになっている。

だが現実のWebページは、強連結ではない。すなわち隣接行列は既約でない。具体的には、リンクをたどっていくと外向きのリンクがまったくないページに行き当たることがある。こういう場合は通常は web ブラウザの「戻る」機能を用いるしかない。人間がブラウジングするだけならばそれで済むが、 PageRank 計算の上ではそれでは済まない。 PageRank が吸い込まれてしまって戻ってこないからである。このようなページのことを、Page らは「dangling page」と呼んでいる。同じ理屈で、外向きのリンクはあるけれども、張られているリンクがまったく無いページも存在する。 Page らはこのようなページについては考慮していないが、流入する PageRank がないのに流出する PageRank だけ考慮できるのは対称性から言ってもおかしなはずである。

また、リンクが部分集合だけでループになって外に出られない現象もある。これは非周期的再帰類が複数存在すると起こりうる問題である (上記の図で R の一つにはまりこんでしまったら、他のR や T にはもう移れないことを考えて頂きたい)。 Page らは「rank sink」と呼んでいる。それに現実のページでは、リンクをどうたどっていっても、リンクをたどるだけでは絶対にたどりつけないページ群が存在する、つまりページ群が相互に連関のない複数の同値類(再帰類)からなっているわけである。

つまり、現実の Web ページからなる推移確率行列のほとんどは既約でない。既約でない場合は最大固有値(すなわち1)が重複しており、優固有ベクトルが複数存在する問題を避けられない。言い換えれば、PageRank が一意に決まらないことを意味する。

そこで、Page らはこのような問題を解決するために、 「ユーザは、多くの場合は現在のページに存在するリンクをたどって移動するが、時々は全く無関係なページにジャンプする」 というブラウジングモデルを考えた。なお、「時々」というのは具体的には 15% という数字に固定して計算している。ユーザは 85% はリンクをたどるが、15% は突然無関係なページに飛んでいくということである。 (注：Page らのオリジナルの手法ではそれぞれ 87% (= 1/1.15) と 13% (= 0.15/1.15) であった。)

これを数式で表わすと以下のようになる。

M' ＝ c・M + (1-c)・[1/N]

ただし、[1/N] はすべての要素が 1/N である N次正方行列であり、 c = 0.85 (= 1-0.15) である。 M' も同じく推移確率行列になることは自明だろう。すなわち、Page たちによる変形はもともとの行列 M の固有値問題から、行列 M' の優固有ベクトルを求める固有値問題に変形したことを意味する。 M が定常無記憶情報源(i.i.d.)である場合、M' は「混合情報源」と呼ばれ、定常ではあるがエルゴート的でない情報源の典型例である。

このことを数学的に見れば「非既約な推移行列を既約にする」こと、別の言葉では「強連結ではないグラフを強連結にする」変換操作を施したことを意味する。全ての要素に移転確率 0.15 を考慮すると言うことは、もともとの既約でない推移確率行列を、既約かつ再帰(当然のことながら非負でもある) の推移確率行列に変換することを意味する。もともとの推移確率行列に対してこのような変換操作を行うことによって、 PageRank が一意に決まること、すなわち、最大固有値の重複度を 1 にすることが保証される。このような変換操作を考慮することによって推移確率行列の再帰類の数は 1 になり同時に既約になるから、先の定理により、優固有ベクトル(すなわち PageRank)が一意に決まると言うことになるのである。

数値計算上の問題点(その1)

ここでは PageRank のだいたいの概念がわかれば良いので、数値計算上の技術的問題に深く立ち入る必要はないとおもわれる (そもそも、筆者自身も自信を持って説明できない)。だが、固有値解析は連立一次方程式解析と同様に各種の統計分析の中で利用される重要な数値計算手法の一つなので、解析法について簡単に触れておく。

数値計算する上での問題の一つは、主記憶領域の問題である。

仮に N が 10⁴ のオーダだったとしよう。通常は数値計算プログラムの内部では行列やベクトルは倍精度で格納されるから、N次正方行列 A の記憶領域は sizeof(double) * N * N = 8 * 10⁴ * 10⁴ = 800MB となる。さすがに、800MB の主記憶領域はなかなか持てるものではないだろうが、とはいえ不可能な数字と言うわけでもない。だが、N が 10⁵ や 10⁶ になると、それぞれ 80GB, 8TB となる。こうなるとメモリどころかハードディスクでももうムリである。 Google では 10億以上のページを扱っているから(2001年時点)、まともなやり方ではまったくダメであることがわかる。

もっとも、A は疎(sparse)な行列である。リンクを張りまくっているページが一部にあったとしても、 Web全体に張っているものはないし、あったとしてもそれは極めてまれな存在であるからだ。平均的には、1ページあたり10-20リンク程度ではないだろうか (IBM Almaden 研究所による 'Graph structure in the web'によれば、平均すると 16.1 程度だそうである)。だから、A は適切な圧縮方法を用いて圧縮できる。 N が 10⁶ であっても平均リンク数を10とすれば 80MB で済み、規模からいって無理のない数字に納めることができる。

疎行列の格納方式はすでに十分研究されているから(有限要素法の解法など)、適切な数値計算の専門書にあたってそれらを学べば良い。とはいえ、相当に難解で面倒な手法が必要である。ただしうまくすれば並列化による高速計算の可能性がでてくる(らしい)ことは指摘しておきたい。疎行列の解法では非零要素をどのように配列上に格納するかにより、計算性能と並列性能が強く影響を受けるからである。

数値計算上の問題点(その2)

もう一つは、収束の問題である。

定常方程式

x_i = ΣA_ijx_i

は N 元の連立一次方程式であり、一般的には解析解が得られないから、数値的に解くしかない。先に挙げた例では固有値と固有ベクトルを求めるのに Octave の eig() 関数を用いたが、これは問題が小さい場合にしか適用できない。そもそも、全部の固有値／固有ベクトルを計算する必要はない。

最大固有値とそれに属する固有ベクトル(優固有ベクトル)を求める数値計算手法には、「べき乗法」(反復法とも呼ばれる)を用いるのが普通である。これは、初期ベクトル x⁰ を適当にとり、 x⁽ⁿ⁺¹⁾ = A y⁽ⁿ⁾ (ただし、y⁽ⁿ⁾ = x⁽ⁿ⁾ / c⁽ⁿ⁾) として n →∞ とした場合、x は最大固有値を持つ固有ベクトルに収束し同時に c はその最大固有値に収束するという、線形代数的な性質を利用した計算方法である (証明は線形代数の教科書に載っているので参照されたい)。べき乗法(反復法)の特長は逐次繰り返しの近似法により解ベクトルが改善できることである。その利点は、行列とベクトルの掛け算を適当な回数繰り返すだけで良いのでプログラムが簡単で済むことと、直接法ではメモリやディスクの制限によって取り扱えないような大規模な解析を行えることであり、多くの実用的算法の原点である。

ここで、線形代数の簡単な定理(ペロン・フロベニウスの定理)から、推移確率行列の絶対値最大の固有値は 1 であることに注意しておこう。このことを用いれば、反復法での PageRank の計算がよりやりやすくなる。すなわち、最大固有値が既知であるから、 Ax = x を満たすベクトル x を求めよという、より簡単な問題に帰着されるからである。これは細かいことではあるが重要であるとおもう。まず、計算に比較的コストのかかる割り算 (y⁽ⁿ⁾ = x⁽ⁿ⁾ / c⁽ⁿ⁾) を不要にできる。さらに、反復法においては十分な精度を取らずかつ加速方法を間違えると、最大固有値でなく二番目に大きい固有値とそれに属する固有ベクトルを計算してしまう場合があるからである (もっともこれは稀であるし、根本的に誤っているからかもしれない)。だが最大固有値がわかっているから、チェックすることが可能になる。 Page らの第一論文ではこのことには気が付いていなかったようだが、 Haveliwala の第二論文でこの点に関する修正が加えられている。

反復回数は、どの程度の精度を求めるかによって決まる。つまり精度が欲しければ反復回数を増やしてやる必要がある。しかし、べき乗法(反復法)の誤差の収束比は、係数行列のスペクトル特性(固有値の絶対値の分布)に強く依存する。具体的には、絶対値最大の固有値λ₁、二番目をλ₂とし、優越率(ないしは収束率) d = λ₁ / λ₂ とすると、 d が 1 に近いほど収束が遅くなることが知られている。だが、d は、N が大きい場合には当然 1 に近くなる。なぜなら、絶対値最大固有値が 1 であることから、他の N-1 個の固有値の絶対値はすべて 1 より小さい。だが、 N-1 個がひしめきあうことから λ₁ とλ₂ の間にはほとんど差がないためである。このため一般に収束が遅くなる。

収束が遅いというのは、ベタな言葉で言えば、いつまで経っても計算が終らないということである。対して、収束を速めるための適当な加速法もいくつか存在することは存在するが、それらを適用するためには数値計算技法に対する十二分な理解が必要となるため、数値計算の専門家でない限りは導入は易しいものではない。

前へ | 次へ

5. Namazu での実装実験

これまで述べてきたことから容易に推測できるように、 PageRank の考え方そのものは、世界中の全webページの場合でないと適用できないものではなく、個人的な利用法であっても実現できるはずである。そこで「Personalized PageRank」を実現するために、各種 UNIX や Windows などで動作する中小規模サイトに適した全文検索システム Namazu に対しての実装実験を行った。 (Namazu については日本語全文検索エンジンソフトウェアのリストも参考になるだろう。)

実験では、メモリ使用量を簡単に押えることができることと、最大固有値が 1 になるように考慮されていることから、 Haveliwala (1999) の考え方を基本にした。ただし dangling pages の扱いなどは若干異なる。固有ベクトルの計算用エンジンとして数値計算スクリプト言語の GNU Octave を用いた。このため基本的なコーディング作業自体はたったの1日で済んだ。なお、mknmz で作ったインデックスからは直接 PageRank が計算できず、隣接関係を表わすためのインデックス(早い話が隣接リスト)を事前に準備しなければならない。これはインデクサ本体に組み込んでしまうことも可能である。

実際の計算時間を以下に示す(単位は秒)。実行したマシンは PentiumII 400MHz x 2, メモリ 512MB, Kondara MNU/Linux 1.2 (kernel-2.2.17-15ksmp), Octave-2.0.16 (ディストリビューション附属のノーマル状態のもの) という感じである。収束精度(残差ベクトルのL1ノルム)は 1.0e-10 に取ったが、これはたぶん取り過ぎであろう。

    文書数N     mknmz時間       準備時間        PageRank計算時間
    ============================================================
    128         58              2               6
    2,301       1,575           46              214
    49,604      15,975          478             5,872

あまり巨大なwebページ群をテスト用に持ち合わせていないので、小規模な実験にとどまっていることが難点であるが、基本的にはインデックスにかかる時間よりは短い時間で PageRank を計算できる傾向を見て取ることができるだろう。

Namazu 側にも困難があるのであまり高望みはしていないが、せめて 10⁵ 程度(できれば 10⁶)の規模の web ページ群で実験したいとはおもっている。傾向から見るとおそらく N=10⁶ では計算時間が発散してしまうことが予想されるので、 N=10⁶ で mknmz 時間と comparable になるように加速法を検討できれば、Personalized PageRank としては十分に実用的なものであると言って良いだろう。参考までに Page et al.(1998) によれば、Google での実際の PageRank 計算に要する時間は、7500万のURLに対して約5時間だったそうである。 (2001年2月現在でどうなっているかは不明)。このことからすると、より効率的な加速法を検討する余地が十分に残されていることは言えるだろう。

計算実行時の使用メモリは最大でも10数MB程度であった。 Haveliwala (1999) にあるような「ケチケチ作戦」を取れば最大でも O(3N+2) 程度のメモリ使用量で済ませることができるのであるが、 N が 10^4-5 程度だとメモリ使用量に関しては N² さえ入れないようにすれば他はあまりカリカリとチューニングしてもしょうがないので、 O(5N+α) (ただしαは疎行列の非零成分の数で、典型的には5-20N程度) 程度取るようにコーディングしている。また N が 10³ 程度だと、疎行列を圧縮せずに疎のままメモリ上に取ってしまってべき乗法を用いる方が速度面で非常に有利になることも確認している。実測では上記の数字の 6-7 倍程度の速さにできる。ただし、この方法はメモリの制限から言って、せいぜい2-3千ページまでしか使えないのが残念なところである。

今回は Octave はディストリビューション附属の「ツルシ」のものを使ったが、良く知られているように、Octave はチューニングすれば劇的に速くできるらしい。Octave-2.1.x と ATLAS との組合わせでは場合によって大規模行列同士の掛け算の速度が10倍以上になることすらあるようである。

実験結果の詳細は prnmz-1.0.tar.gz 中のドキュメントも参照して頂きたい。

Personalized PageRank の基本的な性質

MHonArc や latex2html あるいは PowerPoint のようなツールを用いて HTML に変型することは良く行われることであるが、このような人工的に作ったHTMLリンク群に対して PageRank を求めると、ほとんどすべてのページのスコアが同じ(～1/N)になる。隣接行列を考えればほとんど全ての成分が 1 であるか対角成分付近が全て 1 である。このような推移確率行列の固有ベクトルは (1,1,…,1) になるからである。

あるいは、sitemap.html のようにツリー状になっている場合は、 sitemap.html にスコアが集中する。全体の9割を占めることも珍しくない。

これらから言えることは、意味のある PageRank を計算するためには、機械的に生成したリンク関係はできるだけ排除してやる必要があるということである。これはリンク関係を推薦関係と見なせば容易に是認できるだろう。

前へ | 次へ

6. PageRank に対する個人的見解

PageRank のようなハイパーリンクを利用したランキング手法が有効であることには疑いの余地はないだろう。

ただ、その論文を見ればいろいろ考えることもある。そこで、PageRank に対する個人的な見解をいくつか挙げる。見解と言ってもあくまで方法論に対するものである。間違っていることも多々あることに注意して頂きたい。

・dangling page については考えているのにその逆を考慮しないのはなぜか: 一定の変異確率を考えることで「たまたま」既約になっているから考慮していないだけなのか。それとも何か見落としていることがあるのか。ちょっとわからないでいる。
・推移確率行列の改善の可能性: そもそも、PageRank の一意性を保証するためには、推移確率行列が既約であること(ないしは有向グラフが強連結であること) が保証されればよいのであって、全ての要素 a_ij を非零にする必要は別にないはずである。実際、webブラウジングでトヨタ自動車のサイトを見た直後にポルノサイトに跳び、続いてホワイトハウスに跳んで２ちゃんねるに跳ぶ、というようなヘンな挙動を示す人はほとんど誰もいないだろう。 (あくまで、時間的に連続した形で、という意味であることに注意)。従って、実用的な意味でどの程度使い勝手が改善されるかは別として、アルゴリズム的には改良を加える余地は残されているはずである。
・「滞留確率」を考慮してはどうか: PageRank の考え方によれば、一定の時間後には必ずリンクをたどってどっか別のページに飛ぶか、あるいは突然変異的・ワープ的にその他のページに飛ぶかである。だが現実のwebブラウジングモデルに照らし合わせるなら、一定の滞留確率も考慮する方が良いのではないか。具体的に言えば、推移確率行列の対角成分に (1-c)/N しか取らないのは小さすぎるのではないかということである。どうせなら、すべて一定の遷移確率よりも重みづけしてはどうか。つまんないページからはあっという間に別ベージに遷移するはずであるし、逆に重要なページには長い時間滞留するはずだからだ。
・確率論の応用と考えればいろいろ考えられるはず: このような考え方を、実現性は度外視してもう少し進めてみる。確率論には、消滅確率・あるいは固定確率と呼ばれるものがある。 PageRank の考え方における単純かつ一様な移転確率よりも、これらの考え方を導入する方がより望ましい結果を生むことが当然期待される。マルコフ連鎖には、分枝過程という考え方が知られている。これは遺伝子の突然変異を考えるときのモデルの一つであり、すなわち、一定の時間が経てば淘汰を起こす可能性を説明するモデルである。この考え方は、おそらく取り入れることが可能であろうとおもわれる。制限付き確率(タブー確率)の考え方を導入してはどうか。すなわち、状態 i から状態 j へ n 回の推移で移動し、その間に状態 k には行かないという確率を導入することに相当する。 web ブラウジングの性質を考えれば当然の仮定となり得るのではないか。
・非マルコフ過程(ないしは m次の多重マルコフ過程)として考えられないか: マルコフ過程とは、過去の履歴とは関係なく現在の状態のみから未来の確率法則が決定される確率過程のことである。マルコフ過程は1ステップ前の過程に依存するだけである。この過程には過去の記憶はないし、過去の履歴に依存する要素はない。 PageRank は単純マルコフ過程の時間的定常状態で求められるとして計算されたものである。だが、すべからく人間の知的行動は非マルコフ過程によって表現される。複雑な過程は何らかの形で過去を引きずっているものである。したがって、単にどのページからたどりついたかというだけでなく、どういう経路をたどってそのページにたどりついたかを分析すれば、より有用なランキングシステムになる可能性があると考えられる。計算量の爆発をおさえこめる範囲で、非マルコフ過程の考え方を取り入れることを検討してみるのもおもしろいかもしれない。

いろいろ考えては見た中には、実装するのはそれほど難しくないものもあるし、言ってみただけでどうやったら実装できるかよくわからないものもあるものの、いずれにしても、その効果を定量的に評価するのは極めて難しい。なんとかできないものだろうか。

PageRank 技術はどれほどのものか

評判の高い PageRank 技術にしても、基本的なアイデアとしては枯れた数値解析的手法を用いるだけで実現されていることがわかるだろう。だが、私がここで説明したような事柄は、専門の研究者から見ればまったく自明の、毒にも薬にもならない程度のことでしかないのである。規模の点を克服するだけで一つの専門的な研究分野ができるだろう。それくらい、専門分野の奥は深く果てしないと考えた方が良い。実際、私のやったことは、たかだか「ごくごく小規模な問題であれば、教科書的な手法であってもそこそこの計算量で満足できる結果を得られるようだ」ということを示したに過ぎない。

それにも関わらず、たかだか概要の上っ面を撫でただけで口先だけで「なんだ基本的にはそんな程度の技術か」などと知ったかぶって言う人が一部にいるようだが、そのような浅薄な見方は 根本的にまったく間違っていることをここで改めて強調しておきたい。

むろん、PageRank 手法のすばらしい点は、「多くの良質なページからリンクされているページはやはり良質なページである」という、わかってしまえば簡単なアイデアを出したことにある。だがさらに言えば、本当にすばらしい点は、単に考えついただけでなくて、アイデアを定常状態遷移の確率分布で定式化し、その有効性を実証するために実際にインプリメントし、現実のフィールドでもうまく動作することを実地に証明したことにある。この全ての段階において成功をおさめたことこそが、真に称賛されてしかるべきものなのである。

たしかに、斬新かつ巧妙なアイデアさえあれば、あとは教科書的な手法を組み合わせるだけであっても、Google に匹敵する(あるいは凌駕する) サーチエンジンを作れる可能性はある。現に Google 自身が身をもって示しているとも言える。だが、それを実際に出来る人は驚くほど少ない。仮想モデルで「できるはずだ」ということと、動くものを示して「ほらどうだ」ということの間には、天と地ほどの差があるのである。実際問題としても大規模疎行列を扱うこと自体、通常の手法では相当困難であり高度な専門技術を要することである。頭の中でなんとなく理解できることとそれを実現できることとの間には、絶対に埋めることの出来ない格差があることを銘記すべきだ。あまり軽々しく考えてはいけない。

前へ | 次へ

7. 参考文献

「はじめに」で挙げた基本論文以外の関連論文を以下に挙げる。

S. Brin, L. Page, 'The Anatomy of a Large-Scale Hypertextual Web Search Engine', http://www-db.stanford.edu/~backrub/google.html
山名早人, 近藤秀和, 「解説：サーチエンジンGoogle」 (概要), 情報処理42巻8号(2001年8月), pp.775-780 (PDF)
原田昌紀, 「道しるべ：WWWサーチエンジンの作り方」 (概要), 情報処理41巻11号(2000年11月), pp.1280-1283
原田昌紀, 「サーチエンジンにおける検索結果のランキング」, bit 2000年8月号(Vol.32), pp.8-14
米クレバープロジェクト, 「ハイパーリンクを賢く使う」 (概要), 日経サイエンス 1999年9月号, pp.28-35
Dell Zhang, Yisheng Dong, 'An Efficient Algorithm to Rank Web Resources', http://www9.org/w9cdrom/251/251.html
Jon M. Kleinberg, 'Authoritative sources in a hyperlinked environment', Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, 1998. http://www.cs.cornell.edu/home/kleinber/auth.ps
IBM Almaden Research Center, 'CLEVER Searching', http://www.almaden.ibm.com/cs/k53/clever.html

参考にした数学関連の書籍一覧を以下に挙げる。

S. カーリン著, 佐藤健一, 佐藤由身子訳, 『確率過程講義』 (数理解析とその周辺3), 1974年, 産業図書
岩堀信子著, 『グラフと確率過程』 (数理解析とその周辺4), 1974年, 産業図書
伊藤昇他著, 『経済系・工学系のための行列とその応用』, 1987年, 紀伊国屋書店, ISBN4-314-00477-0
L. V. アトキンソン, P. J. ハーリ, J. D. ハドソン共著, 神谷紀生, 大野信忠, 佐脇豊, 北栄輔共訳, 『数値計算とその応用 - FORTRAN77 -』, 1993年、サイエンス社、ISBN4-7819-0690-7
宮沢政清著, 『確率と確率過程』(現代数学ゼミナール17), 1993年, 近代科学社, ISBN4-7649-1034-9
伊理正夫著, 『線形代数II』(岩波講座応用数学11), 1994年, 岩波書店, ISBN4-00-010521-3
韓太舜, 小林欣吾著, 『情報と符号化の数理』(岩波講座応用数学13), 1994年, 岩波書店, ISBN4-00-010523-X
小国力著, 『MATLABと利用の実際－現代の応用数学とCG －』 (Information & Computing=86), 1995年, サイエンス社, ISBN4-7819-0763-6
長谷川里美, 長谷川秀彦, 藤野清次訳, 『反復法 Templates』 (応用数値計算ライブラリ), 1996年, 朝倉書店, ISBN4-254-11401-X
小谷眞一著, 『測度と確率2』(岩波講座現代数学の基礎10), 1997年, 岩波書店, ISBN4-00-010640-6
藤野清次著, 『数値計算の基礎 - 数値解法を中心に』 (ライブラリ新情報工学の基礎9), 1998年、サイエンス社、ISBN4-7819-0861-6

Google に関するオンラインニュース記事一覧(日本語記事のみ)は別ページ(googlenews.html) として分離しました。(2003/5/20)

その他に、特に関連するとおもわれるwebページをいくつか挙げる。

本家インタビュー：Googleに訊け！(Slashdot)
Interview with Google's Sergey Brin(翻訳記事)(LinuxGazette)
how do I 成功するビジネスプランとは - Google(インテル株式会社)
Webサーチエンジンのビジネスモデルと検索技術動向－Googleを例にとって－(JCOTレポート)
インターネット検索裏マニュアル2(ZDNN/PCJapan2001年10月号)
インターネット検索裏マニュアル(ZDNN/PCJapan2001年3月号)
【ミニQ&A】最近流行りのGoogleって、gooなどと違うの？(PC-Gaz/日経モバイル)
賢く使い分けよう！　21世紀の検索エンジン(InternetWatch)
ウェブは世界中どこまでも繋がりあっているというわけではない――という研究結果が発表され、様々に報じられた(内田明氏)
Webの「地図」の研究成果が公表。10％はリンクされていない(InternetWatch)
Webの分離度合いは19クリック分？(ZDNN)
サイバースペースの「地図」と「カタチ」(Take IT Easy, 白井康之氏)
サイトの研究結果「検索エンジンは片寄っている」(HotWired Japan)
検索エンジンの検索結果は不平等(HotWired Japan)
Google -- 時よとまれ、お前は美しい --(yomoyomo 氏)
Google Weblog (Japanese Version)
The Future of Search Engines(The Standard)
Patent Death Pending(the cluetrain weblog)
Google's PageRank: Calculator(Web Workshop)

掲載Thanks!。他にも多数の個人サイトや掲示板その他で紹介されたようです。

ZDNet China 如何提高网站在Google中的排名(2003/1/6記事) さらに中国語です。読めません... :-)
ZDNet China 如何評价一个网站的人气(2002/8/5記事) なんと中国語です。読めません... :-)
日経BP/WebGuide 「Google」の検索技術を探る／第一回：Googleを支える「PageRank」(コラム 2001/08/29)
日経BizTech/eBusiness グーグルはいつEXITできるのか/今日のコラム2001年4月23日号
中村正三郎「BRAVO! Linux」Linux Japan 2001年5月号
InternetWatch ウォッチャーが選ぶ今日のサイト 2001年3月16日号
日経ネットブレーン注目サイト 2001年3月2日号
InternetWatch ダイジェストニュース 2001年2月26日号
Google World > Japanese > コンピュータ > インターネット > WWW > ホームページ検索ディレクトリ
Lycos / コンピュータ・インターネット / インターネット / サイトの検索・リンク集 / 検索エンジン / ロボットサーチ / Googleディレクトリ
Yahoo! JAPAN ビジネスと経済 > 企業 > インターネットサービス > 企業間取引 (BtoB) > 検索、ナビゲーション > Googleディレクトリ

前へ | 次へ

8. おまけ：「グーグル？／ゴーグル？」

英語(米語)では、Google を「ゴーグル」と読むことはありえない。ラーメンの noodle を「ノードル」と発音したり表記する人がいないのと同じことで、敢えてカタカナで表記するなら「グーグル」としかならないはずだ。

どうでもいいが、oo という綴りを持つ英単語には以下のようなものがある。

book, bool, cook, cool, food, good, hook, look, loop, loose, mood, moon, noon, pool, roof, soon, tool, wood, zoo, ...

いずれも簡単で一般的な英単語だが、どれを取っても「ウ」ないし「ウー」の発音に聞こえるはずだ。少なくとも、多くの典型的な日本人の耳にはそう聞こえるだろう。英語(米語)では、oo の綴りは基本的に「ウ」になるのである。もちろん、goo も「グー」になる。広末涼子も中古車情報誌のTVCMで「かーといえばぐー」と言っているではないか。そもそも、水泳で使うゴーグルの綴りは goggle である。

むろん、Google が英語(米語)でないのなら話は別だ。だが、 Google の名前の由来が 10の100乗を示す英単語「googol」から来ているのだから、やはり英語風に発音するのが適当ではないだろうか。 googol の発音も「グーグル」と聞こえることは言うまでもないだろう。

あるいは、創業者の片割れの Sergey Brin は名前からわかるようにロシア出身だから、もしかしたら彼の英語の発音は訛っている可能性はないではない。しかしそこまで行くと、もはやこじつけだろう。それに、Google をロシア訛りでどのように発音するか僕は知らない。もし識者がいらっしゃるなら、ぜひお知らせ頂きたいものである。

補注(2001/4): Googleのサポートに「ゴーグルなのか、グーグルなのか？」と問い合わせた方から、ご親切にもメールを転送して頂いた。すなわち、Google は自分自身のことを「ぐーぐる」と発音しているが、しかしまあ好きなように呼んでくれて構わないよ! ということのようだ。

Date: Wed, 31 Jan 2001 16:12:01 -0800
From: "GoogleTech" <googletech@google.com>
Subject: RE: {Google#034-917} pronunciation
To: メールを転送して頂いた方(Thanks!)

We go by: "GU Gul" 

But you are welcome to say whichever you prefer!

Regards,
The Google Team

補注2(2001/10/29):Googleのページに "Google"はどのように発音しますかができましたので、どうぞ。

前へ | 目次へ