動機

Twitter東海林ファジィロボット研究所という方がGNG（GrowingNeuralGas）を使った三次元物体の認識を行ってる動画をアップしているので面白そうなので私も挑戦してみることにしました。Gazeboか何かでシミュレーションを行っており、見ていてすごい面白いのですが、このアルゴリズム、調べてもgoogleだとあんまり日本語情報が出てこないんですね。

webページでは結構きれいにまとまっているなと思ったのは以下のwebサイトです。 www.thothchildren.com

論文はそれなりの数が見つかります。首都大と岡山大で盛んに研究されているらしく、これとかすごいいいですね。自己増殖型ニューラルネットワークと教師無し分類学習。これも図が載っていてとても分かりやすいです。Growing Neural Gasの基礎と点群処理

今回の記事ではこの資料を元にGNGのアルゴリズムをPythonで実装してみます。

注意素人の実装なので実装が正しい保証はありません。日本語のPython実装がおそらくweb上にこれしかないので、実装が間違っていた場合それがデファクトになってしまうのは避けたいです。

Growing Neural Gasについて

GrowingNeuralGasとは教師無し学習を行うアルゴリズムの一つでニューラルネットワークの一種です。ニューラルネットワークといってもDeepLearningのように固定の個数のパラメータに対して、チューニングを行うわけでは無く、ニューラルネットワーク自体が変形します。ベクトル群に対して位相構造をとらえるのが得意であり、点群情報から対象物形状を推測したり、データに対して位相情報を抽出したりできます。。

人間が環境を認識する手法と比較するとかけ離れているように感じました。どちらかというと粘菌っぽいですね。

アルゴリズム

自己増殖型ニューラルネットワークと教師無し分類学習を読みながら実装を行ったのですが、そのアルゴリズムについて私の理解を図解していきます。合っているかどうかはあんまり自信がありませんが、後続のプログラムとステップが一対一で対応しています。

あと数式ははてなブログの数式機能で使えない記号とかいっぱいあってガバガバなので雰囲気で読んで下さい、色々記号が出てきますが、基本的にそれぞれの文字の意味は以下のような感じです。それと、論文書くときほど真面目に書いてないので誤植は沢山あると思います。

$\alpha$ と $\beta$ はなんか論文読んでも定数としか書いてなかったので何の働きをしているのかよく理解できてないです。

Step 0

初期化として、二つのノードの参照ベクトル $w1$ と $w2$ をランダムに生成し、結合関係 $c_{1,2}$ 、エッジを接続します。緑色の点はニューロンだと思ってい下さい

Step 1

入力データ $v$ の中からデータの分布[tex : p(v)]にしたがってランダムに取り出します。今回はデータの分布がよくわからないので、適当に一様分布仮定して取り出してます。

Step 2

入力データ $v_i$ にたいして重み $s$ の中から最も近い勝者ノード $s_1$ と二番目に近い第二勝者ノード $s_2$ を選択します。

$s_1= argmin|| v - w_i||$

$s_2= argmin|| v - w_i|| (not s_1)$

Step 3

ノード $s_1$ に関して入力データ $v$ との事情誤差を計算し、積算誤差 $E_{s_1}$ に加算する

Step 4

ノード $s1$ および $s2$ と結合関係のあるノードの位置を更新するこの時、s1の学習率を $\eta_1$ 、それ以外の学習率を $\eta2$ とする。ただし( $\eta1 > \eta2$ である)。勝者ノードや周辺のノードを取り出したデータに対して距離的に近づけている。

Step 5

$s_1$ と $s_2$ の間にエッジが存在すればエッジの年齢を0にする。そうでなければ $s_1$ と $s_2$ の間にエッジを生成する。

Step 6

$s_1$ と接続関係のあるすべてのエッジの年齢を１増加させる。

Step 7

エッジの年齢が事前に設定した閾値を超える場合、そのエッジを切断する。さらにエッジが接続されたことによって発生する。孤立ノードも削除する。

Step 8

GNGへのデータの入力回数が $\lambda$ 回ごとに次の操作を行う

(i)

積算誤差が最大のノードqを選択する。

(ii)

ノード $q$ と結合関係のあるエッジのなかで最も長いエッジを選択し、このノードに結合するノードを $f$ とすると、このエッジを二分するようにノード $r$ を挿入する

(iii)

ノード $q,f$ 間のエッジを削除し( $C_qf = 0$ ),ノード $qr$ および $rf$ 間にエッジを追加する。

(iv)

ノード $q,f$ の積算誤差を次の様に更新する

(v)

$q$ と $f$ の誤差の平均をrの誤差とする

Step 9

すべてのノードの積算誤差を減らす。

Step 10

終了条件が満たされない場合Step1に戻る。この辺はまだあんまりちゃんと勉強できてない。エラーが一定以下になったらとか聞いたけど。積算誤差のことでいいのかな？

実装

自己増殖型ニューラルネットワークと教師無し分類学習の資料を基に1ステップずつ実装してゆきます。

今回はNumpyで実装していきます。PythonはPythonでプログラミングらしいことを始めたら負けなので、なるべく演算はNumpyにやらせましょう。

neuronsはニューロンの配列、neurons_existはその番地のニューロンが存在するかどうかのマスクです。接続は100マス計算の様に接続関係にある要素の番号の行と列が交わる点がTrueになるようにしています。なので一つの接続があると二点がTrueになります。

import matplotlib.pyplot as plt
import networkx as nx
from numpy.random.mtrand import randint
lr_s1 = 0.2 #s1の学習率
lr_s2 = 0.1 #s2の学習率
beta  = 0.2 #ナニコレ？
alpha = 0.2

MAX_N = 250 #ニューロン数は最値
th_age = 13 #エッジの寿命
lambda_value = 11


#ニューロンは二次元配列で使っていないところに突っ込む
neurons = np.ones([MAX_N,2])
neurons_error = np.zeros((MAX_N))
#ニューロンが生きているかのマスク
neurons_exist = np.zeros((MAX_N)).astype(np.bool)

#ニューロン間の接続は行列で表現する.接続はbool値で表現する
connectivity = np.zeros((MAX_N,MAX_N)).astype(np.bool)
#エッジの年齢も同様に行列で表現する
edge_age = np.ones((MAX_N,MAX_N))

#step0 初期化として、二つのノードの参照ベクトルw1とw2をランダムに生成し、結合関係C_1,2、エッジの年齢a_1,2を0にする
neurons[0] = [randint(0,500),randint(0,500)]
neurons[1] = [randint(0,500),randint(0,500)]
#存在することにする
neurons_exist[0] = True
neurons_exist[1] = True
#s1とs2を接続する
connectivity[0][1] = True
connectivity[1][0] = True

#対象データvの全体の長さを取得
data_len = cluster_pos.shape[0]
index_pad = np.array(range(MAX_N))

for i in range(1,1000):
  #Step1 入力データvをp(v)を使ってランダムに取得する
  v = cluster_pos[randint(0,data_len)]
  #Step2 入力データvに対する勝者ノードs1と第二勝者ノードs2を取り出す
  #生きているニューロンだけを取り出す
  active_neurons = neurons[neurons_exist]
  active_neurons_error = neurons_error[neurons_exist == True]
  active_neurons_index = index_pad[neurons_exist]
  distance = np.argsort(pow(abs(active_neurons - v),2).sum(axis=1))
  s1_index = active_neurons_index[distance[0]]
  s2_index = active_neurons_index[distance[1]]

  s1 = neurons[s1_index]
  #Step3 勝者ノードs1について入力データvとの事情誤差を積算誤差E_sに」加算する
  neurons_error[s1_index] += pow(s1-v,2).sum()
  
  #Step4 ノードs1およびノードs2と結合関係あるノードと参照ベクトルを更新する。
  neurons[s1_index] += lr_s1*(v - neurons[s1_index]) 
  for item in neurons[connectivity[s1_index]|connectivity[s2_index]]: 
    neurons[s2_index] += lr_s2*(v - neurons[s2_index]) 

  #Step5 エッジの年齢を0にリセットする。またノードs1とs2の間にエッジが存在しなければ新たにエッジを作成する
  if(connectivity[s1_index][s2_index] == False):
    connectivity[s1_index][s2_index] = True
    connectivity[s2_index][s1_index] = True
  edge_age[s1_index][s2_index] = 0
  edge_age[s2_index][s1_index] = 0

  #Step6 ノードs1と結合関係のあるすべてのエッジの年齢をインクリメントする。
  edge_age[s1_index][connectivity[s1_index]] += 1
  edge_age[:,s1_index][connectivity[:,s1_index]] += 1

  #Step7 事前に設定したしきい値a_maxを超える年齢のエッジを削除する。その結果ほかのノード結合関係を持たないノードが表れた場合は該当ノードを削除する
  connectivity[edge_age > th_age] = False

  #ニューロンの削除
  neurons_exist[connectivity.sum(axis=0) == 0] = False


  #Step8 GNGへのデータ入力がlambda回ごとに次の操作をおこなう
  if(i % lambda_value == 0):
    #(i)積算誤差が最大のノードqを選択する。
    q_index = neurons_error.argmax()
    q = neurons[q_index]
    #(ii)ノードqと結合関係のあるエッジのなかで最も長いエッジを選択し、このノードに結合するノードをfとすると、このエッジを二分するようにノードｒを挿入する
    
    connected_neurons = neurons[connectivity[q_index]]
    connected_neurons_index = index_pad[connectivity[q_index]]
    
    f_index = connected_neurons_index[np.argsort(pow(abs(connected_neurons - q),2).sum(axis=1))[-1]]
    

    f = neurons[f_index]

    #ニューロン rを作成するために開いている最も小さなニューロンの番地を探す
    r_index = np.where(neurons_exist == False)[0][0]

    #ニューロンrを生成する
    neurons_exist[r_index] = True
    neurons[r_index] = (q+f)/2
    #(iii)つぎに、ノードq,f間のエッジを削除し(C_qf = 0),ノードqrおよびrf間にエッジを追加する。(C_qr = 1,C_rf = 1)
    #qf間の接続を切断する

    connectivity[q_index][f_index] = False
    connectivity[f_index][q_index] = False
    edge_age[q_index][f_index] = 0
    edge_age[f_index][q_index] = 0
    #rf間を接続する
    connectivity[r_index][f_index] = True
    connectivity[f_index][r_index] = True
    edge_age[r_index][f_index] = 0
    edge_age[f_index][r_index] = 0
    #qf間を接続する
    connectivity[r_index][q_index] = True
    connectivity[q_index][r_index] = True
    edge_age[r_index][q_index] = 0
    edge_age[q_index][r_index] = 0
    
    #(iv)ノード積算誤差を更新する
    neurons_error[q_index] -= alpha*neurons_error[q_index] 
    neurons_error[f_index] -= alpha*neurons_error[f_index] 

    #(v)qとfの誤差の平均をrの平均とする
    neurons_error[r_index] = neurons_error[q_index]+neurons_error[f_index]*0.5
   

  #Step 9すべてのノードの積算誤差を減らす。
  neurons_error[neurons_exist] -= beta * neurons_error[neurons_exist]
  
  #Step 10 終了条件が満たされない場合Step1に戻る
  if(i%1 == 0):
    #描画処理
    fig = plt.figure()
    ax = plt.axes()


    plt.scatter(cluster_pos[:,0], cluster_pos[:,1])
    fig.set_size_inches(10, 10)


    #edgeの描画
    for row in range(0,250):
      for col in range(row+1,250):
        if(connectivity[row][col]):
          neuron_A_pos = neurons[row]
          neuron_B_pos = neurons[col]
          plt.plot([neuron_A_pos[0],neuron_B_pos[0]],[neuron_A_pos[1],neuron_B_pos[1]],color="lime")
    #ニューロンの描画
    for neuron_pos in neurons[neurons_exist]:
      c = patches.Circle(xy=(neuron_pos[0],neuron_pos[1]), radius=5.0, color='lime', fill=True)
    
      ax.add_patch(c)
    c = patches.Circle(xy=(v[0],v[1]), radius=5.0, ec='r',color='r', fill=True)
    ax.add_patch(c)

    plt.savefig(f"img_{str(i).zfill(4)}.png")

    plt.show()

実行

以上のプログラムを実行して動作を確認するサンプルをGooglecolabでシェアします。学習対象のデータとしては、2Dと3Dの両方を対象としました。はてなブログは動画が貼れないのでTwitterから貼れるのは便利ですね。

2D版プログラム

２Dは私が適当に作ったドーナツ型のランダムのデータです。

colab.research.google.com

機械学習の待ち時間に手癖で作ったGrowing Neural Gasです（まだバグがあるかも）
まあ、ある程度動いてるかな？
アルゴリズム的に順序依存があって並列化が難しそうなのが考えものですね。マルチスレッド化する論文は出てるみたいなので要調査です。 pic.twitter.com/qpCbgy644e
— とりてん＠論文数0.5 (@NoOne_1024) February 9, 2023

3D版プログラム

３Dはスタンフォードバニーです。