はじめに

Local and Global Optimization Techniques in Graph-based Clusteringを読んだのでメモ．札幌で開催されたMIRU2018で著者の方が発表されていて気になったので読んでみた次第．

graph-based clustering

この論文では以下の目的関数の最小化問題としてのgraph-based clusteringに着目している．

$\displaystyle E(\mathbf{Z})=\sum_{j=1}^k\frac{\mathbf{z}_j^T\mathbf{A}\mathbf{z}_j}{f_j(\mathbf{Z})}$

ここで， $\mathbf{A}\in\mathbb{R}^{n\times n}$ はn個のデータ点に対するaffinity matrixで， $\mathbf{Z}=[\mathbf{z}_1,\dots,\mathbf{z}_k]\in\mathcal{Z},\:\mathcal{Z}=\{\mathbf{Z}\in\{0,1\}^{n\times k}|\sum_jZ_{ij}=1\}$ はassignment matrixを表す．assignment matrixは $i$ 番目のデータがクラスタ $c$ に属する場合， $Z_{ic}=1$ となるような行列．つまり各データ点がどのクラスタに属するかを表している． $f(\mathbf{Z})$ はコスト関数ごとに異なる関数．

Graph-based clusteringはk-meansやGMMのようなrepresentative-based clusteringと違い，データ間のつながり(グラフの構造)を利用したクラスタリングが可能という利点がある．

論文ではgraph-based clusteringの3つの重要な要素としてaffinity matrixの構成，目的関数，最適化の方法をあげていて，それぞれの観点から関連研究をまとめている．

Affinity matrix

最も単純なaffinity matrixの作り方は距離に基づく方法で例としては $k$ -NNやガウスカーネルを使う方法がある．その他にはデータからの学習によるaffinity matrixの獲得方法もあり，学習ベースでは線形結合の係数行列によってaffinity matrixが表現される．

objective function

従来，macro averageに基づく指標，例えば $f_j(\mathbf{Z})=\sum_iZ_{ij}$ や $f_j(\mathbf{Z})=\mathbf{1}^T\mathbf{A}\mathbf{z}_j$ など(ただし $\mathbf{1}$ は全ての要素が1の縦ベクトル)が用いられていた．ただ，macro averageに基づく目的関数は望まない小さなクラスタを生成してしまうため，クラスタサイズのバランスを取るような目的関数，balanced association(BA)が2017年に提案されている．BAの目的関数は以下で表される．

$\displaystyle \sum_{j=1}^k\mathbf{z}_j^T\mathbf{Az}_j+\lambda||\mathbf{Z}^T\mathbf{Z}||^2_F=\sum_{j=1}^k\mathbf{z}_j^T(\mathbf{A}-\lambda\mathbf{1}\mathbf{1}^T)\mathbf{z}_j$

$\lambda$ がクラスたのサイズを調整する係数で大きいほど各クラスタのサイズが等しくなる．論文のTable 1に提案手法の目的関数を含め各目的関数がまとまっている．

optimization methods

最初に与えられた $E(\mathbf{Z})$ はNP-hardな組合せ最適化の問題であり，大局的な最適解を見つけるのは難しい．normalizing cutやspectral cluseringはspectral緩和を使うことで解いていて，最も広く使われている．これらの類似手法であるmacro-AAでは目的関数 $E(\mathbf{Z})$ は次のような形で表現される．

$\displaystyle E(\mathbf{Z})=\mathrm{tr}(\mathbf{Y}^T\mathbf{A}\mathbf{Y}),\:\mathrm{where}\:\mathbf{Y}=\left[\frac{\mathbf{z}_1}{||\mathbf{z}_1||_2},\dots,\frac{\mathbf{z}_k}{||\mathbf{z}_k||_2}\right]$

これは $\mathbf{Z}$ を $\mathbf{Z}\in\mathcal{Z}',\:\mathcal{Z}'=\{\mathbf{Z}\in\mathbb{R}^{n\times k}|\mathbf{Z}^T\mathbf{Z}=\mathbf{I}_k\}$ のように緩和することで $\mathbf{A}$ の固有ベクトルを利用することで $\mathbf{Z}$ 上で解くことが可能．問題としては緩和が必要なことやmacro-average-based cost functionを用いること， $\mathcal{O}(n^3)$ の計算コストなどがあげられる．

その他の方法としてはkernel k-meansなどで知られるbound optimization method (BO)などがあり，BOは次のような上界の最小化を行う．

$\displaystyle \mathbf{Z}^{(t+1)}=\mathrm{arg}\max_\mathbf{Z}E_t(\mathbf{Z})\displaystyle E_t(\mathbf{Z})=\sum_{j=1}^k\mathbf{z}_j^T\left(\frac{\left(\mathbf{z}_j^{(t)}\right)\mathbf{K}\mathbf{z}_j^{(t)}}{\left(\mathbf{w}^T\mathbf{z}_j^{(t)}\right)^2}\mathbf{w}-\frac{2\mathbf{K}\mathbf{z}_j^{(t)}}{\mathbf{w}^T\mathbf{z}_j^{(t)}}\right)$

Macro-AAにおいては $\mathbf{K}=\mathbf{A}+\delta\mathbf{I}_n,\:\mathbf{w}=\mathbf{1}$ であり，normalizing cutにおいては $\mathbf{K}=\mathbf{A}+\delta\mathrm{diag}(\mathbf{S1}),\:\mathbf{w}=\mathbf{A1}$ として表現される．これは $\mathbf{K}$ が半正定値行列である場合に厳密なbound functionになる．

Micro-average association

関連研究で議論されていたようにnormalizing cut等に用いられるmacro-average-based cost functionは小さなクラスタを生成してしまう場合がある．ここではこの問題を解決するために，以下のmicro average associtationに基づく目的関数を提案する．

$\displaystyle E(\mathbf{Z})=\frac{1}{\sum_{j=1}^k(\mathbf{z}_j^T\mathbf{1})^p}\sum_{j=1}^k\mathbf{z}_j^T\mathbf{Az}_j$

これは $f_k(\mathbf{Z})=\sum_{j=1}^K(\mathbf{z}_j^T\mathbf{1})^p$ としたもので， $p$ によってクラスタの大きさをコントロールできる．つまり，分母が各クラスタに入っているデータ数の総数の $p$ 乗の総和で定義されているため，コスト関数を最大化するには均一に近い方が望ましいということ．これをここではmicro average association cost (micro-AA)と呼ぶ．

Micro-AAの利点は小さなクラスタの出現を防ぐことで，同様の効果を持つBAと比べて実験的にmicro-AAの方が良いクラスタリング結果を実現したとのこと．ただし，micro-AAはNP-hardであることと，既存手法には適用できない問題がある．

direct local optimization

ここでは目的関数の上昇が保証されている繰り返し最適化手法であるdirect local optimization (DLO)を提案．DLO単体では良いクラスタリング結果を得るためには良い初期値が必要であるが，同時に提案するgreedy incremental algorithm (GIA)を適用することで初期値の影響を受けにくくする事が可能．

まずDLOの説明の前にaffinity matrixを対称行列と仮定する．仮にaffinity matrixが非対称行列だった場合 $\mathbf{A}'=(\mathbf{A}+\mathbf{A}^T)/2$ とすれば対称行列になることから一般性は失わない．また， $\mathbf{Z}$ の列ベクトルと行ベクトルをそれぞれ， $\mathbf{z}_{\cdot,i},\:\mathbf{z}_{i,\cdot}$ と定義する．

DLOは座標降下法の一種で，目的関数の値が繰り返しの度に上昇することが保証されている．iteration $t$ における解 $\mathbf{Z}^{(t)}$ が与えられた時，DLOは行ベクトル $\mathbf{z}_{l,\cdot}$ ごとに最適化していく．

$\displaystyle \mathbf{z}^\ast=\mathrm{arg}\max_\mathbf{z}E(\mathbf{z}_{1,\cdot}^{(t)},\dots,\mathbf{z}_{l-1,\cdot}^{(t)},\mathbf{z},\mathbf{z}_{l+1,\cdot}^{(t)},\dots,\mathbf{z}_{n,\cdot}^{(t)}) \\ \displaystyle \mathbf{z}_{i,\cdot}^{(t+1)}=\left\{ \begin{array}{} \mathbf{z}_{i,\cdot}^{(t)}\:\:\: (i\neq l) \\ \mathbf{z}^\ast\:\:\:\:(i=l) \end{array} \right.$

最大化問題は，ある $l$ 番目のサンプルの所属クラスタを変えた時に最もエネルギー関数が上昇するクラスタをそのサンプルに割り振ることで解かれる．すなわち一回の更新に対しクラスタ数 $k$ 回の計算を行う．これは少なくともサンプル $l$ を同じクラスタに割り振れば目的関数の値は等しくなるため，目的関数の値を下げることはない．

サンプル $l$ の選び方はrandomized, cyclic, greedyの3つのタイプに分けられる．randomized coordinate descentはサンプルの集合 $\{1,\dots,n\}$ からランダムにサンプル $l$ を選び，cyclic coordinate descentは順番に $l$ を選ぶ．greedy coordinate descentは目的関数を最も上昇させるサンプルを選ぶ．3つの中でもgreedyなものは最良のサンプルを選択するため計算コストがかさむが，良いサンプルを選択することができるため実践的にはrandomなものよりも計算コストにおいて良いパフォーマンスを示す．そのためこの論文ではgreedyな選択をすることにしたとのこと．

$t$ 回目の更新の時にサンプル $l$ を $c$ 番目のクラスタに割り振った時の目的関数の値を $F^{(t)}(l,c)$ とする．この目的関数の値を愚直に計算するとコストが高いため， $t-1$ 回目の更新時の目的関数の値を利用することで効率良く計算する．繰り返し $t$ においてサンプル $l$ が所属するクラスタを $\hat{c}$ とすれば目的関数は次のように書ける．

$\displaystyle F^{(t)}(l,c)=\sum_{j=1}^k\left(\frac{\left(\mathbf{z}_{\cdot,l}^{(t)}\right)^T\mathbf{Az}_{\cdot,l}^{(t)}}{f_j(\mathbf{Z}')}\right)-\frac{2\mathbf{a}_l^T\mathbf{z}_{\cdot,\hat{c}}}{f_\hat{c}(\mathbf{Z}')}+\frac{2\mathbf{a}_l^T\mathbf{z}_{\cdot,c}}{f_c(\mathbf{Z}')}\\ \displaystyle =\sum_{j=1}^k\left(\frac{G_l^{(t)}}{f_j(\mathbf{Z}')}\right)-\frac{2H^{(t)}(l,\hat{c})}{f_\hat{c}(\mathbf{Z}')}+\frac{2H^{(t)}(l,c)}{f_c(\mathbf{Z}')}$

ただし， $\displaystyle G_l^{(t)}=(\mathbf{z}_{\cdot,j}^{(t)})^T\mathbf{Az}_{\cdot,j}^{(t)},\:H^{(t)}(l,j)=\mathbf{a}_l^T\mathbf{z}_{\cdot,j}^{(t)}$

$G_l^{(t)}$ と $H^{(t)}(l,j)$ の計算オーダーはそれぞれ $\mathcal{O}(n^2),\mathcal{O}(n)$ になるが，次のように効率的に計算が可能．

$\displaystyle G_l^{(t)}=\left\{ \begin{array}{} G_j^{(t)}\:\:\:(j\neq\hat{c}\:\mathrm{and}\:j\neq c) \\ G_j^{(t)}-2H_{l,\hat{c}}^{(t)}\:\:(j=\hat{c}) \\ G_j^{(t)}+2H_{l,c}^{(t)}\:\:(j=c) \end{array} \right.$ $\displaystyle H^{(t)}(l,j)=\left\{ \begin{array}{} H^{(t)}(l,j)\:\:\:(j\neq\hat(c)\:\mathrm{and}\:j\neq c) \\ H^{(t)}(l,j)-a_{l,l\ast}\:\:(j\neq\hat{c}) \\ H^{(t)}(l,j)+a_{l,l\ast}\:\:(j=c) \end{array} \right.$

結局，上記のような方法で計算をすればそれぞれの計算オーダーは $\mathcal{O}(a)$ になる．最終的には全ての $l,c$ に関する目的関数 $F^{(t)}(l,c)$ の計算オーダーは繰り返し1回目は $\mathcal{O}(kn^2)$ ，その後は $\mathcal{O}(kn)$ となる．

greedy incremental algorithm

DLOは局所最適化法なため良い解を得るためには良い初期値が必要となる．初期値としてspectral clusteringの結果を使う方法などもあるがspectral clusteringは特定の場合においてはうまく機能しない問題がある．そこでここでは初期値の影響を減らすことのできるgreedy incremental algorithm (GIA)を提案する．

まず $\mathbf{Z}$ の初期値を $\mathbf{Z}^{(0)}=\mathbf{0}$ とし， $F_0(l,c)=s_{l,l}$ とする．さらにまだクラスタの割り当てが決まっていないサンプルの集合を $T=\{1,\dots,n\}$ とする．DLOと同様の手順を用いて目的関数の値 $F^{(t)}(l,c)$ を計算し，目的関数の値を最大にするサンプル $l^\ast$ とクラス $c^\ast$ を用いて $\mathbf{Z}^{(t)}$ と $T$ を更新する．要は初期の割り振りを与えずにDLOをするという感じ．これにより初期値に依存をしないためDLOのパフォーマンスを改善できるというもの．GIAの計算オーダーは $\mathcal{O}(n^2k+lnk)$ で $l$ は繰り返し回数．

提案手法を含む多くのgraph-clustering最適化手法は局所解につかまりやすいという問題があるよう．そこで論文ではGIAを用いる上で大局的な最適解を導きやすくする二つの方法を紹介している．

GIAはaffinity matrixが疎な行列である場合，悪い局所解にトラップされる傾向にあるらしい．そこでgraduated optimization (GO)を適用することでこれを回避する術を紹介している．凸でない関数 $f(x)$ を解く上でGOはまずはじめに平滑化された関数 $f_s(x)$ を解き，更新とともに徐々に $f_s(x)$ を $f(x)$ へと変形していく．graph-clusteringの文脈では平滑化されたaffinity matrix $\mathbf{A}^g$ を使うことで平滑化された関数を得る．論文中のFigure 3には $g$ を変えた際のaffinity matrixの変化が示されていて，疎な行列が $g$ が大きくなるにつれ徐々に密になっていることがわかる．GOのやり方に従えば，最初は $g$ を大きな値に設定して最適化を行い，最終的に $g=1$ になるよう徐々に $g$ の値を小さくしていくことで局所解にトラップされることを防ぐ．

もう一つの局所解を回避する方法としてclustering ensemble (CE)がある．GIAは局所解にトラップされても，部分的には綺麗なクラスタを形成していることが論文中のFigure 4の結果からわかる．そこで，GIAの $n$ 個の解 $\mathbf{Z}_1,\dots,\mathbf{Z}_n$ からco-association matrix $\mathbf{\Theta}_{en}=1/n\sum_{i=1}^n\mathbf{Z}_i^T\mathbf{Z}_i$ を計算する．簡単に言ってしまえば複数の結果の平均を最終的な結果としようというもの．ただし，クラスタリングの結果を得るためには $\mathbf{\Theta}_{en}=\mathbf{Z}^T\mathbf{Z}$ という変換が必要になる．そこでaffinity matrixを $\mathbf{A}=\mathbf{\Theta}_{en}$ として目的関数 $E(\mathbf{Z})$ を解くことでこの変換を達成する．ただし，目的はgraph-based clusteringの大局的最適解を達成することなので， $\mathbf{\Theta}_{en}$ から得られた解を使って元のaffinity matrix $\mathbf{A}$ 上でDLOを使い最適解を得る．

実験

実験に用いたデータセットの多くで既存手法を大きく上回るクラスタリング精度を達成している．特にCOIL-20ではクラスタリング精度100%となっていて驚き．ただ，clustering ensembleがうまく働かない，すなわちクラスタリング結果にバイアスが乗るようなデータでは若干悪い結果となるようで，実際クラス毎のサンプル数に偏りのあるHopkins 155ではspectral clusteringを6%程下回る結果になっている．

まとめ

Graph-based clusteringに関する知識があまりにもないため若干理解しきれていない部分(目的関数の根本的なところや各手法の嬉しさなど)があるからお盆の間に基本的なところから勉強して理解したい．逆にそんな知識不足の中読んだ論文なのでメモの内容は謝りを多く含むかもしれないので注意。。。

機械学習とかコンピュータビジョンとか

CVやMLに関する勉強のメモ書き。

Local and Global Optimization Techniques in Graph-based Clusteringを読んだのでメモ