(DL論文)【ICLR2023】Visual Recognition With Deep Nearest Centroids(DNC) 

# はじめに
ICLR2023にある論文を読んでみて、論文解説してみました。
今年から研究を始めたばかりでまだ知識も浅いですので、曖昧な部分が多いかもしれません。

# 概要
・古典的な分類手法であるNearest Centroidsを改良したDeep Nearest Centroids(DNC)を提案

・通常のNNにおけるClassification Layer(分類層)において、DNCに置き換えることで推論結果の説明性を向上

・出力の次元数がクラス数に依存せず、source task からtarget taskへのパラメータの輸送性を向上

・画像分類とセグメンテーションにおいて、精度も向上した
# 前提知識及び注意点
### パラメトリックとノンパラメトリックについて
パラメトリックは、「このパラメータでは、これになる確率が多い」というように、確率分布に従うので、外れ値に弱い(t検定など)
ノンパラメトリックは、分布を仮定しない(事例ベースの推論)ので、パラメトリックよりも外れ値に強い
(ウィルコクソンの順位和検定など)

### DNCについての注意点
DNCはNNモデルではなく、分類器である
バックボーンはResNetなどであり、分類層をDNCに置き換えている、つまり、バックボーンから来た特徴量をsubcentroidによりクラスタリングし、分類するという手法である

自分が読む上でよく勘違いしていた
# 背景
著者は従来のDNNの分類器(層)の欠点について以下を挙げている
1.説明性に欠けている
2.特定のタスクに最適化されており、モデルの潜在データを活用できていない
3.事前学習において、通常分類層を切り離すので、重要なパラメータが失われてしまう
つまり、特徴量の分布を学習により推定し、その分布に基づいて出力、所謂パラメトリックな手法


# 提案手法
以上の問題に対して、DNCは
DNC
1.特徴量分布に依存していない
2.事例(距離)ベースの推論を行う(ノンパラメトリックな手法)
3.出力結果に対する説明性を持つ

### DNCとは何なのか
一言で言えば、
#### 人間が解釈できる分類器
と言える

古典的手法であるnearest centroids分類器を改良
※nearest centroids分類器とは、学習時、クラス毎に重心を求め、推論時、重心が最も近いクラスに分類する方法(k-meansクラスタリングと手法は似ている?)

提案手法DNCでは、ニューラルネットワークで抽出した特徴量に対して、クラス毎に重心を求める
それに加えて、クラス内でサブ重心に分け(k=4)、クラス分類を行う
この重心およびサブ重心を学習中に更新していく(オンラインクラスタリング)

計算量が大きいので、それを改善するためにSinkhorn Iterationアルゴリズムに基づいてオンラインクラスタリングを行う

つまり、教師あり表現学習と教師なしのサブクラス重心の決定を行っている

![スクリーンショット 2023-06-21 23.09.21.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2610305/cda9bad9-c143-3461-73ea-7848bf61a082.png)

重心およびサブ重心の更新は、momentum的に実行する

セグメンテーションも、ピクセル毎に分類を行う




説明性を向上とは、従来の分類器は確率(犬60%など)を指標としていたが、
NearestCentroid分類器は入力特徴量とクラスタの代表との特徴間距離(犬が1番近いけど、猫が2番目に近いなど)を指標にする『メトリック分類器』である。この意味で、説明性を向上と著者は言っている

以下の図のように、判断根拠を入力画像との類似度をベースに表示することができる
![スクリーンショット 2023-06-21 23.12.42.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2610305/d0d1b8cb-15b2-a7b3-50d6-79e92ff26de7.png)

解釈可能とは、距離ベースの分類器はノンパラメトリックであり、人間の行う経験ベースの分類に似ている。その意味で、DNCは解釈可能である。
![スクリーンショット 2023-06-21 23.07.50.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2610305/c8137167-6123-9965-418b-444b7c27baa9.png)


### サブ重心の推定
より有効な表現を示すサブ重心を求めるため、決定論的なクラスタリング手法を、特徴空間内で行った
$X$,$P$をそれぞれ特徴、サブ重心行列とする

特徴行列$X$からサブ重心行列$P$にするには、最適輸送問題を解く必要があり、Sinkhorn Iterationアルゴリズムを用いる(メリットとして、行列計算のみで最適輸送問題を解くことができ、また、自動微分で勾配が求まる)
以下の式を解くことで、サブ重心を推定する

```math
\max_{Q\in{\mathbb{Q}}}{Tr(Q^{T}P^{T}X)}), \mathbb{Q}=\{Q\in{\ \{0,1\}}^{K\times{N}} |Q^{T}1_{K}=1_{N} \}
```

ここで、$Q$はサブ重心に割当てるための行列である
$\mathbb{Q}$という制約条件を付け、クラスタリングを行うことでスパース性と表現性を追求する

※Sinkhorn Iterationアルゴリズムについては少し曖昧な表現とさせて頂きます

$Q$は次のように求めることができる
```math
Q=diag(\alpha)exp(\frac{P^{T}X}{\epsilon})diag(\beta)
```

ここで、$α$,$β$はrenormalization parameterといい、勾配爆発を防ぐ
$α$,$β$はSinkhorn Iterationを通じて計算されるもの
$ε$は、収束の速度とトレードオフであり、元々のSinkhorn アルゴリズムと同じ速度に近づけるため0.05としている


### DNCの学習

以上のサブ重心推定処理により、クラス数Cとサブ重心数Kの、合計C×K個の特徴ベクトルが得られる

サンプルデータ$x$、サブ重心行列$p$を用いて、損失関数は次のようになる
```math
L=\frac{1}{N}\sum^{N}_{n=1}{-\log{p}(y_{n}|x_{n})},p(y|x)=\frac{exp(-min(\{ \langle x,p^{y}_{k} \rangle \}^{K}_{k=1}))}{\sum_{c \in {y}}{exp(-min(\{ \langle x,p^{c}_{k} \rangle \}^{K}_{k=1}))}}
```

$\sum_{c \in {y}}$とは、「全クラスの和を取る」という意味
つまり、DNCの学習は、教師あり表現学習とクラス毎の重心推定(上の式)の繰り返しである
学習の過程で特徴空間は変化するので、それに応じてサブ重心まで推定するのは、高速なSinkhorn アルゴリズムと言えども、計算負荷が大きい
そこで、以下のようにmomentum的にサブ重心$p$を更新していく

```math
p_{k}\leftarrow \mu p_{k}+(1-\mu)\bar{x}_k
```

ここで、μはmomentum係数、xは現在のバッチ内での、クラスcのサブ重心kに割り当てられた平均特徴ベクトルである

しかし、表現学習において、バッチ数が小さいと表現の精度も落ちてしまう
そこで、前のバッチ分の特徴量を保存しておき、保存した特徴量と現在の分でクラスタリングを行う

# 関連手法
kNNを分類器として教師あり表現学習を行う手法も提案された
しかし、nearest neighbor法はあまりクラス表現の学習には向いていない
nearest centroidsをDNNの分類器に使う研究もあったが、その時はサブ重心を用いず、特徴表現を細かくできていなかった(つまり、クラス毎に1つの表現しかない)
サブ重心(sub centroids＝prototype)に分けて、今まで見たものに基づいて物事を認識するという方法は、心理学のプロトタイプ理論に当てはまる
よって、DNCは人間が普段行っている認識方法を模倣している
# 実験
### 画像分類
CIFAR-10とImageNetをデータセットとして用いる

CIFAR-10:200epoch
バッチサイズ:128,
学習率:ResNet 0.1
schedule:step polynomial annealing
サブ重心の数:K=4
μ:0.999

![スクリーンショット 2023-06-22 0.04.05.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2610305/f463449c-4eac-4390-9144-48a482570803.png)

ImageNet
epoch:100(ResNet), 300(Swin Transformer)
バッチサイズ:16
学習率:ResNet 0.1(ResNet), 0.0005(Swin Transformer)
schedule:step(ResNet) polynomial annealing(Swin Transformer)

![スクリーンショット 2023-06-22 0.04.31.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2610305/9e36dc08-b8d2-10bc-d93c-d55fac847691.png)


### セグメンテーション
最後の1×1畳み込み層を外して、DNCを入れる
サブ重心の数:K=10
μ:0.999
学習率:0.1(backbone:ResNet101), 6e-5(backbone:Swin-B)
cropsize&batch:512&16(ADE20K), 769&8(Cityscapes)
data augmentation: scale&color jittering, flipping&cropping

![スクリーンショット 2023-06-22 0.18.33.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2610305/7afe9db7-6562-4f78-49b4-aa271004ff91.png)


## 即席(アドホック)の説明可能性についての実験
特徴量のコサイン類似度に基づいて、各サブ重心と最も近い画像を結び付ける(90epochまでは通常の学習、残り10epochでこの操作を行う)
IF,thenルールに基づいて、各サブ重心の特徴量同士のコサイン類似度を比較し、任意の画像がそのクラスに分類される過程を示す
これは人間の内部での意思決定と似ているので、説明可能性が向上していると考えられる
![スクリーンショット 2023-06-22 0.26.50.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2610305/af1d14ce-11fa-ff27-4352-938a6a408bba.png)

DNCがクラスのサブ重心同士の(dis)similarityを表示することで、推定結果の透明性を向上させることができる
![スクリーンショット 2023-06-22 0.28.24.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2610305/8aa39bbc-992a-21c7-a153-453447b5d344.png)

サブ重心K=4の場合の、各サブ重心の代表画像
![スクリーンショット 2023-06-22 0.29.07.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2610305/bfc15905-aa08-f48b-01a1-94d2a69c726f.png)

## その他の実験(一部抜粋)

### サブ重心, 外部メモリ(バッチサイズ), モーメンタム更新について
![スクリーンショット 2023-06-22 0.20.35.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2610305/7fea5cce-1f1a-c595-d4d1-8fdbe94d7ac9.png)

### k-meansとSinkhorn との精度比較
![スクリーンショット 2023-06-22 0.35.32.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2610305/95b74bf0-8f17-a7a9-c7b0-83a65da7a478.png)


### 他の距離ベース分類器との比較
DeepNCMは、k-means法をクラスタリングに用いる(サブ重心なし)
![スクリーンショット 2023-06-22 0.34.12.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2610305/e046aa4d-2940-2436-a670-c7ad38ff3d0f.png)
DeepNCAは、k-NN法を用いる
![スクリーンショット 2023-06-22 0.34.25.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2610305/0a952c10-0a91-a1c3-4d8f-5f0d87a7b528.png)
ContrastiveSeg-DeepLabV3は、セグメンテーションにcontrastive learningを用いる
![スクリーンショット 2023-06-22 0.34.39.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2610305/4f9101c0-82b5-7a87-c204-427ef101a2e7.png)


### Kをサンプル数に応じて変えた場合
![スクリーンショット 2023-06-22 0.33.30.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2610305/ab36ebe4-4be9-e843-4235-446868a88bc0.png)


# これからの課題(future work)

Sinkhorn-KnoppアルゴリズムがO(n^2ε^3)時間で動作するため、学習効率が低下してしまう。
クラス毎のサンプル数に応じてKを変えることで、さらなる向上に繋がる(実際に、1〜4までサンプル数に応じて変えた結果を示す)
従って、学習時にクラスタ数を自動的に決めるようなアルゴリズムだとさらなる向上に繋がる

# 所感
やはりsub centroidsが効いているのかと最初に感じた(論文の著者も述べている)
事前学習する際の、学習パラメータの輸送損失が0であることは確かに有用性があると考えた
説明可能性とは、間違った例にはこの画像(サブ重心の代表から画像を引っ張ってくる)がありますよみたいなことができる、ということ？
DNCが出力次元に左右されない、とはいってもクラス毎に重心を取る時点で出力次元を変えているのではないかと考えられる

SimCLRなどの教師なし表現学習との精度比較について知りたかった→(著者の解答(Open Review))DNCはそもそも「softmaxを用いない分類器」の提案であり、SimCLRなどは距離学習の手法の1つに過ぎない


# 参考文献
[1] "Visual Recognition With Deep Nearest Centroids" Wenguan Wang, Cheng Han, Tianfei Zhou & Dongfang Liu
CCAI, Zhejiang University, Rochester Institute of Technology & ETH Zurich(Published as a conference paper at ICLR 2023)