MIT OCW, Machine Learning 14日目

Rohit Singh, Tommi Jaakkola, and Ali Mohammad. 6.867 Machine Learning. Fall 2006. Massachusetts Institute of Technology: MIT OpenCourseWare, https://ocw.mit.edu. License: Creative Commons BY-NC-SA.
Lecture 18.

• • Specral clustering
    • Graph construction
    • Graph partitioning and criteria
    • Spectral clustering, the eigenvalue problem
    • Spectral clustering, random walk
      • Definition

Specral clustering

データ点の近さの尺度を導入してそれぞれの点同士を頂点とし，辺をその近さの尺度によって重み付けしたグラフを構成できる. spectral clusteringはその重みづけグラフの分割を，固有値問題と考えるアルゴリズムのクラスである. 大きな正の重みで繋がれているノードたちは同じクラスターに入れられることが多い． グラフ表現を行うことで，そのアルゴリズムがノード間の近さだけを基準にして分類を行っていることを際立たせることができる.

Graph construction

ベクトル空間上で表現できる場合にも，グラフ構造での表現には有利な点が有る．例えばfig.1.aの点は2つの半円上の点に分類できるが，これを少数のGaussianの混合で表現することはできない一方，それぞれの点の最近傍の2点をつなげることで,fig.1.bの，非常によく特徴を捉えたグラフが構成できる. このような重み付けグラフを構成するより一般的な方法を議論する. これには多くの方法が有るが，もっとも典型的なのが，上で見たように,k-nearest neighborを使う方法である. すなわち，すべての点について，$k$個の最近傍の点をつなげる無向グラフを作成し，さらに
$$W_{ij} = \begin{cases} \exp(-\beta \|\mathbf{x_i - x_j}\|) \ \ &\text{if } i, j \text{ are connected} \\ 0 & \text{otherwise} \end{cases}$$
によって重みを計算する. $W_{ij} = W_{ji}$である. 対角成分は全て0とする.
$k, \beta$が選べるパラメータである. $k$は求めたいクラスターたちの次元によって適した値が決まってくる．例えば，クラスターが$d$次元の表面をもつとするなら，$k\geq d$が望ましい. 小さな$k$は疎なグラフを作りやすくし，よく似た点たちのみのクラスターが作られるようになる． これは,遠く離れた点ではユークリッド距離を使うのがナンセンスになるような場合に有利である ．例えば球面にのみ全てのデータ点が存在して，点たちの距離が球面に沿った距離で図られるべきときには，点が遠くなれば遠くなるほど，ユークリッド距離と球面上の距離が乖離してくることが想像できるだろう.
$\beta$も同様の役割を果たす．

Graph partitioning and criteria

$n$個の点を2つに分類する問題を定式化する. より多くの種類に分類するときには再帰的に二値分類を適用する. 対象は，重み付け行列$W$で表現されていて，$W$は非負の対称行列で対角成分は0である． $W$を近さの尺度として，ノードたちを$C^+, C^-$の二つに分類する. $y_i = \begin{cases} 1 \ \ & i \in C^+ \\ -1 & i \in C^-\end{cases}$という変数$y=\{y_i\}$を定義する.
$C^+, C^-$を決めれば分類は一意に定まり，その分類(cut)に対する重み
$$s(C^+,C^-)= \sum_{i \in C^+, j\in C^-} W_{ij} = \frac{1}{4}W_{ij} \sum_{i,j} (y_i-y_j)^2 = J(y)$$
を導入する. $i, j$が異なって分類されると$W_{ij}$分の重みが$s$につく． 全てが同じクラスタに分類されるとき$s=0$だから，どちらのクラスタにも同じくらいの数のノードが入るようにするため，minimum cut criterionを導入する. よく使われるcriterionにnormalized cut(Shi and Malik 2000)がある.
$$\text{Norm-cut}(C^+, C^-) = \frac{s(C^+, C^-)}{s(C^+,C^+)+s(C^+,C^-)}+\frac{s(C^+,C^-)}{s(C^-, C^-)+s(C^+,C^-)}$$
である．ただし$s(C^+, C^+)=\sum_{i \in C^+, C^+} W_{i,j}$とする.
この問題を厳密かつ効率的に解く方法は存在しないため，eigenvalue problemによって近似的に解く.

Spectral clustering, the eigenvalue problem

$y= (y_1,..,y_n)$でそれぞれは$\pm 1$のどちらかを取ったが,$z= (z_1,..,z_n)$で$z_i \in \mathbb{R}$に条件を緩和する．やはり$i \in C^+ \Rightarrow z_i >0, i \in C^- \Rightarrow z_i < 0$とする.このように二値分類問題を緩和し，eigenvalue問題に帰着させる．まずはcutの重みを改めて表現する.
$$\begin{aligned} J(z) &= \frac{1}{4} W_{ij}(z_i-z_j)^2 = \frac{1}{4}\sum_{i,j} (z_i^2-2z_iz_j+z_j^2)=\frac{1}{4}\sum_{i,j}W_{ij}(2z_i^2-2z_iz_j) \\ &= \frac{1}{2}\sum_i \underline{(\sum_j W_{ij})}_{D_{ii}}z^2_i + \frac{1}{2} \sum_{i,j} W_{ij}z_iz_j = \frac{1}{2}z^T (D-W)z \end{aligned}$$

$D_{ii}=\sum_j W_{ij}$という対角行列を使って表現した.
$L=D-W$はgraph Laplacianという名でしられ，半正定値行列である. $L$の最小固有値は必ず$0$であり，対応する固有ベクトルは$z=(1,...,1)$である. normalized cut criterionを考慮すると，最適化問題は
$$minimize \frac{1}{2} z^T (D-W)z \ \ \text{ subject to } z^TDz=1, z^TD1=0$$
となる. Lagrange multiplierを使うと,
$$(D-W)z = \lambda Dz$$
の2番目に小さい固有値を求めることと同じになる(らしい). $\hat{y_i} = sign(z_{2_i})$の符号が有るノードが入るクラスターになる.fig.2はあるspectral cluseringの近似解である.

Spectral clustering, random walk

normalized cut problemを緩和して近似的に解いた．全く異なったアプローチでこの近似方法を正当化する． 重み付きグラフの上でのrandom walkを考えるのである.
$$P_{ij} = \frac{W_{ij}}{\sum_{j'}W_{ij'}} = \frac{W_{ij}}{D_{ii}}$$
によって定義される行列$P=D^{-1}W$である. $\sum_j P_{ij} = 1$で,$P \mathbf{1}=\mathbf{1}$が成立する.よって$P$を重み付きグラフの上でのrandom walkのtransition matrixと考えることが出来る. すなわち,$X(t)$を時刻$t$(ここでは$t$回目の遷移とする)でのrandom walkのstateを表すとすると,
$$P(X(t+1)=j|X(t)=i)=P_{ij}$$
であって，homogeneous Markov chainと考えることが出来る. Markov chainのstateはこの場合グラフのnodeである. Markov chainのErgodic propertyを定義する.

Definition

Markov chain $\{X(t)\}$がergocid
$\Leftrightarrow \exists m \text{ s.t. } \forall t, i,j .\ P(X(t+m)=j|X(t)=i)>0$

erogodicであるとき，$\{X\}$はirreducible かつrecurrentかつstationary distributionをもつ.
stationary distribution $\pi$は$\pi_j = \lim_{m\rightarrow \infty} P(X(t+m)=j|X(t)=i)$である． これまで議論してきた重み付きグラフを上の方法でMarkov chainにするとergodicであり，したがってergodic theoremが成立する．

(以下，講義はもう少し続くが固有値とMarkov chainがどうつながるかわからないので飛ばす．そのうちいい教科書を見つけて読む)