奈良に移ってきました

4月1日から奈良に引っ越してきました。いよいよ念願のNAISTです。これから二年間、成長できるように頑張っていきます。

しかし生駒は本当に坂が多い！まさに山。山の多い群馬から来た僕でさえもこんな急勾配なところでやっていけるのか不安になってしまいます。原付の免許を取ろうか考えてしまいますが、事故が怖いのでふんぎりがつきません。チキンですねー

希望のM本研究室は希望者が尋常じゃないくらい多いので、第一希望で希望調査書を提出しても通らないかもしれません。とはいえ第二第三希望の研究室も人気のようで、結局どうなることやら予想がつきません。NAISTまではるばるきておいてM本研に入れなかったら「なんてこっちゃ」って感じですが、まあなるようになると思うので楽しみです。

またTwitter上で知っていた方々と実際にお会いすることができるのはとても面白いものです。自分がイメージしていた通りの人は一人もいなくて、やっぱりTwitterで知ることができるその人の一面はごく限られたものなのかな、とも思いました。

あと、高専生が異様に多いのは驚きでした！自己紹介をするたびに「お、高専ですか！ｗ」となるので楽しかったです。マイノリティ同士、親近感を感じてしまうんでしょうね。しかしここまで多いとすごいな。

初めての一人暮らしなので、当面は自炊ができるように頑張ります。勉強も研究も、まわりの人たちから刺激を受けながら精進していけたらいいと思います。

DEIM2011で発表してきます

2月27日から3月1日まで伊豆で開催されるDEIM2011で発表してきます。
http://db-event.jpn.org/deim2011/

なかば実名を公開するようなものですが、もし興味がある方はプログラムで「高専」を検索にかけてください。発表する高専生は二人で、ソーシャルネットワークのセッションで発表するのが私です。

学会で発表するのは初めてなので、とても緊張しています。。。発表する前から冷や汗が出てしまいます。

Eamonn Keogh　のチュートリアル

Eamonn Keogh のKDD 2009のチュートリアル"How to do good research, get it published in SIGKDD and get it cited!"を読んでみた。
これは表題のとおり、良い研究はいかにして行われるか、そしてどのような論文がKDDで採択されるかを解説したチュートリアルである。著者自身、部分時系列クラスタリングにおいて、K-means法のクラスタ中心が入力時系列にほぼ無関係に正弦波パターンとなることを実験的に示し、当該分野における従来の研究成果を大きく覆した著名な研究者である（これについて詳しく知りたい方はIBMの井手剛さんの「部分時系列クラスタリングの理論的基礎」という論文を参照のこと）。

このチュートリアルを読んで自分が衝撃を受けたのは、ある国際会議のベストペーパーを引用している多くの論文で、そのベストペーパーの誤った記述を何の検証もなしにそのまま引用し、提案する手法の仮定として採用してしまったという事例であった。

他にも色々な具体例を挙げてあり、これから自分が研究をしていくうえで既存の研究を自分の手で再実験することの重要性を感じた。

以下の論文は著者が挙げている参考文献である。時間ができたら読もうと思っている。

Voodoo Correlations in Social Neuroscience. Vul, E, Harris, C, Winkielman, P & Pashler, H.. Perspectives on Psychological Science.

Why most Published Research Findings are False. J.P. Ioannidis. PLoS Med 2 (2005), p. e124.

Publication Bias: The “File-Drawer Problem” in Scientific Inference. Scargle, J. D. (2000), Journal for Scientific Exploration 14 (1): 91–106

Classifier Technology and the Illusion of Progress. Hand, D. J. Statistical Science 2006, Vol. 21, No. 1, 1-15

Everything you know about Dynamic Time Warping is Wrong. Ratanamahatana, C. A. and Keogh. E. (2004). TDM 04

Magical thinking in data mining: lessons from CoIL challenge 2000 Charles Elkan

How Many Scientists Fabricate and Falsify Research? A Systematic Review andMeta-Analysis of Survey Data. Fanelli D, 2009 PLoS ONE4(5)

スペクトラルクラスタリングの基本的な解説、および高速化手法のざっくりとした説明

久しぶりにブログを更新してみる。

以前スペクトラルクラスタリングについて記事を書いたが、そのときはだいぶ勉強不足で、少し見当違いのことを書いていた気がする。

スペクトラルクラスタリングは、本質的にはラプラシアン固有マップ法と同じことをしている。ラプラシアン固有マップ法は次元削減の手法で、もともとの高次元空間におけるデータ間の類似度が、低次元に写像した後にも反映されるように設計されている。それが結果的に類似度行列から定義されるグラフ・ラプラシアンの固有値問題に帰着されるのだ。具体的には、グラフ・ラプラシアンLの固有値を大きいほう（定式化によっては小さいほう）からk番目までをλ1, λ2, …,λk, それに対応する固有ベクトルをv1, v2, …, vk とすると、その固有ベクトルを列として並べた行列 V = (v1 v2 … vk)の各行が、各データ点の低次元空間における座標とする。このときkは、低次元空間の次元となる。

スペクトラルクラスタリングはこのデータの低次元表現に対して、k-meansなどのクラスタリングアルゴリズムを適用することによってクラスタ結果を得る。では最初からk-meansを高次元空間のデータに対して適用すればよさそうなものであるが、実はk-meansにはよく知られているように弱点がある。それは1.局所解に陥る可能性があること、2.線形分離不能なデータに対しては適切なクラスタリングができないこと、等である。スペクトラルクラスタリングの場合、k個のクラスタをつくる場合は、まずラプラシアン固有マップ法によってk次元の低次元空間へ写像する。この低次元空間において、データが線形分離になっているのがスペクトラルクラスタリングのうまいところで、これに対してk-meansを実行すれば、もともとのデータ空間においては線形分離不能でクラスタリングができなかったのに、適切にクラスタリングができるのだ。また、スペクトラルクラスタリングは正規化カットと呼ばれるコスト関数を最小化する最適化問題であり、大域解を得ることができることが理論的に保証されている。

このように、スペクトラルクラスタリングはいいことづくめのように思えるが、計算量が大きい（データ数の三乗のオーダー）といった弱点もある。最近は高速化アルゴリズムも研究されており、例えば

Fast approximate spectral clustering.
D. Yan, L. Huang, and M. I. Jordan. 15th ACM Conference on Knowledge Discovery and Data Mining (SIGKDD), Paris, France, 2009.

がある。これは、まず先に前処理としてデータに対してk-meansを実行し（クラスタ数はおおきめに）、ベクトル量子化を行う。ベクトル量子化を元のデータに対する摂動と解釈して、前処理なしのスペクトラルクラスタリングと前処理ありのスペクトラルクラスタリングの差、つまり誤分類の大きさを理論的に評価する。この誤分類の大きさをmis-clustering rateと呼んでおり、これを前処理のクラスタ数kの関数とみなす。これによって、許容できる誤分類率の範囲内でベクトル量子化が可能になる。もともとのデータ数をN,前処理におけるクラスタ数をKとすると、計算量はO（N^3）からO（K^3）に減る事になり、高速化が可能となる。

スペクトラルクラスタリングが正規化カットの最小化が帰着されることの厳密な数学的な証明は、

Learning spectral clustering.
F. R. Bach and M. I. Jordan. In S. Thrun, L. Saul, and B. Schoelkopf (Eds.), Advances in Neural Information Processing Systems (NIPS) 16, (long version), 2004.

にある。これにはまた、スペクトラルクラスタリングを教師あり学習にする方法も書いてある。
これらは両方ともMichael Jordan が共著者として入っているので、彼のページhttp://www.cs.berkeley.edu/~jordan/publications.html
から論文を読むことができる。

余談ながら、私はまだ機械学習のことを学び始めてから幾ばくもたっていないのでよくわからないのだが、このMichael Jordanはおそらく大御所なのだろう…。いろいろなところで名前が目に付く。いつかこういうようにオールラウンダーに活躍できるような研究者になりたい。

焼け石と焼き芋

焼け石は「焼く」の活用が「け」なのに焼き芋は何で「き」なんだろう。

活用が「け」のものは他には「焼け野原」「焼け跡」「焼け太り」など。
逆に「き」のものは「焼き饅頭」「焼き討ち」「焼き菓子」「焼き印」など。

直感的な印象では「焼け○○」は○○が受動的に焼かれていて、「焼き○○」は○○を能動的に焼いているという感じがする。