“Constrained 1-Spectral Clustering (AISTAS2012)” 読んだ
論文100本ノック4本目です。
Resource
arxiv: http://arxiv.org/abs/1505.06485
Long : http://jmlr.csail.mit.edu/proceedings/papers/v22/sundar12/sundar12.pdf
Author
Syama Sundar Rangapuram
ドイツのPh.D Student.unsupervised, semi-supervised系のグラフマイニングに関する研究を行ってる。 ICML2013,WWW2013,NIPS2013,NIPS2014 accepted. グラフカットに関する論文で面白そうなのがチラホラ。 http://www.ml.uni-saarland.de/people/rangapuram.htm
Matthias Hein
ドイツにあるサーランド大学の教授。 機械学習全般が研究領域(最適化・CV・統計,etc..)、COLT,NIPSなど高難易度の国際会議の常連。 教え子はCOLT 2005, AISTATS 2007, NIPS 2008のBest Paerを受賞。 http://www.ml.uni-saarland.de/people/hein.htm
Abstract
クラスタリングには特定のデータ間が
同一クラスタに属するべきなのか
同一クラスタに属さないべきなのか
というPrior Infomation(事前情報)がとても重要である。
この論文では、Spectral Clustering (SC) に対して制約を組み込み事を提案。 研究の動機として、最近は制約なしのSCが提案されるが当論文の提案手法は制約付きNormalized Cut(NCut)における連続最適化問題のrelaxation(緩和)について提案する。
この手法はどんな制約であろうとも成立することを約束し、NCUtと制約条件の違反数におけるトレードオフの最適化が可能。 また、他のどんな手法に比べても実験では優っている。
Summary
SCはNP困難な問題で、固有値問題に帰着させることでNP完全を緩和している。 しかし、その緩和方法は緩い(帰着はできてるが、元のNCutの性質を完全に継承していない)点が問題だった。近年はNCutを改良した combinational NCut,グラフの調和を基準にしたNCutなど様々な手法が提案れてきており、NCUt問題から厳密な帰着が行われるようになってきた。
Must Link(ML),Can not Link(CL)の制約条件などは提案されてきたが、我々はグラフ分野における制約付き学習について貢献する。
提案手法はCOSC(Constraind One Spectral Clutering)と呼んでいる。
Notation
グラフ $G(V,E,w,b)$
&V&:頂点集合
$E$:辺集合
$w$:辺の重み
$b$:頂点の重み
$$cut(C,\bar{C})=2 \sum_{i \in C , j \in \bar{C}} w_{ij}$$
$$gvol( C )=\sum_{i \in C} b_{i}$$
$$bal( C )=2 \frac{gvol( C )gvol(\bar{C})}{gvol(V)}$$
$$NCut(C,\bar{C})=\frac{cut(C, \bar{C})}{bal( C )}$$
＊NCutの式に比べると、頂点の重みが評価に組み込まれてる事と、正規化が頂点集合によってなされる。
＊ $b_i=1$,$b_i = \sum_{j=1}^{n}w_{ij}$の際に$gvol( C) \to vol( C)$と変化する。(ノードの重みが1、そしてそのノードの連結するエッジの重みの総和が1の場合
制約付きNCut問題
$Q^m,Q^c$を制約の指標とする。$Q^m$:Must Link, $Q^c$: Can not Link
$q_{ij}^m(\rm{or} \ q_{ij}^c) \in {1,0 } $ ＊$i,j$間の制約を示す。
$q_{ij}^m(\rm{or} \ q_{ij}^c) \in [1,0 ] $ も可能(集合から閉区間表現)、この論文では簡単にするために理論的集合表現とする。
集合関数を定義する $M,N = 2^V \to \mathbb{R}$
$$\hat{M}( C ) := 2\sum_{i \in C, j \in \bar{C}} q_{ij}^m$$ $$\hat{N}( C ) := \sum_{i \in C, j \in C} q_{ij}^c + \sum_{i \in \bar{C}, j \in \bar{C}} q_{ij}^c = vol( Q^c)-2 \sum_{i \in C, j \in \bar{C}}q_{ij}^c $$
＊2式:CLの制約式全体から集合$C,\bar{C}$間の制約を2倍したものを引く
$\hat{M}( C),\hat{N}( C)$は部分グラフ$C,\bar{C}$間の制約違反な MLとCLの２倍の数に等しい。
＊ここの説明がわからない: $\hat{M}()$は$C,\hat{C}$のML(繋がるべき辺)の２倍を表してるんだから、制約違反の数ではなく、制約の数の２倍に等しいのが正しいのでは?
soft ver. tight ver.な緩和の照明がある。集合論が出現してきていてちょっと理解が甘い。
アルゴリズムは、反復法によって解かれている。(意外な感じ)
制約のトレードオフ
Cuts(カットコストの事を指してる?怪しいです)と誤差のトレードオフを示す。 制約の数を増やせば増やすほど、誤差とCutsは反比例していく。
Multi Cut
二分割だけではなく、複数の分割を行うことができる。 Figure 2では制約付きSCが制約なしに比べると真の分布に近い事が示されている。
Exeperiments
他の制約付きSCとの比較実験。 Clustering Error(多分純度の事を示してる。細かい定義無し) 他の4つの手法に比べてもCOSPの結果が勝っている事がわかった。 特に二分割ではなく複数分割だと圧勝。
Comments
性能的に、多々ある制約付きSCのなかでも優れてる論文だった。
他の制約付きSCはあまり見れてない..
集合論が参入してきて数式的に難しいなと感じた論文だった。(完全に理解できてない) あと実験の評価指標でNCutの値出してるけど、その特性がいまいちわからない。(低かったらいいのか、高ければいいのか？))
SCは半教師を組み込みやすい手法なんだなと再確認。