SRFlow: Learning the Super-Resolution Space with Normalizing Flowを読んだのでメモ

はじめに

SRFlow: Learning the Super-Resolution Space with Normalizing Flowを読んだのでメモ．従来のdeep super resolutionが決定的な出力をすることに対し，超解像はそもそも決定的に決まる問題ではないという考えからconditionalなgenerative flowを使って，低解像度画像を条件とする確率モデルとして超解像を実現．

SRFlow

手法はシンプルで，基本的にはGlowをベースとしている．低解像度画像を条件としてモデルに与えるために，まず低解像度画像 $\mathbf{x}$ をCNN $g_\theta(\cdot)$ により， $\mathbf{u}=g_\theta(\mathbf{x})$ と変換する．このCNNはinvertibleではなく通常のCNN．得られた表現 $\mathbf{u}$ をaffine coupling層へ次のように導入することでconditionalなモデルとする．

$\displaystyle \mathbf{h}_A^{n+1}=\mathbf{h}_A^n\\ \mathbf{h}_B^{n+1}=\exp(f_{\mathbf{\theta},s}^n(\mathbf{h}_A^n;\mathbf{u}))\cdot\mathbf{h}_B^n+f_{\mathbf{\theta},b}^n(\mathbf{h}_A^n;\mathbf{u})$

$\mathbf{h}^n=\{\mathbf{h}^n_A,\mathbf{h}^n_B\}$ は $n$ 層目の出力を2分割したもの．アフィン変換のパラメータを出力するニューラルネットに $\mathbf{u}$ も同時に入力するというのが通常のgenerative flowとの違い．

さらにAffine Injector層も導入する． Affine injector層は次のように表現される．

$\displaystyle \mathbf{h}^{n+1}=\exp(f_{\mathbf{\theta},s}^n(\mathbf{u}))\cdot\mathbf{h}^n+f_{\mathbf{\theta},b}(\mathbf{u})$

Coupling層のようにアフィン変換のパラメータをニューラルネットに出力させるもので，変換対象はgenerative flowの中間出力で，パラメータを出力するニューラルネットへの入力が $\mathbf{u}$ となっている．これも条件付けを強めている．

モデルの学習は通常のgenerative flowと同様に変数変換の公式から導かれる尤度の最大化によって実現され，従来のdeepモデルによる超解像と違い複数の損失の組み合わせなどが必要ない．

まとめ

結果がかなり良い．特に低解像度画像で潰れてしまい超解像の際に不定性が残るような画素はサンプリングごとに変化しており（Fig. 3参照），期待通りの働きができていることがわかる．

2020-06-18

Semi-Supervised Semantic Segmentation with Cross-Consistency Trainingを読んだのでメモ

semi supervised segmentation

はじめに

Semi-Supervised Semantic Segmentation with Cross-Consistency Trainingを読んだのでメモ． semantic segmentationのための半教師あり学習手法．

Cross-Consistency Training

semantic segmentationでは入力の空間では半教師あり学習のcluster assumption（同じクラスに属するデータが入力の空間で近いという仮説）が成り立たない（領域分割ではデータ点はピクセルのため同じクラスに属すると言って色が近いとは限らない）が，CNNの中間特徴では成り立つという観測の下，中間層に摂動を与えてconsistencyを課すというもの．

まず，ラベル付きデータを集合 $\mathcal{D}_l=\{(\mathbf{x}_1^l,y_1),\dots,(\mathbf{x}_n^l,y_n)\}$ で表し，ラベルなしデータを集合 $\mathcal{D}_u=\{\mathbf{x}_1^u,\dots,\mathbf{x}_m^u\}$ で表す．仮定として $m\gg n$ とする．

encoder $h$ とdecoder $g$ から成り立つモデル $f=g\circ h$ を考える．提案するモデルでは上記モデルに対し $K$ 個のauxiliary decoder $\{g_a^k\}_k^K$ を導入する．ベースのdecoder (main decoder) $g$ は教師付きラベルによって学習が進み，auxiliary decoderはラベルなしデータによって学習が進んでいく．

より具体的には教師付きデータに関しては次の損失をencoderとmain decoderに関して最小化する．

$\displaystyle \mathcal{L}_s=\frac{1}{|\mathcal{D}_l|}\sum_{\mathbf{x}^l_i,y_i\in\mathcal{D}_l}\mathbf{H}(y_i,f(\mathbf{x}_i^l))$

ただし， $\mathbf{H}(\cdot, \cdot)$ はクロスエントロピーを表す．ラベルなしデータに関してはまず共通のencoderで中間表現 $\mathcal{z}_i=h(\mathbf{x}_i^u)$ とした後， $R$ 個の確率的な摂動を与える関数 $p_r,r\in[1,R]$ のどれかをランダムに選び， $K$ 個の異なる摂動が加えられた中間表現 $\tilde{\mathbf{z}}_i^k$ を作り，それぞれを $K$ 個のauxiliary decoderへ入力する．これに対し下記の損失を最小化するようにauxiliary decoderとencoderを学習する(main decoderに関しては勾配を計算しない)．

$\displaystyle \mathcal{L}_u=\frac{1}{|\mathcal{D}_u|}\frac{1}{K}\sum_{\mathbf{x}_i^u\in\mathcal{D}_u}\sum^K_{k=1}\mathbf{d}(g(\mathbf{z}_i),g_a^k(\tilde{\mathbf{z}}_i))$

$\mathbf{d}(\cdot,\cdot)$ は距離関数で自乗誤差やJSダイバージェンスなど．よって最終的な損失は次のようになる．

$\displaystyle \mathcal{L}=\mathcal{L}_s+\omega_u\mathcal{L}_u$

$\omega_u$ はハイパーパラメータで，他のconsistency regularizationと同様に学習中にrampupする．

auxiliary decoderに関して，イントロダクションにはラベルなしデータを利用するため導入すると書いてあるが，アイディアのベースとしているcluster assumptionやアルゴリズム的に導入する必然性がないため，いまいちどういう役割を担うか分からない．

Perturbaation functions

摂動としては下記の5つを利用する．

F-Noise: $N\sim\mathcal{U}(-0.3,0.3)$ としてサンプリングしたノイズを $\tilde{\mathbf{z}}=(\mathbf{z}\odot N)+\mathbf{z}$ と加える．
F-Drop: $\gamma\sim\mathcal{U}(0.6,0.9)$ としてサンプリングした閾値を使って入力を $\tilde{\mathbf{z}}\odot\mathbf{M}_\text{drop},\mathbf{M}_\text{drop}=\{\mathbf{z}'\lt\gamma\}_1$ としてマスクする．ただし， $\{\cdot\}_1$ は指示関数．大体10%から40%くらいの領域がマスクされるとのこと．
Guided Masking:main decoderの予測結果 $\hat{y}=g\circ h(\mathbf{x})$ を使って生成したマスク $\mathbf{M}_\text{obj}$ からcontext mask $\mathbf{M}_\text{con}=1-\mathbf{M}_\text{obj}$ を作り，このcontext maskにより $\mathbf{z}$ をマスクする． $\mathcal{M}_\text{obj}$ の生成は2007年に提案された手法を利用とのこと．
Guided Cutout: $\mathbf{M}_\text{obj}$ から物体らしい領域のbounding boxを取得し，それに基づき $\mathbf{z}$ に対しcutoutを行う．
Intermediate VAT: $\mathbf{z}$ に対しVATを計算．

Practical considerations

UDAで提案されたTSAと同様に，段階的に教師あり損失を計算するサンプルを増やしていく方法，an annealed version of the bootstrapped-CE (ab-CE)を使う．具体的には予測結果に対し，予測確率がある閾値 $\eta$ 以下のピクセルのみ損失を計算するというもの．式的には下記．

$\displaystyle \mathcal{L}_s=\frac{1}{|\mathcal{D}_l|}\sum_{\mathbf{x}_i^l,y_i\in\mathcal{D}_l}\{f(\mathbf{x}_i^l)\lt\eta\}_1\mathbf{H}(y_i,f(\mathbf{x}_i^l))$

式にも文章に書いてはないが，閾値判定はおそらく予測確率の最大値に対して評価する． $\eta$ は学習中に徐々に大きくしていく．意味としては，大きく間違えているサンプルから優先的に学習していくというもの．

もう一つのpracticalな要素として，弱教師付きセグメンテーションの利用をする．image-level labelはセグメンテーションラベルより入手コストが低いため存在するものとし，そのようなデータを集合 $\mathcal{D}_w=\{(\mathbf{x}_1^w,y_1^w),\dots,(\mathbf{x}_m^w,y_m^w)\}$ とする．元々のモデルの構成に加えて，image-level labelを分類するglobal average poolingを持つブランチ $g_c$ を追加し，学習する．このブランチからclass activation mappingを使ってマスク $M$ を作り，適当な閾値を使って擬似ラベル $y_p$ を作る．この擬似ラベルをCRFによりrefinementし教師データとして他の2つの損失に加え，次の損失を最小化するようにauxiliary decoderとencoderを学習する．

$\displaystyle \mathcal{L}_w=\frac{1}{|\mathcal{D}_w|}\frac{1}{K}\sum_{\mathbf{x}_i^w\in\mathcal{D}_w}\sum_{k=1}^K\mathbf{H}(y_p,g_a^k(\mathbf{z}_i))$

その他，デコーダーを追加することで複数ドメインでの学習にも利用可能とのこと．ざっくり言えば，ドメイン1とドメイン2があれば，encoderは共通でそれぞれのドメインに対応するmain decoder $g^{(1)},g^{(2)}$ とauxiliary decoder $g^{k(1)}_a,g^{k(2)}_a$ を用意して学習するというもの，

まとめ

ablationを見るとab-CEの利用が精度向上にかなり寄与するよう． auxiliary decoderの数は増やしても精度が上がったり下がったりで設定にかなり依存がありそう．個人的にはauxiliary decoderの必要性に関してもう少し説明もしくは実験が欲しかった．

2020-06-16

Bootstrap Your Own Latent A New Approach to Self-Supervised Learningを読んだのでメモ

representation learning

はじめに

Bootstrap Your Own Latent A New Approach to Self-Supervised Learningを読んだのでメモ．とにかくcontrastive learningのnegativeとの比較というものをなくしたいという思い．ただcontrastive learningにおいてnegative examplesとの比較をなくすと全てを同じ表現にする自明な解に落ちるので新たな手法，Bootstrap Your Own Latent(BYOL)を提案．

BYOL

BYOLでは二つのモデルを用意する．一つはonline networkでこれが真に学習したいモデル．もう一つはtarget networkで，online networkの教師信号を作り出すモデル． Target networkはonline networkと同一の構造でパラメータがonline networkの指数移動平均で定義される．すなわち，online networkのパラメータを $\theta$ ，target networkのパラメータを $\xi$ とすると，学習のステップごとにtarget networkのパラメータは次のように更新される．

$\displaystyle \xi\leftarrow \tau\xi+(1-\tau)\theta$

ただし $\tau$ は減衰係数．

それぞれのモデルは入力から特徴ベクトルを得る $f_\theta,f_\xi$ と表現を適当な空間へ写像する $g_\theta,g_\xi$ と，写像されたベクトルから予測を行う $q_\theta,\mathrm{sg}$ から成る．入力データ $x$ が与えられた時，画像のaugmentation $t\sim\mathcal{T},t'\sim\mathcal{T}'$ をそれぞれ二種類ランダムに選び新たな画像 $v=t(x),v'=t'(x)$ を作る．それぞれをonline networkで $y=f_\theta(v),z_\theta=g_\theta(y)$ ，target networkで $y'=f_\xi(v'),z_\xi'=g_\xi(y')$ のように写像する．得られた表現をonline networkは $\bar{q}_\theta(z_\theta)=q_\theta(z_\theta)/\|q_\theta(z_\theta)\|_2$ ，target networkは $\bar{z}_\xi'=z_\xi'/\|z_\xi'\|_2$ とそれぞれ変換し，次の二乗誤差を最小化するようにonline modelを学習する．

$\displaystyle \mathcal{L}_\theta^{\text{BYOL}}=\|\bar{q_\theta}(z_\theta)-\bar{z}_\xi'\|_2^2=2-2\cdot\frac{\langle q_\theta(z_\theta),z'_\xi\rangle}{\|q_\theta(z_\theta)\|_2\cdot\|z_\xi'\|_2}$

上記の例では $v$ をonline networkに $v'$ をtarget networkに入力する形だったが，これらを入れ替え， $v$ をtarget networkに $v'$ をonline networkに入力して計算した二乗誤差を $\tilde{\mathcal{L}}_\theta^\text{BYOL}$ と定義し，最終的な目的関数を $\mathcal{L}_\theta^\text{BYOL}+\tilde{\mathcal{L}}_\theta^\text{BYOL}$ として，これを $\theta$ について最小化する．

学習終了後は $f_\theta$ のみを保持し，任意のタスクへ利用する．

Image augmentation

BYOLで利用する画像拡張 $\mathcal{T},\mathcal{T}'$ はSimCLRと同じ候補を利用．具体的には画像をランダムに切り抜き(224,224)にリサイズし，画像反転と，brightness, contrast, saturation, hue adjustments, optional grayscale conversionなどの色変換を行い，最後にGaussian blurとsolarizationをする．

Architecture

$f_\theta$ はResNet50の出力層手前の平均プーリング層までをベースとして，パラメータを2x~4xまで増やしたResNet101, 152, 200それぞれ実験． $g$ はSimCLRと同様にMLPで構成され，隠れ層が4096次元で出力層が256次元． $q_\theta$ は $g_\theta$ と同様の構造とのこと．

Optimization

ここも他手法と同じくLARS optimizer+cosine learning rate scheduleを利用し，1000epoch学習．学習率は $0.2\times\text{BatchSize}/256$ で定義し，重み減衰を係数 $1.5\cdot10^{-6}$ で使用． target networkの減衰係数は $\tau_\text{base}=0.996$ とし， $\tau=1-(1-\tau_\text{base})\cdot(\cos(\pi k/K)+1)/2$ でスケジューリング．ただし， $k$ は学習の繰り返し回数で， $K$ は最大繰り返し回数．

まとめ

半教師あり学習で使われるmean teacherという感じ． SimCLRの時も少し思ったが，半教師あり学習と教師なし表現学習は手法的にはどんどん似通ってくるのかなと．

2020-05-21

BATCHENSEMBLE: AN ALTERNATIVE APPROACH TO EFFICIENT ENSEMBLE AND LIFELONG LEARNINを読んだのでメモ

ensemble

はじめに

BATCHENSEMBLE: AN ALTERNATIVE APPROACH TO EFFICIENT ENSEMBLE AND LIFELONG LEARNINを読んだのでメモ．

気持ち

簡単にモチベーションを言えば，通常のモデルアンサンブルはアンサンブルする分だけモデルを個別に用意する必要があるが学習にも推論にも時間がかかる．そのため，コストを減らすために一つのモデルに少量のパラメータを追加することでアンサンブルを実現する．

Method

まずベースとなるモデルの各層における重みを $W\in\mathbb{R}^{m\times n}$ とする．ここではいわゆる全結合のニューラルネットを例に説明するが，畳み込み層などへの拡張も簡単にできる．

各層は追加の学習パラメータとして $r_i\in\mathbb{R}^n$ と $s_i\in\mathbb{R}^m$ を持つ．添字 $i$ は $1$ から $M$ までのインデックスで $M$ はアンサンブルの数(モデルの数)を表す．すなわち，通常の $M$ 個のモデルを用意するアンサンブルに対し，提案する手法は各層につき $M$ 個の追加の学習パラメータ $s_i,r_i$ を持つだけとなる．

各層はこの追加パラメータを使って次のように重みを計算する．

$\displaystyle \bar{W}_i=W\circ F_i,\ \text{where}\ F_i=s_ir_i^\top$

すなわちrank-1の行列ともとの重みの要素積で $i$ 番目のモデルの重みを作り出すというもの．これは入力のベクトルを $x_n$ とすれば全結合層の計算を次のように計算を展開できる．

$\displaystyle (W^\top(x_n\circ s_i))\circ r_i$

すなわち層への入力時点で $x_n$ と $s_i$ の要素積をとり，出力で $r_i$ との要素積をとるとかけ，演算量の点で非常にリーズナブルとなる．結果として通常の独立に $M$ 個のモデルを容易するより計算コストが低い．

このモデルはいわゆるlifelong learningのようなタスクが時々刻々と変化していく問題においても，タスク毎に $r_i,s_i$ を用意することで応用が効く．

通常のモデルアンサンブルと比較したときの欠点としては学習時に入力されたバッチサイズの $M$ 倍のサンプルを計算することになるという点．通常のモデルアンサンブルなら $M$ 個のモデルは非同期に勝手に学習すればいいので1モデル分の学習で済むが，提案する方法では $M$ 個のモデルに対し共通する重み $W$ があるため，個々のモデル $s_i,r_i$ 毎に学習するわけにはいかなくなる．ただし，data parallelや分散学習などはできるのでそれはマシーンパワーで解決しろとのこと．

まとめ

実装の簡便さや性能が十分出ることから非常に使い勝手の良い手法なよう．ただ，時間があってマシンが限られる場合には従来の方法が好まれる気がするのでその辺は使い分けかなと．

2020-05-19

Prototypical Contrastive Learning of Unsupervised Representationsを読んだのでメモ

representation learning contrastive learning

はじめに

Prototypical Contrastive Learning of Unsupervised Representationsを読んだのでメモ．

気持ち

近年流行しているContrastive Learning（例えばSimCLR）はpositive pairとnegative pariを元となるデータ点が等しいかどうかで識別的に分類することで表現学習を行う．この論文ではそのようなinstance-wiseなcontrastive learningでは例えどんなに似たデータだったとしても異なるデータとして扱うためデータに内在するsemanticな構造を得られないと考え，instance-wiseではなくprototypical contrastive learningを提案する．

一言で言ってしまえば，contrastive learningとself-labeling(DeepClusterなど)の組み合わせ．

Prototypical Contrastive Learning

データセットを $X=\{x_1,x_2,\dots,x_n\}$ で定義する．学習対象のモデルを $f_\theta,v_i=f_\theta(x_i)$ とする．従来のinstance-wise contrastive learningでは次の損失を最小化する．

$\displaystyle \mathcal{L}_\text{InfoNCE}=\sum_{i=1}^n-\log\frac{\exp(v_i\cdot v_i'/\tau)}{\sum_{j=0}^r\exp(v_i\cdot v_j'/\tau)}$

$v_i'$ は $i$ 番目のデータに対する埋め込みで， $v'_j$ は一つのpositive pairの埋め込みと $r$ 個のnegative pairの埋め込みを含む． $\tau$ は温度パラメータ．

prototypical contrastive learningではこの $v'$ の代わりにprototype $c$ を利用する．さらにハイパーパラメータ $\tau$ をprototype毎の集中度 $\phi$ に置き換える．

ここでの目的は下記の対数尤度の最大化として表現される．

$\displaystyle \theta^\ast=\underset{\theta}{\mathrm{arg}\max}\sum_{i=1}^n\log p(x_i;\theta)$

ここでは仮定として，観測されたデータ $\{x_i\}_{i=1}^n$ は潜在変数 $C=\{c_i\}_{i=1}^k$ に関係があるとし，対数尤度を次のように書き直す．

$\displaystyle \theta^\ast=\underset{\theta}{\mathrm{arg}\max}\sum_{i=1}^n\log p(x_i;\theta)=\underset{\theta}{\mathrm{arg}\max}\sum_{i=1}^n\log\sum_{c_i\in C}p(x_i,c_i;\theta)$

これを直接的に最適化するのは困難であるため，次の下界を考える．

$\displaystyle \sum_{i=1}^n\log\sum_{c_i\in C}p(x_i,c_i;\theta)=\sum_{i=1}^n\log\sum_{c_i\in C}Q(c_i)\frac{p(x_i,c_i;\theta)}{Q(c_i)}\geq\sum_{i=1}^n\sum_{c_i\in C}Q(c_i)\log\frac{p(x_i,c_i;\theta)}{Q(c_i)}$

$Q(c_i)$ は $\sum_{c_i\in C}Q(c_i)=1$ を満たす分布．この不等式はJensenの不等式から得られる．等式は $\log$ の中身が定数の場合に成り立ち，そこから $Q(c_i)=p(c_i;x_i,\theta)$ が得られる．

定数 $-\sum_{i=1}^n\sum_{c_i\in C}Q(c_i)\log Q(c_i)$ を無視することで次の式の最大化として考えられる．

$\displaystyle \sum_{i=1}^n\sum_{c_i\in C}Q(c_i)\log p(x_i,c_i;\theta)$

最適化は次のEMアルゴリズムで実現される．

E-stepでは $p(c_i;x_i,\theta)$ の推定を行う．これは $v_i'=f_{\theta'}(x_i)$ 上の $k$ -meansとして実行される．prototype $c_i$ を $i$ 番目のクラスターのセントロイドとし， $p(c_i;x_i,\theta)=\mathbb{1}(x_i\in c_i)$ として計算する．この時の $f_{\theta'}(x_i)$ はMoCoと同様にmomentum encoderを利用する．
M-stepではE-stepで得られた $p(c_i;x_i,\theta)=\mathbb{1}(x_i\in c_i)$ を前述の目的関数の下界に代入して $\theta$ について最大化する．

ここでは $p(x_i,c_i;\theta)$ に対し事前分布として一様分布を仮定することで次のように書き直す．

$\displaystyle p(x_i,c_i;\theta)=p(x_i;c_i,\theta)p(c_i;\theta)=\frac{1}{k}\cdot p(x_i;c_i,\theta)$

さらに $p(x_i;c_i,\theta)$ に対して等方性のガウス分布を仮定する．

$\displaystyle p(x_i;c_i,\theta)=\exp\left(\frac{-(v_i-c_s)^2}{2\sigma_s^2}\right)/\sum_{j=1}^k\exp\left(\frac{-(v_i-c_j)^2}{2\sigma^2_j}\right)$

これを目的関数に代入すると，下記の目的関数が得られる．

$\displaystyle \theta^\ast=\underset{\theta}{\mathrm{arg}\min}\sum_{i=1}^n-\log\frac{\exp(v_i\cdot c_s/\phi_s)}{\sum_{j=1}^k\exp(v_i\cdot c_j/\phi_j)}$

ただしここでは $v$ と $c$ のl2ノルムが1に正規化されていることを仮定した．また，practicalなところとして従来のInfoNCEをコストに加える， $k$ -meansによるセントロイドの計算は複数回繰り返すというのが効いたらしく，最終的な目的関数は以下のようになる．

$\displaystyle \mathcal{L}_\text{ProtoNCE}=\sum_{i=1}^n-\left(\log\frac{\exp(v_i\cdot v_i'/\tau)}{\sum_{j=0}^r\exp(v_i\cdot v_j'/\tau)}+\frac{1}{M}\sum_{m=1}^M\log\frac{\exp(v_i\cdot c_s^m/\phi_s^m)}{\sum_{j=0}^r\exp(v_i\cdot c_j^m/\phi_j^m)}\right)$

ここまで説明が保留されていた $\phi$ だが，これはprototype $c$ 内のデータに対するmomentum encoderの出力 $\{v'_z\}_{z=1}^Z$ を使って次のように計算される．

$\displaystyle \phi=\frac{\sum_{z=1}^Z|v_z'-c|_2}{Z\log(Z+\alpha)}$

$\alpha$ は小さいクラスタが不当に大きな $\phi$ をもたないようにするためのパラメータ．意味するところとして，相対的に分散が大きいクラスタは類似度が高くなりにくく，分散が小さいクラスタは低くなりにくいということ．

まとめ

実験結果を見ると，semi-supervisedの評価で異様に精度を向上させている．論文の気持ちから，目的関数はprototypeを使った項だけで済まして欲しかった．そういった意味で，prototypeを使ったcontrastive lossのみの精度も気になる．

2020-05-15

SELF-LABELLING VIA SIMULTANEOUS CLUSTERING AND REPRESENTATION LEARNINGを読んだのでメモ

optimal transport representation learning self-supervised

はじめに

SELF-LABELLING VIA SIMULTANEOUS CLUSTERING AND REPRESENTATION LEARNINGを読んだのでメモ． K-Meansクラスタリングによりデータにラベル付け(self-labeling)を行うDeepClusterに対し，self-labelingで生成されたラベルとモデルの出力間のクロスエントロピーを最適輸送問題として考えることでself-labelingを行う手法．

Method

事前準備として色々定義する．まず，データ $I$ を適当な空間マッピングするニューラルネット $\boldsymbol{x}=\Phi(I)$ を考える．ただし， $\boldsymbol{x}\in\mathbb{R}^D$ は特徴ベクトル．さらに，特徴ベクトルを入力とし識別を行うclassification head $h:\mathbb{R}^D\rightarrow\mathbb{R}^K$ を考える．ただし， $K$ はカテゴリ数を表す．データは $N$ 点 $I_1,\dots,I_N$ あるとし，それぞれのデータに対応するラベルを $y_1,\dots,y_N\in\{1,\dots,K\}$ とする．最終的な分類スコアはsoftmax関数を用いて下記のように計算される．（論文の通りに書いたが，ここまでの定義に従えば $\Phi$ を挟んでいるので $\boldsymbol{x}_i$ は $I$ となる気がする．）

$\displaystyle p(y=\cdot|\boldsymbol{x}_i)=\mathrm{softmax}(h\circ\Phi(\boldsymbol{x}_i))$

モデルは下記のクロスエントロピーを最小化するように学習が進められる．

$\displaystyle E(p|y_1,\dots,y_N)=-\frac{1}{N}\sum_{i=1}^N\log p(y_i|\boldsymbol{x}_i)$

上記の学習は，ラベルが利用できない場合にはself-labelingの方法によって自動的にラベル付けを行う必要がある．

半教師あり学習などの枠組みではモデル $h\circ\Phi$ とラベル $y_1,\dots,y_N$ の同時最適化となるが，完全な教師なし学習では全てを同一ラベルにアサインすることによってコストを簡単に最小化してしまう．そのためここではラベルを事後分布 $q(y|\boldsymbol{x}_i)$ として下記のようにクロスエントロピーを書き直す．

$\displaystyle E(p,q)=-\frac{1}{N}\sum_{i=1}^N\sum_{y=1}^Kq(y|\boldsymbol{x}_i)\log p(y|\boldsymbol{x}_i)$

仮に事後分布をクロネッカーのデルタ $q(y|\boldsymbol{x}_i)=\delta(y-y_i)$ として決定的に定義をしたのならば上記の式は最初に定義したクロスエントロピーの式に等しい([E(p,q)=E(p|y_1,\dots,y_N)])．この式でも自明な解にたどり着くため，下記のように制約を与えることでこれを避ける．

$\displaystyle \min_{p,q}E(p,q)\ \text{subject to}\ \forall y:q(y|\boldsymbol{x}_i)\in\{0,1\}\ \text{and}\ \sum_{i=1}^Nq(y|\boldsymbol{x}_i)=\frac{N}{K}$

この制約は，各データには一つのラベルしか割り当てが行われず，各カテゴリに属するデータ数が均一であることを意味する．するとこの問題は最適輸送理論の問題として考えることが可能となる．より具体化するため $P_{yi}=p(y|\boldsymbol{x}_i)\frac{1}{N}$ をモデルから予測された $K\times N$ の同時確率行列とし，同様に $Q_{yi}=q(y|\boldsymbol{x}_i)\frac{1}{N}$ を $K\times N$ の同時確率行列とする．ここでは $Q$ を次のような輸送多面体の要素(すなわち $\{0,1\}$ ではなく $(0,1)$ の連続値)に緩和する．

$\displaystyle U(r,c):=\{Q\in\mathbb{R}^{K\times N}_+|Q\mathbb{1}=r,Q^\top\mathbb{1}=c\}$

$\mathbb{1}$ は全要素が1の列ベクトルで， $Q\mathbb{1},Q^\top\mathbb{1}$ は $Q$ を列方向，行方向へ積分することを意味している．ここで $Q$ が条件付き確率となることを要請する．すなわち

$\displaystyle r=\frac{1}{K}\cdot\mathbb{1},\ c=\frac{1}{N}\cdot\mathbb{1}$

これにより元の目的関数(クロスエントロピー)は次のように書き直される．

$\displaystyle E(p,q)+\log N=\langle Q,-\log P\rangle$

$\langle\cdot\rangle$ はフロべニウス内積（要素積+総和）で $\log$ は行列の各要素ごとに適用されるものとする．結果として最適な $Q$ は次の最小化問題を解くことで得られる．

$\displaystyle \min_{Q\in U(r,c)}\langle Q,-\log P\rangle$

これは線形計画法で溶けるが，通常データ数がミリオンオーダーでクラス数が数千になるので解くことが困難である．ここではSiknhorn Distance(以前まとめたブログ記事)で導入された次のような正則化を導入することで高速に解く方法を提案する．

$\displaystyle \min_{Q\in U(r,c)}\langle Q,-\log P\rangle+\frac{1}{\lambda}\mathrm{KL}(Q\| rc^\top)$

$\mathrm{KL}$ はKullback-Leiblerダイバージェンスで $rc^\top$ は $K\times N$ の確率行列．この正則化の導入により上記の最小化問題のかいが次のように表現される．

$\displaystyle Q=\mathrm{diag}(\alpha)P^\lambda\mathrm{diag}(\beta)$

注意として $P^\lambda$ は行列の $\lambda$ 乗ではなく要素毎の $\lambda$ 乗を表す． $\alpha$ と $\beta$ は $Q$ が確率行列の性質を満たすためのスケーリング係数ベクトルで単純な繰り返し計算で得られる．面白い知見としては， $\lambda$ は大きな値を取れば元の最適輸送問題と等しくなるが，ここでは $\lambda$ を大きくして正確に解くよりも適当な固定の $\lambda$ を使う方が良い結果が得られた．おそらく $Q$ の緩和により，各クラスに属するデータが均一であるという制約も多少緩和されるためや，smooth labelを使うと良いという知られた知見によるものと考えられる．

最終的なアルゴリズムとしては，モデル $h\circ \Phi$ と $Q$ の最適化を交互に解くことで表現学習をする．より具体的には

現在得られている $Q$ に対し，クロスエントロピーの最小化により $h\circ\Phi$ のパラメータを更新．
現在得られているモデル $h\circ\Phi$ に対し $P_{yi}=\mathrm{softmax}_y(h\circ\Phi(\boldsymbol{x}_i))$ を計算し， $\alpha$ と $\beta$ を次のように更新することで $Q$ を得る．

$\displaystyle \forall y:\alpha_y\leftarrow[P^\lambda\beta]^{-1}_y\ \forall i:\beta_i\leftarrow[\alpha^\top P^\lambda]_i^{-1}$

$Q$ の更新は行列ベクトル積であり計算オーダーは $\mathcal{Q}(NK)$ であるため，線形計画法で解くよりもリーズナブルに計算が可能(とは言え $NK\approx10^9$ くらいなのでどうなのかという疑問がある)．論文によれば繰り返し計算はGPUで収束まで2分程とのこと．

解釈

ここまでのアルゴリズムが結局何をやっているのかを考える．簡単のため，データ $\boldsymbol{x}_i$ をそのインデックス $i$ として $p(y|\boldsymbol{x}_i)=p(y|i),q(y|\boldsymbol{x}_i)=q(y|i)$ と書き換える．すると

$\displaystyle E(p,q)+\log N=-\sum_{i=1}^N\sum_{y=1}^Kq(y,i)\log p(y,i)=H(q,p)$

とかける．この最小値は $p=q$ の時に得られる．ここで， $q(i)=1/N$ ，周辺化エントロピー $H_q(i)=\log N$ が定数， $q(y)=1/K$ から $H_q(y)=\log K$ もまた定数と仮定する．するとエントロピーから二つの定数を引くことで

$\displaystyle \min_pE(p,q)+\log N=E(q,q)+\log N=H_q(y,i)=H_q(y)+H_q(i)-I_q(y,i)=\mathrm{const.}-I_q(y,i)$

と相互情報量が導かれる．すなわち結果として元の問題は相互情報量の最大化に等しくなっている．

まとめ

DeepClusterとの関連や，data augmentationの活用，マルチタスクでの学習に関する説明は省略した．データ数が各クラス毎に均一という仮定を導入することで最適輸送問題としてラベリングを定式化する着眼点が非常に面白かった．一方で， $Q$ をデータ数に対して線形時間で得ることができると言っているがデータ数を考えるとそんな簡単な話でもない気がするがどうなのか．また $Q$ の更新の際に $P$ を計算する必要があるが，それもナイーブには全データを一回モデルに入力する必要があるので実装上どう実現されているか気になるところ(実験の章はまともに読んでいないので書いてあるかも…)．

2020-04-30

RandLA-Net: Efficient Semantic Segmentation of Large-Scale Point Cloudsを読んだのでメモ

point cloud

はじめに

RandLA-Net: Efficient Semantic Segmentation of Large-Scale Point Cloudsを読んだのでメモ． LiDARデータなど，大量の点群データ( $10^6$ オーダー)に対して従来より高速にsemantic segmentationをするモデルの提案．

RandLA-Net

提案するモデルは点群を効率的に演算するためのRandom Samplingと局所的な特徴を抽出するLocal Feature Aggregationからなる．

Random samplingは名前の通り入力の点群からランダムに点をサンプリングする．ランダムのモチベーションは，何か凝ったことをやろうとすると $O(N)$ オーダーになり，ミリオンオーダーの点群に対しては例え線形のオーダーでも厳しい．強化学習で効率的なサンプリングのpolicyを学習する方法もあるが，探索空間が広すぎて学習が収束しないという問題がある．なのでランダムサンプリングにしたよということ．一方で，ランダムにサンプリングすると重要な点を落とす可能性があるので強力なfeature aggregationが必要ということで，新たなaggregation方法を提案する．

RandLA-Netのlocal feature aggregationはlocal spatial encoding (LocSE)とAttentive Poolingから成るresidual blockによって実現される．

local spatial encoding (LocSE)

入力として，点群の点ごとの3次元座標 $p_i\in\mathbb{R}^3$ と特徴量(RGBや中間出力など) $f_i\in\mathbb{R}^d$ を考える．処理としてまず， $i$ 番目の点に対して $K$ 近傍[tex:\{p_i^1,\dots,p_i^k,\dots,p_i^K\}を計算する．これらrの点を使い次のように変換する．

$\displaystyle \mathbf{r}^k_i=\mathrm{MLP}(p_i\oplus p_i^k\oplus(p_i-p_i^k)\oplus\|p_i-p_i^k\|)$

ただし， $\oplus$ はconcatenationで， $\|\cdot\|$ はユークリッド距離を表す． MLPの入力は冗長性を持つがプラクティカルには良かったとのこと．結果的に $3+3+3+1=10$ 次元ベクトルをMLPに入力し，対応する特徴ベクトルと同じ $d$ 次元ベクトルを出力する．これは $K$ 近傍の各点に適用されるため，結果として $\mathbf{r}_i\in\mathbb{R}^{K\times d}$ 次元となる．

最終的に $\mathbf{r}_i^k$ と $\mathbf{f}_i^k$ をconcatenateして $\hat{\mathbf{f}}_i^k$ 次元ベクトルを出力する．

Attentive Pooling

Attentive PoolingはLocSEの出力 $\hat{\mathbf{F}}_i=\{\hat{\mathbf{f}}_i^1,\dots,\hat{\mathbf{f}}_i^k,\dots,\hat{\mathbf{f}}_i^K\}$ を集約する．

より具体的には次のように重み付き和を行う．

$\displaystyle \tilde{\mathbf{f}}_i=\sum_{k=1}^K(\hat{\mathbf{f}}_i^k\cdot\mathbf{s}_i^k)$

$\mathbf{s}^k_i$ はMLP $g(\cdot)$ から $\mathbf{s}_i^k=g(\hat{\mathbf{f}}_i^k;\mathbf{W})$ として計算される．ただし， $\mathbf{W}$ はMLPの学習パラメータで，式の通り $k$ や $i$ に依存しない（パラメータ共有してる）．また，式からは分かりにくいが， $\mathbf{s}_i^k$ はsoftmaxで正規化されている(Fig. 3)．

Dilated Residual Block

上記のLocSEとAttentive Poolingから成るDilated Residual BlockとRandom Samplingを積み上げることで提案するRandLA-Netは構成される．言葉で書くと煩雑に成るためFig. 3参照．

最終的なモデルの全体像はAppendixのFig. 7参照．

まとめ

各種データセットで従来手法を上回るmIoUを達成．計算時間もPointNetより少し早いにもかかわらずmIoUはPointNetを大幅に上回る． Random Samplingでも十分動くものだなという印象．前のPoint-Voxel Convでも思ったけど，点群処理は意外と単純なやり方でも精度出るものだなと．