論文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の値出してるけど、その特性がいまいちわからない。(低かったらいいのか、高ければいいのか？))