Kohonenの自己組織化マップをpythonで実装

Kohonenの自己組織化マップ(Self Organizing Map, SOM)をpythonで実装してみた。
SOMの元論文はKohonen1982*1
以下の説明と実装はAI Junkieの平易な解説を参考にしている。
http://www.ai-junkie.com/ann/som/som1.html


実装したpythonのコードはgithubにあります。
https://github.com/latboy/som-in-python


SOMとは?

一般の大きな次元のデータ群を、それらの特徴に基いて、低次元(典型的には1〜2次元)空間に配置する方法。似ているもの(データベクトルがベクトル空間上で近いもの)同士が、低次元空間でも互いに近い位置にマップされるようになる。
ここで、アルゴリズム自身にはデータ量の特徴を与える必要がない。以下に述べる単純で再帰的なアルゴリズムで、データの特徴をとらえた低次元マップが得られる。すなわち、これは1種の教師なし学習である。
また、一つのユニットに収められているベクトルは、マップ上のその位置が表す特徴をもった典型的なベクトルであるので、SOMは一種の生成モデルと言っても良いと思う。

アルゴリズムの概要

分析したいデータが、D次元のベクトルの集合として与えられたとしよう。これを2次元平面にマップする方法を与える。
まず、D次元の要素を持ったユニットを、2次元空間に配置する(競合層と呼ぶ)。各ユニットの値は適当な乱数によって初期化しておく。
この時、データの集合に対して、次の操作を繰り返す。

  1. あるデータに対し、それと最も似ている(D次元空間でユークリッド距離の近い)ベクトルを持つユニットを探す。(そのようなユニットをBMU: Best Matching Unitという)
  2. BMUとBMUの近傍のユニットを、与えられたデータに近づくよう更新

実際には学習過程におけるパラメータの調整など細かな注意がある。
BMUの更新規則から、頻出するベクトルの特徴が強く競合層に学習される。
また、BMUだけでなく、BMUの近傍ユニットも入ってきたベクトルに近づけるため、競合層において近い位置にあるユニット同士が、似た特徴のベクトルを持つようになる。

実装

今回は3次元のランダムに生成した実ベクトル V \in [0,1)^3 を2次元の競合層にマップする実験を行った。
2次元平面上の座標を \vec xと表し、その上の N^2個のユニットを W(\vec x) と表すと、
更新式は次のように与えられる。
{ 
W_{t+1}(\vec x) = W_t(\vec x) + \Theta(\vec x, t) L(t) (V_t-W_t(\vec x))
}
ここで添字 tは学習ステップ(計算機時間)であり、t=0からVのサンプル数までを走る。
右辺の括弧の中が、入力ベクトルと、あるユニットに格納されていたベクトルとの誤差を表している。
ここで、学習パラメータ \Theta(t),  L(t)が両方共1であれば、Wが完全にVに更新されてしまうことに注意しよう。
 \Theta(t),  L(t)の関数型は次のように与える。
 L(t) = L_0 \exp\left( -\frac{t}{\lambda} \right) \\
\Theta(\vec x, t) = \exp\left( -\frac{d^2}{2 \sigma^2(t)} \right)
学習の速度を決定するパラメータLは、時間とともに減少する関数である。 \lambdaは時定数である。
 \Thetaは更新するユニットが、どの程度BMUの近傍にいるかを表現している。dはユニットの位置 \vec xとBMUとの距離であり、d=0の時 \Theta =1である。dが大きくなるに従って、 \Thetaは減少する。
ここで \sigma(t)は典型的なBMUの近傍を定義する量であり、これも次式によって時間とともに減少するとする。
 \sigma (t) = \sigma_0 \exp\left( -\frac{t}{\lambda} \right)

結果

競合層として、20x20のユニットを用意し、ランダムな3次元ベクトルで初期化した。学習データとしては、ランダムに生成した3次元実ベクトル V \in [0,1)^3 を10000個用意した。
(なので、学習データの特徴が抽出されるというより、いかに分類されるかに興味を持って結果を見るべき)
学習パラメータは、 L_0=0.1, \lambda=10000/4=2500, \sigma_0 = 20/2=10とした。

3次元の実ベクトルは、RGB強度と解釈できるので、視覚的に学習を観察できる。学習前の競合層は以下の図のようであった。ユニット間の相関はないため、色がランダムに各マス目に配置されているのがわかる。
f:id:monopole:20150212003956p:plain
1万回の学習ステップを繰り返したあとの競合層は下図のようになった。隣り合うグリッドには似た色が並んでおり、うまく色分けできているように見える。
f:id:monopole:20150212003954p:plain
コンピュータはもともと、3次元の色ベクトルの意味を知っていたわけではない。(例えば(1,0,0)が赤である、とか。)ところが、いまやそれらの近いもの同士のマップを得たので、例えば赤とピンクの色コードを与えてやれば、それがどの程度近いのか、マップ上の距離で判定することができる(半教師なし学習)。また、与えた色コードから類似色を類推することも可能である。


最後に、学習過程をもう少し詳しく見る。10回目と20回目の更新後のマップの様子を下に並べた。
マップのランダム性は速やかに薄れていき、全体として同じような色が並んでいる。これは、学習過程の早い時期では、BMUを中心とした大きな円の内側で強い近傍学習が行われているためである。
f:id:monopole:20150212011525p:plain
f:id:monopole:20150212011537p:plain


次に50回めと90回めの更新後のマップを示す。
50回目の更新後のマップは、まだ全体として似たような色をしているが、少しずつ色分けの効果を見ることができる。90回目になるとその傾向がさらに顕著になる。
f:id:monopole:20150212011549p:plain
f:id:monopole:20150212011608p:plain


1000回目、2000回目の更新後のマップを以下に示す。学習パラメータが時間の減少関数であるため、学習はゆっくりしたものであるが、次第に最後のマップのように、マス目の間の色の区別がはっきりしていくのが見て取れる。
f:id:monopole:20150212011627p:plain
f:id:monopole:20150212011635p:plain

考察・課題・感想

  • 今回は1つのパラメータセットで実験したが、より良いパラメータセットはあるだろうか?
  • numpyの便利機能を使わず、forループのゴリ押しで書いたところを直して高速化する
  • 色の仕分け以外にも色々応用できそう。MNIST画像データではどうだろうか
  • 流行りのdeepなアーキテクチャにできるだろうか?
  • Pythonすごい、Numpyすごい
  • 神経科学的基板も勉強したい