なぜ線形代数を学ぶ? Googleのページランクに使われている固有値・固有ベクトルの考え方

どうも、木村(@kimu3_slime)です。

大学1年で教えられることの多い教養数学では、線形代数学を学びます。

行列計算を教えられることが多いですが、なぜそもそも行列の理論を考えるのか。

今回は、Googleのページランクの考え方に、線形代数学の考え方、特に固有値・固有ベクトルが使われていることを簡単に紹介します。

 

ページランクとは

現在でこそ「検索エンジンと言えばGoogle」「ググる=Google検索する」が定着していますが、1990-2000年代はさまざまな検索エンジンがありました。

つまり、Googleは検索精度において、他の検索エンジンよりすぐれていたから、現在ここまでの評価を得ているわけです。どうすぐれていたのか。

検索エンジンは、ウェブサイトを巡回(クロール)して情報を集め、検索する「キーワード(クエリ)」に答えてくれそうな結果を返すものです。

簡単な検索エンジンでは、「ページにキーワードがどれだけ登場するか」(など)の情報で測っていました。これだとあまり関連のないページも検索結果に出てきますし、また意図的にキーワードを入れ込むスパムも通用してしまいます。

 

この状況を一変させたのが、Googleのページランクという考え方です。

Googleの検索結果は、ランキング方式で表示されていますよね。あのランキングの順序をつけるために、ページの重要度・関連度を数値化するわけです。

ページランクの考え方では、ページ同士の「リンク」に注目します。「他ページからリンクがある=言及されている=価値がある」と推測できるわけです。

ポイントは、リンク数が多ければ多いほど高くなる。さらに、雑多なページからのリンクよりも、「良いページ」からのリンクの方がより価値があると考えられるので、それに応じてポイントを加算する。こうしたルールで考えます。

ページランクの考え方は、Google創業者のラリー・ペイジとセルゲイ・ブリンによって、1998年に発明されました。ふたりとも大学時代の専門は計算機科学でした。線形代数学を学ぶことは、Googleのような世界的な企業を立ち上げることに役立つかもしれません。

ページランクのみで検索結果を表示しているわけではありませんが、現在でもその評価基準は内部で使われています。

参考:Google’s Gary Illyes: Yes, PageRank Still Matters – search engine roundtable

 

ページランクを計算してみよう

簡単な例で、ページランク(的なもの)を計算してみましょう

次の画像のように5つのウェブページがあって、その間にいくつかのリンクがあるとします。

\(i\)でページの番号を表すことにします。

ページ\(i\)へのリンクよって与えられるポイント\(p_i\)を、次のように定義しましょう。

\[p_i = \sum_{j = iへのリンクがある番号} \frac{p_j}{ページjが出しているリンク数}\]

\(\sum\)は、\(j\)が満たす条件すべてにわたって、右側の数値を足し合わせることを意味しています。

例えば、\(i=1\)のときに式を書くと、ページ1は2、3、5からリンクを受けているので、

\[p_1 = \frac{p_2}{3}+\frac{p_3}{1} +\frac{p_5}{1}\]

となります。

あるページのポイントは、ざっくり言えば、リンクを受けているページのポイントの足し合わせです。このときにただ足し合わせるわけではなく、「リンクをたくさん出しているページからのポイントは(比較的)低くなる」というように重みをつけています

 

同じように\(p_2,\dots,p_5\)のポイントの定義式が書き下させます。が、合計で5本の式になるので面倒です。

そこで「行列」を使います。すると、

\[\left( \begin{array}{c} p_1 \\ p_2 \\ p_3 \\ p_4 \\ p_5 \end{array}\right) = \begin{pmatrix} 0 & \frac{1}{3} & 1 & 0 & 1 \\ \frac{1}{2} & 0 & 0 & \frac{1}{2} & 0 \\0 & \frac{1}{3} & 0 & \frac{1}{2} & 0 \\ \frac{1}{2} & 0 & 0 & 0 & 0 \\\frac{1}{3} & 0 & 0 & 0 & 0  \end{pmatrix} \left( \begin{array}{c} p_1 \\ p_2 \\ p_3 \\ p_4 \\ p_5 \end{array}\right)\]

と表せます。ポイントを\(p=(p_1,\dots,p_5)\)とベクトルでまとめて表記し、行列を\(A\)とおくと、\(p =A p\)という式になります。

線形代数学では、\(\lambda\)を数、\(A\)を行列として、\(Ap = \lambda p , p \neq 0\)という式は固有値問題と呼ばれます。そして\(\lambda\)は固有値、この式を満たす\(p\)は固有ベクトルと呼ばれます。

つまり、ページランクを求める問題は、ページランクの行列について、固有値1に対応する固有ベクトル\(p\)を求める問題ということができるのです。

 

 

実際にさきほどの行列で\(p =A p\)を解くと、固有ベクトル(のひとつ)は\(p_1=1,p_2=\frac{3}{4},p_3=p_4=\frac{1}{2},p_5=\frac{1}{4}\)となります。

つまり、\(p_1 >p_2>p_3=p_4>p_5\)となっていて、ページに順位をつけることができましたね。

ページ1がリンクが集まっているので重要そうなのはわかります。

ページ4と5を比べると、ページランク「らしい」です。どちらも1本のリンクを受けていますが、4は重要な1からのリンクを受けています。これが実際に\(p_4>p_5\)と、リンクの「質」があらわれているわけですね。

 

参考:線形代数とGooglePageRank – 科目「線形代数」補足資料PageRankについて調べてみた – seri::diary

 

実際の行列のサイズは1兆超え?

さて、さきほどの例ではサイトが5つありました。いえ、5つしかありませんでした。

現実はGoogleは世界中のあらゆるサイトをクロールしています。サイトが増えれば増えるほど、行列\(A\)のサイズは増えて、計算が大変になるでしょう。

Googleは、2008年の時点でウェブページの総数は1兆(1,000,000,000,000)を超えたと報告しています。

参考:We knew the web was big… – Google Official Blog

internet live stats」というサイトによると、2018年時点では19兆のサイトが存在します。

画像引用:internet live stats

このような膨大な成分を持つ計算にも、線形代数の考え方は通用します。

すべての成分が正の行列では、固有値問題が(実数として)解けるということは、ペロン=フロベニウスの定理によって保証されています。また、固有値問題をコンピュータで解くときには、べき乗法という手法が使われます。また、実際のGoogleのページランクでは、確率論の考え方(マルコフ連鎖)も用いられています。

参考:インターネットを支える数学 – 九州大学PageRankアルゴリズムおよびそれに関連する研究について – 京都大学 総合人間学部 認知情報学系 数理情報論分野 宮嶋健人

 

ネットを使う人で、Google検索にお世話にならない人はいないでしょう。

ということは、同時に線形代数(や他のさまざまな数学・計算機科学)にもお世話になっている……ということが感じられたでしょうか。

線形代数の行列の理論は抽象的に感じられるかもしれませんが、Googleのページランクに使われていることを思い出せば、より現実味を感じられるのではないでしょうか。

木村すらいむ(@kimu3_slime)でした。ではでは。

 

Google PageRankの数理 ―最強検索エンジンのランキング手法を求めて―
Amy N.Langville Carl D.Meyer
共立出版
売り上げランキング: 272,186

 

線型代数入門 (基礎数学1)
齋藤 正彦
東京大学出版会
売り上げランキング: 23,207

 

行列の固有値―最新の解法と応用
F.シャトラン
丸善出版
売り上げランキング: 735,592

 

こちらもおすすめ

なぜ線形代数を学ぶ? 経済波及効果の分析を例に

なぜ教養数学として微積分学と線形代数学を学ぶのか ブルバキが現代数学に与えた影響

線形微分方程式の解の安定性は「固有値」を調べればわかる