J. Weston.
Proceedings of NATO Advanced Study Institute on Mining Massive Data Sets for Security, IOS Press.
videolectureのvideoとかプレゼンの資料とか。
これまでSSLの論文をいくつか読んできたけど、読んでて思ったのは「このアルゴリズム、大規模データに耐えられなくね?てか実験小規模なものしかやってないし。。。」ということだった。ということで、論文の名前につられて読んでみることにした。結論としては、詳細な部分は書いてないので、それぞれの元論文をたどらないと分かった気にしかなれないかなぁという感じ。
この論文では、既存のSSLのアプローチとして
- graph-based approaches
- change of representation approaches
- margin-based regularization based approaches
の3つをあげているが、いづれもとなってしまう。SSLでは特にUのほうが大きくなりがちなので、そいつの3乗だとうまくスケールしてくれないのでどうにかしましょう、というお話。
Graph-Based Approaches
グラフベースのSSLはいままでいくつか見てきた。
- #5 Learning from Labeled and Unlabeled Data using Graph Mincuts - yasuhisa's blog
- #6 Seeing stars when there aren’t many stars: Graph-based semi-supervised learning for sentiment categorization - yasuhisa's blog
ここでは損失関数を予測と実測の二乗和と「重みを利用して近くのデータは同じクラスに所属しているべき」ということを表わしている。後者のほうを実現するアルゴリズムとしてラベル伝播*1がある。ラベル伝播は収束するまでiterationを繰り返していくのだが、closed form solutionで書くことができる。これはkNNをSSLに拡張して一般化したものだ、と書いてある。が、逆行列の計算が入ってくるため計算量としてはでうまくスケールしてくれない。
で、こいつをスケールするようにしたい。iterativeなアルゴリズムなので、early stopping(早期終了?)するのはどうかというのが最初に書いてある。他にもスピードアップするための方法(というかここだと条件)があって、重み行列Wがスパースだと早くできたり、ラベルなしデータは他のサンプルの線形結合で書けてデータの数を減らすことができるので、最適化がしやすくなるんじゃないかということが書いてある。こいつの計算量はとできて(m << U + L)、わりとましになるようだ。
Change of Representation Approaches
この手法のきもは、入力データを(カーネル法みたく)特徴空間に飛ばすときに、どういう特徴空間だとデータのことをうまく表現できるかっていうのはラベルなしデータを使っても考えられるんじゃないか?っていうこと。そんな感じでうまく選ばれた特徴ベクトルでもって、SVMとかにかければよいのではないか、という流れ。で、どういう風によいカーネルを設計してあげるか?ということだが、ここではcluster kernelというものが使われている。
まず、edgeの重みを決めてあげて、それを正規化して確率にする。その確率でもってランダムウォークする。t期での遷移確率をPとしよう。この行列に基づいてカーネルを設計するということだが、具体的なことは[1]を見ろってことだそうです。ただ、このカーネルも計算量がでスケールしないっていうのは同じ。
そこでスケールさせるべく2つのステップに分ける。ステップ1では教師なし学習をやり、ステップ2でその結果を使って教師あり学習をやるという方法(詳しくは[2]を参照)。教師なし学習ではk-meansをN回やる。そして、と
が同じクラスターに入っている割合をカーネルとして使う。カーネルができればあとはカーネルを使うような教師あり学習の中から好きなものを使うとよい(ここではSVMが使われている)。
margin-based regularization based approaches
transductive SVM(TSVM)もこのアプローチの範疇に入る。このアプローチでは「決定境界は密度の低いところにあるに違いない」という仮定に基いて決定境界がどこかを決めている。(16)式の損失関数の第三項目が特徴的。ただ、ラベルなしデータのところのhinge関数が凸でないため最適化は困難なものになってしまう。いくつか(ヒューリステックなところを入れるなどして)工夫したものもあるが、計算量としてはである。
しかし、近年TSVMでスケールするような性質を持ったものが登場している([3]を参考)。concave-convex procedure(CCCP)というもの(非凸の関数を最適化するときに使う手法。[4]が詳しい)を使うのがメインのアイデアらしい。こやつを使うとiterativeに解けて、単調減少な性質があるので、局所最適解に収束することが保証させる、らしい。EMっぽいな。
CCCPに関する論文も読んだ。わりと簡単。
参考文献
[1] M. Szummer & T. Jaakkola (2002). `Partially labeled classification with markov random walks'.
[2] J. Weston, et al. (2005). `Semi-supervised protein classification using cluster kernels.'. Bioinformatics 21(15):3241-3247.
[3] R. Collobert, et al. (2006). `Large Scale Transductive SVMs'. Journal of Machine Learning Research 7:1687-1712.
[4] Yuille, A.L., Rangara jan, A.: The concave-convex procedure. Neural Computation 15(4) (2003) 915–936
*1:これも勉強しないと(ry
