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

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

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参照),期待通りの働きができていることがわかる.

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

はじめに

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の必要性に関してもう少し説明もしくは実験が欲しかった.

Bootstrap Your Own Latent A New Approach to Self-Supervised 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 blursolarizationをする.

Architecture

f_\thetaはResNet50の出力層手前の平均プーリング層までをベースとして,パラメータを2x~4xまで増やしたResNet101, 152, 200それぞれ実験. gはSimCLRと同様にMLPで構成され,隠れ層が4096次元で出力層が256次元.q_\thetag_\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の時も少し思ったが,半教師あり学習と教師なし表現学習は手法的にはどんどん似通ってくるのかなと.

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

はじめに

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

気持ち

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

Method

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

各層は追加の学習パラメータとしてr_i\in\mathbb{R}^ns_i\in\mathbb{R}^mを持つ. 添字i1から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_ns_iの要素積をとり,出力でr_iとの要素積をとるとかけ,演算量の点で非常にリーズナブルとなる. 結果として通常の独立にM個のモデルを容易するより計算コストが低い.

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

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

まとめ

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

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

はじめに

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_ii番目のクラスターのセントロイドとし,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)}

ただしここではvcの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のみの精度も気になる.

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

はじめに

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はカテゴリ数を表す. データはNI_1,\dots,I_Nあるとし,それぞれのデータに対応するラベルをy_1,\dots,y_N\in\{1,\dots,K\}とする. 最終的な分類スコアはsoftmax関数を用いて下記のように計算される.(論文の通りに書いたが,ここまでの定義に従えば\Phiを挟んでいるので\boldsymbol{x}_iIとなる気がする.)

\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^\topK\times Nの確率行列. この正則化の導入により上記の最小化問題のかいが次のように表現される.

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

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

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

  • 現在得られている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を計算する必要があるが,それもナイーブには全データを一回モデルに入力する必要があるので実装上どう実現されているか気になるところ(実験の章はまともに読んでいないので書いてあるかも…).

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

はじめに

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_iMLPg(\cdot)から\mathbf{s}_i^k=g(\hat{\mathbf{f}}_i^k;\mathbf{W})として計算される. ただし,\mathbf{W}MLPの学習パラメータで,式の通りkiに依存しない(パラメータ共有してる). また,式からは分かりにくいが,\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でも思ったけど,点群処理は意外と単純なやり方でも精度出るものだなと.