大学で参加していたミニゼミが終わりました.
日記を書きます.
学科のイベントでミニゼミというものが実施されていたので,それに参加していました.
僕が参加したのは「4.Google を実装する」というテーマのもので,おとといから今日までの3日間参加しました.
初日に研究室の方からいくつか説明を聞いた後はひたすらマシンに向かってコードを書く作業をしていました.
初日
初日はまず,Googleで採用されている(らしい)Pagerankアルゴリズムについて概要を聞き,その次に線型代数の知識を用いてアルゴリズムを実装する方法を聞いて,実際にコードを書いていきました.
今回使ったPageRankアルゴリズムは,あるWebページからリンクで他のWebページへ移る際の確率は全部等確率だと仮定し,そのうえで推移確率行列を作って,推移が無限回行われた後のベクトルを求めるというもの.
んでこれを求めたかったら実際に十分な回数だけ行列×ベクトルの乗算を実行してやればよいとのことだったので,行列とベクトルを掛け算するプログラムとかを書きました.
乗算1回あたりの計算量がO(n^2)なので,n=1000とかで十分な回数を実行すると結構時間が掛かりました.
実際のPagerankアルゴリズムでは乗算とかどうやってるんでしょうね.
んでPagerankが求められたら今度はGraphvizというソフトでWebページを可視化してみようとか言われたので可視化しました.
割といい感じのものができたのですが,画像は残念ながら保存してないので無いです.
2日目
どうも向こうが想定していたより早く進んでいるっぽく,やる事が無かったのでGraphvizでPagerankの高いほど色が濃くなるようにグラデーションしたりとかインターネットをしていました.
ゼミといっても基本的にみんな黙々と作業していて,たまに会話が発生するという感じなので眠くなって寝ていても誰も文句とか言いませんでした.自由.
午後からはWikipediaから抽出したデータ数千件を解析して,実際のWebページみたいにPagerankをつけて,キーワードで検索できるようにするといったことを始めました.
言語はC++を使っていたのですが文字列処理がめんどくさくて難儀.