Google検索エンジンにみる線型代数の応用
参考サイト
How Google Finds Your Needle in the Web's Haystack
他のページからリンクをされていればいるほど、そのページのランキングが高くなる
というもの。要はリンクを行うことが一種の投票行為となっているのだ。我々はリンクを張ることで、ネット上の人気投票に知らず知らずのうちに参加していることになる。
ただし、一つ一つのリンクが全て同じ価値を与えるのではなくて、ランキングの高いページからのリンクは、より大きな価値を与えると考える。
このような条件を数式的に、定量的に表現する。
j番目のページはリンクを張っている他のページに対して、自身の価値を均等に分配すると考える。例えば100のリンクを張っているページは、自身の価値を100等分してリンク先のページへ渡す。
このことを分配される側のから見ると次のようになる:
ここではページのPageRankを表す。は重みであり、jからiへリンクが貼られているならをページjの張っているリンク総数として
であり、jからiへリンクが無いなら0である。(自分自身から自分自身へのリンクは存在しないと考える。自分から自分への投票は出来ない!)
Nは世界に存在するwebページの総数であり、数千億とか、そういうレベルの数である。
このようなランキングの決定方法は、よくよく考えると再帰的である。実際、ページAのランキングを計算するためにはページBのランキングを知らなければならず、そのためにはページAのランキングを知らなければならない!
そこでこのように逐次的に考えるのではなく、巧妙な数学的テクニックを使おう。それは答えが既に分かっていると仮定し、それを文字で表すというものだ。
いま、全てのページのランキングが計算できたと仮定する。そしてこれをと文字で表す。するとこれらの数は、上の数式に従い、連立方程式
\begin{align}
a_{11} I(P_1) + a_{12} I(P_2) + \cdots + a_{1N} I(P_N) &=P(I_1)\\
a_{21} I(P_1) + a_{22} I(P_2) + \cdots + a_{2N} I(P_N) &= P(I_2)\\
&\cdots\\
a_{N1} I(P_1) + a_{N2} I(P_2) + \cdots + a_{NN} I(P_N) &= P(I_N)
\end{align}
を満たす。
ところで連立方程式を解くための洗練された手法として、線型代数が使える。行列Aを
\begin{bmatrix}
a_{11} & \cdots & a_{1N}\\
\vdots & & \vdots \\
a_{N1} & \cdots & a_{NN}
\end{bmatrix}
と定義して、ベクトルvを
\begin{bmatrix}
v_1\\
\vdots\\
v_N
\end{bmatrix}
で定義すれば、元の連立方程式は
と表せる。行列Aを乗じても変化しないことが、その再帰性を表現している。また、この式はベクトルvが行列Aの固有値1の固有ベクトルであることを意味している。従って、次のことが分かった
ページのランクを求めたければ、行列Aの固有値1の固有ベクトルを求めればよい。
問題はこの行列がN x Nというとんでもない大きさの行列であることである。