uDiary

◆ リンク集： PageRank 関連

1. 野尻ボード：たざき　Google の PageRank　2009年05月03日(日)16時31分41秒
2. 野尻ボード：まきの　Google の秘密 - PageRank 徹底解説
   • (野尻ボードでは、このあと少しこの話題がつづくので、他の投稿も読むと面白いと思う。)
3. Google の秘密 - PageRank 徹底解説
4. JGeek Log: Google ページランクの計算アルゴリズム

なんで急にこんなこと思い出したかというと、 NTT データの Hadoop 報告書の中で、ページランクを Hadoop MapReduce でやってみまーす的な記述があったもんで。

ま、なんというか、あれなんですけど。（どれだろう？）

メモ

いままで、なんとなく知ってるけど、まじめに考えたことのなかった PageRank について、 そろそろちゃんと読んで理解しておきたいと思いました。

きっかけは、上であげた NTT データの報告書内に MapReduce 応用例として PageRank がとりあげられていて、かつ、その内容に誤りがあるように思えて、かつ、 自分にはどこが間違ってるのかちゃんと説明できないことを思い出したからです。

いくつか読んでみましたが、おそらく日本語で読める公開資料のなかでは、 田崎さんの数学の教科書 の解説が一番正確で過不足がないと思います。

たぶん、「ああ、これできっと数値計算できそうだな」と納得するまでのポイントは、 以下のとおり：

• ページランクのアイデア（より良いページからリンクされているページはより良いページ）が確率行列の固有値問題に帰着されるということ
• 帰着した問題を解く上での問題点
  • 現実のページ間リンクをそのまま表現した確率行列は、かならずしも既約でない（ページ間リンクを表現した有向グラフはかならずしも連結でない）
  • べき乗法でもとまるんだけど、ふつーは収束が極めて遅い
• Google のやりかた

実際には、このあと現実の数値計算上の困難は小さくないはずですが。

んで、たさきさんの本だけ読めばよさそうなのですが、 野尻ボードでのやりとりは楽しいし、（おそらく）ただしいし、理解の助けになります。 「 3. Google の秘密 - PageRank 徹底解説 」も、イメージを掴むのに役立ちます。

でも、ちゃんと本の中の証明をおっかけておきたい。

疑問： 数値計算上の困難のうち、確率行列が巨大である点については、 「でも、スパースだからいいんだよ」的なのを見かけることが多くて、「そんなもんかな」 と思ってました。……が、グーグル行列化したらスパースじゃなくなってません？

「ほとんどの要素が 0」ではなくなるけど、 「ほとんどの要素が小さい定数」だから、ほんとのスパースほどじゃないけど儲かったりするのかな。

グーグル行列化しても、行列を覚えておくために必要なメモリスペースは、 元のスパースな確率行列から（ほとんど）増えませんね。

たくさんあった０だった要素が、０じゃなくなるので、そこの掛算ははぶけなくなるだろうなぁ。

あとで考えよう*1。

メモ２

いままで「あとで読む」は、事実上「読まない」と同義でしたが、 Kindle のおかげでほんとにあとで読むことができそう。

たさきさんの数学の本を、ときどきだけど読めるのは、Kindle にいれて持ち歩いているからなんだよ！

ちなみに、熱力学と統計力学は、PDF じゃないから、おなじようにはもちあるけなくて、 めったに開けないですよ！

自炊…