2018-08-16

Spectral Networks and Deep Locally Connected Networks on Graphsを読んだのでメモ

はじめに

Spectral Networks and Deep Locally Connected Networks on Graphsを読んだのでメモ．前回spectral clusteringの勉強の中でgraph Laplacianについて触れたので，せっかくだから今一度いわゆるgraph convolution関連の論文を読み漁ろうかなと．この論文は2013年の論文で，サーベイ不足でなければ世間で言われているgraph convolutionをちゃんと定式化した最初の論文．

CNNとgraph

Convolutional Neural Networks (CNNs)は基本的にregular grid上のデータ(画像や動画など)を処理する上で優れた性能を発揮している．特に，そのregular gridの構造をうまく使うことでパラメータ数の大きな削減ができていることがポイント．具体的には以下の3つがCNNの重要な点．

The translation structure (一般的な線形写像の代わりにfilterを使うことによるweight sharing)
The metric on the grid (入力信号に比べて非常に小さいサイズのフィルタの適用)
The multi scale dyadic clustering of the grid (strideが2以上のconvolutionやpoolingによるsubsampling)

ただし，CNNはregular gridでない，一般的なgraph構造を持つデータには適用できない．そこでここではCNNの拡張として2つの構造を提案する．最初に2.と3.を一般のgraphに拡張したSpatial Constructionを導入し，次にFourier domainにおける畳み込みを使うSpectal Constructionを導入する．

Spatial Construction

入力データとして重み付きグラフ $G=(\Omega, W)$ を考える． $\Omega$ はサイズ $m$ の離散集合でグラフの頂点を表現するもの． $W$ は $m\times m$ の要素が非負の対象行列でいわゆる重み付きの隣接行列．

$W$ における局所性

局所性(隣接関係)はグラフにおいて簡単に一般化が可能．例えば， $W$ における隣接の定義はある閾値 $\delta\gt 0$ を超えるものとして以下のように記述可能．

$\displaystyle N_\delta(j)=\{i\in\Omega :W_{ij}\gt\delta\}$

この定義によって与えられる隣接関係を使えば，局所的な接続のみを見ることでCNNと同様にパラメータ数を減らすことができる，

グラフ上でのMultiresolution

CNNで使われるpooling等によるsubsampling layerはgridのmultiscale clusteringとして考えることが可能．multiscael clusteringはクラスタに含まれる全ての頂点の持つ特徴量を入力として，クラスタの代表値として一つの特徴量を出力する関数として考えることができる．クラスタリングのためのクラスタはgraph Laplacianの文脈で様々な研究がされているためここではあまり深入りせず，naive agglomerative methodを使ってクラスタを決めるとのこと．このクラスタリングのクラスタ数によってグラフの解像度が決定する．

Deep locally connected networks

グラフにおける局所性と解像度が定義できたので一般化されたネットワークを導入する．まずネットワークによる計算の前にグラフのmultiscale clusteringから始める．ここでは $K$ 個のスケールを考える．入力として $\Omega_0=\Omega$ を定義し，各スケール $k=1,\dots,K$ におけるグラフのクラスタリング結果を $\Omega_k$ とする．ただし， $\Omega_k$ は $\Omega_{k-1}$ を $d_k$ 個のクラスタに分けた結果．さらに， $k$ における隣接関係は次のように与えられる．

$\displaystyle \mathcal{N}_k=\{\mathcal{N}_{k,i};i=1,\dots,d_{k-1}\}$

以上を使って，ネットワークの第 $k$ 層を定義する。入力は $\Omega_0$ で定義される実数の信号とし， $f_k$ を第 $k$ 層のフィルタの数とする．ネットワークの第 $k$ 層は $\Omega_{k-1}$ で記述される $f_{k-1}$ 次元の信号を $\Omega_k$ で記述される $f_k$ 次元の信号へと変換する．

より一般的に， $k$ 層目の入力を $x_k\in\mathbb{R}^{d_{k-1}\times f_{k-1}}$ とすればその出力 $x_{k+1}$ は次のように記述される．

$\displaystyle x_{k+1,j}=L_kh\left(\sum_{i=1}^{f_{k-1}}F_{k,i,j}x_{k,i}\right)\:\:(j=1,\dots,f_k)$

$F_{k,i,j}\in\mathbb{R}^{d_{k-1}\times d_{k-1}}$ は隣接関係 $\mathcal{N}_k$ に従って定義されるスパースな行列． $L_k$ は出力を $\Omega_k$ に従ってクラスタリングするプーリングの操作を表す．

論文の文章を無視して簡単にまとめると，上の式の $i,j$ はそれぞれCNNでいう入力のチャネルと出力のチャネルを表していて， $F_{k,i,j}$ は隣接関係があるとこのみ値を持つ $d_{k-1}\times d_{k-1}$ 行列，すなわち $F_k$ 自体は $F_k\in\mathbb{R}^{f_{k-1}\times f_k\times d_{k-1}\times d_{k-1}}$ になる．また $x_{k.i}\in\mathbb{R}^{d_{k-1}}$ から $F_{k,i,j}x_{k,i}$ は行列とベクトルの積になっていて，要は隣接関係のあるノードにだけ重みをかけて総和を取る処理になっている．それに加えて $\sum_{i=1}^{f_{k-1}}$ でチャネルでの総和を取っているため，CNNと同一の処理（空間方向，チャネル方向に重みをかけて総和）になっていることがわかる．

ここでは隣接関係 $\mathcal{N}_k$ は次の手順によって得られる．

$\displaystyle W_0=W \\ \displaystyle A_k(i,j)=\sum_{s\in\Omega_k(i)}\sum_{t\in\Omega_k(j)}W_{k-1}(s,t),\:(k\leq K) \\ \displaystyle W_k=\mathrm{rownormalize}(A_k),\:(k\leq K) \\ \displaystyle \mathcal{N}_k=\mathrm{supp}(W_k),\:(k\leq K)$

またクラスタリング結果 $\Omega_k$ はここでは $\epsilon$ coveringで与える． $\epsilon$ coveringは類似度カーネル $K$ (ガウスカーネル等)とグラフの分割結果 $\mathcal{P}=\{\mathcal{P}_1,\dots,\mathcal{P}_n\}$ を使って $\sup_n\sup_{x,x'\in\mathcal{P}_n}K(x,x')\geq\epsilon$ として分割を与える方法で，簡単にいってしまえば以前のspectral clusteringの勉強でやったfully connected graphに閾値を設けてグラフを分割するという感じ．

ここで $S_k$ を各ノードの隣接ノード数の平均とすれば， $k$ 層における学習パラメータのオーダーは $\mathcal{O}(S_k\cdot|\Omega_k|\cdot f_k\cdot f_{k-1})$ となる．

ただ，論文にも書いてあるよう，隣接関係はデータごとに違うためweight shareの構造を導入するのは容易ではなく，単純に実装してしまえば $F_k\in\mathbb{R}^{f_{k-1}\times f_k\times d_{k-1}\times d_{k-1}}$ を学習パラメータとして持つことになる．一応グラフ全体を低次元空間に埋め込むというのが回避策として書かれているが，この論文で考えているようなデータではそこまで高次元のものはほとんど出てこないからおっけー的なことも主張している．

Spectral Construction

今度はgraph Laplacianの固有値を使った畳み込みの一般化を考える．

重み付きグラフ上での調和解析

ここではgraph Laplacianの呼び方は前回の勉強のメモに合わせて， $L-D-W$ をunnormalized Laplacian， $\mathcal{L}=I-D^{-1/2}WD^{-1/2}$ をnormalized Laplacianとする（論文ではそれぞれcombinatorial Laplacian，graph Laplacianと定義している）．ここではシンプルにunnormalized Laplacianを使う．仮に信号 $x$ を $m$ 次元のベクトルとすれば，ノード $i$ における信号の変化の滑らかさ $||\nabla x||^2_W$ (グラフにおける周波数)は次のように定義できる．

$\displaystyle ||\nabla x||^2_W(i)=\sum_jW_{ij}[x(i)-x(j)]^2$

さらに全体としては

$\displaystyle ||\nabla x||^2_W=\sum_i\sum_jW_{ij}[x(i)-x(j)]^2$

となる．上記の定義に従えば最も滑らかなベクトルは常に

$\displaystyle v_0=\mathop{\mathrm{argmin}}_{x\in\mathbb{R}^m,||x||=1}||\nabla x||^2_W=(1/\sqrt{m})1_m$

となり，続く値

$\displaystyle v_i=\mathop{\mathrm{argmin}}_{x\in\mathbb{R}^m,||x||=1,x\perp\{v_0,\dots,v_{i-1}\}}||\nabla x||^2_W$

は $L$ の固有ベクトルで与えられる．最小化問題の解 $v_i$ が $L$ の固有ベクトルから得られるのは $2x'Lx=\sum_i\sum_jW_{ij}[x(i)-x(j)]$ の関係からわかる．この関係の証明は前の記事参照．各固有ベクトルに対応する固有値 $\lambda_i$ jはgridに定義された信号のフーリエ係数として見ることができ，同様に固有ベクトルはフーリエ基底として考えられる．直感的なところではグラフにおける周波数 $||\nabla x||^2_W$ のargminがgraph Laplacianの固有ベクトルから与えられることと，固有値と固有ベクトルの関係から $Lx=\lambda x$ の関係が成り立つ，すなわちグラフの構造を表す $L$ が固有ベクトル（フーリエ基底）とその固有値による線形結合で与えられることからフーリエ変換としてみなせるというもの？（グラフ信号処理ど素人の自分なりの解釈なので自信はない）

以上を踏まえれば信号の変換はフーリエ基底の結合係数を変化させることと考えられる，すなわち固有ベクトルとdiagonalな行列の積として考えられるためパラメータ数は $\mathcal{O}(m^2)$ から $\mathcal{O}(m)$ として表現できる．

Extending convolutions

ここまでの関係を使って，ネットワークの定義を行う． $V$ をgraph Laplacianの固有ベクトルとする．すると第 $k=1,\dots,K$ 層における入力 $x_k\in\mathbb{R}^{|\Omega|\times f_{k-1}}$ に対する変換はsubsamplingを考えなければ次のようにかける．

$\displaystyle x_{k+1,j}=h\left(V\sum_{i=1}^{f_{k-1}}F_{k,i,j}V^Tx_{k,i}\right)\:\:(j=1,\dots,f_k)$

$F_{k,i,j}$ は対角行列で， $h$ は非線形関数を表す．実験的に，graph Laplacianの最初の $d$ 個の固有ベクトルを使う場合の方がいい場合があるらしい（つまりは高周波成分は無視するということ）．仮に $d$ 個の固有ベクトルを使ったとすれば，学習パラメータのオーダーは $\mathcal{O}(f_{k-1}\cdot f_k\cdot d)$ になる．ただし，計算コストの面においては $V$ と $V^T$ の積があるため非常に大きくなっていることには注意（加えてgraph Laplacianの固有ベクトルを求める必要もある）．

まとめ

この論文が出た時点ではまだまだgraph convolutionは問題点が多いから，最新の論文がどれくらい進化しているか楽しみ．また続けて関連論文を読んで行きたいところ．

2018-08-11

A Tutorial on Spectral Clusteringを読んだのでメモその２

graph clustering spectral clustering

はじめに

A Tutorial on Spectral Clusteringを読んだのでメモその２．準備ができたのでいよいよspectral clusteringについて

Spectral Clustering Algorithms

ここでは $n$ 個のデータ点 $x_1,\dots,x_n$ が与えられ，類似度関数 $s_{ij}=s(x_i,x_j)$ が対象(入力を入れ替えても出力が変わらない)かつ非負の値を返す関数として定義する．また類似度行列を $S=(s_{ij})_{i,j=1\dots n}$ として定義する．

Spectral clusteringはunnormalized Laplacianを使うかnormalized Laplacianを使うかで，unnormalized spectral clusteringとnormalized spectral clusteringに分けられる．

Unnormalized spectral clustering

入力として，類似度行列 $S\in\mathbb{R}^{n\times n}$ ，クラスタ数 $k$ が与えられる．

その１の記事で紹介した方法のどれか( $k$ -nearest neighborなど)を用いてグラフを構成し，重み付き隣接行列 $W$ を得る．
そこからunnormalized Laplacian $L$ を計算し，Laplacianの固有ベクトルを順に $k$ 個取り出した集合 $u_1,\dots,u_k$ を得る
$U\in\mathbb{R}^{n\times k}$ を $k$ 個の固有ベクトルを列にもつ行列とし， $y_i\in\mathbb{R}^k$ を $U$ の $i$ 番目の行とする．
k-meansのアルゴリズムを用いて点 $(y_i)_{i=1,\dots,n}$ を $k$ 個のクラスタ $C_1,\dots,C_k$ にクラスタリングしていく．

Normalized spectral clustering according to Phi and Malik (2000)

入力として，類似度行列 $S\in\mathbb{R}^{n\times n}$ ，クラスタ数 $k$ が与えられる．

その１の記事で紹介した方法のどれかを用いてグラフを構成し，重み付き隣接行列 $W$ を得る．
そこからunnormalized Laplacian $L$ を計算し，Laplacianの一般化固有値問題 $Lu=\lambda Du$ から得られる一般化固有ベクトルを順に $k$ 個取り出した集合 $u_1,\dots,u_k$ を得る．
$U\in\mathbb{R}^{n\times k}$ を $k$ 個の固有ベクトルを列にもつ行列とし， $y_i\in\mathbb{R}^k$ を $U$ の $i$ 番目の行とする．
k-meansのアルゴリズムを用いて点 $(y_i)_{i=1,\dots,n}$ を $k$ 個のクラスタ $C_1,\dots,C_k$ にクラスタリングする．

このアルゴリズムは一般化固有値問題の解を用いていて，命題3からわかるように，得られる固有ベクトルは $L_{rw}$ の固有ベクトルと等しい．よってアルゴリズム上はunnormalized Laplacianを使っているが，理論的にはnormalized Laplacianである $L_{rw}$ を使っている．

Normalized spectral clustering according to Ng, Jordan, and Weiss (2002)

入力として，類似度行列 $S\in\mathbb{R}^{n\times n}$ ，クラスタ数 $k$ が与えられる．

その１の記事で紹介した方法のどれかを用いてグラフを構成し，重み付き隣接行列 $W$ を得る．
そこからnormalized Laplacian $L_{sym}$ を計算し，Laplacianの固有ベクトルを順に $k$ 個取り出した集合 $u_1,\dots,u_k$ を得る．
固有ベクトルを列ベクトルとする行列 $U\in\mathbb{R}^{n\times k}$ を作る．
各行のノルムを $t_{ij}=u_{ij}/(\sum_ku_{ik}^2)^{1/2}$ のように1になるように正規化することで行列 $T\in\mathbb{R}^{n\times k}$ を作る．
$T$ の $i$ 番目の行を $(y_i)_{i=1,\dots,n}$ とする．k-meansを用いて $y_i$ を $k$ 個のクラスタ $C_1,\dots,C_k$ にクラスタリングする．

3つのアルゴリズムは異なるgraph Laplaciansを使うだけでおおよその手順は等しい．どのアルゴリズムも肝となるのはデータ点 $x_i$ の表現を $y_i\in\mathbb{R}^k$ に変える事にある．

資料ではtoyデータに対して $k$ -nnを使ってグラフを作った際とfully connectedによりグラフを作った際，さらにんそれぞれのグラフ構成法においてnormalized spectral clusteringをした場合とunnormalized spectral clusteringをした場合の全4パターンで固有値と固有ベクトルを可視化して考察を行っている．ここでは詳細は割愛．

Graph cut point of view

ここではgraphを分割するという観点からspectral clusteringを見る．隣接行列 $W$ を持つsimilarity graphが与えられた時，最も単純かつ直接的なグラフ分割方法はmincut問題を解く事．つまり重みの小さい(=類似度の低い)エッジを切る事でクラスタを形成しようというもの．これを定義するために再度 $W(A,B):=\sum_{i\in A,k\in B}w_{ij}$ ， $A$ の補集合 $\bar{A}$ を与える． $k$ 個の部分集合が与えられた時，mincutは以下を最小化する分割 $A_1,\dots,A_k$ を探す．

$\displaystyle \mathrm{cut}(A_1,\dots,A_k):=\frac{1}{2}\sum_{i=1}^kW(A_i,\bar{A}_i)$

上記のmincutは $k=2$ においては特別簡単に計算が可能ということが知られているが，多くの場合は良い分割を導く事は難しく，また一般的にはmincutの解は単純にグラフから一つの頂点を分割する事であり，クラスタリングの目的に合わない．これを避ける一つの方法として集合 $A_1,\dots,A_k$ は十分大きいという条件を陽に加えることがあげられる．各集合が十分大きいという条件を付け加えた目的関数として有名なものはRatioCut (Hagen and Kahng, 1992)とnormalized cut(Ncut) (Shi and Malik, 2000)の二つがある．それぞれの目的関数は以下．

$\displaystyle \mathrm{RatioCut}(A_1,\dots,A_k):=\frac{1}{2}\sum_{i=1}^k\frac{W(A_i,\bar{A}_i)}{|A_i|}=\sum_{i=1}^k\frac{\mathrm{cut}(A_i,\hat{A}_i)}{|A_i|} \\ \displaystyle \mathrm{Ncut}(A_i,\dots,A_k):=\frac{1}{2}\sum_{i=1}^k\frac{W(A_i,\bar{A}_i)}{\mathrm{vol}(A_i)}=\sum_{i=1}^k\frac{\mathrm{cut}(A_i,\hat{A}_i)}{\mathrm{vol}(A_i)}$

これら二つの目的関数はクラスタ $A_i$ が十分に小さくない場合，小さな値をとる．特に関数 $\sum_{i=1}^k(1/|A_i|)$ の最小値は全ての $|A_i|$ が等しい時に達成する．また，関数 $\sum_{i=1}^k(1/\mathrm{vol}(A_i))$ も同様に全ての $\mathrm{vol}(A_i)$ が等しい時に最小になる．すなわち両方の目的関数が達成しようとしているのはクラスタ間の大きさのバランスを取る事で，それぞれクラスタの大きさを頂点の数で測るか，エッジの重みで測るかの違いしかない．ただし，基本的にmincut問題を解く単純な方法はNP hardであることが言われている．Spectral clusteringはNP hardな問題を緩和した解き方で，ここでは緩和Ncutがnormalized spectral clusteringを，緩和RatioCutがunnormalized spetal clusteringを導くことを見る．

Approximating RatioCut for $k=2$

手始めに緩和が最も理解しやすい $k=2$ の場合のRatioCutを見る．目標は以下の最小化問題を解くこと．

$\displaystyle \min_{A\subset V}\mathrm{RatioCut}(A,\bar{A})$

まず，この式をより扱いやすい形に変形する．部分集合 $A\subset V$ が与えられた時，ベクトル $f=(f_1,\dots,f_n)'$ を以下のように定義する．

$\displaystyle f_i=\left\{ \begin{array}{} \sqrt{|\bar{A}|/|A|}\:\:\:\mathrm{if}\:v_i\in A \\ -\sqrt{|A|/|\bar{A}|}\:\:\mathrm{if}\:v_i\in\bar{A} \end{array} \right.$

Unnormalized graph Laplacianを使えば，RatioCutの目的関数は以下のように導ける．

$\displaystyle f'Lf=\frac{1}{2}\sum_{i,j=1}^nw_{ij}(f_i-f_j)^2 \\ \displaystyle =\frac{1}{2}\sum_{i\in A,j\in\bar{A}}w_{ij}\left(\sqrt{\frac{|\bar{A}|}{|A|}}+\sqrt{\frac{|A|}{|\bar{A}|}}\right)^2+\frac{1}{2}\sum_{i\in\bar{A},j\in A}w_{ij}\left(-\sqrt{\frac{|\bar{A}|}{|A|}}-\sqrt{\frac{|A|}{|\bar{A}|}}\right)^2 \\ \displaystyle =\mathrm{cut}(A,\bar{A})\left(\frac{|\bar{A}|}{|A|}+\frac{|A|}{|\bar{A}|}+2\right) \\ \displaystyle =\mathrm{cut}(A,\bar{A})\left(\frac{|A|+|\bar{A}|}{|A|}+\frac{|A|+|\bar{A}|}{|\bar{A}|}\right) \\ \displaystyle =|V|\cdot\mathrm{RatioCut}(A,\bar{A})$

2行目は $f$ の定義に従って場合分けをし，2乗の項を展開すれば3行目が得られる．また， $|A|+|\bar{A}|=|V|,\:|A|+|\bar{A}|=\sum_i|A_i|$ の関係を使えば最後の式が導ける．また， $f$ に関して以下が成り立つ事に注意．

$\displaystyle \sum_{i=1}^nf_i=\sum_{i\in A}\sqrt{\frac{|\bar{A}|}{|A|}}-\sum_{i\in\bar{A}}\sqrt{\frac{|A|}{|\bar{A}|}}=|A|\sqrt{\frac{|\bar{A}|}{|A|}}-|\bar{A}|\sqrt{\frac{|A|}{|\bar{A}|}}=0 \\ \displaystyle ||f||^2=\sum_{i=1}^nf_i^2=|A|\frac{|\bar{A}|}{|A|}+|\bar{A}|\frac{|A|}{|\bar{A}|}=|\bar{A}|+|A|=n$

以上のことを用いればRatioCutを使った最小化問題は以下のように記述できる．

$\displaystyle \min_{A\subset V}f'Lf\:\mathrm{subject}\:\mathrm{to}\:f\perp\mathbb{1},\:||f||=\sqrt{n}, \: f_i=\left\{ \begin{array}{} \sqrt{|\bar{A}|/|A|}\:\:\:\mathrm{if}\:v_i\in A \\ -\sqrt{|A|/|\bar{A}|}\:\:\mathrm{if}\:v_i\in\bar{A} \end{array} \right.$

これは $f$ が離散値を取ることから離散最適になっていて，変わらずNP hardになっている．そこで $f$ の元の定義を忘れて $f_i\in\mathbb{R}$ とすることで緩和することを考える．すなわち

$\displaystyle \min_{f_i\in\mathbb{R}^n}f'Lf\:\mathrm{subject}\:\mathrm{to}\:f\perp\mathbb{1},\:||f||=\sqrt{n}$

と緩和する．この最適化問題はRayleigh-Ritz theoremより $L$ の2番目に小さい固有値に対応する固有ベクトル $f$ によって解が与えられる．ただし，グラフの分割結果を得るためには実数値解となっている $f$ を離散値である指示ベクトルに変える必要がある．単純な方法としては以下のような指示関数によって得られる．

$\displaystyle \left\{ \begin{array}{} v_i\in A\:\:\:\mathrm{if}\:f_i\geq 0 \\ v_i\in\bar{A}\:\:\:\mathrm{if}\:f_i\lt 0 \end{array} \right.$

以上が $k=2$ の場合のunnormalized spectral clusteringのアルゴリズムになっている．

Approximating RatioCut for arbitrary $k$

次に一般的な $k$ の場合のRatioCutの最小化問題の緩和法を考える．グラフ $V$ に関して $k$ 個の集合 $A_1,\dots,A_k$ が与えられた時，集合 $j$ の指示ベクトル $h_j=(h_{1,j},\dots,h_{n,j})'$ を以下のように定義する．

$\displaystyle h_{i,j}=\left\{ \begin{array}{} 1/\sqrt{|A_j|}\:\:\:\mathrm{if}\:v_i\in A_j \\ 0\:\:\:\:\:\mathrm{otherwise} \end{array} \right. (i=1,\dots,n;\:j=1,\dots,k)$

ここで $k$ 個の指示ベクトルを列ベクトルとして持つ行列を $H\in\mathbb{R}^{n\times k}$ として定義すれば，各指示ベクトルは直交していることから $H$ は直交行列( $H'H=I$ )になる．前節と同様に計算を行えば( $f$ を $h_i$ に変えて計算すれば)以下の関係が導かれる．

$\displaystyle h_i'Lh_i=\frac{\mathrm{cut}(A_i,\bar{A}_i)}{|A_i|}$

$h'_iLh_i$ とある一つのクラスタ $i$ に関する式になっているのは $H$ が直交行列，すなわち異なる行同士の積は0になるため．すなわちクラスタごとに独立に計算が可能で，上の式を行列 $H$ を用いて次のように表現する事にする．

$\displaystyle h_i'Lh_i=(H'LH)_{ii}$

すると最終的な目的関数は以下のように表現できる．

$\displaystyle \mathrm{RatioCut}(A_1,\dots,A_k)=\sum_{I=1}^kh_i'Lh_i=\sum_{i=1}^k(H'LH)_{ii}=\mathrm{Tr}(H'LH)$

ただし， $\mathrm{Tr}$ は行列のトレースを表す．以上の関係を用いて最小化問題を書き表わせば，

$\displaystyle \min_{A_1,\dots,A_k}\mathrm{Tr}(H'LH)\:\mathrm{subject}\:\mathrm{to}\:H'H=I, \: h_{i,j}=\left\{ \begin{array}{} 1/\sqrt{|A_j|}\:\:\:\mathrm{if}\:v_i\in A_j \\ 0\:\:\:\:\:\mathrm{otherwise} \end{array} \right. (i=1,\dots,n;\:j=1,\dots,k)$

となる．先ほどと同様，やはりこれは離散最適でNP hardなので行列 $H$ を任意の実数値に緩和する．すなわち最適化問題は以下のようになる．

$\displaystyle \min_{H\in\mathbb{R}^{n\times k}}\mathrm{Tr}(H'LH)\:\mathrm{subject}\:\mathrm{to}\:H'H=I$

これは一般的なトレースの最小化問題になっていて，やはり先ほどと同様Rayleight-Ritz theoremから $L$ の $k$ 個の固有ベクトルから構成された行列を $H$ として選ぶことで解が得られる．これは $H$ がunnormalized spectral clusteringで使われていた行列 $U$ と等しいことを表す．最終的な解を得るためにはやはり実数値として得られた解 $H$ を離散値として求め直す必要がある．これは $U$ の各行をデータ点としてk-meansをすることで実現される．

Approximating Ncut

同様に今度はNcutについて最小化問題の緩和を考える．まずは $k=2$ の場合について．Ncutではクラスタの指示ベクトル $f$ を以下のように定義する．

$\displaystyle f_i=\left\{ \begin{array}{} \sqrt{\frac{\mathrm{vol}(\bar{A})}{\mathrm{vol}(A)}}\:\:\:\mathrm{if}\:v_i\in A \\ -\sqrt{\frac{\mathrm{vol}(A)}{\mathrm{vol}(\bar{A})}}\:\:\:\mathrm{if}\:v_i\in\bar{A} \end{array} \right.$

単純にRatioCutの $|A|$ が $\mathrm{vol}(A)$ に変わっただけ．なので満たす性質や計算結果もほぼ変わらず， $(Df)'\mathbb{1}=0,\:f'Df=\mathrm{vol}(V),$ and $f'Lf=\mathrm{vol}(V)\mathrm{Ncut}(A,\bar{A})$ が得られる．するとNcutの最小化問題は以下のようにかける．

$\displaystyle \min_Af'Lf\:\mathrm{subject}\:\mathrm{to}\:Df\perp\mathbb{1},\:f'Df=\mathrm{vol}(V), \: f_i=\left\{ \begin{array}{} \sqrt{\frac{\mathrm{vol}(\bar{A})}{\mathrm{vol}(A)}}\:\:\:\mathrm{if}\:v_i\in A \\ -\sqrt{\frac{\mathrm{vol}(A)}{\mathrm{vol}(\bar{A})}}\:\:\:\mathrm{if}\:v_i\in\bar{A} \end{array} \right.$

やはり，RatioCutと同様に $f$ を任意の実数値に緩和する．

$\displaystyle \min_{f\in\mathrm{R}^n}f'Lf\:\mathrm{subject}\:\mathrm{to}\:Df\perp\mathbb{1},\:f'Df=\mathrm{vol}(V)$

さらに， $g:=D^{1/2}f$ を導入すれば

$\displaystyle \min_{g\in\mathrm{R}^n}g'D^{-1/2}LD^{-1/2}g\:\mathrm{subject}\:\mathrm{to}\:g\perp D^{1/2}\mathbb{1},\:||g||^2=\mathrm{vol}(V)$

と書き換えることができ， $D^{-1/2}LD^{-1/2}=L_{sym}$ であり， $L_{sym}$ の最小固有値に対応する固有ベクトルが $D^{1/2}\mathbb{1}$ であることを思い出せば，Rayleight-Ritz theoremから解 $g$ は $L_{sym}$ の2番目の固有ベクトルで与えられる．

続いて $k\gt 2$ の場合を考える．クラスタの指示ベクトル $h_j=(h_{1,j},\dots,h_{n,j})'$ を以下のように定義する．

$\displaystyle h_{i,j}=\left\{ \begin{array}{} 1/\sqrt{\mathrm{vol}(A_j)}\:\:\:\mathrm{if}\:v_i\in A_j \\ 0\:\:\:\:\:\mathrm{otherwise} \end{array} \right. (i=1,\dots,n;\:j=1,\dots,k)$

やはりRatioCutの $|A|$ が $\mathrm{vol}(A)$ に変わっただけなのでRatioCutと同様の導出から， $H'H=I,\:h_i'Dh_i=1,\:h_i'Lh_i=\mathrm{cut}(A_i,\bar{A}_i)/\mathrm{vol}(A_i)$ が導かれる．するとNcutの最小化問題は以下のようにかける．

$\displaystyle \min_{A_1,\dots,A_k}\mathrm{Tr}(H'LH)\:\mathrm{subject}\:\mathrm{to}\:H'DH=I,\\ \displaystyle h_{i,j}=\left\{ \begin{array}{} 1/\sqrt{\mathrm{vol}(A_j)}\:\:\:\mathrm{if}\:v_i\in A_j \\ 0\:\:\:\:\:\mathrm{otherwise} \end{array} \right. (i=1,\dots,n;\:j=1,\dots,k)$

ここで $T=D^{1/2}H$ を導入し，Tが任意の実数を要素に持つように緩和すれば，最小化問題は以下のように緩和できる．

$\displaystyle \min_{T\in\mathbb{R}^{n\times k}}\mathrm{Tr}(T'D^{-1/2}LD^{-1/2}T)\:\mathrm{subject}\:\mathrm{to}\:T'T=I$

この式も一般的なトレースの最小化問題でその解は $L_{sym}$ の $k$ 個の固有ベクトルによって構成される行列によって与えられる．この最小化問題はnormalized spectral clusteringになっていることが証明されている．

Comments on the relaxation approach

今まで色々と導出してきた緩和された最適化問題は元の最適化問題と比べて解の良さは保証されていない．それどころか，仮に $A_1,\dots,A_k$ を真のRatioCutの最小化の解として， $B_1,\dots,B_k$ を緩和された問題の解とすれば， $\mathrm{RatioCut}(B_1,\dots,B_k)-\mathrm{RatioCut}(A_1,\dots,A_k)$ は任意に大きくなるらしい．これについてはGuattery and Miller (1998)で言及されているようで，論文中で著者らはcockroach graphsなるグラフを取り上げて考えている．cockroach graphsは梯子状に $4k$ 個のデータが分布していて，RatioCutによって二つのクラスタに分割されることが望ましいような形になっている．しかも分割されたグラフは $|A|=|\bar{A}|=2k$ ， $\mathrm{cut}(A,\bar{A})$ となるように設計されている．にも関わらず，著者らはunnormalized graph Laplacianを使ったunnormalized spectral clusteringは常に $\mathrm{RatioCut}(A,\bar{A})=2/k,\:\mathrm{RatioCut}(B,\bar{B})=1$ となることを証明したらしいこれが意味するところは，理想的なカットに対し，RatioCutは $k/2$ 倍悪い結果を導くことを意味している．一般的にbalanced graph cutsを近似する効果的なアルゴリズムは存在しないということが知られていて，しかも近似問題自身がNP hardらしい．ただ，現状いろんな近似方法が提案されていて実験的には良い結果を導いている上，基本的な線形代数の問題として解けることから現状いろんなところで使われてるとのこと．

まとめ

ようやく具体的なアルゴリズムが見えて，なんとなく前に読んだLocal and Global Optimization Techniques in Graph-based Clusteringの気持ちが少しだけわかってきた気がする．

にしても線形代数をゴリゴリやって解析的な解が見えるアルゴリズムはやっぱりいいなあという気持ち．とりあえず普通にスルーしたRayleigh-Ritz theoremを勉強しなきゃ何も言えないけど．

2018-08-10

A Tutorial on Spectral Clusteringを読んだのでメモその１

graph clustering graph laplacian

はじめに

A Tutorial on Spectral Clusteringを読んだのでメモ．タイトルからわかるようにspectral clusteringを基本の部分から解説した資料．構成としてはsimilarity graphs $\rightarrow$ graph laplacians $\rightarrow$ spectral clustering $\rightarrow$ アルゴリズムの解析という感じ．とりあえずここではspectral clusteringの手前のグラフ理論的な話まで．

Similarity graphs

データ点 $x_1,\dots,x_n$ が与えられた時，データ点のペア $x_i,x_j$ の類似度を $s_{ij}\geq 0$ とする．ここで，データ間の類似度よりも多くの情報を持っていないとすれば，データを表現する良い方法はsimilarity graph $G=(V,E)$ を作ること．各頂点 $v_i$ はデータ点 $_i$ に対応し，二つのデータ点間の類似度 $s_{ij}$ が正またはある閾値より大きいとすれば，グラフのエッジは $s_{ij}$ によって重み付けられる．このようにグラフのエッジがデータ間の類似度に基づくものをsimilarity graphという．このsimilarity graphを用いてクラスタリングの問題を考えれば，エッジの重みが大きいデータ同士は同じクラスタに所属し，エッジの重みが小さいデータ同士は異なるクラスタに所属するということが直感的に言える．この考えを定式化するために，まずは基本的なグラフの概念を導入する．

graph notation

まず $G=(V,E)$ を無向グラフとして定義する．ただし，二つの頂点 $v_i,v_j$ を結ぶ各エッジは非負の重み $w_{ij}$ を持つ，重み付きのグラフとなっている．グラフの重み付き隣接行列(adjacency matrix)を $W=(w_{ij})_{i,j=1,\dots,n}$ と定義し， $w_{ij}=0$ ならば $v_i,v_j$ を結ぶエッジが存在しないことを意味する．また， $G$ が無向グラフであることから $w_{ij}=w_{ji}$ が成り立つ．頂点 $v_i\in V$ の度数(degree)を次のように定義する．

$\displaystyle d_i=\sum_{j=1}^nw_{ij}$

度数 $d_1,\dots,d_n$ を対角成分に持つ対角行列を度数行列(degree matrix)を $D$ と定義する．また，頂点の部分集合 $A\subset V$ が与えられた時，その補集合を $A$ を用いて $V\setminus A$ として記述する．さらに $v_i\in A$ を満たすかどうかを示す指示ベクトル(indicator vector)を $\mathbb{1}_A=(f_1,\dots,f_n)'\in\mathbb{R}^n$ で定義し， $v_i\in A$ が真ならば $f_i=1$ ，それ以外なら $f_i=0$ となる．指示ベクトルは式を見ればわかるように，部分集合に含まれる頂点の個数分だけ成分に1を持つベクトルになっている．

ここで部分集合 $A\subset V$ の大きさを測る以下の二つの方法について考える．

$\displaystyle |A|:=\:\mathrm{the}\:\mathrm{number}\:\mathrm{of}\:\mathrm{vertices}\:\mathrm{in}\:A \\ \displaystyle \mathrm{vol}(A):=\sum_{i\in A}d_i$

$|A|$ は頂点の数により定義され， $\mathrm{vol}(A)$ は $A$ に含まれる頂点から伸びる全てのエッジの重みの和によって定義される． $A$ に含まれる二つの頂点がpathを持ち(どこか他のノードを介してでも繋がっている状態)，間にある全ての頂点が $A$ に含まれている場合， $A$ はconnectedであるといい， $A$ がconnectedかつ， $A$ と $\bar{A}$ の頂点同士がpathをもたない(connectedでない)場合， $A$ をconnected componentと呼ぶ．

Different similarity graphs

Similarity graphを構成することのゴールはデータ間の局所的な隣接関係をモデル化することで，その方法にはいくつか代表的な方法がある．

The $\epsilon$ -neighborhood graph

これは距離がある閾値 $\epsilon$ より小さいデータのペア全てにエッジを張る方法．この方法は接続されたデータ間の距離のスケールが大体同じ(ほぼ $\epsilon$ )になり，重みをつけたところでグラフの持つ情報はほとんど増えないため(ここの理由がよくわからない)重みのないグラフとして構成するのが一般的．

$k$ -nearest neighbor graphs

ここのゴールは頂点 $v_j$ が $v_i$ の $k$ 近傍に含まれるときに二つの頂点を接続すること．ただし，この定義だと近傍の関係性が非対称であることから有向グラフを構成する場合がある．そこで $k$ 近傍によって作られるグラフを無向グラフにする二つの方法を紹介する．一つは単純にエッジの向きを無視する方法，すなわちどちらか一方の頂点がもう一方の頂点の $k$ 近傍であればエッジを張る方法で，これは $k$ -nearest neighbor graphと呼ばれる．もう一つは双方向からエッジが張られる場合のみエッジを張る，すなわちどちらの頂点も相手の $k$ 近傍に含まれる時のみエッジを張る方法で，これはmutual $k$ -nearest neighbor graphと呼ばれる．どちらの場合でグラフを作った場合でも，endpointの類似性からエッジの重み付けを行う．

The fully connected graph

これは，単純に正の類似度を持つ全てのデータのペアにエッジを張る方法でエッジの重みは $s_{ij}$ になる．グラフは局所的な隣接関係を表現すべきであるため，この構成方法は類似度関数そのものが局所的な隣接関係を捉えているような場合のみ有効に働く．類似度関数の例としてはGaussian similarity function $s(x_i,x_j)=\exp(-||x_i-x_j||^2/(2\sigma^2)$ などがあげられ，この場合 $\sigma$ がどれくらい離れた頂点を見るか調節する．これは丁度 $\epsilon$ -neighborhood graphの $\epsilon$ と似た働きをする．

上記3つの構成方法は全てspectral clusteringで一般的に用いられる．どの構成方法を使えばより良い結果が得られるかという理論的な回答は(このtutorialが執筆された時点では)ないらしい．

Graph laplacians and their basic properties

Spectral clusteringにおいて重要となってくるのはgraph Laplacian matricesで，spectral graph theoryとして古くから研究されているよう．graph convolutional networksなどでもお馴染み．"graph Laplacian"という呼称はいろんなところで使われていて文献によってgraph Laplacianの定義が違うので他の文献を読むときには注意とのこと．

以下， $G$ を無向グラフ， $W$ をグラフの重み行列として扱い， $w_{ij}=w_{ji}\geq 0$ を満たす．また，ここでは固有ベクトルを使うときは正規化されている仮定は置かず，固有ベクトルは値が小さい順に並んでいるものとする．

The unnormalized graph Laplacian

正規化されていないgraph Laplacian matrixを以下のように，度数行列と重み行列の差として定義する．

$\displaystyle L=D-W$

ここではspectral clusteringで必要とされる命題を以下にまとめる．

Proposition 1 (properties of $L$ )

全てのベクトル $f\in\mathbb{R}^n$ に対し次の関係が成り立つ． $\displaystyle f'Lf=\frac{1}{2}\sum_{i,j=1}^nw_{ij}(f_i-f_j)^2$
$L$ は半正定値対称行列
$L$ の最小固有値は0であり，対応する固有ベクトルは $\mathbb{1}$ (成分が全て1のベクトル)となる．
$L$ は $n$ 個の非負の実数固有値を持つ． $0=\lambda_1\leq\lambda_2\leq\dots\leq\lambda_n$

証明

$d_i$ の定義より， $\displaystyle \:\\ \displaystyle f'Lf=f'Df-f'Wf=\sum_{I=1}^nd_if_i^2-\sum_{i,j=1}^nf_if_jw_{ij} \\ \displaystyle =\frac{1}{2}\left(\sum_{i=1}^nd_if_i^2-2\sum_{i,j}^nf_if_jw_{ij}+\sum_{j=1}^nd_jf_j^2\right)=\frac{1}{2}\sum_{i,j=1}^nw_{ij}(f_i-f_j)^2 \\$ 　　　　　　 1行目は $L=D-W$ の関係性と $D$ が対角行列であることから導かれる．また，2行目は $f_i^2$ の項を無理やり二つに分けることで因数分解可能な形にし， $d_i=\sum_jw_{ij}$ を利用して最終的な形を導いた．
$L$ が対称行列であることは $D,W$ が対称行列であることから言える．また全ての $f\in\mathbb{R}^n$ に対して $f'Lf\geq 0$ であることから固有値が0以上，すなわち半正定値であることが言える．
$D$ の $i$ 番目の対角成分は $d_i=\sum_{j=1}^nw_{ij}$ で与えられることから， $L=D-W$ の関係性より $L\mathbb{1}=0$ となる．よって固有値と固有ベクトルの関係性から $L\mathbb{1}=\lambda\mathbb{1}=0\mathbb{1}$ が得られ，固有値0に対応する固有ベクトルは $\mathbb{1}$ であることがわかる．
自明．

また，以下の命題はspectral clusteringを考える上で重要な命題．

Proposition 2 (Number of connected components and the spectrum of $L$ )

$G$ を非負の値で重み付けられた無向グラフとする． $L$ の値0の固有値の数 $k$ はグラフのconnected components $A_1,\dots,A_k$ の数と等しい．また，値0の固有値が張る固有空間は各connected componentsの指示ベクトル $\mathbb{1}_{A_1},\dots,\mathbb{1}_{A_k}$ によって張られる．

証明

$k=1$ の場合について考える． $f$ を値が0の固有値に対応する固有ベクトルとする．すると固有値と固有ベクトルの関係と命題1の1から以下が成り立つ．

$\displaystyle 0=f'Lf=\sum_{i,j=1}^nw_{ij}(f_i-f_j)^2$

$w_{ij}$ は非負であることから全ての項が0の時に成り立つ．つまり，二つの頂点 $v_i,v_j$ が結ばれている時(つまり $w_{ij}\gt 0$ の時)， $f_i=f_j$ が成り立つ必要がある．つまり接続関係にある全ての頂点に対して $f$ は一定である必要がある．グラフがただ一つのconnected componentで構成されている場合，固有値0に対応する固有ベクトルは $\mathbb{1}$ のみを持ち，これはconnected componentの指示ベクトルになっていることがわかる．

次に $k$ が2以上の時について考える．この時，一般性を失うことなく頂点を，所属するconnected componentの順に並べることができる．すると，各頂点は異なるconnected componentに含まれる頂点とは接続を持たないためadjacency matrix $W$ はブロック対角行列になる．よって $L=D-W$ の関係から $L$ も同様にブロック対角行列になる．すなわち $i$ 番目のconnected componentに関数graph Laplacian matrix $L_i$ を対角成分に持つ行列として表現できる． $k=1$ の場合の議論を考えれば各graph Laplacian matrix $L_i$ の0固有値に対応する固有ベクトルはその集合の指示ベクトルになるため， $L$ の0固有値に対応する固有ベクトルは各connected componentの指示ベクトルになることが言える．よって0固有値の個数とconnected componentの数は等しいことが言える．

The normalized graph Laplacians

先ほどまでは正規化されていないgraph Laplacianを扱ってきた．今度は正規化されたgraph Laplacianを考える．正規化されたgraph Laplacianには以下の2種類の表現方法がある．

$\displaystyle L_{sym}:=D^{-1/2}LD^{-1/2}=I-D^{-1/2}WD^{-1/2} \\ \displaystyle L_{rw}:=D^{-1}L=I-D^{-1}W$

$L_{sym}$ は対称行列になっていて， $L_{rw}$ はrandom walkと密接な関係がある．以下に $L_{sym},L_{rw}$ に関する命題を示す．

Proposition 3 (Properties of $L_{sym}$ and $L_{rw}$ )

全ての $f\in\mathbb{R}^n$ において以下が成り立つ．

$\displaystyle f'L_{sym}f=\frac{1}{2}\sum_{i,j=1}^nw_{ij}\left(\frac{f_i}{\sqrt{d_i}}-\frac{f_j}{\sqrt{d_j}}\right)^2$

2. $\lambda$ が固有ベクトル $w=D^{1/2}u$ に対応する $L_{sym}$ の固有値であるとき， $\lambda$ は固有ベクトル $u$ に対応する $L_{rw}$ の固有値になる．

3. $\lambda$ と $u$ が一般化固有値問題 $Lu=\lambda Du$ の解ならば， $\lambda$ は固有ベクトル $u$ に対応する $L_{rw}$ の固有値になる．

4.0固有値に対応する $L_{rw}$ の固有ベクトルは $\mathbb{1}$ ．また，0固有値に対応する $L_{sym}$ の固有ベクトルは $D^{1/2}\mathbb{1}$

5. $L_{sym},L_{rw}$ は共に半正定値で $n$ 個の非負な実数固有値 $0=\lambda_1\leq\dots\leq\lambda_n$ を持つ．

証明

基本的には命題1の1と同様の方針で， $L_{sym}=I-D^{-1/2}WD^{-1/2}$ を代入して解ける．計算式は省略．
$\displaystyle L_{sym}w=D^{-1/2}LD^{-1/2}w=\lambda w \\ \displaystyle D^{-1}LD^{-1/2}w=\lambda D^{-1/2}w \\ \displaystyle L_{rw}D^{-1/2}w=\lambda D^{-1/2}w \\ \displaystyle L_{rw}u=\lambda u$
$\displaystyle L_{rw}u=D^{-1}Lu=\lambda u \\ \displaystyle Lu = \lambda Du$
3から $L\mathbb{1}=0D\mathbb{1}$ となり， $D^{-1}L\mathbb{1}=L_{rw}\mathbb{1}=0\mathbb{1}$ が得られる．また，2より $L_{sym}$ の固有ベクトルは $D^{1/2}\mathbb{1}$
$L_{sym}$ に関しては命題1の2と同様1の右辺が正であることから言える． $L_{rw}$ に関しては2の $L_{sym}$ との関係性から言える．

また，以下の命題により，正規化されたgraph Laplacianの0固有値の個数はconnected componentの数と関係があることが言える．

Proposition 4 (Number of connected components and spectra of $L_{sym}$ and $L_{rw}$

$L_{rw}$ と $L_{sym}$ の0固有値の個数 $k$ はグラフのconnected componentの数と等しい． $L_{rw}$ の固有空間は指示ベクトル $\mathbf{1}_{A_i}$ によって張られ， $L_{sym}$ は $D^{1/2}\mathbb{1}_{A_i}$ によって固有空間が張られる．

証明

命題3の内容を使って命題2と同様の手順により導けるので割愛．

まとめ

Graph Laplacianとかは流行りの？graph convolution等との関係も深く他にもいろんな場面で見る気がするのでそれなりに勉強できてよかった．

最近生成モデルを中心に勉強してたから久しぶりに線形代数に触れられて楽しい．

2018-08-09

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

graph clustering

はじめに

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

2018-08-04

Graph R-CNN for Scene Graph Generationを読んだのでメモ

graph convolutional network scene graph generation

はじめに

Graph R-CNN for Scene Graph Generationを読んだのでメモ．

手法の概要

まず， $I$ を入力画像， $V$ を $I$ の物体領域と対応したグラフのノード， $E$ を物体間の関係性(グラフのエッジ)， $O,\:R$ が物体と関係性を示すラベルとしてそれぞれ定義．ゴールとしては $P(S=(V,E,O,R)|I)$ というモデルを作ること．言葉で言えば画像を入力とした時に物体位置とそれらの関係性を出力するようなモデルを作りたいということ．この論文では以下のようにモデルを3つの要素(物体検出，関係性検出，グラフラベリング)に分解して考える．

$\displaystyle P(S|I)=\overbrace{P(V|I)}^{Object\: Region\: Proposal}\underbrace{P(E|V,I)}_{Relationship\: Proposal}\overbrace{P(R,O|V,E,I)}^{Graph\: Labeling}$

要は物体を検出してから物体同士の関係性を結ぶ処理をend-to-endにやったというもの．グラフラベリグは最終的なrefinementと考えていいらしいが，処理的には物体の分類と関係性の分類（人と服に対して"wear"を出力するようなこと）をする．

Object proposals

object proposalsはFaster R-CNNで実装したとのこと．出力として空間的な位置 $r_i^o=[x_i,y_i,w_i,h_i]$ ，poolされた特徴ベクトル $x_i^o\in\mathbb{R}^d$ ，クラス推定ラベル $p_i^o\in\mathbb{R}^C$ の3つ．これらをproposalの数 $n$ 並べたものを $R^o\in\mathbb{R}^{n\times 4},\:X^o\in\mathbb{R}^{n\times d},\:P^o\in\mathbb{R}^{n\times C}$ とする．

Relation Proposal Network

Object proposalsによって $n$ 個の物体領域候補が得られた際， $\mathcal{O}(n^2)$ の可能なconnectionがある．ただ基本的には多くの物体ペアは実世界の規則性から関係性を持たないことが知られているため，Relation Proposal Net (RePN)なるものを用いてその規則性をモデリングするというのが論文のコントリビューションの一つ．RePNは物体間の関連度合い（relatedness）を効率的に推定できるらしく，関連度の低いエッジを切ることでscene graph候補を減らしていく．

Relatednessの推論にはクラス推定結果の分布 $P^o$ を使う．具体的には $P^o$ が得られたらエッジの方向を含んだ全ての組み合わせ $n\cdot(n-1)$ についてrelatedness $s_{ij}=f(\mathbf{p}_i^o,\mathbf{p}_j^o)$ を計算する． $f$ は学習によって得られる関数で，ここでは $[\mathbf{p}_i^o,\mathbf{p}_j^o]$ を入力とする多層パーセプトロンを考える．ただし，愚直に実装すれば入力のペアの二乗回計算が必要になるため，次のようなカーネル関数を使ってこれを避ける．

$\displaystyle f(\mathbf{p}_i^o,\mathbf{p}_j^o)=\langle\Phi(\mathbf{p}_i^o),\Psi(\mathbf{p}_j^o)\rangle$

$\Phi(\cdot ),\Psi(\cdot )$ はそれぞれ，relationshpにおけるsubjectsとobjectsのための関数で，論文ではそれぞれ2層の多層パーセプトロン(MLP)を使ったとのこと．このように分解すれば，score matrix $S=\{s_{ij}\}^{n\times n}$ が行列積で表現できる．注意としてスコアの範囲を0から1にするために最後にsigmoid関数をかますとのこと．スコア行列が得られた後はソートしてtop $K$ を選ぶことで物体ペアの候補を選ぶ．ただし，以下で計算されるIoUを使ってNMSを行う．

$\displaystyle IoU(\{u,v\},\{p,q\})=\frac{I(r_u^o,r_p^o)+I(r_v^o,r_q^o)}{U(r_u^o,r_p^o)+U(r_v^o,r_q^o)}$

$I,U$ はそれぞれbounding box間のintersection領域とunion領域を示す．一般的に検出で使われているIoUとの違いは入力が二つの物体ペア $\{u,v\},\{p,q\}$ （つまり4つのbounding box）であること．以上の操作によって $m$ 個の物体ペアを表現したグラフ $\mathcal{g}=(\mathbf{V},\mathbf{E})$ を得て，各々のペアのunion boxからvisual representations $X^r=\{x_1^r,\dots,x_m^r\}$ を取得する，

Attentional GCN

出来上がったグラフの構造からcontextual informationを得るためのモデル，attentional graph convolutional network (aGCN)について．

まずベースとなるGCNについて．グラフの各ノード $i$ が特徴量 $z^i\in\mathbb{R}^d$ を持つとし，隣接ノードの特徴量を $\{z_j|j\in\mathcal{N}(i)\}$ とする．ここでは学習される重み $W$ と隣接行列 $\mathbf{\alpha}$ を使って以下のような変換を行う．

$\displaystyle \mathbf{z}_i^{(l+1)}=\sigma\left(WZ^{(l)}\mathbf{\alpha}_i\right)$

$\sigma$ は非線形関数を表し， $Z\in\mathbb{R}^{d\times Tn}$ は特徴量を並べた行列．隣接行列はノード $i,j$ が隣接関係にある時 $\alpha_{ij}=1$ でそれ以外は0の値を持つ．ただしここでは対角成分は1としている．つまるところ重み行列に隣接行列をかけることで隣接関係があるところのみ重みが残るというもの．

この論文では上のGCNの $\mathbf{\alpha}$ を2層MLPを使って次のように求めてしまおうというもの．

$\displaystyle u_{ij}=w_h^T\sigma(W_a[\mathbf{z}_i^{(l)},\mathbf{z}_j^{(l)}]) \\ \displaystyle \mathbf{\alpha}_i=\mathrm{softmax}(\mathbf{u}_i)$

$w_h,W_a$ は学習パラメータで $[\cdot,\cdot]$ はconcatenationを表す．また， $\mathbf{\alpha}$ はsoftmaxの値にかかわらず対角成分1，隣接関係が無いノードに対応する要素は0にするそう．要は隣接行列にアテンションの構造を突っ込んだということ．

ここまでで $N$ の物体と $m$ の関係性が得られていて，上記のaGCNを使って物体と関係性の表現を更新しようというもの．ただし，その時aGCNが処理するグラフは今までの流れで得られたグラフにスキップコネクション(離れたノード同士を繋げるもの)を導入したグラフになる．これは従来研究で取られていた方法でパフォーマンスが向上するらしい．ここで注意として，現状得られたグラフにはobject $\leftrightarrow$ relationship，relationship $\leftrightarrow$ subject，object $\leftrightarrow$ objectに関する接続がある．さらに言えば，subjectからrelationship方向とrelationshipからsubject方向で接続の意味合いが変わることが考えられる．そこでタイプ $a$ からタイプ $b$ への変換(例えば $s=$ subjectsから $o=$ objectsへの変換)の重み行列を $W^{ab}$ と定義する．色々ごちゃごちゃした説明が続いたが，この論文における最終的なaGCNの計算は以下のように行われる．objcetに関する特徴量の更新は次のように行われる．

$\displaystyle \mathbf{z}_i^o=\sigma(\overbrace{W^{skip}Z^o\mathbf{\alpha}^{skip}}^{Message\:from\:Other\:Objects}+\overbrace{W^{sr}Z^r\mathbf{\alpha}^{sr}+W^{or}Z^r\mathbf{\alpha}^{or}}^{Messages\:from\:Neighboring\:Relationships})$

次にrelationshipに関する更新は

$\displaystyle \mathbf{z}_i^r=\sigma(\mathbf{z}_i^r+\underbrace{W^{rs}Z^o\mathbf{\alpha}^{rs}+W^{ro}Z^o\mathbf{\alpha}^{ro}}_{Messages\:from\:Neighboring\:Objects})$

として計算される．ただし，ここでの各隣接行列は $\mathbf{\alpha}^{skip}$ を除き対角成分は0．

論文中ではobjectとrelationshipのノードの特徴量 $z$ の初期値はopen choiceだと述べられていて，intermediate feature (多分物体検出で使われるCNNの中間出力のことかと)か検出の時のsoftmax関数を噛ませる前の特徴量が選べるとのこと．

loss function

最初に三つに分けたプロセス $P(\mathbf{R},\mathbf{O}|\mathbf{V},\mathbf{E},\mathbf{I}),P(\mathbf{E}|\mathbf{V},\mathbf{I}),P(\mathbf{V}|\mathbf{I})$ それぞれ教師ありで学習する． $P(\mathbf{V}|\mathbf{I})$ はfaster RCNNのRPNで使われたロスと同様のものを使う． $P(\mathbf{E}|\mathbf{V},\mathbf{I})$ はbinary cross entropyを使って各objectペアの関係性のあるなしを学習．最後に $P(\mathbf{R},\mathbf{O}|\mathbf{V},\mathbf{E},\mathbf{I})$ はmulti-class cross entropyを使って物体の分類，術語の分類を学習．

まとめ

去年くらいGCNの研究を少ししてたけど，どうしてもノード数が増えてくると演算回数，メモリ共に厳しくなるからその辺誰か解決してくれないかなという気持ち．後，今回はGCNへの入力となるグラフのノード数は物体の数に依存して可変な気がするけどどうやって扱っているのでしょう．

2018-08-02

Understanding and Improving Interpolation in Autoencoders via an Adversarial Regularizerを読んだのでメモ

生成モデル

はじめに

Understanding and Improving Interpolation in Autoencoders via an Adversarial Regularizerを読んだのでメモ．

気持ち

Autoencoderはデータの潜在的な表現を学習することができ，その潜在空間上でデータ間の補間を行うと，デコードされた画像も連続的に変化していくことが知られている．ただし，時たま何の意味もなさないデータが生成される場合があるので，そこをより良くしていきたい，つまりhigh-qualityなinterpolationがしたいという思い．

Adversarial Regularizer

今回は多層ニューラルネットを使ったautoencoderを考える．encoderを $z=f_\theta(x)$ ，decoderを $\hat{x}=g_\phi(z)$ として，目的関数には二乗誤差を使う． $\theta,\phi$ はニューラルネットの学習パラメータ．補間は潜在空間上で $\hat{x}_\alpha=g_\phi(\alpha z_1+(1-\alpha)z_2),\:\alpha\in[0,1]$ として行う．ただし， $z_1=f_\theta(x_1),\:z_2=f_\theta(x_2)$ ．

High-qualityな補間の特徴として，補間の途中の画像もreal dataと見分けが付かないような画像であり，データ間の特徴を滑らかに変化させていくことがあげられる．ただし，後半の定義は難しいので今回はrealistic側を重点的に考える．

本物の画像と見分けが付かないようなということでGANの考えを導入する．するとGANのdiscriminator(論文ではcriticと表現)は次の目的関数を最小化するよう学習する．

$\displaystyle \mathcal{L}_d=||d_\omega(\hat{x}_\alpha)-\alpha||^2+||d_\omega(\gamma x+(1-\gamma)g_\phi(f_\theta(x))||^2$

$\gamma$ はスカラーのハイパーパラメータ．第1項目はデータの混ざり具合を判断する項で，2項目は二つの関数からなる正則化項となっていて，データ空間での補間に対してdiscriminatorが0を出力するようにするもの．別に重要ではないけどあった方がadversarial lerning processが安定するとのこと．正直この正則化の意味はちょっとよくわからなかった．

Autoencoder側の目的関数は正則化項が加わって以下のように表される．

$\displaystyle \mathcal{L}_{f,g}=||x-g_\phi(f_\theta(x))||^2+\lambda||d_\omega(\hat{x}_\alpha)||^2$

$\lambda$ はハイパーパラメータで $\alpha$ にかかわらずdiscriminatorの出力を0にしようとするもの．これが $\mathcal{L}_d$ 最大化の代わりになっている．

まとめると，discriminatorを $\mathcal{L}_d$ 最小化で学習して，autoencoderを $\mathcal{L}_{f,g}$ 最小化で学習する．

以降論文ではかなり密な実験と考察が続くがその辺は割愛（むしろここからが論文の本番ではあるが）．

まとめ

以前，潜在空間の補間をgeodesicsに沿ってやると綺麗になるというのがあったけど，このアプローチなら線形補間で十分になるからなかなか賢いアプローチだなあという感じ．

2018-08-02

Sylvester Normalizing Flows for Variational Inferenceを読んだのでメモ

生成モデル normalizing flow 変分推論

はじめに

Sylvester Normalizing Flows for Variational Inferenceを読んだのでメモ．planer flowの一般化であるSylvester normalizing flowを提案．planer flowは以前勉強した．

Normalizing flow

復習がてらnormalizing flowについて．

確率変数 $\mathbf{z}$ を関数 $f$ を使って $\mathbf{z}'$ に変数変換する．その時， $\mathbf{z}'$ の確率密度は次のように計算できる．

$\displaystyle p_1(\mathbf{z}')=p_0(\mathbf{z})\left|\mathrm{det}\left(\frac{\partial f(\mathbf{z})}{\partial \mathbf{z}}\right)\right|^{-1}$

上記は変数変換の公式として知られていて調べればいくらでも出てくる．基本的には $P_0(\mathbf{z})$ も $P_1(\mathbf{z}')$ も確率密度の定義から積分が1であるため $P(\mathbf{z})d\mathbf{z}=P(\mathbf{z}')d\mathbf{z}'$ という関係が成り立つことから導かれる．

次にこの変数変換を変分推定に組み込むことを考える．初期の確率変数 $\mathbf{z}_0$ をdiagonal Gaussian $\mathcal{N}(\mathbf{z}_0|\mathbf{\mu}(\mathbf{x}),\mathbf{\sigma}^2(\mathbf{x}))$ に従う確率変数とする．この変数 $\mathbf{z}_0$ を $\mathbf{z}_K=(f_K\circ\dots\circ f_1)(\mathbf{z}_0$ のように $K$ 回変数変換することを考える．すると確率密度 $q_K(\mathbf{z}_K)$ は以下の計算により求めることができる．

$\displaystyle \log q_K(\mathbf{z}_K|\mathbf{x})=\log q_0(\mathbf{z}_0|\mathbf{x})-\sum_k\log\left|\mathrm{det}\left(\frac{\partial f_k(\mathbf{z}_{k-1};\lambda_k(\mathbf{x}))}{\partial\mathbf{z}_{k-1}}\right)\right|$

$\lambda_k$ は $k$ 番目の変換のパラメータを表す．上記の $q_K(\mathbf{z}|\mathbf{x})$ を変分事後分布とすると変分推論における下限の式は以下のように表現ができる．

$\displaystyle \mathcal{F}(\theta,\phi) \\ \displaystyle =\mathbb{E}_{q_phi}[\log q_\phi(\mathbf{z}|\mathbf{x})-\log p_\theta(\mathbf{x},\mathbf{z})] \\ \displaystyle =\mathbb{E}_{q_0}[\log q_0(\mathbf{z}_0|\mathbf{x})-\log p_\theta(\mathbf{x},\mathbf{z})] - \mathbb{E}_{q_0}\left[\sum_k\log\left|\mathrm{det}\left(\frac{\partial f_k(\mathbf{z}_{k-1};\lambda_k(\mathbf{x}))}{\partial\mathbf{z}_{k-1}}\right)\right|\right]$

通常の変分推論では変分事後分布は勾配計算のためにサンプリングを用いるため，サンプリングが簡単にできるような単純な分布である必要がある．それに対し，noramlizing flowは単純な分布から複雑な分布へ変換することで複雑な分布を変分事後分布として用いることが可能で，サンプリングも単純な分布から行うことができる．それにより変分推論の近似精度をあげることができるというもの．

先行研究ではこの変数変換の関数を以下のplanar flowと呼ばれる関数族で定義した．

$\displaystyle \mathbf{z}'=\mathbf{z}+\mathbf{u}h(\mathbf{w}^T\mathbf{z}+b)$

各パラメータは $\mathbf{u},\mathbf{W}\in\mathbb{R}^D,b\in\mathbb{R}$ として定義されれ $h$ は $\mathrm{tanh}$ のような全単射の活性化関数を表す．このplanar flowは $\mathbf{u}^T\mathbf{w}\geq -1$ である限り逆変換が可能である．

またplanar flowのヤコビアンの行列式は以下の形で計算が可能．

$\displaystyle \mathrm{det}\frac{\partial\mathbf{z}'}{\partial\mathbf{z}}=\mathrm{det}(\mathbf{I}+\mathbf{u}h'(\mathbf{w}^T\mathbf{z}+b)\mathbf{w}^T)=1+\mathbf{u}^Th'(\mathbf{w}^T\mathbf{z}+b)\mathbf{w}$

ここで $h'$ は $h$ の導関数を表し，このように計算できることで行列式の計算コストが $\mathcal{O}(D)$ になる（普通は $\mathcal{O}(D^3)$ ）．

Sylvester normalizing flow

名前がかっこいい．ここでは次のようなresidual connectionを持つ隠れユニット数 $M$ の単層ニューラルネットのような変換を考える．

$\displaystyle \mathbf{z}'=\mathbf{z}+\mathbf{A}h(\mathbf{B}\mathbf{z}+\mathbf{b})$

各変数は $\mathbf{A}\in\mathbb{R}^{D\times M},\mathbf{B}\in\mathbb{R}^{M\times D},\mathbf{b}\in\mathbb{R}^M,M\leq D$ で定義されている．この変換のヤコビアンの行列式は以下のSylvester's determinant identityを使うことにより求めることが可能とのこと．

$\displaystyle \mathrm{det}(\mathbf{I}_D+\mathbf{A}\mathbf{B})=\mathrm{det}(\mathbf{I}_M+\mathbf{B}\mathbf{A})$

ここで $\mathbf{I}_D$ は $D$ 次元単位行列を表す．上記の関係を用いれば $M\lt D$ の時に $D\times D$ 行列の行列式を $M\times M$ 行列の行列式として計算ができるため，計算コストの削減ができる．このSylvester's determinant identityを使えば最初に定義した変換のヤコビアンの行列式は以下のように計算できる．

$\displaystyle \mathrm{det}\frac{\partial\mathbf{z}'}{\partial\mathbf{z}}=\mathrm{det}(\mathbf{I}_M+\mathrm{diag}(h'(\mathbf{B}\mathbf{z}+\mathbf{b}))\mathbf{B}\mathbf{A})$

導出は普通に微分するだけ．嬉しいこととしては $\mathbf{BA}$ のように計算している点で，さっきも書いたように行列のサイズが落ちるため計算コストが下がる．

注意としてこの変換自体は基本的には逆変換を持たない．逆変換を持つためには $\mathbf{A},\mathbf{B}$ が次のようなQR分解の形で表される必要がある．

$\displaystyle \mathbf{z}'=\mathbf{z}+\mathbf{QR}h(\mathbf{\tilde{R}Q}^T\mathbf{z}+\mathbf{b})=\phi(\mathbf{z})$

ただし， $\mathbf{R},\mathbf{\tilde{R}}$ は $M\times M$ 上三角行列で $Q$ は $D\times M$ 直交行列となる．この時ヤコビアンの行列式は次の形で表される．

$\displaystyle \mathrm{det}\frac{\partial\mathbf{z}'}{\partial\mathbf{z}}=\mathrm{det}(\mathbf{I}_M+\mathrm{diag}(h'(\mathbf{\tilde{R}Q}^T\mathbf{z}+\mathbf{b}))\mathbf{\tilde{R}Q}^T\mathbf{QR})=\mathrm{det}(\mathbf{I}_M+\mathrm{diag}(h'(\mathbf{\tilde{R}Q}^T\mathbf{z}+\mathbf{b}))\mathbf{\tilde{R}}\mathbf{R})$

最後は $Q$ が直交行列であることを利用した．ここで $\mathbf{\tilde{R}R}$ は上三角行列であるため行列式の計算オーダーは $\mathcal{O}(M)$ となる．

この変換が逆変換を持つための十分条件は， $\mathbf{R},\mathbf{\tilde{R}}$ が上三角行列で $h:\mathbb{R}\rightarrow\mathbb{R}$ が連続な関数である時， $\mathbf{R},\mathbf{\tilde{R}}$ が $r_{ii}\tilde{r}_{ii}\gt -1/||h'||_\infty$ かつ $\mathbb{\tilde{R}}$ が逆行列を持つという条件で与えられる．以下 $\mathbf{R},\mathbf{\tilde{R}}$ がともに対角行列であるときの証明．

$\mathbf{Q}$ は直交行列であるため， $\mathbf{Q}$ が張る部分空間は $\mathcal{W}=\mathrm{span}\{\mathbf{q}_q,\dots,\mathbf{q}_M\}$ として表すことができ，その直交補空間を $\mathcal{W}^\perp$ で定義する．すると $\mathbf{z}=\mathbf{z}_{||}+\mathbf{z}_perp$ として分解することができる．ただし， $\mathbf{z}_{||}\in\mathcal{W},\mathbf{z}_\perp\in\mathcal{W}^\perp$ ．当然， $\mathbf{QR}h(\mathbf{\tilde{R}Q}^T\mathbf{z}+\mathbf{b})\in\mathcal{W}$ となる．したがって関数 $\phi$ は $\mathbf{z}_{||}$ 上のみで振る舞うことになる．したがって， $\mathbf{z}_{||}$ 上での $\phi$ の振る舞いのみを考えればよく， $\phi(\mathbf{z})$ に左から $\mathbf{Q}$ をかければ

$\displaystyle \mathbf{Q}^T\mathbf{z}' = \mathbf{Q}^T\mathbf{z}+\mathbf{R}h(\mathbf{\tilde{R}}\mathbf{Q}^T\mathbf{z}+\mathbf{b})=(f_1(v_1),\dots,f_M(v_M))^T$

としてかける．ここでベクトル $\mathbf{v}$ は $\mathbf{Q}$ が張る部分空間上での $\mathbf{z}_{||}$ の座標を表す．ここでは $\mathbf{R}$ は対角行列であることを仮定しているため， $\mathbf{v}$ の各次元は独立であり， $f_i(v)=v+r_{ii}h(\tilde{r}_{ii}v+b_i)$ という変換としてかける．よって各次元ごとに考えることができ， $||h'||_\infty r_{ii}\tilde{r}_{ii}\gt -1$ であることから， $f_i'(v)\gt 0$ であることが言える．導関数が正の1次元の実関数は逆変換を持つため $f_i$ は逆変換を持つ．よって $\phi(\mathbf{z})$ は逆変換を持つことが言え，その変換は

$\displaystyle \phi^{-1}(\mathbf{z}')=\mathbf{z}_\perp'+f^{-1}(\mathbf{z}_{||}')=\mathbf{z}$

としてかける．論文では当然 $\mathbf{R}$ が三角行列の時の証明も行われているがかくのが面倒なのでここでは割愛．

実践的な面での課題ではパラメータの学習時にどのようにして $\mathbf{Q}$ を直交行列として保ち続けるかという問題がある．ここでは $\mathbf{Q}$ を直交行列として保ち続けるために，Orthogonal Sylvester flows, Householder Sylvester flows, Triangular Sylvester flowsの三つのflowを提案する．

Orthogonal Sylvester flows（O-SNF）

ここでは $||\mathbf{Q}^{(0)T}\mathbf{Q}^{(0)}-\mathbf{I}||_2\lt 1$ を満たしながら以下の手順を用いることで $\mathbf{Q}$ の直交性を保つ．ただし，行列の2-normは $||\mathbf{X}||_2=\lambda_{\max}(\mathbf{X})$ で計算され， $\lambda_\max(\mathbf{X})$ は $\mathbf{X}$ の最大特異値を表す．

$\displaystyle \mathbf{Q}^{(k+1)}=\mathbf{Q}^{(k)}\left(\mathbf{I}+\frac{1}{2}\left(\mathbf{I}-\mathbf{Q}^{(k)T}\mathbf{Q}^{(k)}\right)\right)$

ただし実験の時には $||\mathbf{Q}^{(k)T}\mathbf{Q}^{(k)}-\mathbf{I}||_F\lt \epsilon$ を満たすように行ったらしい． $||\cdot||_F$ はフロベニウスノルム．この手順は微分可能なためbackpropに組み込めるので嬉しいという点も．

Householder Sylvester flows（H-NSF）

ここでは次のHouseholder変換の積によって直交行列を作る．ハウスホルダー変換は超平面上での反射を表していて， $\mathbf{v}\in\mathbb{R}^D$ とすると $\mathbf{v}$ に直交する超平面上での反射（つまりハウスホルダー変換）は以下で与えられる．

$\displaystyle H(\mathbf{z})=\mathbf{z}-\frac{\mathbf{vv}^T}{||\mathbf{v}||^2}\mathbf{z}$

これは計算コストは低くパラメータも $D$ しか持たないため嬉しい．ちなみに $M\times M$ 直交行列は $M-1$ 回のハウスホルダー変換の積で記述できることが知られているらしい．注意としてはハウスホルダー変換を使う場合は，ハウスホルダー変換の結果が正方行列であるため $M=D$ とする必要がある．

Triangular Sylvester flows（T-SNF）

これは $\mathbf{Q}$ を単位行列または置換行列として，flowの変換の過程で単位行列と置換行列が交互に現れるようなflow．つまり， $\mathbf{\tilde{R}}$ と $\mathbf{R}$ が上三角と下三角として交互にflowに現れるようにすることと等しい．すなわちT-SNFでは $\mathbf{Q}$ は固定．

まとめ

実験的には3つのflowの性能はだいたい同じくらいっぽい．計算コストや実装の観点から言えばO-SNFかなあというところ．

Flow-basedな生成モデルは論文書く目処もついたのでそろそろ次の勉強ネタが欲しいところ．

はじめに

CNNとgraph

Spatial Construction

における局所性

グラフ上でのMultiresolution

Deep locally connected networks

Spectral Construction

重み付きグラフ上での調和解析

Extending convolutions

まとめ

はじめに

Spectral Clustering Algorithms

Unnormalized spectral clustering

Normalized spectral clustering according to Phi and Malik (2000)

Normalized spectral clustering according to Ng, Jordan, and Weiss (2002)

Graph cut point of view

Approximating RatioCut for

Approximating RatioCut for arbitrary

Approximating Ncut

Comments on the relaxation approach

まとめ

はじめに

Similarity graphs

graph notation

Different similarity graphs

The -neighborhood graph

-nearest neighbor graphs

The fully connected graph

Graph laplacians and their basic properties

The unnormalized graph Laplacian

Proposition 1 (properties of )

証明

Proposition 2 (Number of connected components and the spectrum of )

証明

The normalized graph Laplacians

Proposition 3 (Properties of and )

証明

Proposition 4 (Number of connected components and spectra of and

証明

まとめ

はじめに

graph-based clustering

Affinity matrix

objective function

optimization methods

Micro-average association

direct local optimization

greedy incremental algorithm

実験

まとめ

はじめに

手法の概要

Object proposals

Relation Proposal Network

Attentional GCN

loss function

まとめ

はじめに

気持ち

Adversarial Regularizer

まとめ

はじめに

Normalizing flow

Sylvester normalizing flow

Orthogonal Sylvester flows（O-SNF）

Householder Sylvester flows（H-NSF）

Triangular Sylvester flows（T-SNF）

まとめ

$W$ における局所性

Approximating RatioCut for $k=2$

Approximating RatioCut for arbitrary $k$

The $\epsilon$ -neighborhood graph

$k$ -nearest neighbor graphs

Proposition 1 (properties of $L$ )

Proposition 2 (Number of connected components and the spectrum of $L$ )

Proposition 3 (Properties of $L_{sym}$ and $L_{rw}$ )

Proposition 4 (Number of connected components and spectra of $L_{sym}$ and $L_{rw}$