DeepClusterでお前をクラスタリングしてやれなかった

はじめに

久しぶりの投稿となってしまいましたが、お久しぶりです。(毎回これを書いている気がします)

この記事は Chainer/CuPy Advent Calendar 2018 - Qiita の19日目の記事となります。

今回取り上げるのはしばらく前にTwitterで話題になっていたDeepClusterについてです。

他の参加者の方はChainerに関しての記事を書いていたのに対して、Chainerで実装したとはいえDeepClusterの記事を書いても良いものか悩みましたが、結局DeepClusterの記事になってしまいました。

話題になった頃あたりにDeepClusterの実装を試みたのですが、faissの使い方が分からないからなのか謎に発生するセグメンテーションフォールトに苦しめられて断念していました。

なぜ今なのかというと、実はあまり話題になっていないように思いますが、しれっと本家のpytouch実装がgithubに上がっていたので、それを参考に再チャレンジしたら loss がそれっぽく下がってくれて、それっぽくNMIが上がるようになったからです。(とは言うものの、残念ながらこの先は上手くクラスタリングできませんでしたブログになります)

DeepClusterとは

利点

DeepClusterを使う利点としては以下があります。

1. k-means のような標準的なクラスタリングアルゴリズムを使って、簡単にconvnet の end-to-end で学習できるので、実装が比較的簡単
2. 教師なし学習で使用される標準的な転移タスクで最高の性能
3. uncured image distribution(意味はよくわからなかった)で訓練した時に従来手法より上の性能

クラスタリングそのものではなく、どちらかといえば、「教師データのないデータに対して、高精度なニューラルネットワークのpretrained modelを作成できる」というところがこのアーキテクチャの魅力なのかなと思っています。

例えば、教師データの少ない上にあまり一般的でない種類の画像の巨大なデータセットが手元にあったとして、最善の方法としては全ての画像に対してアノテーションすることですが、アノテーションの人手が足りない、もしくは予算が降りないなどの理由で一部しかアノテーションできず、少量のデータを使ってモデル構築に挑まなければいけない場合があるかもしれません。
そのような場合には、このアーキテクチャを使ってpretrained modelを作成して使うと嬉しいのではないかなと思いました。

ネットワークのアーキテクチャ

さて、実際のネットワークのアーキテクチャは流行っていたのもあり、論文の図にちょっとアレンジを加えたものを載せてみます。
全体像としては以下の形になります。

f:id:gat-chin321:20181110214427p:plain

それでは、手順ごとに見ていきましょう。まず初めに行われるのは、k-meansによるPseudo-label(擬似ラベル)の生成になります。
正確な定義ではないですが、Pseudo-label(擬似ラベル)とは、何らかの方法で機械的に生成されたラベルのことを指していて、それを使って分類器に教師あり学習をさせるアプローチが多々あります。
Pseudo-labelの生成のプロセスはこうです。

1. Inputの画像をconvnetに通し、特徴量を作成します。(ここではfully-connectedレイヤーは通さないことに注意)
2. 作成した特徴量を主成分分析+L2正則化で次元圧縮します。
3. k-meansを実行して、その時に生成されたクラスタ番号をPseudo-labelとして利用します。
4. これを1 epochごとに実施。

f:id:gat-chin321:20181110214637p:plain

このステップで、画像の全データをメモリに格納しておく必要があるので、かなりのメモリ容量が必要になる点がややデメリットかなと思います。(上手くやれば結構節約はできる気もしますが…)

次にPseudo-labelを用いた分類器の学習を行なっていきます。

このフェーズでは以下の手順で分類器の学習を行います。

1. Inputの画像をconvnetに通し、fully-connectedレイヤーに通します
2. fully-connectedレイヤーを通った出力にsoftmax cross entropy lossを求める(ここで私の実装ではclass weightにPseudo-labelごとの数の逆数を渡しています)
3. 次のepochまで繰り返したあと、k-meansによるPseudo-labelの生成を再度行う

f:id:gat-chin321:20181110215448p:plain

というのがDeep Clusterによる学習の流れになります。
また、この時、大多数の画像がごく少数のクラスタに割り当てられている場合、どの画像に対しても1つのクラスに分類してしまうようになる可能性があります。
この対策として以下のどちらかを行います。(割と一般的な方法だとは思います)

  • Inputの画像を一様分布にしたがってサンプリングする(論文での実装)
  • クラスの画像のサンプル数の逆数をclass_weightに渡す(こちらの方が楽なので私の実装ではこちらにしています)

「なぜこれで学習できるのか?」という問いについては論文中にて

The good performance of random convnets is intimately tied to their convolutional structure which gives a strong prior on the input signal
(ランダムな convnet で良い性能が出せるのは入力信号に強い事前分布を与える畳み込み構造に密接に関係している)

というような記載がありますが、入力信号に強い事前分布を与えることでなぜうまく学習できるのかがあまりよくわかりません。
多少調べたところ、以下の資料などでconv+poolingが入力信号に無限に強い事前分布を与える性質については記載がありました。
無限に強い事前分布を与えることでアンダーフィットが起こる可能性があるみたいな指摘があるので、アンダーフィットしやすい性質 VS オーバーフィットしやすいk-meansによる擬似ラベルでなんかいい感じに学習できたとかでしょうか。(雑な解釈)

https://uwaterloo.ca/data-analytics/sites/ca.data-analytics/files/uploads/files/cnn1.pdf

以下の論文のconvnetの教師なし学習によるセグメンテーションに似ているような気がするが、こちらもなぜうまくいっているのかは謎な感じです。

https://kanezaki.github.io/pytorch-unsupervised-segmentation/ICASSP2018_kanezaki.pdf

実装

ソースコードは以下のgithubに公開しています。

GitHub - pesuchin/deepcluster-chainer

この実装ではPseudo-labelの生成についてはtrainer.extendを使って1 epochごとにPseudo-labelを生成する処理を行なっています。(github上のtrain.pyに記載)

また、AlexNetのLocal Response Normalizationは本家の実装の通り、Batch Normalizationに変えています。

そのうちリファクタリングもしたいのですが、今のところは気力の都合上、無駄の多い汚い実装になっているとは思います。

本家の実装と異なる点としてはUniformSampler(分類または疑似ラベルの一様分布に基づいて画像をサンプリングする)を使わずに、論文中で等価と言われている割り当てられたクラスタのサイズの逆数をclass weightに渡している点です。(見落としているだけで他にもあるかもですが…)

実験結果

実験で利用する評価指標について

評価指標は論文でクラスタリング結果を評価するのに利用している正規化相互情報量 (NMI; Normalized Mutual Information) を利用します。

NMIは以下の式で定義される評価指標です。

 NMI(A; B) = \frac{I(A;B)}{\sqrt{H(A)}\sqrt{H(B)}}

また、

 I(A;B) = \sum_{y \in Y} \sum_{x \in X} n_{x, y} log \frac{n_{x, y}}{n_{x}n_{y}}

 H(A) = \sum_{y \in Y} n_y \frac{n_y}{n}
 H(B) = \sum_{x \in X} n_x \frac{n_x}{n}

 n_{y}: 正解の集合 y の画像数
 n_{x}: クラスタ x の画像数
 n_{x, y} : クラスタ x 中で正解集合 y に属する画像数
 n: 全体の画像数

NMIはクラスタ x がわかった場合に、正解集合 y が必ずわかるような場合(つまり、それぞれのクラスタ x の画像と正解集合 y の画像が一致する場合)は1になり、そうでない場合に値は0に近づく。例えば、以下の場合はNMIは1になります。

  • 予測クラス: [2, 2, 2, 2, 1, 1, 1, 1]
  • 正解クラス1: [1, 1, 1, 1, 2, 2, 2, 2]

個人的にはもう少しきちんと理解しておきたいものですが、本筋ではないのでNMIの説明はこれくらいにしておきます。

CIFAR 10での実験結果

CIFAR 10の訓練用データセット60000件をクラスタリングした場合のNMIの推移がこちらです。

f:id:gat-chin321:20181213215718p:plain
cifar10のNMIの推移

上記の図を見ると、12 epochあたりからピタリとNMIが上がらなくなり、24 epoch目あたりがNMIのピークとなっていることがわかります。

NMIの値は同じデータで普通のk-meansでやってみた時は0.07程度のNMIが出たので、正直全く良くないです。

本家実装でも同じデータでコードを動くように多少修正して動かしてみたのですが、0.06程度のNMIだったので、実装はそんなに違わないはず…。

論文で使われていた一つ前の予測ラベルと現状の予測ラベルのNMIをとった結果をプロットしたものをみてみましょう。

f:id:gat-chin321:20181213220255p:plain
一つ前の予測ラベルと現状の予測ラベルのNMIをとった結果

こちらを見ても、12 epoch目からNMIが上がらなくなっていることがわかり、論文に記載している通り、概ねNMIが0.8を超えたあたりで収束していることが分かります。

では、24 epoch目で実際に分類した結果をいくつか貼っていきます。

f:id:gat-chin321:20181213220747p:plain
class 1: 馬っぽいのがそこそこある例

f:id:gat-chin321:20181213220922p:plain
class 0:ダメそうな例

f:id:gat-chin321:20181213221017p:plain
class 7: 車がそこそこ集まっている例

全体的に「そんな似ているか?」というものが色々入っちゃっている印象です。

終わりに

CIFAR10のデータを使って、NMIによるクラスタリングの評価を行なってみました。

ここでは結果は載せませんが、他にもMNIST・Fashion-MNIST・CIFAR 100などでも実験してみたり、AlexNetのネットワークを小さくしてみたりはしたのですが、どれも普通のk-meansに及ばないNMIでした。

もしかすると、論文で提案されているAlexNetを用いたDeep Clusteringでは画像サイズの小さいもしくは画像数の少ないデータは苦手なのかもしれません。もちろん実装ミスの可能性もなきにしもあらずですが…。

DeepClusterを使って作成したpretrained modelの精度も実験したかったのですが、今回はやりきれなかったので、一旦ここまでとしようかと思います。

あとImageNetでどうなるかを見て実装があっているのか確かめたかったのですが、ImageNetで学習させるだけのハードウェアを用意するほどの資金力がないのと実験を回すスクリプトの実装の時間がなかったので、実装が正しいのか確かめられていない状況です。

もし、「ここが間違っているよ」みたいなことがあればお気軽にご指摘ください。

投稿までに間に合わせたかったのですが、悔しいことに間に合いませんでした。自分の無力さを感じます。

Deep Learningは実装が正しいのかを確認するのが難しく、巨大なデータセットで実装されていると計算資源の問題で追実験が気楽にはできないですね。今日で私のGCPの300ドル使い放題期間が終わってしまったのが悔やまれます。