【Google】PageRankの計算の仕方
■ このスレッドは過去ログ倉庫に格納されています
0001１３２人目の素数さん
NGNGここにGoogleで使われているPageRankのアルゴリズムが
書かれています。
そこで、一億×一億の正方行列を作り計算しようと思いましたが
PCのメモリ２GではOctaveを使って計算するにも
メモリ上にも載せれません。
別の公式かなにかはないのでしょうか？
0002１３２人目の素数さん
NGNG0003１３２人目の素数さん
NGNG0004１３２人目の素数さん
NGNG∧_∧ ／￣￣￣￣￣
(ω・ )ゝ ＜ なんだって？
. ノ/ / ＼＿＿＿＿＿
ノ￣ゝ
0005１３２人目の素数さん
NGNG0006１３２人目の素数さん
NGNG0007１３２人目の素数さん
NGNG0008１３２人目の素数さん
NGNG0009１３２人目の素数さん
NGNGリーグ戦で
Ａ Ｂ Ｃ Ｄ
Ａ ＼○○×
Ｂ ×＼○○
Ｃ ××＼○
Ｄ ○××＼
っつう結果だったら、
1 2 2 0
0 1 2 2
0 0 1 2
2 0 0 1ていう行列の固有ベクトルを求めて、すべての成分が皮膚の物を探すと、
{0.62563, 0.551628, 0.321336, 0.448372}
てのがあるから、Ａ〜Ｄの実力の比率はこんなもんだろうと分かる。
0010１３２人目の素数さん
NGNG友達が卒論で、こういうスポーツのリーグ戦などの最終的な順位付けについて
グラフ構造にもっていって順位付けの方法を公理化するなんてことをやっていて、
勝ち2, 引き分け1, 負け0のときの公理だかなんだかを
卒論提出の二週間前にやりはじめて、最終的に4つぐらいの公理におさまったらしいのだが、
証明などが膨大な量になってしまって、指導教官がチェックを投げ出してしまった。
引き分けがない状態では、勝ち数のみで順位を決定する方式が
非常にシンプルな公理で表されているみたいです。
0011１３２人目の素数さん
NGNGそこを考えてほしいなりけり
0012１３２人目の素数さん
NGNGGoogleは、PCサーバーでこれを実現しているよね。
googleだと０と１だからどうなの？
公理キボンヌ
0013１３２人目の素数さん
NGNG0014１３２人目の素数さん
NGNG引き分けがない状態での公理は、
Ranking the Participants in a Tournament,
Journal of the Society of Industrial and Applied Mathematics 38 (1980), 108-111.
に書いてあるんだけど、論文捨てちゃった(作者は経済の人みたい)。
覚えているのは、「公理I: Anonimity」だけ・・・
0015１３２人目の素数さん
NGNG"Google での実際の PageRank 計算に要する時間は、7500万のURLに対して約5時間だったそうである。
(2001年2月現在でどうなっているかは不明)。
このことからすると、
より効率的な加速法を検討する余地が十分に残されていることは言えるだろう。 "
らしいから、何か方法があるのかな？
２ちゃねらーで導けば、すごいよね 笑
0016１３２人目の素数さん
NGNGこれは 関係ないよね 笑
0017１３２人目の素数さん
NGNG2月7日のWeb記事に"Understanding and Building Google PageRank"という英文の解説記事があります。
ページランクはInternal Linking と External Linking を使っているとのことです。私が十数年前に
リファレーション（Referations = References + Document + Citations）を使った文献検索技術を研究していましたが、
まだDocumentの部分が含んでないように思います。いろいろな測度を計算するのに、データ数が多く、しかもSparse行列を
解くのは不可能です。この難解な測度を非常に簡単なアルゴリズムで求める方法を十数年前に開発しています。
それにしてもGoogleの躍進でリンクが脚光を浴びてきたことは大変望ましい状況です。
0018１３２人目の素数さん
NGNGこれは関係ないよね？
0019１３２人目の素数さん
NGNGこれはもっと関係ないよね
0020１３２人目の素数さん
NGNGﾜﾗﾀ
0021１３２人目の素数さん
NGNG0022１３２人目の素数さん
NGNGこれ、俺わかるよ。加速方法もなんとなく予想できる。
>収束が遅いというのは、ベタな言葉で言えば、いつまで経っても計算が
>終らないということである。 対して、収束を速めるための 適当な加速法も
>いくつか存在することは存在するが、 それらを適用するためには数値計算
>技法に対する十二分な理解が必要と なるため、 数値計算の専門家でない限
>りは導入は易しいものではない。
って勉強すればいいじゃん。Googleのやつは勉強ぎらいなのか？
002322
NGNG>あまり軽々しく考えてはいけない。
スマソ。じゃあもっと深く考えてみるか。
0024１３２人目の素数さん
NGNGhttp://www.rakuten.co.jp/elblanco/img1005177827.jpeg
0025１３２人目の素数さん
NGNG002622
NGNGhttp://www.denkinomise.com/_sys/images/product/333.1.jpg
関係なかったらごめん
0027１３２人目の素数さん
NGNG悪いけどそれはびっくりするほど関係ないね
0028１３２人目の素数さん
NGNGだいたい今のPCってのはよくわからないものをオブジェクト、つまり一個の者として扱ってるんですね、
それを「2進数だよね?」とかいって考えるのが数学板の人なんだよね。
それが数それが数学板の人なんだよねれそれが数それが数学それが数学板の人なんだよね。板の人なんだよね。なんだよね。なんだよね。
0029１３２人目の素数さん
NGNGここでご披露願いたいものです。
0030１３２人目の素数さん
NGNG0031１３２人目の素数さん
NGNG調べてみると著者はAriel Rubinsteinでした。
ゲーム理論の大御所。今はテルアビブとプリンストンにいるはず。
0032１３２人目の素数さん
NGNG２ ｃ ｈ の 有 名 な ス レ に 書 き こ め ば Ｐ ａ ｇ ｅ Ｒ ａ ｎ ｋ が 上 が る
0033１３２人目の素数さん
NGNGクローラが訪問するころにはとっくに次スレ移行してそのスレはdat落ちしてますが。
人間と違ってpartXXなどのシリーズモノかどうかの判別はできない。
0034１３２人目の素数さん
NGNG近似固有値を計算したいだけだろ？ ミロ↓
http://www.rakuten.co.jp/elblanco/img1005180869.jpeg
0036１３２人目の素数さん
NGNG実際のところ1億×1億の全ての要素が埋まっているわけではなく
むしろそのほとんどが0なわけだから、そこらへんを上手く扱うと
メモリに収まるのかもしれない。
(これは1のリンク先にも書いてあるけど)
ただ数学でもシミュでも共通して言えることだが
いきなり1億なんてやらずに、ある程度閉じた環境でローカルの
ランキングとか計るとかしてみたほうがいいのではないかと思う。
1億サイトのランキングを計算する意味って何よ？ >>1
00371
NGNG当方、ただいま約一億サイトの収集を完了したので。
0038１３２人目の素数さん
NGNG仮に N が 10^4 のオーダだったとしよう。
通常は数値計算プログラムの内部では行列やベクトルは倍精度で格納されるから、
N次正方行列 A の記憶領域は
sizeof(double) * N * N = 8 * 104 * 104 = 800MB となる。
さすがに、800MB の主記憶領域はなかなか持てるものではないだろうが、
とはいえ不可能な数字と言うわけでもない。
だが、N が 10^5 や 10^6 になると、それぞれ 80GB, 8TB となる。
こうなるとメモリどころかハードディスクでももうムリである。
Google では 10億以上のページを扱っているから(2001年時点)、
まともなやり方ではまったくダメであることがわかる。
もっとも、A は疎(sparse)な行列である。
リンクを張りまくっているページが一部にあったとしても、
Web全体に張っているものはないし、
あったとしてもそれは極めてまれな存在であるからだ。
平均的には、1ページあたり10-20リンク程度ではないだろうか
(IBM Almaden 研究所による 'Graph structure in the web'によれば、
平均すると 16.1 程度だそうである)。
だから、A は適切な圧縮方法を用いて圧縮できる。
N が 10^6 であっても平均リンク数を10とすれば 80MB で済み、
規模からいって無理のない数字に納めることができる。
0039１３２人目の素数さん
NGNGそこはわかったから、それ以外の加速法を聞いているわけで
004014
NGNG先日卒研発表があって、友達の発表を聞いたら、
Rubinsteinさんの論文では
1. 匿名性
2. 正の反応性
3. 無関係対象からの独立性
を満たすランキング方法は、勝ち数でランク付けする以外ないとのことでした。
0041１３２人目の素数さん
NGNG厨房でもわかりやすくお願いします
0042１３２人目の素数さん
NGNG0043１３２人目の素数さん
NGNG0044１３２人目の素数さん
NGNG難しいみたいだね
0045１３２人目の素数さん
NGNG0046１３２人目の素数さん
NGNG0047山崎渉
NGNG0048１３２人目の素数さん
NGNG0049d ◆GJenck4cmw
NGNG0050１３２人目の素数さん
NGNG0051１３２人目の素数さん
NGNGそのときの固有値は3.79067になりましたがこれに意味はあるんでしょうか？
0052１３２人目の素数さん
NGNG0053１３２人目の素数さん
NGNG２ちゃんアカデミーとか？
0054１３２人目の素数さん
NGNG0055山崎渉
NGNG0056山崎渉
NGNG（ ＾＾ ）＜ ぬるぽ（＾＾）
0057１３２人目の素数さん
NGNGの語源なの？
0058動画直リン
NGNG0059１３２人目の素数さん
NGNGGoogleだと17%はリンクさしてないサイトに等分にして配分。
83%をリンクしているサイトに配分するので。
1億ページ中のリンク構造モデルを用意しておいて。
1億ページ分のページランク領域を2つだけ確保すれば良いのです。
計算量も、くそマジメに計算するよりかなり減るです。
ちなみに自前検索エンジンで、キーワードに引っかかったサイト一覧の中の
リンク構造を元にページランクを動的に計算しているのですが、ページランクを
計算することによる負荷は殆ど発生してないです。
0060１３２人目の素数さん
NGNG0061山崎渉
NGNG0062山崎渉
NGNG0063山崎渉
NGNGﾋﾟｭ.ｰ ( ＾＾ ） ＜これからも僕を応援して下さいね（＾＾）。
＝〔~∪￣￣〕
＝ ◎――◎ 山崎渉
0064１３２人目の素数さん
NGNG0065１３２人目の素数さん
NGNG「PageRank をマルコフ過程の用語で言い直すならば、
PageRank は、ランダムにリンクをたどって動くユーザが一定の時間のうちに
それぞれのページを訪問する定常分布であるとも言える。」
ちゅうことなんで、モンテカルロ法じゃだめ?
かえって時間かかるかなあ?
0066１３２人目の素数さん
NGNG0067１３２人目の素数さん
NGNG0068ぼるじょあ ◆yBEncckFOU
NGNGﾋﾟｭ.ｰ （ ・３・） ( ＾＾ ） ＜これからも僕たちを応援して下さいね（＾＾）。
＝〔~∪￣￣￣∪￣￣〕
＝ ◎――――――◎ 山崎渉&ぼるじょあ
0069１３２人目の素数さん
NGNG0070１３２人目の素数さん
NGNG0071１３２人目の素数さん
NGNG0072１３２人目の素数さん
NGNG0073１３２人目の素数さん
NGNG0074１３２人目の素数さん
NGNG0075１３２人目の素数さん
NGNG0076１３２人目の素数さん
NGNG0077１３２人目の素数さん
NGNG0078１３２人目の素数さん
NGNG0079１３２人目の素数さん
NGNG0080１３２人目の素数さん
NGNG0081１３２人目の素数さん
NGNG0082１３２人目の素数さん
NGNG0083１３２人目の素数さん
NGNG0084１３２人目の素数さん
NGNGここみるとgoogleつくってる人たちのただもので無さが伝わってくる・・・
ぐーぐる、ぐーぐる簡単に言ってるけど実はけっこうすごいものなんだなぁと・・・
まあ、ジュリア集合の時点でちょっとそんな気してたけど・・・
0085１３２人目の素数さん
NGNGこんなの楽勝だろーが。
0086１３２人目の素数さん
NGNG0087１３２人目の素数さん
NGNG■ このスレッドは過去ログ倉庫に格納されています