【論文と実装】「このデータセットは難しいの？」と言われたら...

畳み込みニューラルネットワーク（CNN）の学習には時間がかかります。

特に、転移学習を使わずに本気で精度を出そうとした場合、**5日ほどかかる**
時もあります。本稿で紹介する論文はデータセットの難しさを定量的に
評価することにより、CNNの学習を行わずに分類精度を高速に推定できる
というものです。

![ダウンロード (1).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264781/a00827e4-829f-74e1-704e-a10d972a0890.png)

※コード全体は[こちら](https://github.com/shinmura0/Spectral_Metric_for_Dataset_Complexity_Assessment-Keras/blob/master/Spectral_Metric.ipynb)に置きました。
※本稿の図は基本的に論文（[Spectral Metric for Dataset Complexity Assessment](http://openaccess.thecvf.com/content_CVPR_2019/papers/Branchaud-Charron_Spectral_Metric_for_Dataset_Complexity_Assessment_CVPR_2019_paper.pdf)）から引用しています。
※こちらの資料は[【オンライン】pythonデータ分析勉強会#13　その2](https://pythondata.connpass.com/event/150387/)の発表資料です。

#論文
##概要
+ CNNの分類問題で、**CNNを学習させずに**CNNの分類精度を推定できるCSGを提案
+ 従来手法より高速化し（約2倍）、さらに相関係数を上昇させた（0.77→0.97）

##クラスオーバーラップ
本論文のキーとなるのは、画像分類タスクにおいて「2つのクラス間の重複が大きければ
その分類問題は難しい問題」といえることです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264781/f27f454b-c30d-b33f-de85-03c4d62c20f3.png)

上の図は自作したものです。いま、CNNを使って画像を2次元空間を埋め込んだと
します。

そして、オレンジの点と青い点を分類するタスクだとして、左図に対し、
右図の方が分類しやすい問題といえそうです。これはいいかえると、
クラス間の重複が大きい方が難しい分類問題といえます。

数式で考えると、ある点の近傍で自分とは同じグループの点が多いと重複が
小さい（易しい分類問題）、自分と違うグループの点が多いと重複が大きい
（難しい分類問題）といえそうです。

論文では、以下の式を提示しています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264781/bfe6ef1a-2002-4117-334b-8aad74321cac.png)

この式はクラス$C_i$から見たクラス$C_j$の重複度を表した式です。

MとVは一定値のため、ひとまず置いておいて、$K_{C_j}$はクラス$C_i$の画像xの
近傍にあるクラス$C_j$の個数です。つまり、$K_{C_j}$が大きいと重複が大きいと
いえます。

ここで、$\phi(x)\in R^d$は$C_i$の画像xを埋め込んだベクトル、Mは$C_j$から
抽出されたサンプル数、Vはハイパーキューブの大きさです。最終的に
クラス$C_i$の画像に（4）式を適用して和をとっています。

※はっきりいって、MもVも後で出てくる（5）式でキャンセルされるため、
　M=V=1と置いても差し支えないかと思います。

（4）式はあくまでも2クラス間の重複度しか計算できないため、
複数のクラスがある場合は、各クラスの重複度をそれぞれ計算する
必要があります。

クラス数をKと置くと、類似行列(similarity matrix）$S\in R^{K\times K}$が
定義されます。$S_{ij}$は（4）式の和で計算されます。

$S$の各要素が大きいということは、（4）式が大きい値ということになり、
クラスiから見てクラスjが近くに多くあるということになります。
つまり、難しい分類問題と言えます。

##スペクトラルクラスタリング
あとは、$S$を使って、どうやって分類問題の難しさを数値化するか
という問題です。

論文では、スペクトラルクラスタリングを使っています。

スペクトラルクラスタリングは元々、教師無し学習のクラスタリングで
使われる手法のようです。各グラフの結びつきが弱いところで分割
することで、k-means法などでは難しい分割問題でも、きれいに分割
することが可能です。詳しくは以下のリンクをご覧ください。
https://www.slideshare.net/pecorarista/ss-51761860
https://qiita.com/sakami/items/9b3d57d4be3ff1c70e1d

スペクトラルクラスタリングでは、以下のラプラシアンLの
固有値を求めることで、グラフの分割する難しさを数値化する
ことができます。

```math
L=D-W
```

本論文に当てはめると、$S_{ij}$をグラフと見立て、分割の難しさ
（分類の難しさ）を数値化してくれます。一般的にはLの固有値が
大きいほど、分割が難しいとなるようですが、本論文では、後述するように
固有値の大きさだけではなく、固有値の傾向を捉えて数値化することで
より**精度の高い数値化**が可能になっています。

Lの式について、Dは$D_i=\sum_jw_{i,j}$と定義されます。
Wには$S$を直接代入したいところですが、Wには対称行列という制約が
あるため、以下の式を使って対称化しています。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264781/b30b774a-9cd9-f5cf-f640-0adfbd7f7567.png)

実験結果を先に見せてしまうと、Wだけでもデータセットの難しさを
推定することができます。下の図はCIFAR10を使った実験結果です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264781/fe6a4c70-1d28-519f-1e65-df27558e8dca.png)

上段がWの実験結果。下段が学習させたAlexNetの推論による混同行列。
Wによる推定が、AlexNetの推論結果と酷似しているのが分かります。
「犬」と「猫」が判別しにくい状況も的中させています。

##ラプラシアンL
ここまでの処理を確認しておきます。
画像　→　埋め込み　→　クラス間の重なりを（4）式で算出　→　Lの固有値を計算

前述したようにラプラシアンLの固有値の最大値を見るだけで
グラフの分割の難しさ（本論文の場合、データセットの難しさ）を
推定することができます。

実験結果を先に見せてしまうと、固有値の最大値あるいは総和を
見るだけでも、データセットの難しさを推定することができます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264781/d6566c4d-f10b-2476-c5bb-31c6b73da8ee.png)

上の表はCIFAR10を使った実験結果。

+ 緑の枠は従来手法。相関係数は高くても**0.773**。
+ 赤の枠はLの固有値を使って算出した結果。固有値の最大値を使うと相関係数は0.88、総和だと**0.94**。
+ 青の枠は後述するCSGを使った結果。相関係数は最も高い**0.968**。

固有値の総和を見るだけでも、従来手法を超える性能が出ます。

上の表では、「埋め込み手法」は以下の4つを用意しています。

+ RAW：データそのまま。CIFAR10の場合1,024次元
+ $CNN_{AE}$：オートエンコーダで獲得した潜在変数（次元数は不明）
+ t-SNE：データをt-sneで次元圧縮。CIFAR10の場合1,024→2次元
+ $CNN_{AE}$t-SNE：オートエンコーダによる潜在変数にt-SNEを適用

ちなみに、本論文の手法は「高速」を謳っていますが、オートエンコーダを学習させないと
良いCSGは算出できません。上の表で括弧書きになっている時間がオートエンコーダの学習時間です。
ご覧のとおり、従来手法に対し2倍速くなる程度です。（それでも凄いことですが。）

##CSG
最後に、CSGについて説明します。
固有値を小さい方から順にi=0,1,2...と並べた場合、まずは次の式で標準化します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264781/192c35a7-4a6c-7e2e-c6ab-72ca743a7cc4.png)

そして、CSGを算出します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264781/8181f5eb-1746-80cc-b4c4-b4cf1c1e1971.png)

ここで、cummaxとは[1,4,3,2]という配列があったとして、

```
cummax[1,4,3,2] = [1,4,4,4]
```

を意味します。つまり左から順に読み込んでいったときに、読み込んだ
数字の最大値を記録する関数です。

##実験結果
下の表はMNISTを使った実験結果です。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264781/a65e11c9-2a3e-4fb8-0673-a2828c374cef.png)

ご覧のように、mnistに含まれるクラス数が増加するにつれ、CSGもエラー率も上がっていく
ことが分かります（相関関係）。ちなみに、水色のmnistは「mnist1」を意味しています。
すなわち、一つのクラスしかない状態です。

下の表は異なるデータセット（クラス数：10）を使った実験結果です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264781/bc24bfcd-930c-3003-7115-81b9680297aa.png)

注目すべきは、CSG（赤色）とAlexNetのエラー率（青色）が相関関係にあることです。
データセットが異なっていても、CSGが正しく機能していることが分かります。

下の図は、MioTCDというデータセットを使った実験結果です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264781/74afc547-f169-af96-c522-37e725e3428c.png)

ここでは、データ数を削減しながらCSGを計算しています。そして、CSGに
比例するようにエラー率も上がっていきます。このデータセットでは、
80％ほどのデータを削減しても問題ないことが分かります。

※この図では、一見CSGを使ったからエラー率が水平のまま推移していくように
　見えますが、データ削減の方法は無作為に選んだものと思われます。

一方、CIFAR10では次の表にある通りデータを削減するにつれて
如実にエラー率が上がっていきます。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264781/3fc9e8a1-4e8c-e24f-f5d2-c7bc16609783.png)

ここでもエラー率に比例してCSGが大きくなるのが分かります。

また、行列Wを使って、以下の式にMDSを適用することでクラス間の類似度を
可視化することができます。

```math
S=1-W
```

下の図はMDSを適用した図です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264781/11cd2385-069b-1180-3e13-2f0b231da79f.png)

MNISTはきれいにクラス間の距離が離れていますが、CIFAR10の場合、
「犬」と「猫」、「鹿」と「鳥」が近い位置にあり、似ていることが
分かります。つまり、これらは比較的判別が難しいということです。

#実装
結論からいうと、MDSとWは何とか結果が出ましたが、肝心の
**CSGはうまく再現しませんでした。**

※コード全体は[こちら](https://github.com/shinmura0/Spectral_Metric_for_Dataset_Complexity_Assessment-Keras/blob/master/Spectral_Metric.ipynb)に置きました。

##実装条件
実験目的は「CIFAR10のデータを削減しながら、CSGの推移を見ます。」
つまり、Table6を再現します。

埋め込み用のオートエンコーダは以下の条件で実験しました。

+ オートエンコーダは11層（論文では9層）
+ 最適化手法はAdam（デフォルト）
+ バッチサイズは128
+ エポックは50を基本とし、データサイズによりエポックを変える（論文では100で固定）

##埋め込み手法
埋め込み手法は論文で一番スコアが出た手法を採用します。
その手法とは、CSG $CNN_{AE}$ t-SNE です。

これは以下の手順で計算されます。

+ 学習データでオートエンコーダ（エンコーダ+デコーダ）を学習させる
+ エンコーダにテストデータを入れ、出力を取得する
+ 出力をt-sneに入力し、埋め込みデータを得る
+ 埋め込みデータでCSGを算出

##苦心の安定化
実験で出したCSGはなかなか安定しません。そもそも、論文で出た固有値が
再現していないため、実装のどこかが間違えている気がするのですが、
私の実力では分かりませんでした。

何とか安定させるため、以下の対策を行っています。

+ テストデータの抽出
論文では、テストデータの抽出は各クラスから100個ずつとってこれば十分と
いっています。ところが、この100個に何が含まれるかでCSGがかなり変動します。
そのため、抽出は**5回行って**CSGを計算し、平均値をとっています。

+ t-sne
t-sneはその都度、結果が異なるため、**5回実行して**CSGを計算し、平均値をとっています。

以上の対策の結果、各データサイズでCSGの計算は5×5＝25回行い、平均値を算出しました。

##実装結果
CSGは算出しましたが、相関係数が0.9くらいのときもあれば、0になることも
あるので、全く信用できないといえます。

ただし、WとMDSは論文と似たような結果になったので、報告します。

![ダウンロード.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264781/e3b5de7c-62db-8a63-dcfb-1aec3db63b9d.png)

Wは似たような結果になったものの、「犬」と「猫」の類似度は論文のように
大きな値にはなりませんでした。

![ダウンロード (1).png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/264781/a00827e4-829f-74e1-704e-a10d972a0890.png)

MDSの結果は、論文と似たようなものになりました。
ちゃんと、「cat」と「dog」、「deer」と「berd」が近い位置にきています。

##実行速度
今回、ColaboratoryのGPUを使って検証しました。
GPUは**まさか**の```Tesla P100```が出たため、一応括弧書きで```Tesla K80```を使った時の
うろ覚えの時間も書いておきます。

+ オートエンコーダの学習時間：3分30秒（30分）
+ t-SNEの学習時間：7分（1時間）

上記の時間はCIFAR10のデータ全てを使った時の時間です。
ご覧のように、CNNを学習させて直接分類精度を見るより、実行速度が速いことが
分かります。

#まとめ
+ 実装により、CNNを学習させて直接分類精度を見るより**CSGを算出する方が速い**ことが分かりました。
+ 実装でCSGは再現できませんでしたが、オートエンコーダ+t-SNEを適用することで、画像データの傾向を捉えることが可能です。

上記の知見を応用すると**分類データ量の効率的な削減、データクレンジング**で有効に
機能する可能性があります。それらの詳細は次回の記事で書きます。