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

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

CornerNet: Detecting Objects as Paired Keypointsを読んだのでメモ.

はじめに

CornerNet: Detecting Objects as Paired Keypointsを読んだのでメモ.

気持ち

現状のアンカーベースのobject detectorは,大量のアンカーを用意する必要があるのとハイパーパラメータが多くなるという課題があるのでそこを解決したいというもの.そこで,物体の左上の座標と右下の座標をヒートマップとして出力するCornerNetを提案.中心座標を回帰する場合は4点分の情報が必要だがcornerなら2点で済むから簡単であるはずという仮説にも基づいているらしい.

CornerNet

CornerNetのメインのアイディアとしてはbounding boxの左上,右下をkeypointsとして,そのkeypointsのペアを物体として検出するというもの.イメージとしてはConvolutional Pose Machine(CPM)などのやり方を応用した感じ.

CornerNetは,左上のkeypointsのheatmapを出力するモジュールと右下を出力するモジュール,その他にkeypointsのペアを決めるのに使う埋め込みベクトルを出力するモジュールとbounding boxを決定する際の補助に使うoffsetを出力するモジュールから成り立つ.

Cornerの検出

Cornerの検出のためのheatmapは,bounding boxの左上,右上それぞれ用意され,各heatmapはクラス数Cのチャネルを持つ.ただし背景クラスのheatmapは無く,各heatmapはcornerが有るか無いかの2値分類器として学習される.このとき,正解のcornerをmapの中の唯一1点として与えるのは当然筋がよく無いので,CPM等と同様アノテーションの座標を中心としてガウス分布に従う広がりを持たせたものを正解として学習する.具体的には\exp\left(-\frac{x^2+y^2}{2\sigma^2}\right)として正解の値を作る.\sigmaは正解の矩形とのIoUから決まる半径の1/3に設定したとのこと.半径は,半径以内に収まる点をcornerとして作った矩形と正解矩形とのIoUがt以上になる様に決められ,実験は[t=0.7]で行ったらしい.

p_{cij}をクラスcのheatmapの(i,j)ピクエルのスコアとして,y_{cij}を正解の値とする.目的関数を以下のfocal lossとして学習する.

\displaystyle
L_{det}=-\frac{1}{N}\sum_{c=1}^C\sum_{i=1}^H\sum_{j=1}^W\left\{\begin{matrix}
(1-p_{cij})^\alpha\log(p_{cij})\:\:\:\mathrm{if}\:y_{cij}=1\\
(1-y_{cij})^\beta(p_{cij})^\alpha\log(1-p_{cij})\:\mathrm{otherwise}
\end{matrix}\right.

Nは画像中の物体の数で,\alpha,betaはハイパーパラメータで\alpha=2,\beta=4で実験を行なったとのこと.

基本的にCNNは空間方向の情報の集約と計算コストの削減のためにpoolingの様なdownsamplingの操作が入り,出力は元画像より小さくなる.すなわちdownsamplingのスケールをnとすれば出力の空間方向のサイズは(\lfloor\frac{x}{n}\rfloor,\lfloor\frac{y}{n}\rfloor)となる.そのため,heatmapからbounding boxを作り出して元の画像の座標値に直す際に多少なり精度が落ちる.この精度の劣化は小さい物体ほど顕著に現れるため,こんお問題を解決するために,次の様なlocation offsetsの推定を行う.

\displaystyle
\mathbf{o}_k=\left(\frac{x_k}{n}-\lfloor\frac{x_k}{n}\rfloor,\frac{y_k}{n}-\lfloor\frac{y_k}{n}\rfloor\right)

\mathbf{o}_kがoffsetでx_k,y_kは推定されたcorner kのx,y座標.heatmapはカテゴリごとに出力されるのに対し,このoffsetはカテゴリ関係なく一つのcornerに対して1つ出力される.学習は次のsmooth L1 Lossによって行われる.

\displaystyle
L_{off}=\frac{1}{N}\sum_{k=1}^N\mathrm{SmoothL1Loss}(\mathbf{o}_k,\hat{\mathbf{o}}_k)

Cornerの統合

一般的に一つの画像に対し複数の物体が存在しているため,cornerも複数検出される.そのため,左上のcornerと右下のcornerのペアを決定しなければならない.そこで,各cornerごとに埋め込みベクトルを出力させ,その埋め込みベクトル間の距離を使ってグルーピングを行う.

e_{t_k}を物体kの左上のcornerのembedding,e_{b_k}を右下のcornerのembeddingとする.embeddingの次元は1次元とし,学習には次の"pull" lossと"push" lossを使った.

\displaystyle
L_{pull}=\frac{1}{N}\sum_{k=1}^N\left[(e_{t_k}-e_k)^2+(e_{b_k}-e_k)^2\right]\\
L_{push}=\frac{1}{N(N-1)}\sum_{k=1}^N\sum_{j=1\\j\neq k}^N\max(0,\delta-|e_k-e_
j|)

e_ke_{t_k},e_{b_k}の平均で\deltaは1に設定したとのこと.

Corner Pooling

Cornerを使った検出の課題として,斜めに置かれた棒などの矩形を出す際に,cornerの付近に検出対象の物体が写ってなくてcornerを推定するための根拠がない場合がある(論文Fig. 2参照).なのでcornerを決めるためには水平方向,垂直方向の情報を集約する必要があるため,ここではそれを実現するためにcorner poolingを提案する.

f_t,f_lをtop-left corner pooling layerの入力の特徴マップとし,f_{t_{ij}},f_{l_{ij}}f_t,f_l(i,j)ピクセルのベクトルとする.H\times Wの特徴マップが与えられたとき,corner pooling layerは(i,j)から(i,H)(i,j)から(W,j)の間でmax-poolをする.これは次の様に表現できる.

\displaystyle
t_{ij}=\left\{\begin{matrix}
\max(f_{t_{ij}},t_{(i+1)j})\:\mathrm{if}\:i\lt H\\
f_{tH_j}\:\:\:\:\:\mathrm{otherwise}
\end{matrix}\right.\\
l_{ij}=\left\{\begin{matrix}
\max(f_{l_{ij}},l_{i(j+1)})\:\mathrm{if}\:j\lt W\\
f_{l_iW}\:\:\:\:\:\mathrm{otherwise}
\end{matrix}\right.

Bottom-right cornerに関しても(0,j)から(i,j)(i,0)から(i,j)間のmax-poolとして同様に定義ができる.

学習について

モデルの構成については省略.簡単にはbackboneにhourglass networkを使い,出力のブランチは論文Fig. 7にのってる.

入力画像の解像度は511\times511で出力の解像度は128\times128.データ拡張として,random horizontal flipping, random scaling, random cropping and random color jitteringを使用.検出で使われる一般的な拡張方法.最適化はAdamを使い,以下のコスト関数を最小化する様学習.

\displaystyle
L=L_{det}+\alpha L_{pull}+\beta L_{push}+\gamma L_{off}

\alpha,\betaは0.1で\gammaは1に設定.\alpha,\betaを1以上にすると性能が低下するらしい.バッチサイズは49で500k iteration学習.学習率は2.5\times 10^{-4}から始め,250k回学習した段階で2.5\times 10^{-5}に減衰させる.

まとめ

SoTAモデルと比較して精度はほぼほぼトップ.個人的にdenseなシーンでどれくらい機能するか気になるところ.一般的な検出器はdenseなシーンだとNMSで矩形が統合されて検出率が落ちるけどこっちはこっちでcornerが統合されてダメになるのかどうか.とは言え物体検出の論文で久しぶりに大きな変化があった気がする.

SHADE: INFORMATION-BASED REGULARIZATION FOR DEEP LEARNINGを読んだのでメモ

はじめに

SHADE: INFORMATION-BASED REGULARIZATION FOR DEEP LEARNINGを読んだのでメモ.ICIP2018のベストペーパーに選ばれた論文.(調べてみるとICLR2018にrejectされてた)

SHADE: SHAnnon DEcay

まずX\in\mathcal{X}を入力の変数,C\in\mathcal{C}を出力の変数,wをモデルパラメータ,Y=h(w,X)をNNによる変換の表現として定義する.ここでは分類問題を考え,次のような目的関数を最適化する問題を解く.

\displaystyle
\mathcal{L}(w)=\mathbb{E}_{X,C}(l_{cls}(w,X,Y,C)+\beta\cdot\Omega(w,X,Y,C))

ここでは新しい正則化\Omega(w,X,Y,C),shannon decayを提案する.

Conditional entropy-based regularization

条件付きエントロピーH(Y|C)を使ったクラス内の不変性に焦点を当てる.もともとInfromation Bottleneck(IB)と呼ばれる相互情報量I(X,Y)=I(C,Y)+H(Y|C)正則化に使う手法があり,ここではこのH(Y|C)が中間表現にどれほどの不変性を与えるかを考える.学習したDNNがdeterministicであれば,H(Y|X)=0であり,同時にH(Y)=I(X,Y)=H(X)-H(X|Y)が成り立つ.H(X)が固定ならばH(Y)H(X|Y)は負の相関を持つ.H(X)-H(X|Y)は入力の再構成誤差の下限を与えていて,このことから得られた表現Yから入力を復元するのがどれくらい難しいかを測ることができる.すなわち条件付きエントロピーのみを考えれば入力をよく表現する(言い換えれば不変的な)特徴を得ることが可能.

DNNは入力に対しレイヤー数Lの変換を加える.l層目の出力をY_lとすれば次の関係が成り立つ.

\displaystyle
H(Y_l|C)\leq H(Y_{l-1}|C)\leq\dots\leq H(Y_1|C)\leq H(X|C)

ある層の条件付きエントロピーはその後に続く層の条件付きエントロピーの上界を与えることになる.よってここでは全てのレイヤーにH(Y_l|C)を最小化するような正則化を導入する.すなわち正則化項として次の形を与える.

\displaystyle
\Omega_{layers}=\sum_{l=1}^LH(Y_l|C)

さらにlayer-wiseな正則化からunit-wiseな正則化へと議論を広げる.レイヤーlの表現Y_lに対して各座標(ユニット)の表現をY_{l,i}とし,その次元をD_l:Y_l=(Y_{l,1},\dots,Y_{l,D_l}とする.上界H(Y_l|C)\leq\sum_{i=1}^{D_l}H(Y_{l,i}|C)は異なるユニットの独立性を仮定して考えることが可能で,このynit-wiseな条件付きエントロピーの最小化をすることが提案手法のSHADE.最終的な正則化は次のような形で記述される.

\displaystyle
\Omega_{layers}\leq\Omega_{units}=\sum_{l=1}^L\sum_{i=1}^{D_l}H(Y_{l,i}|C)

以下,Y_{l,i}Yとして表現する.

正則化項の定義はできたが問題として条件付きエントロピーをどのように計算するかが残る.基本的にH(Y|C)を計算する上で必要なYの分布が未知であるため計算することができない.[tx:H(Y|C)=\sum_{c\in\mathcal{C}}p(c)H(Y|c)]から条件付き情報量を計算するには|C|個の異なるエントロピーH(Y|c)を計算する必要があり,ImageNetなどの1000クラス分類を考えた時には扱いにくい.

そこで条件付き情報量を計算するためのトリックとして潜在変数Zを導入する.これはY\gg 0の場合にZY\leq 0の場合にZ=0となるような変数で,ベルヌーイ分布に従う確率変数として仮定する.するとC\rightarrow Z\rightarrow X\rightarrow Yのようなマルコフ連鎖を仮定できる.よって定常状態になった時にはH(Y|C)=H(Y|Z)が成り立ち,最終的に条件付きエントロピーを次のように計算できる.

\displaystyle
H(Y|C)=H(Y|Z)=\sum_{z\in\{0,1\}}p(z)H(Y|Z=z)

これはz=0z=1の二つの場合のみについて計算すればいいため扱いやすい.

ただこのままでは,クラス数の増加による計算の扱い難さは解決したが根本のエントロピーの計算ができない点については解決していない.そこでエントロピーそのものではなくH(Y|Z)\leq\frac{1}{2}\ln(2\pi e\mathrm{Var}(Y|Z))という上界を利用して計算する.これは任意の連続な分布Yについて成り立ち,もし分布がガウシアンであれば等号が成り立つ.

以上をまとめれば最終的に提案手法であるSHADEの正則化は次のようになる.

\displaystyle
\Omega_{SHADE}=\sum_{l=1}^L\sum_{i=1}^{D_l}\sum_{z\in\{0,1\}}p(Z_{l,i}=z|Y)\mathrm{Var}(Y|Z_{l,i}=z)

ただし,あるレイヤーのあるユニットに関する\mathrm{Var}(Y|Z)は次のように計算される.

\displaystyle
\mathrm{Var}(Y|Z)=\int_\mathcal{Y}p(y)\int_\mathcal{Z}p(z|y)(y-\mathbb{E}(Y|z))^2dzdy\\ \displaystyle
\approx\frac{1}{K}\sum_{k=1}^K\left[\int_\mathcal{Z}p(z|y^{(k)})(y^{(k)}-\mathbb{E}(Y|z))^2dz\right]

ようはミニバッチを使って近似しようというもの.ここでp(Z|y)\sigma(y)=1-e^{-\mathrm{ReLU}(Y)}を使って次のように計算する.

\displaystyle
p(Z=1|y)=\sigma(y),\:p(Z=0|y)=1-\sigma(y)

また,\mu^z=\mathbb{E}(Y|z)移動平均を使って推定精度を高める(詳細は論文のAlgorithm 1).よって以上の議論を踏まえればSHADEは次のように書き直せる.

\displaystyle
\Omega_{SHADE}=\sum_{l=1}^L\sum_{i=1}^{D_l}\sum_{k=1}^K\sum_{z\in\{0,1\}}p\left(Z_{l,i}=z|y_{l,i}^{(k)}\right)\left(y_{l,i}^{(k)}-\mu_{l,i}^z\right)^2

まとめ

ギリシャからの帰りの乗り換え時間を利用して論文読んだけど疲れと睡魔から読み違いをしていそうで怖い.実験結果は劇的に良くなるという結果ではないものの安定して精度向上している感じ.ただICIPの論文は4ページと書ききれないことが多々ある気がするのでICLRに投稿された方も少し読んでみたい.

THE UNREASONABLE EFFECTIVENESS OF (ZERO) INITIALIZATION IN DEEP RESIDUAL LEARNINGを読んだのでメモ

はじめに

THE UNREASONABLE EFFECTIVENESS OF (ZERO) INITIALIZATION IN DEEP RESIDUAL LEARNINGを読んだのでメモ.ICLR2019の査読中論文.

2019/2/4 ICLR2019に採択されていたがタイトルがFIXUP INITIALIZATION:RESIDUAL LEARNING WITHOUT NORMALIZATIONに変わっていた.内容の再確認はしていないのでもしかしたら細かな議論が変わっているかも.

気持ち

NNの重みをゼロで初期化してしまおうという論文.ここではbatch normalizationのような正規化を行うことなく深いネットワークが学習可能か,さらに学習可能だとして正規化を行う場合とそうでない場合で同じ学習率を使って学習可能か,学習の速度や汎化性は等しいかという問題を投げかけている.論文曰くどちらもyesでゼロ初期化によってそれは可能ということ.

ResNetの勾配爆発問題

勾配爆発や勾配消失問題を解決するために様々なdeep learning toolでも実装されているxavierの初期化やheの初期化が提案されている.ただこれらの初期化方法はbatch normalizationを含まないネットワークで議論されていて,実はresidual connectionのせいでこれらの初期化方法は勾配爆発を引き起こすことがあるとのこと.この問題はReLUを使ったネットワークについて言及されていたのでここではpositively homogeneous functionの場合に拡張する(positively homogeneous functionは論文の定義1参照).まずResNetのresidual blocksを\{F_1,\dots,F_L\}とし,入力を\mathbf{x}_0とするとresnetは次のように定式化される.

\displaystyle
\mathbf{x}_l=\mathbf{x}_0+\sum_{i=0}^{l-1}F_i(\mathbf{x}_i)

ここでは初期化について考えるので入力\mathbf{x}_0は固定として,重みの曖昧性のみ考える.\mathbf{x}_lの各座標の分散の和を\mathrm{Var}[\mathbf{x}_l]とする.簡単のため各ブロックが平均ゼロ\mathbb{E}[F_l(\mathbf{x}_l)|\mathbf{x}_l]=0で初期化されていると仮定すれば,\mathbf{x}_{l+1}=\mathbf{x}_l+F_l(\mathbf{x}_l)の関係から\mathrm{Var}[\mathbf{x}_{l+1}]=\mathbb{E}[\mathrm{Var}[F(\mathbf{x}_l)|\mathbf{x}_l]]+\mathrm{Var}(\mathbf{x}_l)となる.すなわちResNetの構造は分散が層の増加に伴って増えることで\mathbf{x}_lが0になることを防いでいると言える.言い換えれば\mathbb{E}[\mathrm{Var}[F(\mathbf{x}_l)|\mathbf{x}_l]]\gt 0ならば,\mathrm{Var}[\mathbf{x}_l]\lt \mathrm{Var}[\mathbf{x}_l]が成り立つということ.Heの初期化を使えば\mathrm{Var}[F_l(\mathbf{x}_l)|\mathbf{x}_l]が入力の分散\mathrm{Var}[\mathbf{x}_l]とほぼ等しくなるため\mathrm{Val}[\mathbf{x}_{l+1}]\approx 2\mathrm{Var}[\mathbf{x}_l]となる.positively homogeneous functionを使った正規化がないblockの場合には次のように出力の分散が深さに対して指数的に増加する.

\displaystyle
\mathrm{Var}[\mathbf{x}_l]=\mathrm{Var}[\mathbf{x}_0]+\sum_{i=0}^{l-1}\mathrm{Var}[\mathbf{x}_i]\mathbb{E}\left[\mathrm{Var}\left[F_i\left(\frac{\mathbf{x}_i}{\sqrt{\mathrm{Var}[\mathbf{x}_i]}}\right)\mid\mathbf{x}_i\right]\right]=\Omega(2^l)

この分散の増加は勾配爆発の原因となり学習においてはあまり嬉しくない性質.そこで,初期状態においてある時点のactivationと重みの勾配のノルムがcross-entropy lossにおいてある下限を持つことを示す.

Definition 1 (positively homogeneous function of first degree)

ある関数f:\mathbb{R}^m\rightarrow\mathbb{R}^nがpositively homogeneous of first degreeであるとは任意の入力\mathbf{x}\in\mathbb{R}^mにおいて\alpha\gt 0とした時,f(\alpha\mathbf{x})=\alpha f(\mathbf{x})という性質を持つ.

Definition 2 (positively homogeneous set of first degree)

\Thetaf(\mathbf{x})のパラメータの集合とし,\Theta_{ph}=\{\theta_i\}_{i\in S}\subset\Thetaとする.\Theta_{pH}がpositively homogeneous setであるとは,任意の[tex:\alpha\gt 0においてf(\mathbf{x};\Theta\setminus\Theta_{ph},\alpha\Theta_{ph})=\alpha f(\mathbf{x};\Theta\setminus\Theta_{ph},\Theta_{ph})という性質を持つ.ただし\alpha\Theta_{ph}\{\alpha\theta_i\}_{i\in S}

P.h.(positively homogeneous)関数の例としてはNNで使われる演算(fully-connected,convolution,pooling,addition,concatenation,dropout,ReLUなど)があげられる.さらにp.h.関数に関して次の命題が成り立つ.

Propostion 1

P.h.関数で構成される関数もまたp.h.関数.

ここで一般的な分類問題を考える.すなわちcクラスの分類をcross-entropy lossを用いて解く.fを最終出力がsoftmax層のNNを表す関数として,cross-entropy lossをl(\mathbf{z},\mathbf{y})=-\mathbf{y}^T(\mathbf{z}-\log\sum\exp(\mathbf{z}))と定義する.ただし,\mathbf{y}はone-hotラベルで,\mathbf{z}=f(\mathbf{x})\in\mathbb{R}^cとする.ミニバッチ\mathcal{D}_M=\{(\mathbf{x}^{(m)},\mathbf{y}^{(m)}\}_{m=1}^Mを使った学習を考えれば,cross-entropy lossはl_{avg}(\mathcal{D}_M)=\frac{1}{M}\sum_{m=1}^Ml(f(\mathbf{x}^{(m)}),\mathbf{y}^{(m)})となる.ここでネットワークfについて次の過程を置く.

  1. fはsequentialな構成,すなわちネットワークのブロックをp.h.関数\{f_i\}_{i=1}^Lとすれば入力から出力までをf(\mathbf{x}_0)=f_L(f_{L-1}(\dots f_1(\mathbf{x}_0)))と計算可能である.

  2. 全結合層の重みの要素はi.i.dに平均0の対象な分布からサンプリングされている.

Theorem 1

i番目のブロックの入力を\mathbf{x}_{i-1}とすれば,仮定1から次の関係が得られる.

\displaystyle
\left|\frac{\partial l}{\partial\mathbf{x}_{i-1}}\right|\geq\frac{l(\mathbf{z},\mathbf{y})-H(\mathbf{p})}{|\mathbf{x}_{i-1}|}

\mathbf{p}はsoftmaxによって得られる確率で,Hはシャノンエントロピー.証明は記事が長くなりそうなのでAppendix A参照.エントロピーは上界を持ち,|\mathbf{x}_{i-1}|は下位のブロックでは小さい.ロスにおける爆発は下位のブロックの入力に依存して勾配のノルムが大きくなることで起こる.次の定理でp.h. setの勾配のノルムが下限を持つことを示す.

Theorem 2

仮定1から次の関係が成り立つ.

\displaystyle
\left|\frac{\partial l_{avg}}{\partial\Theta_{ph}}\right|\geq\frac{1}{M|\Theta_{ph}|}\sum_{m=1}^Ml(\mathbf{z}^{(m)},\mathbf{y}^{(m)})-H(\mathbf{p}^{(m)})=G(\Theta_{ph})

さらに,仮定1と2から次の関係が得られる.

\displaystyle
\mathbb{E}G(\Theta_{ph})\geq\frac{\mathbb{E}[\max_{i\in[c]}z_i]-\log(c)}{|\Theta_{ph}|}

正規化のないResNetにおけるp.h. setsの例としては以下の3つがある.

  1. 一番最初のmax pooling前のconvolution層

  2. ダウンサンプリング等の際に生じるskip connection中のconvolution層とその時のresidual branchのconvolution層

  3. softmax前の全結合層

Theorem 2はもし初期状態において\mathbf{z}が爆発していたならば,この3つの層が勾配爆発の原因となることを示していて,仮に正規化のないResNetを従来の方法で初期化すればこの現象が起こるということを言っている.

ZeroInit

Scale of the output

これまでの流れから勾配爆発を起こさないためには初期状態において出力が爆発しないことを保証する必要がある.この考えから次の初期化のための良い方針が得られる.

(a.) 出力のスケールは\mathbb{E}[\max_{i\in[c]}z_i]=\mathcal{O}(1)のように深さとは独立であるべき

ナイーブな方法としては出力層を0に初期化すること.ただし,この場合には最終層にスケールを抑えることを押し付けているため,ノルム\mathcal{O}(1)の勾配で数回更新をしてしまえば爆発することになる.

Scale of the residual branches

Residual branchesのスケールが学習初期に深さに応じて爆発することを防ぐ必要がある.すると次のような初期化方針が得られる.

(b.) Residual branchesのスケールは\mathrm{Var}[F_l(\mathbf{x}_l)]=\mathcal{O}(\frac{1}{L})のようにバランスが取れているべき

この方針はL個のresidual blockを持つネットワークfが与えられた時,m層を持つresidual branchに対して次の初期化方法を導く.(b.)を満たすことに関しての細かい話は省略.

ZeroInit (How to train a deep residual network without normalization)

  1. Classification layerと各residual branchの最後の畳み込み層を0に初期化

  2. その他の層はHeの初期化など従来の方法で初期化し,residual branches内のconvolution層においては\sqrt[2-2m]{L}でスケーリング

  3. 各ブランチにおいてconvolution, linear, elemnt-wise activation layerの前に1で初期化されたscalar multiplierと0で初期化されたscalar biasを挿入

3に関してはbatch normalization層のaffine変換と同様の変換で論文のFigure 1の一番右の図を見ればどこに挿入されているかわかる.この初期化は勾配の爆発を防ぐことができて,DenseNetのような場合にも適用可能とのこと(ただしその辺りはfuture workとしてる).

まとめ

かなり良好な結果を出しているよう.ただやはりBatchNormの破壊力は高いなという印象.

ZeroInit自体は生成モデルのGlowやfacebookのAccurate, Large Minibatch SGD: Training ImageNet in 1 Hourの論文でも使われているので学習を安定化させたりするのにはかなり効果があるっぽいのでそこに理論的に踏み込んだと見るといい論文.

PeerNets: Exploiting Peer Wisdom Against Adversarial Attacksを読んだのでメモ

はじめに

PeerNets: Exploiting Peer Wisdom Against Adversarial Attacksを読んだのでメモ.adversarial attackに強いモデルをgraph convolutionを利用して作ったというもの.

Peer Regularization

データの空間構造を利用した新しいDNNを提案するというもの.それにより摂動(adversarial attack)の影響を減らすことができるというのが主張.

内容としてはpeersと呼ばれるN個の画像の特徴マップ\mathbf{X}^1,\dots,\mathbf{X}^N\in\mathbb{R}^{n\times d}を利用した演算を導入する(nピクセルの数で,dピクセルの持つ特徴量の次元数).処理としては入力のあるピクセルに対して全peer画像のd次元特徴マップの全ピクセルからK近傍を探し,ピクセルの持つ値をその近傍との重み付き平均で置き換えてしまおうというもの.peer画像にはadversarialな画像がないため摂動の影響を減らすことができるというのが主張.

K近傍との重み付き平均はgraph attention network (GAT)を使って計算する.GATは次の計算によってエッジの重みを推定するもの.

\displaystyle
\alpha_{ij_kpq_k}=\frac{\mathrm{LeakyReLU}(\exp(a(\mathbf{x}_p^i,\mathbf{x}_{p_k}^{j_k})))}{\sum_{k'=1}^K\mathrm{LeakyReLU}(\exp(a(\mathbf{x}_p^i,\mathbf{x}_{p_k'}^{j_k'})))}

各添字はiが入力の画像で,j_k\in\{1,\dots,N\}が参照しているpeer画像,p,p_k,q_kは画像のピクセルを表す(peer画像の画素を示す記号がp_kになっているがおそらくq_kの間違い).また,a(\cdot)ニューラルネットによる変換を表す.この重みを使って次のように平均をとることで注目画素の値を変更する.

\displaystyle
\tilde{\mathbf{x}}_p^i=\sum_{k=1}^K\alpha_{ij_kpq_k}\mathbf{x}_{q_k}^{j_k}

この操作はnon-local means denoisingみたいなものとのこと.

実践的なところとしては,K近傍の計算を全ピクセルでやるのはしんどいのでいろいろと近似で行ったとのこと.またpeer画像は学習データ全体からランダムにN枚選択して計算する.

まとめ

ちょっと短いけどこんな感じ.計算に関して目をつむればベースラインとしてadversarial attackに関する頑健性がかなり上がっている.

GRAPH ATTENTION NETWORKSを読んだのでメモ

はじめに

GRAPH ATTENTION NETWORKSを読んだのでメモ.

気持ち

Kipf & Wellingの提案したGraph Convolutional Networks (GCN)は学習されたフィルタがグラフラプラシアン固有ベクトルに依存するため異なるグラフ構造に対応することができない.そこでフィルタがグラフ構造に依存しないようなアテンションに基づくGCN,Graph Attention Networks (GAT)を提案するというもの.

GAT

Graph attentional layer

まず,一層のgraph attentional layerを考える.入力は各ノードの特徴ベクトルで\mathbf{h}=\{h_1,\dots,h_N\},h_i\in\mathbb{R}^Fとして定義する.ただし,Nはノード数で,Fは特徴ベクトルの次元数.出力としては\mathbf{h}'=\{h_1',\dots,h_N'\},h_i'\in\mathbb{R}^{F'}となる.

ここでは学習パラメータ\mathbf{W}\in\mathbb{R}^{F'\times F}を持つ線形変換を考える.この線形変換は全てのノードに適用される.その際に,次のshared attentional mechanism a:\mathbb{R}^{F'}\times\mathbb{R}^{F'}\rightarrow\mathbb{R}によってアテンション係数を計算する.

\displaystyle
e_{ij}=a(\mathbf{W}h_i,\mathbf{W}h_j)

これはノードiにおけるノードjの特徴の重要度を表す.上記の形だと全てのノードの組み合わせを計算する必要が出てくるため,ここでは隣接しているノードj\in\mathcal{N}_iのみで計算を行う.計算された各係数のオーダーを合わせるため次のようにsoftmax関数を使って正規化を行う.

\displaystyle
\alpha_{ij}=\mathrm{softmax}_j(e_{ij})=\frac{\exp(e_{ij})}{\sum_{k\in\mathcal{N}_i}\exp(e_{ik})}

実験においては,アテンション係数を計算するための関数aは1層のニューラルネットワーク\mathbf{a}\in\mathbb{R}^{2F'}とLeakyReLUを使ったとのこと.そのため愚直に式を書けば次のようになる.

\displaystyle
\alpha_{ij}=\frac{\exp\left(\mathrm{LeakyReLU}\left(\mathbf{a}^T[\mathbf{W}h_i\|\mathbf{w}h_j]\right)\right)}{\sum_{k\in\mathcal{N}_i}\exp\left(\mathrm{LeakyReLU}\left(\mathbf{a}^T[\mathbf{W}h_i\|\mathbf{W}h_k]\right)\right)}

変数の右肩のTは行列の転置,\|は変数の結合(concatenation)を表す.

この係数を使って各層での変換は次のように記述される.

\displaystyle
h_i'=\sigma\left(\sum_{j\in\mathcal{N}_i}\alpha_{ij}\mathbf{W}h_j\right)

さらに,学習過程におけるアテンション係数の安定化のために次のようなmulti-head attentionの構造を取り入れたとのこと.

\displaystyle
h_i'=\overset{K}{\underset{k=1}{\|}}\sigma\left(\sum_{j\in\mathcal{N}_i}\alpha_{ij}^k\mathbf{W}^kh_j\right)

要はK個の独立したアテンション機構を導入するということ.基本的には各アテンションごとの出力を結合するが,最後の識別層においては各出力の平均を計算したとのこと.

まとめ

なんとなくアテンションを計算するための線形変換と,各層における線形変換の重み係数が同じなのに違和感(単純に同じ文字を使っているだけで別なパラメータなのかもしれないが).multi-head attentionもただパラメータ増えて表現力が上がったからうまくいっただけな気もするがどうなのか.

感覚的にはグラフ構造を作る際の距離関数を学習ベースで決めるということだと思うが,PPIデータセットを使った実験ではベースラインと比較して飛躍的に性能が向上していたので実装して試したいところ.

Higher-order Graph Convolutional Networksを読んだのでメモ

はじめに

Higher-order Graph Convolutional Networksを読んだのでメモ

気持ち

現状のgraph convolutional networks(GCN)はone-hopの隣接関係のみを考慮したものになっていて,高次の情報を捉え切れていない.そこでmulti-hopな重み付き隣接行列を使ったGCNを提案するというもの.

Graph Self-Attention Layer

KipfとWellingが提案した多層のGCNは次の形で表現される.(この論文は前に読んでメモを残した)

\displaystyle
\mathbf{H}^{(l+1)}=\sigma(\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-\frac{1}{2}}\mathbf{H}^{(l)}\mathbf{W}^{(l)})

ここで\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}_Nは自己ループを加えた隣接行列で\tilde{\mathbf{D}}\tilde{\mathbf{A}}を使って計算された度数行列.\mathbf{H}^{(l)}はグラフのノードが持つl層目の特徴ベクトルで\mathbf{W}^{(l)}は学習パラメータ.

ここで\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-\frac{1}{2}}は正規化された対称行列で,これはone-hopな隣接関係にあるノードの重み付き和を表現していることになる.そのためノードiに隣接したノード集合\mathcal{N}_iを使えば次のように書き直せる.

\displaystyle
\mathbf{h}_i^{(l+1)}=\sigma\left(\sum_{j\in\mathcal{N}_l^{(\tilde{\mathbf{A}})}}\alpha_{i,j}\mathbf{h}_j^{(l)}\mathbf{W}^{(l)}\right)

\alpha_{i,j}=\frac{1}{\sqrt{\mathrm{deg}(i)\mathrm{deg}(j)}}は正規化の部分にあたる項.

上記のGCNの\alphaを次のようなネットワークの推論結果に置き換えるGraph Attention Networks (GAT)というものも提案されている.

\displaystyle
\alpha_{i,j}=\frac{\exp\left(\mathrm{LeakyReLU}\left(\mathbf{a}[\mathbf{h}_i\mathbf{W}\mathbf{h}_j\mathbf{W}]\right)\right)}{\sum_{k\in\mathcal{N}_i^{(\tilde{\mathbf{A}})}}\exp\left(\mathrm{LeakyReLU}\left(\mathbf{a}[\mathbf{h}_i\mathbf{W}\mathbf{h}_k\mathbf{W}]\right)\right)}

アテンションベクトル\mathbf{a}は学習パラメータ.細かいところはまた今度論文読む.

Convolutional Layer with Motif Attention

ここから論文の貢献部分.GCNもGATもone-hopしか見ないため,ノードの隣接関係が常に最適とは限らない(Fig 2に簡単な例が図解されてる).そこでここではmotif(グラフの隣接関係のpriorのようなもの)を導入して様々な隣接関係を考慮する(motifについてはFig 1の(d)に例が示されている).

ノードN=|\mathcal{V}|,エッジM=|\mathcal{E}|で定義されるグラフ\mathcal{g}=(\mathcal{V},\mathcal{E})と,T個のmotif \mathcal{H}=\{H_1,\dots,H_T\}が与えられた時,motifに対応したT個の隣接行列\mathcal{A}=\{\mathbf{A}_1,\dots,\mathbf{A}_T\}を構成する.隣接行列が計算できると,motif-induced neighborhoods \mathcal{N}_i^{(\mathbf{A}_t)}を定義することができ,この隣接関係を用いてGCNの計算を行うことで様々な隣接関係を考慮した畳み込みが可能.

ここで\Psi:\mathbb{R}^{N\times N}\rightarrow\mathbb{R}^{N\times N}で定義されるmotif-based matrix formulationを導入する.関数\Psiが与えられた時,motif-based matrices \tilde{\mathbf{A}}_t=\Psi(\mathbf{A}_t)を得ることが可能.以下に,\Psiの様々な表現をまとめる.

Unweighted Motif Adjacency w/ Self-loops

最も単純な形として次のような隣接行列が考えられる.

\displaystyle
\tilde{\mathbf{A}}_{i,j}=\left\{
\begin{matrix}
1\:\:i=j \\
1\:\:\mathbf{A}_{i,j}\gt 0 \\
0\:\:\mathrm{otherwise}
\end{matrix}\right.

ただしこれは重みを考慮しない分,motif-induced adjacencyを十分に活用できない.

Weighted Motif Adjacency w/ Row-wise Max

Motif adjacencyの重みを保持した次のような表現が考えられる.

\displaystyle
\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{M}

\mathbf{M}は対角行列でその対角成分はM_{i,j}=\max_{1\leq j\leq N}A_{i,j}で定義される.これは自己ループに隣接ノードの中で最も重要度の高いノードと同様の重要度を割り当てることを意味する.

Motif Transition w/ Row-wise Max

自己ループに行方向の最大値を割り当てた重み付きグラフ上でのランダムウォークの遷移行列はP_{i,j}=\frac{A_{i,j}}{(\sum_kA_{i,k})+(\max_{1\leq k\leq N}A_{i,k})}で定義される.すると,次のようなrandom walk motif transition matrixが定義できる.

\displaystyle
\tilde{\mathbf{A}}=\mathbf{D}^{-1}(\mathbf{A}+\mathbf{M})=\mathbf{P}

Absolute Motif Laplacian

Absolute Laplacian matrixを次のように定義する.

\displaystyle
\tilde{\mathbf{A}}=\mathbf{D}+\mathbf{A}

この表現は自己ループの重要度が隣接ノードの重要度の和で定義されるため,自己ループを重要視しやすくなる.

Symmetric Normalized Matrix w/ Row-wise Max

次のようなsymmetric normalized matrixを計算することもできる.

\displaystyle
\tilde{\mathbf{A}}=\mathbf{D}^{-\frac{1}{2}}(\mathbf{A}+\mathbf{M})\mathbf{D}^{-\frac{1}{2}}

以上がこの論文で定義されている5パターンの\Psiの表現.さらにステップサイズKが与えられた元で,k-step motif-based matricesを各T個のmotifについて定義する.

\displaystyle
\tilde{\mathbf{A}}_t^{(k)}=\Psi(\mathbf{A}_t^k),\:\mathrm{for}\:k=1,\dots,K\:\mathrm{and}\:t=1,\dots,T\\
\mathrm{where}\\
\Psi(\mathbf{A}_t^k)=\Psi(\underbrace{\mathbf{A}_t,\dots,\mathbf{A}_t}_{k})

K\gt 1の場合,より広い範囲のノード(k-hopの隣接ノード)から情報を集約することができる.

ここで,ステップサイズKT個の異なるmotifが与えられた時,ステップサイズとmotif毎に個別にGCNの計算を行い,最終層で特徴ベクトルを結合することが考えられる.ただし単純に結合すると特徴ベクトルが大きくなりすぎるという問題がある.そこでアテンション構造を各層に導入して重み付き和をとることでこれを回避する.

まず,第l層にf_l:\mathbb{R}^{S_l}\rightarrow\mathbb{R}^Tと,f_l':\mathbb{R}^{S_l}\times\mathbb{R}^T\rightarrow\mathbb{R}^Kの二つの関数を導入する.S_lは第l層における状態空間で,関数の出力はsoftmax関数を通って確率表現になっている.これはノードiの状態が与えられた時,ノードiに最も関連のあるmotif tとステップサイズkを推薦することを意味する.

さらに二つの行列を結合して作られるstate matrixを定義する.

\displaystyle
\mathbf{S}_l=\left[\Psi(\mathbf{A})\mathbf{H}^{(l)}\mathbf{W}^{(l)}\:\mathbf{C}\right]

\mathbf{W}^{(l)}\in\mathbb{R}^{N\times D_l}は入力をD_l次元に埋め込む重み行列で,\Psi(\mathbf{A})\mathbf{H}^{(l)}\mathbf{W}^{(l)}はone-hopの隣接関係から得られる局所的な情報を含んだ行列.\mathbf{C}\in\mathbb{R}^{N\times C}はmotif count matrixで各ノードが所属しているC個の異なるmotifを数えることによって局所的な構造に関する情報を与えていて,最初にあらかじめ計算される.

ここで,\mathbf{f}_i=f(\mathbf{s}_i)をmotif probabilitiesとし,\mathbf{f}_i'=f'(\mathbf{s}_i,\mathbf{f}_i)をステップサイズのためのprobability vectorとする.t_i\mathbf{f}_iの最大値のインデックスとし,k_i\mathbf{f}_i'の最大値のインデックスとすれば,アテンションは次のようなN\times N行列で定義できる.

\displaystyle
\hat{\mathbf{A}}=\left[
\begin{matrix}
\left(\tilde{\mathbf{A}}_{t_1}^{k_1}\right)_{1,:}\\
\vdots\\
\left(\tilde{\mathbf{A}}_{t_N}^{(k_N)}\right)_{N,:}
\end{matrix}
\right]

この層ごとに計算される行列\hat{\mathbf{A}}をGCNの\tilde{\mathbf{A}}の代わりに使うことでMotif Convolutional Networksが計算される.

まとめ

ヒューリスティックな手法と理論由来な手法が融合したような感じ.ただ,隣接行列に関してT motifとKステップの組み合わせぶん計算するせいで,T\times Kの隣接行列が必要になるからかなりの計算コストになりそう.

Clustering with Deep Learning: Taxonomy and New Methodsを読んだのでメモ

はじめに

Clustering with Deep Learning: Taxonomy and New Methodsを読んだのでメモ.

気持ち

DNNベースのクラスタリング手法について体系的にまとめて定式化することで,システマティックに新しいクラスタリングの方法を作れる様にしようというもの.

モデル構造

多くのDNNのクラスタリング手法は入力データクラスタリングしやすい表現(潜在表現)に落とし込むための"main branch"が存在する.そのためのモデルには従来以下の5つのモデルが使われる.

  • Multilayer Perceptron (MLP)

  • Convolutional Neural Network (CNN)

  • Deep Belief Network (DBN)

  • Generative Adversarial Network (GAN)

  • Variational Autoencoder (VAE)

各々の説明は割愛.

潜在表現

クラスタリングしやすい表現を得る際の方法としてmain branchの最後の表現のみを得る場合と複数の層から得る場合の2種類に分けられる.

  • One layer

 利点としては次元が低いこと.主に最終層の表現が使われる.

  • Several layers

 利点としては表現がリッチであること.

Non-clustering loss

Non-clustering lossはクラスタリングとは関係のない損失項で正則化項の様な役割として用いられる.以下の選択肢がある.

  • No non-clustering loss

Non-clustering lossを使わない(正則化なし).局所解にハマりやすいという点が指摘されてるがたまにいい結果をもたらす場合もある.

  • Autoencoder reconstruction loss

Decoderを使った再構成誤差.入力と再構成されたデータ間の距離を損失項とし一般的には平均2乗誤差.再構成に必要なデータの重要な情報を残した潜在表現を得られることが保証される.

  • Self-Augmentation Loss

元のデータとaugmentationされたデータ間の表現の類似性を保証する.次のような関数で表される.

\displaystyle
L=-\frac{1}{N}\sum_Ns(f(x),f(T(x)))

xが元のデータでTがaugmentationの関数.f(x)は潜在表現への変換でsは類似度でcross-entropy等.

  • Other tasks

学習データに関する追加情報の項.クラスや属性ラベルが使える場合など.

Clustering loss

クラスタリング手法に依存した損失項.一番重要な部分で以下のような様々な方法が存在.

  • No clustering loss

Non-clustering lossのみを使う方法.次元圧縮等の目的で使われる.基本的にclustering lossがあった方が良い結果となる.

  • k-Means loss

K-Meansしやすい表現を獲得するための損失.データ点がクラスタ中心の周りに分布するような表現を得る方法で次のような損失関数で定義.

\displaystyle
L(\theta)=\sum_{i=1}^N\sum_{k=1}^Ks_{ik}| z_i-\mu_k|^2

z_iはデータ点の潜在表現で\mu_kクラスタ中心.s_{ik}は所属クラスタを表すboolean(普通はone-hot?).

  • Cluster assignment hardening

データ点をクラスタにソフトに割り当てる損失.1例として次のstudentのt分布を元にした関数を使ってソフトな割り当てを行う.

\displaystyle
q_{ij}=\frac{(1+| z_i+\mu_j|^2/\nu)^{-\frac{\nu+1}{2}}}{\sum_{j'}(1+| z_i+\mu_{j'}|^2/\nu)^{-\frac{\nu+1}{2}}}

\nuはハイパーパラメータの定数.データ点の潜在表現とクラスタ中心間の正規化された類似度となっていてクラスタの所属確率としてみなせる.Cluster assignment harging lossは上記の確率が一つのクラスタのみに大きくなるように強いる損失で,そのために次の補助分布を導入する.

\displaystyle
p_{ij}=\frac{p^2_{ij}/\sum_iq_{ij}}{\sum_{j'}(q_{ij'}^2/\sum_iq_{ij'})}

この補助分布と正規化された類似度によって表現される分布間のKLダイバージェンスを損失とする.

\displaystyle
L=\sum_i\sum_jp_{ij}\log\frac{p_{ij}}{q_{ij}}

  • Balanced assignment loss

他の損失と同時に用いられ,クラスタ間の大きさのバランスをとる.各クラスタの大きさ(所属するデータ点の量)はある程度均一であるという仮定から成り立ち,次のKLダイバージェンスとして表現できる.

\displaystyle
L_{ba}=D_{KL}(G| U)

Uは一様分布でGクラスタの大きさに関する分布で次のように定義される.

\displaystyle
g_k=P(y=k)=\frac{1}{N}\sum_iq_{ik}

当然データに偏りがある場合は成り立たず,クラスタサイズに何かしらの事前知識がある場合には一様分布を別な分布に置き換えることもできる.

  • Locality-preserving loss

元の表現での位置関係のようなものを保存するように強いる損失.データ点x_ik近傍集合に対し近傍のデータ点の類似度s(x_i,x_j)を使って次のような損失関数を定義する.

\displaystyle
L_{lp}=\sum_i\sum_{j\in N_k(i)}s(x_i,x_j)| z_i-z_j|^2

  • Group sparsity loss

隠れユニットがクラスタG個に分けられるという仮定を置いたもので,データ点x_iの潜在表現は{\phi^g(x_i)}_{g=1}^GのようにG個の表現として与えられ,group sparsity lossは次のような損失関数として定義される.

\displaystyle
L_{gs}=\sum_{i=1}^N\sum_{g=1}^G\lambda_g|\phi^g(x_i)|

{\lambda_g}_{g=1}^G\lambda_g=\lambda\sqrt{n_g}で定義される重み.ただしn_gはグループサイズ.

  • Cluster classification loss

後述のcluster updateの間に得られるクラスタの割り当て結果をクラスラベルとしてclassification lossに使うというもの.

  • Agglomerative clustering loss

類似度が最も高いクラスタをstopping criterionが満たされるまで統合していき,統合されたクラスタ間の類似度を最適化するような手法.クラスタリングに適した表現が得られる.

損失の組み合わせ方

Clustering lossとnon-clustering lossは次のように組み合わされる.

\displaystyle
L(\theta)=\alpha L_c(\theta)+(1-\alpha)L_n(\theta)

L_c(\theta)はclustering lossでL_n(\theta)はnon-clustering loss.\alpha\in[0;1]は二つの関数のバランスをとるハイパーパラメータ.\alphaの決め方には次のような選択肢がある.

  • Pre-training, fine-tuning

まず\alpha=0として学習した後,\alpha=1とする方法.場合によっては結果を悪くすることもある.

  • Joint training

0\lt\alpha\lt 1として学習する方法.

  • Variable schedule

\alphaを変数と見て,学習中に変化させていく方法.例えば\alphaを初期では小さくして徐々に大きくしていくなど.

基本的に\alpha=1\alpha=0も欠点がある.

クラスタの更新

大雑把にクラスタリングは階層的なものとクラスタ中心に基づく手法に分けられる.学習段階でクラスタの割り当て結果が(クラスタ中心に基づく方法においてはクラスタ中心も)更新されていく.その更新の仕方は一般的に次の二つどちらか.

クラスタの割り当て結果は確率として定義され,ネットワークのパラメータとして定義され逆伝播によって最適化される.

クラスタの割り当て結果は決定的でネットワークのパラメータ更新とは別に更新される.この場合にはさらに次の二つの更新方法がある.

・Number of iterations

クラスタの割り当て結果が固定されるまで繰り返す方法

・Frequency of updates

ネットワークがP回更新されるたびに割り当て結果を更新する方法

学習後

学習終了後,仮に学習過程でクラスタ結果が得られたとしていても,次の理由から学習された特徴を用いて再びクラスタリングし直すのが一般的.

  • Clustering a similar dataset

獲得された潜在表現の一般生を評価するため別なデータで検証すべきというもの.

  • Obtaining better results

ある特定の状況下においては学習過程で得られたクラスタ結果よりも良い結果が得られる場合があるというもの.

関連研究

以下に載せた論文の表1に従来手法が論文の分類に合わせてまとまっている. f:id:peluigi:20180918190536p:plain

New method

手法を項目ごとに分けて,従来手法を表1のようにまとめることで簡単に分析ができて,手法の組み合わせで課題に適した新しいアルゴリズムを組むことが可能というのが主張.実際そのようなアプローチで組み立てた手法のクラスタリング結果が図3,4に記述されていて良く機能しているように見える.

まとめ

サーベイでも手法提案でもない新しい論文の書き方を見た気がする.読みやすく綺麗にまとまったいい論文だった.