はじめに

Deep Spectral Clustering Learningを読んだのでメモ．

気持ち

クラスタリングの良さは類似度の指標とデータの表現に依存する．多くの手法はデータの表現固定であったり線形の変換によって得られることが多かったり．deepな学習ベースの手法も提案されているが勾配計算が複雑な場合が多いとのこと．そこでここではミニバッチサイズに線形に比例する計算オーダーで勾配を計算することができる表現を提案する．

Notation

実数行列 $A,B$ のフロベニウス内積（Frobenius inner product）を $\langle A,B\rangle:=\mathrm{tr}\langle AB^T\rangle$ ，行列 $A$ のフロベニウスノルムを $||A||:=\sqrt{\mathrm{tr}(AA^T)}$ として定義する． $A^\dagger$ をムーアペンローズの擬似逆行列とする．さらに集合 $\mathcal{F}$ の相対的内部（relative interior）を $\mathrm{ri}(\mathcal{F})$ とする．この相対的内部というのは初めて聞いたけど，集合の内部にアフィン包の概念を入れたものっぽい．どんな意味があるかわからないけど，グラフを扱う上で定義しないとどこかでまずいことが起こるのかなと推測．

Data

ここでは一つの行列 $F=[\mathbf{f}_1,\dots,\mathbf{f}_n]^T$ で表現される $n$ 個のサンプルの集合 $\mathbf{f}_1,\dots,\mathbf{f}_n\in\mathbf{F}$ について考える．

Bregman divergence

Bregman divergence $d_\phi:\mathcal{F}\times\mathrm{ri}(\mathcal{F})\rightarrow[0,+\infty)$ を $d_\phi(\mathbf{x},\mathbf{y})=\phi(\mathbf{x})-\phi(\mathbf{y})-\langle\mathbf{x}-\mathbf{y},\nabla\phi(\mathbf{y})\rangle,\:\phi:\mathcal{R}\rightarrow\mathbb{R}$ として定義する．ただし，関数 $\phi$ は微分可能で凸な関数で， $\nabla\phi(\mathbf{y})\in\mathbb{R}^d$ は $\phi$ の $\mathbf{y}$ に関する勾配を表す．

クラスタリングの文脈で使われるBregman divergenceはユークリッド距離の2乗 $\phi=||\mathbf{x}||_2^2$ ，KLダイバージェンス，板倉齋藤距離などで定義されることが多いらしい．

Clustering

$n$ 個の観測 $F=[\mathbf{f}_1,\dots,\mathbf{f}_n]^T\in\mathcal{F}^n$ を $k$ 個のクラスタに分けるのはassignment matrix $\hat{Y}\in\{0,1\}^{n\times k}$ を求めることに等しい．仮定として各サンプルはただ一つのクラスタに割り当てられクラスタに所属しないサンプルはない，つまり $\hat{Y}$ の行ごとの和をとれば必ず $1$ になるという仮定を置く．よって $\hat{Y}$ は次の集合に従う．

$\displaystyle \mathcal{Y}^{n\times k}:=\{\hat{Y}\in\{0,1\}^{n\times k}:\hat{Y}\mathbf{1}=\mathbf{1},\mathrm{rank}(\hat{Y})=k\}$

さらに各クラスタ $c$ は一つの表現ベクトル $\mathbf{z}_c\in\mathrm{ri}(\mathcal{F})$ で表現されると仮定し，各サンプル $\mathbf{f}_i$ は $\forall b\neq c,d_\phi(\mathbf{f}_i,\mathbf{z}_c\leq d_\phi(\mathbf{f}_i,\mathbf{z}_b)$ の時クラスタ $c$ に割り当てられる．記述の簡略化として $\mathbf{z}_c\in\mathcal{F}$ とし， $k$ 個の表現ベクトルを行列の形に並べたものを $Z=[\mathbf{z}_1,\dots,\mathbf{z}_k]^T\in\mathcal{F}^k$ として定義する．すると $d_\phi$ の元， $n$ 個のサンプルをクラスタに分割する問題は次のエネルギー関数の最小化問題として定式化できる．

$\displaystyle \min_{\hat{Y}\in\mathcal{Y}^{n\times k},Z\in\mathcal{F}^k}\sum_{i=1}^n\sum_{c–1}^k\hat{Y}_{ic}\cdot d_\phi(\mathbf{f}_i,\mathbf{z}_c)\\ \displaystyle =\min_{\hat{Y}\in\mathcal{Y}^{n\times k},Z\in\mathcal{F}^k}\mathbf{1}^T\Phi(F)-\mathbf{1}^T\Phi(\hat{Y}Z)-\langle F-\hat{Y}Z,\nabla\Phi(\hat{Y}Z)\rangle$

ただし， $\forall A=[\mathbf{a}_1,\dots,\mathbf{a}_n]^T\in\mathcal{F}^n,\Phi(A)=[\phi(\mathbf{a}_1),\dots,\phi(\mathbf{a}_n)]^T\in\mathbb{R}^n$ ， $\nabla\Phi(A)=[\nabla\phi(\mathbf{a}_1),\dots,\nabla\phi(\mathbf{a}_n)]^T\in\mathbf{R}^{n\times d}$ のように各ベクトルを行列の形で表現したもの．

Banerjeeらは上記の目的関数の最小解 $\mathbf{z}_c$ が $d_\phi$ がBregmanダイバージェンスの時においてクラスタ $c$ に所属するサンプルの平均ベクトルになることを示したらしい．行列で表現すれば $Z=(\hat{Y}^T\hat{Y})^{-1}\hat{Y}^TF=\hat{Y}^\dagger F$ ということ．ここで集合 $\mathcal{P}=\{\hat{Y}\hat{Y}^\dagger:\hat{Y}\in\mathcal{Y}^{n\times k}\}$ を定義すれば次の1変数に関する最小化問題として書き直せる．

$\displaystyle \min_{\hat{C}\in\mathcal{P}}\mathbf{1}^T\Phi(F)-\mathbf{1}^T\Phi(\hat{C}F)-\langle F-\hat{C}F,\nabla\Phi(\hat{C}F)\rangle$

Deep Spectral Clustering Learning

Constraint Relaxation

ここでは $\min_{\hat{C}\in\mathcal{P}}\mathbf{1}^T\Phi(F)-\mathbf{1}^T\Phi(\hat{C}F)-\langle F-\hat{C}F,\nabla\Phi(\hat{C}F)\rangle$ の問題をベースとして考える．この最小化問題はNP-hardであるため，緩和問題を考える．まずは $\hat{C}\in\mathcal{P}$ を $\hat{C}\in\mathcal{C}^{n,k}$ として緩和する．ただし， $\mathcal{C}^{n,k}$ は $\mathcal{P}$ を含むランク $k$ の $n\times n$ の対角行列 $\mathcal{C}^{n,k}:=\{\hat{C}\in\mathbb{R}^{n\times n}:\hat{C}^2=\hat{C},\hat{C}^T=\hat{C},\mathrm{randk}(\hat{C})=l\}$ ．この緩和された問題は次のように定式化できる．

$\displaystyle f(F):=\mathrm{arg}\max_{\hat{C}\in\mathcal{C}^{n,k}}\mathbf{1}^T\Phi(\hat{C}F)+\langle F-\hat{C}F,\nabla\Phi(\hat{C}F)\rangle$

ただし，上記は $\hat{C}$ に関連しない項は式から除外している．

嬉しいことにこの解はclosed-formに求まる． $s=\mathrm{rank}(F)$ と定義した時 $s\leq k$ ならば，この問題の解は $f(F)=\{\hat{C}\in\mathcal{C}^{n,k}:\hat{C}F=F\}=\{\hat{C}\in\mathcal{C}^{n,k}:\hat{C}=FF^\dagger+VV^T,VV^T\in\mathcal{C}^{n,(k-s)},VV^TF=0\}$ となる．特に $s=k$ ならば， $VV^T=0$ で $f(F)=\{FF^\dagger\}$ となる．（証明はsupplementary materialにあるらしいので今度読む．）

以下，学習サンプルの次元 $d$ が $k$ より大きくなく， $s\leq k$ を満たす場合のみを考える．もし $s\gt k$ ならば，解の集合は $f(F)=\{FF^\dagger\}$ として考えられる．

Structured output prediction

まず， $n$ 個のサンプル $\mathbf{x}_i\in\mathcal{X}$ と，パラメータ $\theta$ とする埋め込み関数 $\varphi_\theta:\mathcal{X}\rightarrow\mathcal{F}$ が与えられたとする．ただし， $\varphi$ は $\forall i\in\{1,\dots,n\},\varphi_\theta(\mathbf{x}_i)=\mathbf{f}_i$ で，表現ベクトル $\mathbf{f}_i$ を行列にまとめたものを $F=[\mathbf{f}_1,\dots,\mathbf{f}_n]^T\in\mathcal{F}^n$ とする．また，正解のassignment matrix $Y\in\mathcal{Y}^{n\times k}$ は与えられているものとする．ここでの目標は， $F$ の正解のクラスタリング行列を $C=YY^\dagger\in\mathcal{P}$ とすれば，緩和問題 $f(F)\subseteq\mathcal{C}^{n,k}$ から得られた行列が真のクラスタリング行列 $C$ に可能な限り近づくような埋め込み関数 $\varphi_\theta$ を学習することとなる．

以下では行列 $F$ は $\varphi_\theta$ に依存する変数として考える．行列 $F$ の真のクラスタリング $C\in\mathcal{P}$ と $f(F)$ から推定されたクラスタリング $\hat{C}$ 間の相違度を最小化する問題は次のempirical risk minimizationとして定式化できる．

$\displaystyle \min_{F\in\mathcal{F}^n}\max_{\hat{C}\in f(F)}||C-\hat{C}||^2$

ここで $f(F)$ のとる全ての行列が同じランクである場合，上の問題は $||C-\hat{C}||^2=||C||^2+||\hat{C}||^2-2\mathrm{tr}(C\hat{C}),\:||\hat{C}||^2=\mathrm{tr}(\hat{C})=\mathrm{rank}(\hat{C})=k$ として書ける．この時 $||\hat{C}||^2$ が定数となることから次の問題と等価として扱える．

$\displaystyle \max_{F\in\mathcal{F}^n}\min_{\hat{C}\in f(F)}\mathrm{tr}(C\hat{C})$

この問題は次のような下界を持つ．（証明はsupplementary material）

$\displaystyle \max_{F\in\mathcal{F}^n}\min_{\hat{C}\in f(F)}\mathrm{tr}(C\hat{C}FF^\dagger)=\max_{F\in\mathcal{F}^n}\mathrm{tr}(CFF^\dagger)$

ただし， $\forall\hat{C}\in f(F),\hat{C}FF^\dagger=FF^\dagger$ ．この下界は $\mathrm{rank}(F)=k$ の時に等号が成り立つ．

この下界の最適化の難しいところは $F$ と $F^\dagger$ の両方に依存するところ． $\mathrm{rank}(F)$ が定数と仮定した時，この問題は微分可能となり $F$ に関する勾配は次のように計算できる．

$\displaystyle \nabla_F=2(I-FF^\dagger)C(F^\dagger)^T$

ただし， $I$ は単位行列．この論文の実験においては $F$ は常にフルランクで，ランクが定数になるという条件を満たしていたとのこと．

complexity

この計算が閉形式を持つだけでなく，その計算コストがサンプル数 $n$ に線形，次元 $d$ に対して2乗オーダーであることを示す． $C=YY^\dagger\in\mathcal{P}$ が真のクラスタを表す行列とする．ただし，行列 $Y\in\mathcal{Y}^{n\times k}$ は与えられている． $\mathbf{y}_c$ を $Y$ の $c$ 列とすると， $(Y^\dagger)^T$ の $c$ 列は $\frac{1}{\max\{1,\mathbf{y}_c^T\mathbf{1}\}}\mathbf{y}_c$ と記述できる． $(Y^\dagger)^T$ の計算コストは $Y$ が疎であることから $n$ に線形になる． $C=YY^\dagger$ の関係を使えば $\nabla_F$ は次のように書ける．

$\displaystyle G:=\frac{\nabla_F}{2}=(Y-F[F^\dagger Y])[F^\dagger(Y^\dagger )^T]^T$

$[\cdot]$ は計算結果が $d\times k$ 行列であることを表し， $[\cdot]$ は $Y$ が疎であることから効率的に計算ができる． $F^\dagger$ の計算コストは $\mathcal{O}(nd\min\{n,d\})$ になる( $d\leq n$ の仮定が成り立つ場合には $\mathcal{O}(nd^2)$ )．

Learning deep models

ここまで議論してきた手法を使ってニューラルネットを学習する．まず，ミニバッチの行列表現を $F=[\mathbf{f}_1,\dots,\mathbf{f}_n]^T\in\mathcal{F}^n$ とする．ただし， $\varphi_\theta(\mathbf{x}_i)=\mathbf{f}_i$ ，つまりオリジナルのデータ $\mathbf{x}_i\in\mathcal{X}$ をニューラルネット $\varphi_\theta:\mathcal{X}\rightarrow\mathcal{F}$ で変換して得られた特徴ベクトルを並べたものが $F$ ．すると学習のための目的関数は次のように表現される．

$\displaystyle \mathrm{Loss}(F):=k-\mathrm{tr}(CFF^\dagger)$

$C=YY^\dagger\in\mathcal{P}$ が教師データで，この目的関数は微分が可能であるためニューラルネット $\varphi_\theta$ はbackpropを使って学習が可能．さらにこの方法の良いところは $\mathcal{F}$ が $\mathbb{R}^d$ の場合に限らず，例えばKLダイバージェンスを使った確率分布の分割が目的の場合にはニューラルネットの最終層にsoftmaxを使うことで $\mathcal{F}$ は $d$ 次元の単体上に構成することができる．

まとめ

今回証明までは読めてないのでなんとも言えない部分が多くなってしまった．とりあえずニューラルネットを使った非線形の変換をgraph-based clusteringの枠組みに持って行って，離散最適化問題を緩和することでうまいことbackpropの枠組みに落とし込んだというのが大体の流れ．特に目的関数の勾配がclosed-formに求まることが論文の推しでこの界隈で初めてのアプローチと言っていた．

なんとなくgraph-based clusteringとDNNはもう少しいろんなことに使えそうな気がするけど意外と論文は多くない気がする．

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

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

Deep Spectral Clustering Learningを読んだのでメモ