ニューラルガスを可視化してみた（1） #アルゴリズム

はじめまして。
カラフルボードでAIの研究開発をやっているn-suzukiです。

普段は開発半分、研究・調査半分という感じで稼働しているため、ニューラルネットや機械学習のアルゴリズムに関する学術論文を読む機会が多く、自分の理解のために論文の内容を実装してみて動かしてみることがあります。

今回はその一環で実装した「ニューラルガス」というアルゴリズムについて紹介します。

ニューラルガス

ニューラルガス¹は、ベクトル量子化²手法の一つで、クラスタリング、特徴抽出等に用いられます。同じベクトル量子化手法であり、より広く知られているK-means法と比較して、量子化精度が良いことが報告されています³。
ニューラルガスでは、$N$個の素子（ニューロンと呼ぶ）が代表ベクトルにあたる重みベクトル$w_n$を持ち、この値を適応的に更新することで適切な代表ベクトルを獲得します。この重みベクトル$w_n$を更新する際のダイナミクスが、気体分子のような振る舞いをすることから、ニューラル"ガス"と呼ばれます。

アルゴリズム

アルゴリズムを簡単に説明します。
ニューラルガスのアルゴリズムには、大きく分けて"オンライン型"と"バッチ型"の2種類存在しますが、ここではバッチ型のアルゴリズム⁴について解説します。
ニューラルガスは、以下のような非常にシンプルなアルゴリズムで動作します。

$p$番目のデータ$x^p$に対する、重みベクトル$w_n (n=1,\dots,N)$の近さランキング$k_n^p$を全てのデータ$(p=1,\dots, P)$について決定
重み係数$h_\lambda(k_n^p, t)$を計算
$h_\lambda(k_n^p, t)$をもとに全ての重みベクトル$w_n$を更新
$t_{max}$回、上を繰り返す

重みベクトルの更新式は以下の通りです。

\begin{align}
w_n(t + 1) & =  \frac{\sum_{p=1}^P h_\lambda(k_n^p, t) x^p}{\sum_{p=1}^P h_\lambda(k_n^p, t)} \\
h_\lambda(k_n^p, t) & =  \exp\left(-\frac{k_n^p}{\lambda(t)}\right)\\
\lambda(t) & =  \lambda_{ini} \left(\frac{\lambda_{fin}}{\lambda_{ini}}\right)^\left(\frac{t}{t_{max}}\right) \\
\end{align}

ここでの"近さ"とはユークリッド距離の近さを意味します。
ステップ1.では、あるデータ$x^p$に対して、近い順に重みベクトル$w_n$に番号（ランキング）$k_n^p (= 0, 1, \dots, N-1)$を割り振っていきます。

ステップ2.の重み係数$h_\lambda(k_n^p, t)$は、ランキング$k_n^p$の数字が若いほど大きな値をとり、ランキングが下位になるに従って指数的に減衰していきます。これは、$p$番目のデータに対して近い重みベクトルを持つニューロンほど、より$p$番目のデータに近づくことを意味します。このように、ニューロンと入力データの距離や類似度をもとにしたニューロン同士の優劣度合いをベクトルの更新に適用する学習法を競合学習といい、これにより、与えらたデータ集合に対して重みベクトルを均等に分布させることができます。同じ競合学習を用いたアルゴリズムとして、自己組織化マップ（SOM）があります。

パラメータ$\lambda(t)$は、初期値$\lambda_{ini}$から終了値$\lambda_{fin}$まで学習回数$t$ごとに指数的に減衰させます（$\lambda_{ini} >　\lambda_{fin}$）。これにより、学習が進むにつれて重みベクトルの変化量が小さくなり、学習を収束させます。

デモ

さて、文章だけではイメージしづらいと思いますので、簡単なデモを作成しました。
コードはGitHubにアップロードしました。

タイトルにもなっている可視化の結果は次回掲載します。（試行錯誤しながら画像とGIFアニメのアップロードを繰り返した結果、2MB超えちゃいました笑）

A "Neural-Gas" Network Learns Topologies, Thomas M. Martinetz, Klaus J. Schulten, Artificial Neural Networks, pp. 397-402 (10) ↩
$N$個のベクトルから$K$個（$N > K$）の代表ベクトルを選択し、それ以外のベクトルを代表ベクトルに代表させることで、データの圧縮・単純化を行う手法。 ↩
"Neural-Gas" Network for vector Quantization and its Application to Time-Series Prediction, Thomas M. Martinetz, Stanislav G. Berkovich, Klaus J. Schulten, IEEE TRANSACTION ON NEURAL NETWORKS, Vol. 4, No. 4, (1993-7) ↩
BATCH NEURAL GAS, Marie Cottrell, Barbara Hammer, Alexander Hasenfuss, Thomas Villmann, WSOM 2005, Paris ↩