PFIセミナー 2013/9/5

9/5にあったPFIセミナーで発表しました.

無向グラフの隣接行列の固有値固有ベクトルと,元の無向グラフのパラメータ(グラフの直径とかカットサイズとか)を関連付ける話です.
入門的なことと,どういう応用があるのかについて書いています.
発表は理論からの視点によるものだったので応用については軽く触れる程度でしたが,機械学習やらNLPやらをやってる人達にとってはスペクトラルクラスタリングがそこそこ有名なようで,もしかしたら順番が前後している印象を受けた方もいるかもしれません.

この話をしようと思った理由

僕は大学で理論分野を専門にしていて普段研究室等ではそういう人達に囲まれて生活しているのですが,一方で発表を聞く人は必ずしもそうでない人が多いので,自分の分野の中ではそこそこ有名だけど他の分野の人らにとってはそうでもないようなことを話せると良いかなぁと思っていました.
で,今期ちょうどこの spectral graph の輪講を研究室内でやっていたんですが,せっかくなのでそれについて話してしまおうと思って話すことにしました.
あまり常識というわけでもなくかといってマニアックすぎないのでテーマの選択としては無難だったかなぁと勝手に思っています.

発表してから思ったこと

固有値を使って何かする手法って結構あるけど,固有値がどういう特性を持っているのかって結構見えづらいのですね.固有値は定義自体そのものは簡潔なんですがそこだけからだと見えてくるものがどうしても少ない.そういう一見よく分からないものに対して,例えば不等式とかで固有値と元のグラフの関係を厳密に示せると,そこから固有値が持つ特性について大雑把な感覚を与えられる可能性がある.そうすると,なんかよく分からないと思っていたものがなんとなくちょっと分かるみたいになって便利だと思いました.

まとめ

間違い等がありましたらここのコメント欄とか @ir5 とかで教えて下さい.