[論文読み]Self supervised learning論文解説 part2 MAST ~教師なし学習が教師あり学習を超える日~

#はじめに
[Part1](https://qiita.com/pacifinapacific/items/2632497680d84f8ca68f)に引き続き論文紹介を行なっていきます。今回紹介する論文は1本だけです。

#MAST: A Memory-Augmented Self-Supervised Tracker[^1]
CVPR2020にアクセプトされたまさしく最前線の論文になります。
3番目に紹介したCorrFlowと同著者による論文で,自らの手法をより発展させる内容になっています。

##提案手法
最初にネットワークを説明します。ネットワークの特徴は__Multi-frame tracker__と__ROI Localization__と呼ばれるものの2種類あり順に解説していきます。
###Multi-frame tracker
![スクリーンショット 2020-04-15 21.32.42.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/221156/39d865a8-478d-79b5-8369-d067b2c83c75.png)
__Multi-frame tracker__はReference frameとして隣り合ったフレームだけでなく,異なった時刻のフレーム複数を用いて,それぞれ独立にマッチングさせる手法です。

これはCycle timeでも解説したように近いフレームだけでなく離れたフレームでのマッチングもできるようにするためで,最後にそれぞれ算出した結果を足し合わせることでロバストな予測を可能にしています。

図のpast framesにあたる部分が過去のフレームで,これまでのようにカラーに対するbottle neckをかけてから,Encoderで特徴mapを抽出します(図中のKey)。

それぞれの時刻で抽出した特徴map $K_{t-N}$と現在のframeとのピクセルマッチングを次のROI Localizationで行います。ここで$t-N$はNだけ過去のフレームということを表しています。

###ROI Localization
![スクリーンショット 2020-04-15 21.54.53.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/221156/15afe573-189c-4c94-fa77-185fc342a96a.png)


__ROI Localizationは物理メモリが少なくても計算可能なように,マッチング範囲を絞り、さらに動的にマッチングを行なうための機構です。__part1でも散々使ってきたAffinity matrix $A_{i j}$はピクセルの数の2乗に比例して大きくなります。例えば特徴mapの大きさが64×64なら行列の要素数は$(64×64)^2$となりそれだけで1千万を超えます。これにチャネル分がかけられるのですから自分のPC(GTX 2070)程度ですと余裕でcuda out ouf memoryしちゃいますし、高解像度の画像も扱えません。

そこで__特徴map全体のaffinity matrixを作らず、全体で小さなRegionを先に見つけてからその領域内でマッチングさせる__ことを試みています。

####具体的な計算手順を解説します。
目標はTarget frameをEncoderによって抽出した特徴map、 $Q$(図中Query)のある一点がreference frameの特徴map、 $K$のどこの領域(_ROI_)に含まれているか知ることです。
そのためにはQの一点とKの各ピクセルとの類似度(内積)を計算してあげればよいでしょう。
これは数式でかくと以下のようになります。

```math
H_{t-N, x, y}^{i}=\operatorname{softmax}\left(Q_{t}^{i} \cdot i m 2 \operatorname{col}\left(K_{t-N}^{i}, \gamma_{t-N}\right)\right)
```
数式だけみると(少なくとも私は)脳内が❓だらけになると思うので、今回はこの式を順番に紐解いていきます。(自信がないので間違っていたら指摘お願いします)
まずはこの部分から。
$$i m 2 \operatorname{col}\left(K_{t-N}^{i}, \gamma_{t-N}\right)$$
これは特徴map $K$をdilation $\gamma$のフィルタでim2col展開しろといっています。
$\gamma$の意味は一回無視するとして$\gamma=1$とした普通のim2col展開は次のgifのように画像にフィルタをかけて、1行に展開していく操作です。(gifは3x3のフィルタをかけた場合)


![プレゼンテーション3.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/221156/34b1ad5a-7181-394d-80ea-06b3a75c1338.gif)

これを行うと(フィルタの大きさ)×(画像の要素数)の行列ができます。gifでは最終的に9行25列の行列ができますが、その1列は各ピクセルの近傍3x3の要素が並べられたものになります。
次にQの$i$番目のピクセルとim2col展開したそれぞれの行の内積を計算します。

```math
Q_{t}^{i} \cdot i m 2 \operatorname{col}\left(K_{t-N}^{i}, \gamma_{t-N}\right)
```
たとえば$Q$の最初のピクセル$Q_{1}$との計算を図にすると次のようになります。
![プレゼンテーション4.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/221156/2897f0de-54bd-50cf-51cc-af304b01999c.gif)

im2col展開をした行列の$i$列は$K$の$i$近傍を並べたものですから,この結果得られる行列$H$の各座標は$Q_{1}$と$K$の類似度になることがわかります。

したがって作成される行列を全座標でsoftmaxをとり、仮に$H$が下図のようになったとすると,$Q_{1}$が$K$のどこに類似しているかがわかるのです。
![図k.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/221156/cad5c37d-e57c-25c2-de96-363530e2cac4.png)
これが先ほどの式$H_{t-N, x, y}^{i}=\operatorname{softmax}\left(Q_{t}^{i} \cdot i m 2 \operatorname{col}\left(K_{t-N}^{i}, \gamma_{t-N}\right)\right)$の意味でResponse mapを求めたことになります
さてResponse mapが求まったのでpeak値を取り出すことができれば、その点を中心位置としたRoIが切り取れそうです。
しかし__単純にargmaxすると誤差逆伝搬できないのでダメ!__ということでsoft argmaxという手法で次式のように無理やりpeak値を出力させています。[参考 Soft argmaxの分かりやすい記事](https://qiita.com/masataka46/items/38321c77cf4b0610bbaa)
$$P_{x, y}^{i}=\sum_{x, y} H_{x, y}^{i} * C$$
$C$はxy座標を独立に展開したものでheatmap $H_{x, y}^{i}$の座標期待値をpeakとして取り出しています。
これでRoIの中心位置を求めることができました。あとは中心から適当なw,hで切り取ればRoI矩形の座標が求まりそうです。しかし$P_{x, y}^{i}$は座標の対応なので特徴mapの画素の対応を得るには微分可能な処理としてbilinear samplerを用いる必要があるので注意です。[参考記事](https://qiita.com/nkato_/items/125bd2e7c0af582aa32e)

以上でようやくROI内の少ない範囲でAffinity matrixを計算できるようになりました。この計算は動的に行うことができるのでメモリを大幅に節約することができます。
カラー予測は異なった時系列でもAffinity matrixを求め、最終的に類似度で重み付けすることで行うことができます。アルゴリズムにすると次のようになります。


![スクリーンショット 2020-04-19 23.49.13.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/221156/e681b63e-2d60-d10a-62c1-69a3053de803.png)


最後にすっとばしてしまった$\gamma_{t-N}$について述べます。
$\gamma_{t-N}$はim2colするときのfilterのdilation rateです。[dilation rateについてのわかりやすい記事](http://joisino.hatenablog.com/entry/2017/07/13/210000)
離れた時刻でピクセルを対応させるときには,物体が大きくなっていたり変形したりするため,広い範囲で類似度を計算する必要があるかもしれません。そのため離れたフレームほどdilation rateを大きくすることで、filterの受容野を擬似的に大きくして補正をかけています。$\gamma_{t-N}=\lceil(t-N) / 15\rceil$

ネットワークの説明は以上になります。
あとは論文の細かい検討事項を紹介して結果に移りたいと思います。



###RGB空間 vs Lab空間
この論文では色空間にRGBを用いるのか、Labを用いるのかで検討を行なっています。

この手法では,ボトルネックにCorrFlowと同じでカラーチャネルをランダムに0にする方法を採用していますが、その場合だとLab空間の方がいいそうです。
その理由は下図に示したようにRGBは各チャネル間で相関性が高く、残っているチャネルから0にされたチャネルを簡単に予測できてしまうためです。
![スクリーンショット 2020-04-14 21.14.39.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/221156/108faae5-02d5-8e2c-a969-8b5da35c8f30.png)

色復元でやりたいことはobjectのなんらかの特徴を理解して色付けすることですから、それができないまま復元できてしまうとボトルネックにならないのです。

###Classification vs. Regression
part1で一番最初に紹介した論文では、色をクラスタリングして回帰ではなく分類問題として予測させていました。
しかし、これだと情報がlossしてしまい、高精度な対応が難しくなることから回帰問題の方が適切であると結論づけています。
またそのときのlossとしてHuber lossを利用しています。

```math
\mathcal{L}=\frac{1}{n} \sum_{i} z_{i}
```

```math
z_{i}=\left\{\begin{array}{ll}0.5\left(\mathbf{I}_{t}-\mathbf{I}_{t}^{i}\right)^{2}, & \text { if }\left|\mathbf{I}_{t}-\mathbf{I}_{t}^{i}\right|<1 \\ \left|\hat{\mathbf{i}}_{t}^{i}-\mathbf{I}_{t}^{i}\right|-0.5, & \text { otherwise }\end{array}\right.
```
$\hat{\mathbf{i}}_{t}^{i}$はreference frameからtarget frameにコピーされた色で、Huber lossはMSEより外れ値に左右されないという特徴があります。

#実験結果
実験結果について述べます。
![スクリーンショット 2020-04-20 7.55.46.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/221156/23c670ca-5096-a006-a8d5-a5e31e306fdd.png)
part1でも書いたようself supervisedのdense trackingではSOTAを達成しています。
またsupervisedと比較しても、十分に戦える数値を残しています。SiamMaskなんかは読んだ時スゲーってなった記憶があるのでそれより上の数値なのは驚きです。

個人的に嬉しいのが学習時間の短さで、part1で紹介したUVCはkinetics dataset(600GBあります)で800時間ですから,それよりかなり学習が楽になっていそうです。



## Generalizability
さらにこの論文ではTest dataにしかないクラスに対し,train,test両方に入っているクラスと同様にtrackingが行えるかを測る指標を提案しています。

```math
\text { Gen. Gap }=\frac{\left(\mathcal{J}_{\text {seen}}-\mathcal{J}_{u n s e e n}\right)+\left(\mathcal{F}_{\text {seen}}-\mathcal{F}_{\text {unseen}}\right)}{2}
```
このGen.Gapが低いほど見たことないクラスに対しても正確にtrackingがおこなえることを示しています。
![スクリーンショット 2020-04-20 8.15.56.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/221156/4972c897-ab75-2ed4-a05f-ce8ee10d523b.png)

この指標に関してはsupervisedより高い性能を示していることがわかります。
つまりこのモデルはオブジェクト固有の性質ではなく、より一般的な性質を学習しているといえそうです。

#まとめ
以上でself supervised learningの論文紹介を終わります。
一切のアノテーションなしで教師あり学習と比肩する精度をだせたことは凄まじいです。

またこの論文のintroに書かれていたことですが,人間は生まれて2~3ヶ月で動くものをその物体がなにかわからなくても目で追えるようになるそうです。
self supervised はその意味で人間の視覚システムに非常に似ており、本質的なアプローチということもできます。
もしかしたら１今後のdeep learningのスタンダードになっていくのかもしれませんね。

最後までお読みいただきありがとうございました。（勉強中の身なので間違っていることがあるかもしれませんが、そのときはコメント欄などで教えていただけると幸いです。）

[^1]: Lai, Z., Lu, E., & Xie, W. (2020.). MAST: A Memory-Augmented Self-Supervised Tracker. Retrieved from https://arxiv.org/abs/2002.07793