Search on the blog

2011年8月21日日曜日

固有値・固有ベクトルって何に使うの?

 ふと、固有値・固有ベクトルって何がそんなに嬉しいのか?何の役に立つのか?と思っていろいろ調べていた。(対角化してべき乗計算が速くできますだけだと、ちょっと勉強する動機づけとしては弱い。。)そういえば、一年前くらいに読んだpage rankの論文に固有値・固有ベクトルが使われていたのを思い出したので、これをちょこっと紹介。(解釈に間違いなどありましたら、ご指摘ください。)

 まず、page rankアルゴリズムについて。これは、いわずと知れたgoogleの検索処理において中心的な役割を果たす処理です。page rankの基本的な考え方は、”たくさんリンクを張られているサイトほど重要なサイトである”ということです。つまり、たくさんリンクを張られているサイトが検索で上位に現れます。加えて、同じリンクを張られているでも、重要なページ/人気のあるページからリンクを張られているのか、重要でない/人気でないページからリンクを張られているのかを区別しています。(例えば、あなたのページがクラスメイトの太郎くんからリンクをはられているのと、yahooのカテゴリページからリンクされているのでは意味が違いますよね?)

ここまで、まとめると、
  1. リンクをたくさん張られているサイトほど重要とみなす
  2. 重要なサイトからのリンクほど、大きな重みを付ける
となります。

あるサイトの重要度を上記の定義にしたがって、定式化してみます。(※本当は、リンク元のページから受け取る重要度をそのページのリンク総数で割るという処理がありますが、簡単のため省略しています。)



xは、あなたのページの重要度、xi, i= 1,..,nはそれぞれウェブページiの重要度です。(ウェブページは全部でn個あるとしています。)Ai, i = 1,.., nは、0 or 1の値です。もし、ウェブページiからあなたのページにリンクがあれば1、なければ0です。cは定数で、常に全体のウェブページの重要度の総和が一定となるように正規化しています。

 上の式から分かるように、あなたのページの重要度は、他のページの重要度がわかっていないと計算できません。逆に、他のページの重要度も、あなたのページの重要度の影響を受けています。ということで、連立方程式をたてて、すべてのページに適切な重要度を割り当てます。
連立方程式は、ベクトルx、グラフの隣接行列Aを用いて以下のように書くことができます。隣接行列は先に説明したのと同様のリンクの接続情報です。以下の方程式を解いてx(すべてのウェブページの重要度)を求めることが目標です。



両辺を定数cで割って、左辺と右辺を入れ替えると見慣れた形が現れます。



そうです、xは隣接行列Aの固有ベクトルになっています。実は、私たちが毎日お世話になっているGoogle検索に固有値/固有ベクトルが使われていたのですね。

何のために固有値とか勉強するんだろ?と疑問に思っている高校生/大学生の人や、固有値・固有ベクトルの有効性を生徒さんに簡単に話したい先生方の参考になれば本望です。

このページでは、実際のpagerankを簡素化して説明しました。実際の処理をもっときちんと知りたいという方は、ラリーページとセルゲイブリンがスタンフォード時代に書いた論文をご参照ください。

2 件のコメント:

  1. はじめまして。

    情報科学の方面ではこのように固有値や固有ベクトルを使うのですね。
    地震学・気象学・物理学でも実際に使うところを知っていましたが、情報科学については初めて知りました。ありがとうございます。

    返信削除
  2. >Tatuyanさん
    地震学、気象学でも固有値が使われるというのは、興味深いですね。今度調べてみます。ありがとうございます。

    返信削除