« November 2008 | Main | January 2009 »

2008.12.12

最大マージンクラスタリング

ここ数日、最大マージンクラスタリング(MMC, maximum margin clustering)なるものをサーベイしていました。
自分用にもメモ

Maximum Margin Clustering, NIPS 2004
Maximum margin clustering made practical, ICML 2007
Efficient Maximum Margin Clustering via Cutting Plane Algorithm, SDM 2008
Efficient multiclass maximum margin clustering, ICML 2008

MMCは従来のSVM、Multi-class SVMと全く同じ定式化で次の二点だけが違います

(1) 重み(dualの場合は各例に付くalpha)に加えクラス割り当ても含めて最適化問題を解く。
(2) (1)の自明な解である、「全部同じクラスになって、重みが0になる」のを防ぐため、クラスに属する例の数が大きすぎない、少なすぎないようにとの制約が入る

違うクラス間のマージンを最大化しつつ、各データのクラスも決定します。アイディア自体は非常に素直で(2)の制約だけでそんなにうまくいくのかと思うがうまくいくらしい

最初の論文では、クラス割り当て部分の整数計画問題はとけんということで、連続値の最適化問題に緩和して(それでもSDP)解く方法。

次の論文で、やっぱりSDPは計算量がやばいということで、緩和せず直接解いて、クラスの割り当てと、重みの最適化を交互にするという方法にして、さらにSVMのhinge-lossをそのまま使っているとクラスの再割り当てがされにくいということで、laplace-loss(境界から離れていたら損失)を使うという方法

でその後の二つが、クラス割り当ての部分を全部制約として表現して、で制約を一番効いているやつから順番に入れていくcutting-plane algorithm(最近これもはやってますね)で、効いている一部の制約情報だけを使って最適化をしていくものになっています。一番最後のは多クラスに拡張。式がややこしいが、制約は、今の重みで一番マージンが大きいクラスを正解にしようということに対応しています。

MMCは精度がとてもいいというのと(例えば手書き数字の画像認識とかだとほぼ100%の精度で分類できる)、最後の方になるとk-means並に速いということ、そして研究ネタは従来のSVMやLogistic回帰とかで培われてきたいろんな技術がそのまま応用できるということで、もっと使われるのかなぁと思います。もう一段階ぐらい簡単にしたいところだけれど。

| | Comments (14) | TrackBack (0)

2008.12.05

カーネル多変量解析

タイトルの本を買って読んでみた.

カーネル多変量解析―非線形データ解析の新しい展開 (シリーズ確率と情報の科学)
サポートページ

様々な解説記事で定評のある赤穂先生によるカーネル法による解析についての本。日本語で読めるカーネルに関する本としては、導入部の丁寧さと、そのあとの展開と深さ、最新の話まで抑えている点でお勧めだと思います。カーネルの性質、汎化性能とかはもちろんのこと、例えばカーネルk-means, スぺクトラルクラスタリング、(ちょっとだけ)Gaussian Process, Leave-one-outの閉じた式、L1正則化など、他の和書ではあまり見たことない内容が多く、中身が濃いです。ただ、これらは、どれもさーっとかいて気持ちがわかって、詳しくは参考文献を見るという感じです。まぁ、それだけ詰め込んでいるから仕方ないですね。

--

カーネル法とは、なんらかの対象を解析するときに、対象二つa, bを引数としてとるカーネル関数 K(a, b)を通して解析する方法です。直観的にはK(a,b)はaとbの近さのようなもので、例えばaとbが似ていれば大きな値をとるように関数を決めます(厳密にはKが半正定値性を満たすように)。

カーネル法のすごいところは、このK(a,b)さえ定義できれば対象が何であっても解析できて、たとえば対象がベクトルとかの場合は内積(とそれを凸関数にいれたもの)をKとして使うのが一般的ですが、文字列や木、グラフ、といった一見解析が難しそうな対象でさえ、カーネルさえ定義できれば同じ枠組みで解けてしまいます(人だって良い)。対象の情報はブラックボックスとしてカーネルに凝縮されて、その後はカーネルだけを通して、回帰や分類、クラスタリングなどが統一的なアルゴリズムで解くことができます。

さらに、カーネルを利用して得られる識別関数は、元々のパラメータに対しては非線形でありながら、カーネル関数に対しては線形であり、最適化が容易、過学習しにくいと、いいとこどりの形をしています。

例えば、カーネル法が有名になるきっかけとなったサポートベクターマシンでは、難しいチューニングなしに、対象に対しカーネルを定義して、サポートベクターマシンに突っこんで学習したら、手書き文字認識、文書分類、生物情報など多くの分野で従来の最高精度を大幅に超えて、90年代後半あたりに、"...using Support Vector Machine"という論文がものすごくたくさんでてました。

現在では、これもちょっと落ち着いて、ニューラルネットやパーセプトロンがまた復活してきてたり、凸でない関数でもいいじゃんとか、単純な線形モデルによる最適化、ベイジアンモデルとかが盛んに研究されていますが、(計算量を除けば)相変わらずカーネル法は安定して強く、ちゃんとおさえておく必要があるとおもいます。

| | Comments (184) | TrackBack (2)

« November 2008 | Main | January 2009 »