« カーネル多変量解析 | Main | 昨年の論文をふりかえる »

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回帰とかで培われてきたいろんな技術がそのまま応用できるということで、もっと使われるのかなぁと思います。もう一段階ぐらい簡単にしたいところだけれど。

|

« カーネル多変量解析 | Main | 昨年の論文をふりかえる »

Comments

ECML/PKDD2008 のクラスタリングの御大 Jain さんの講演でも,最近のクラスタリング手法の一つに挙げられてました.
今日からのICDM2008では,半教師ありクラスタリングにまで手がついてます.
http://icdm08.isti.cnr.it/Paper-Submissions/32/accepted-papers

まだ,1本だけ関連文献を読んで,オリジナルはまだ手を付けていませんが,直感的に密度の低いところで切るので,そういうデータには強そうですね.
私は,やはりSVMの親戚なので,基本は N^2 の計算量は避けられないという認識です.最適化テクのオンパレードになっていて,N に比例する感じになっているけど,気がつけば大きな定数項という気がするのですが……

Posted by: しましま | 2008.12.16 01:57 AM

私の経験としては、一番制約のきついやつから順に制約を順に加えていくcutting plane系の技術は実用的にも有効な場合が多く、実際に(精度を犠牲にすれば)線形時間は達成できるものが多いと思います。

最悪時間はO(N^2)はさけられないかもしれませんが実際の世の中のデータは簡単な場合が多く、そういうのだと、きついから入れていくのがヒューリスティックス的にもうまくいくし、あと適当なところで最適化をやめてもそこそこの精度がでるところがいいところだとおもいます。

L1正則化でもほぼ同じ概念でgraftingというのがあって尤度の勾配が一番きついやつからいれていって他は0固定とするのですが、これも特徴種類数が億とかのオーダーでも高速に学習することができます。

Posted by: oka | 2008.12.16 02:58 PM

We're a bunch of volunteers and opening a brand new scheme in our community. Your website offered us with valuable information to work on. You have performed a formidable task and our entire group might be thankful to you.

Posted by: tankless water heater | 2013.09.22 03:56 PM

My brother suggested I might lkke this website. He was totally right. This post truly made my day. You cann't imagine simply how much time I had spent for this information! Thanks!

Posted by: bunn coffee makers | 2013.10.22 01:40 AM

Its such ass you read my mind! You seem to understand soo much about this, such as you wrfote the ebook in it or something. I feel that youu could do with a few p.c. to force the message home a little bit, but instead of that, that is magnificent blog. A great read. I'll certainly be back.

Posted by: http://www.daybedsgiant.Com | 2013.10.24 02:45 AM

Superb website you have here but I was wondering if you knew of any message boards that cover the same topics discussed here? I'd really love to be a part of community where I can get feed-back from other knowledgeable people that share the same interest. If you have any recommendations, please let me know. Bless you!

Posted by: หนังR | 2014.05.11 08:26 PM

Thanks designed for sharing such a fastidious idea, piece of writing is good, thats why i have read it completely

Posted by: cell phone repair in schaumburg | 2014.07.13 09:21 AM

My brother suggested I might like this blog. He was totally right. This post truly made my day. You can not imagine simply how much time I had spent for this info! Thanks!

Posted by: fast food in arlington heights | 2014.09.17 08:10 PM

I'm gone to tell my little brother, that he should also pay a visit this webpage on regular basis to take updated from newest news.

Posted by: en.wikipedia.org | 2014.10.16 06:48 AM

This weakness is already recognized by the development team, according to Bettencourt, and there is a build already under way to remedy it. For small business place of watch, obtain Instagram likes affordable has good edge as they only publicize the corporation profile to your followers who could possibly be keen on the solutions with the corporation. People love visual images, so pictures of products and even employees can be posted to make them feel really closer.

Posted by: buy instagram followers | 2014.10.28 02:17 PM

Thank you for any other informative blog. Where else may I get that kind of info written in such an ideal approach? I have a challenge that I'm just now operating on, and I have been on the glance out for such information.

Posted by: you could check here | 2014.11.21 09:10 AM

First off I would like to say excellent blog! I had a quick question in which I'd like to ask if you don't mind. I was interested to find out how you center yourself and clear your thoughts before writing. I have had a hard time clearing my mind in getting my thoughts out there. I do take pleasure in writing but it just seems like the first 10 to 15 minutes are usually lost simply just trying to figure out how to begin. Any suggestions or hints? Thank you!

Posted by: www.yarex.com | 2014.11.22 12:30 AM

You can certainly see your expertise within the article you write. The world hopes for more passionate writers like you who aren't afraid to say how they believe. At all times follow your heart.

Posted by: www.yarex.com | 2014.11.30 09:11 PM

When someone writes an article he/she retains the plan of a user in his/her mind that how a user can understand it. Thus that's why this piece of writing is great. Thanks!

Posted by: Web Design Company Schaumburg | 2015.03.22 05:09 PM

Post a comment



(Not displayed with comment.)




TrackBack


Listed below are links to weblogs that reference 最大マージンクラスタリング:

« カーネル多変量解析 | Main | 昨年の論文をふりかえる »