【クラスタリングの新トレンド？】DeepClusterとその発展の考察

スポンサーリンク

はじめに

私は普段、Twitterを大いに活用して情報収集をしております。今回の記事のタイトルにある「DeepCluster」はtwitterのTLで流れてきた以下のarxivで提案されたクラスタリング手法です。

[1807.05520] Deep Clustering for Unsupervised Learning of Visual Features

今回はこの手法の基本的な着眼点と、今後の発展について素人ながら考察してみます。

クラスタリング

概要

まずクラスタリングというものが、一体どんな問題設定であるのかをしっかりと認識しておきましょう。多次元のデータD={x1,...,xN}$D=\{{\mathbf{x}}_1,...,{\mathbf{x}}_N\}$が手元にあるとします。このN$N$個のデータは実は何個かの集団に分かれていると考えられ、手持ちのデータだけから（つまり各成分を見比べるというだけで）これらを幾つかの集団に分けたいという問題がクラスタリングになります。

例えば、何個かの集団というのを、ここでは決め打ちして3つということにしておきましょう。すると、クラスタリングでやりたいことというのは、N$N$個のデータをそれぞれ、次の3のクラスタC1$C_1$かC2$C_2$かC3$C_3$のいずれかに割り振る問題だと言えます。

では、どのように割り振るのが良いのでしょうか。残念ながら万能な方法は無いと思われます。しかし、「同じクラスタに属するデータはそれぞれ互いに近い位置にあるのではなかろうか」くらいの仮定をおいてやれば、アルゴリズムを考える手がかりにはなりそうです（注意として、この仮定が正しいのかは誰にもわからない）。

K-means

クラスタリングの基本的手法として（今回紹介するDeepClusterの中でも登場する）K-meansという手法があります。この手法については具体例を交えつつ、下記の記事で説明しているのでぜひ一読ください。

www.hellocybernetics.tech

一応この場所でも軽く説明をしておきます。

1. 手元にあるD={x1,...,xN}$D=\{{\mathbf{x}}_1,...,{\mathbf{x}}_N\}$の散布図を想像する（3次元以上なら想像力豊に）
2. クラスタの数K$K$を仮定する。（今回はK=3$K=3$で行きます。C1,C2,C3$C_1,C_2,C_3$）
3. 適当な初期点をK$K$個、ここでは3個m1,m2,m3${\mathbf{m}}_1,{\mathbf{m}}_2,{\mathbf{m}}_3$準備する。
4. D$D$の各データについて、mk${\mathbf{m}}_k$との距離を測り、最も近いCk$C_k$に属すると設定します。
5. 各クラスタCk$C_k$に属するデータ点の平均を計算し、その平均値を新たなmk${\mathbf{m}}_k$とします。
6. 「4.」「 5.」を繰り返します。

このアルゴリズムによって、概ねユークリッド空間（二乗距離を使った場合）で近いデータ点同士が同じクラスタに属するであろうという結果を出すことができます。ただしそのようなクラスタの定め方が正しいかはまた別の問題です。

K-meansの改良

さて、K-meansの改良版について話すと、DeepClusterのアイデアのある側面が見えてきます。 K-meansでは二乗距離を使うのが一般的であり、これは想像した散布図で、それぞれのクラスタの平均の位置を中心に、同時に円の半径を膨らませていき、最も速く円の内部にデータ点を含むことの出来たクラスタにデータ点を割り振っていっていることになる（まあ要はデータが近い者同士を円で囲んでクラスタを決めている）。

果たしてクラスタはそんな単純でしょうか。現実のデータはもっと複雑に入り乱れた形（凸集合になっていないとか）になっているかもしれませんね。そのような場合は、円じゃなくても良いのではないでしょうか。これは距離の測り方を工夫するだけで割り振り方を変えることが出来、アルゴリズムの変更も容易です。でもどんな測り方が良いのかということにはやはり答えられません。

一方で少し考え方を変えてみましょう。二乗距離を使うということを固定しておくことにして、データD$D$の配置を変えてしまうという方法があります。もしも、データ点のクラスタがぐにゃっと曲がっていたとしても、その曲がり具合を考慮してデータ点を再配置することが可能であれば、最終的には円で囲めるような形に持って行けてしまうかもしれません。

DeepClusterの基本的アイデア

まずデータD={x1,...,xN}$D=\{{\mathbf{x}}_1,...,{\mathbf{x}}_N\}$はうまいこと円では囲むことができなさそうであると考えます。そこで畳み込みニューラルネットワーク（以下ConvNet$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{N}\mathrm{e}\mathrm{t}$）によって新しい配置へz=ConvNet(x)$\mathbf{z}=\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{N}\mathrm{e}\mathrm{t}(\mathbf{x})$と変換します。このときはConvNet$ConvNet$のパラメータは適当なものを使ってしまいましょう（それでなぜうまく行くと思うのかって？実験したらそうだったからじゃない？正直詳しくよくわかないのですが、普通の全結合層に比べConvNetは制約が強い変換であり、その制約は画像のようなデータに適していると考えられています）。

さて、ここで適当なK$K$個のクラスタを想定したK-meansによって変換されたデータDz={z1,...,zN}$D_z=\{{\mathbf{z}}_1,...,{\mathbf{z}}_N\}$をクラスタリングしてしまいます。ここでK$K$はハイパーパラメータの役割を担っていることに注意してください。兎にも角にも、データx$\mathbf{x}$を非線形変換してz$\mathbf{z}$に変えてしまっているおかげで、z$\mathbf{z}$の空間で単純なK-means（二乗距離を使った、円で囲むだけの方法）はx$\mathbf{x}$の空間でそれなりに複雑な形のクラスタリングが行われていると想定できます（ただし、非線形変換ConvNet$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{N}\mathrm{e}\mathrm{t}$は適当な初期値パラメータを使った変換なので、ベストな形でクラスタリングができているとは言えないでしょう）。

さて、次は、このクラスタリングがまだベストではないにしても、完全にランダムよりはまともなクラスタリングができていると思いましょう。そうしたならば、ConvNet$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{N}\mathrm{e}\mathrm{t}$の出力に全結合層（Classifier()$\mathrm{C}\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{i}\mathrm{f}\mathrm{i}\mathrm{e}\mathrm{r}()$として追加して、クラスタリングを正解ラベルとした分類問題だと置き換えて、誤差逆伝播学習をしてしまうのです（全結合層は最初から付けておいても構わない…最初は計算結果を使わないだけ）。

つまり、

ypreylabel=Classifier(ConvNet(x))=(z=ConvNet(x)に対するK−meansの結果)$$\begin{array}{rl}{y}_{pre}& =\mathrm{C}\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{i}\mathrm{f}\mathrm{i}\mathrm{e}\mathrm{r}(\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{N}\mathrm{e}\mathrm{t}(\mathbf{x}))\\ y_{label}& =(\mathbf{z}=\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{N}\mathrm{e}\mathrm{t}(\mathbf{x})に対する\mathrm{K}-\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{n}\mathrm{s}の結果)\end{array}$$

として学習を行ってしまうということになります。学習によってConvNet$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{N}\mathrm{e}\mathrm{t}$のパラメータは変更されるため、すると再度K-meansを使ってみると違った結果が得られることでしょう（あわよくばそれらしい結果になって欲しいが）。このK-meansでの結果を再度新たなラベルデータとして使ってやり、以降このループを繰り返すことになります。

（https://arxiv.org/pdf/1807.05520.pdfより抜粋）

ただしそもそも、K−means$K-means$の結果は正しいラベルになっているかは愚か、クラスタの数（クラスの数）K$K$が正しく設定されているかも知ったことではありません。でも完全にランダムなラベリングをするよりはK-meansの方がまともだと考えれば、完全にランダムな初期値を使っているConvNet$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{N}\mathrm{e}\mathrm{t}$は先程よりもマシなパラメータになってくれるだろうと思えてきます。

考察と今後の展開

まとめとしては、

1. ConvNet()$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{N}\mathrm{e}\mathrm{t}()$とClassifier()$\mathrm{C}\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{i}\mathrm{f}\mathrm{i}\mathrm{e}\mathrm{r}()$を初期化
2. z=ConvNet(x)$\mathbf{z}=\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{N}\mathrm{e}\mathrm{t}(\mathbf{x})$を計算。
3. z$z$に対してK-meansを利用。
4. ypre=Classifier(z)$y_{pre}=\mathrm{C}\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{i}\mathrm{f}\mathrm{i}\mathrm{e}\mathrm{r}(\mathbf{z})$を2.の結果を教師とみなし分類問題として学習
5. 「2.」から「3.」をループ

これはK-meansの結果をラベルデータにしているわけですから、ConvNet$ConvNet$が学習するのはK-meansが上手くクラスタリングできているか否かに依存します。そしてそれが事実上手くいくとなれば、逆にConvNet$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{N}\mathrm{e}\mathrm{t}$はK-meansが次のステップでは先程よりも上手くクラスタリングできるように、すなわち特徴空間で簡単に円によってクラスタリングできるように、特徴量を獲得していっていると推測できます。

そして、そうであるならば、K-meansはより良いクラスタリングを行い、そのクラスタリングの結果を次の誤差逆伝播に用いてConvNet$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{N}\mathrm{e}\mathrm{t}$を訓練するのですから、なにやら相乗効果的に上手く行きそうな雰囲気が漂っているように見えます。

しかし現実はそう甘くないのではないでしょうか。そもそもクラスタの数K$K$は決め打ちです。ここが変な事になっていると上手く行くという保証はできないでしょう。今回は予めクラスの数が分かっているデータを使っているかもしれませんが（そうでなければ評価もできんが）、現実の応用ではそうは行きません。現実のクラスタ数と、妥当な決め打ちのクラスタ数K$K$との関係をどのようにすべきかを理論的に考察することは今後の課題となるでしょう（少なくとも現実のクラスタ数より少ないとよくなさそう？）。

また、画像でない場合には用いるべきニューラルネットワークの構造は正直自明でない気がする。畳み込み層というのは以下の記事でも解説したとおり、全結合層よりも表現力は弱い。だからこそ、イタズラにパラメータの探索範囲が広くなっておらず、適当な初期値が、チャンスレベル以上に良い結果をもたらしていたりする（ある意味、ニューラルネットワークの構造それ自体が初期値である）。

www.hellocybernetics.tech

もしもクラスタリングと誤差逆伝播学習によって何らかの相乗効果があり、初期値がチャンスレベル以上によければ、確かに学習をすすめるうちに良くなっていきそうなものではあるが、ある種のサンプリングの問題に近いような気もします？

一提案

仮に、計算量に一旦目をつむるのであれば以下のような方法が使えると思われます。

単にK-meansを混合ガウスモデルに置き換えて、ベイズ推論する。

www.hellocybernetics.tech

混合ガウスモデルのベイズ推論では、クラスタ数K$K$は実データで想定されるよりもとりあえず多めに見積もっておけば、自動で必要最低限の数まで落としてくれます。つまり、K$K$決め打ち問題はなんとなく緩和されそうな気がしないでもありません。当然、計算量という観点では極めて厳しい問題が残る気がしますが…。

計算量に対する1つの解決方法は、1回のクラスタリング結果に対して誤差逆伝播学習を複数epoch過剰に行うことが考えられます。要はラベルの貼り直しは、たまに行えば良いという考え方です。

一方でせっかくのベイズ推論の結果であるので、K-meansが毎回計算を最初からし直しているのに対して、混合ガウスモデルではベイズ更新によって前回の結果を事前分布として使いまわすことが考えられます。 ただし、これには少し問題がありそうな気がしないでもなく、混合ガウスモデルが前回までに表していたz$\mathbf{z}$と、誤差逆伝播後に新たな特徴量となっているz$\mathbf{z}$はそもそも同じものと見て良いのかということが疑問です。もちろん本質的にはx$\mathbf{x}$というデータであることは間違いないのですが、z$\mathbf{z}$は明らかにx$\mathbf{x}$とConvNet$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{N}\mathrm{e}\mathrm{t}$のパラメータによって決定される変数であり、ConvNet$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}\mathrm{N}\mathrm{e}\mathrm{t}$のパラメータは毎回変わっていると考えると、z$\mathbf{z}$というものは、誤差逆伝播前と後で別の生成モデルで扱わなければならなくなっていてもおかしくありません。

もしかしたらむしろベイズ更新がこのz$\mathbf{z}$の変動を上手く捉えつつ良いクラスタリングを行ってくれるかもしれませんし、あるいは混合ガウスモデルから見たら、単に新しいz$\mathbf{z}$がどんどん追加されているように見えて、すべて別のクラスタに属すると判断してもおかしくはありません。

プリミティブな発展は単にK-meansを混合ガウスモデルに置き換えてしまって、負担率をマルチラベルとして使うなどの方法でしょうか。まあ、そのうちすぐ出る気がする。