goroutineとchannelでGoらしい?Hopfield network

概要

Hopfield networkとはすべてのニューロンが互いに接続している人工ニューラルネットワーク(ANN)の1つです. 完全グラフをイメージするとわかりやすいと思います. 連想記憶のモデルとして考えられたり, 組み合わせ最適化問題を解くために利用されたりします.

Hopfield networkは他のANNと同様に, あるニューロンの出力は他のニューロンからの入力と結合荷重の内積より決定されます.
ひとつのニューロン出力の更新規則は以下の通りで, ニューロンをランダムに選びそのニューロンに適用するということを繰り返します.

\displaystyle{  \begin{array}{rcl}  v_i & = & f(s_i - \theta_i) \\  s_i & = & \sum_j w_{ij}v_j \\  f(x) & = & \left\{  \begin{array}{cc}  1& (x>0) \\  -1 & (x \leq 0)  \end{array}  \right .  \end{array}  }

ここで, v_i, \theta_i, w_{ij}はそれぞれニューロンiの出力, しきい値, ニューロンi,j間の結合荷重です. ただし, w_{ii}=0, w_{ij}=w_{ji}という制約があります(ニューロン自分自身のからの入力は無く, ニューロン間の結合荷重は対称ということ)

普通に書くならシングルスレッドでループを回して1つずつのニューロンを更新していくのですが, ここではそうではなくGoらしい(というかGo独特の機能を使った)書き方をしたいと思います.

Goにはgoroutineと呼ばれる軽量スレッドとgoroutine間のメッセージキューであるchannelと呼ばれる機能があります. このgoroutineひとつをニューロンひとつ, channelひとつをニューロン間の接続ひとつ, とみなしHopfield networkの更新を行うというとても無駄なことをします. イメージとしてはGPUのシェーダプログラミングに近い感じですね. 今回は連想記憶の実験をしてみようと思います.

ここで言う連想記憶とはネットワークに覚えさせたパターンと類似するパターンをネットワークに入力すると, 覚えさせたパターンが想起されるということです. 例えば画像の一部を見ただけで全体をイメージできたり, 次々と類似するものを連想していくことができたりなど, 人間の脳にも備わっている能力のひとつです.

ネットワークの学習(パターンをネットワークに覚えさせる)

詳しい説明は省略しますが, Hopfield networkはニューロンの更新を繰り返すことで以下のエネルギー関数を必ず減少させることがわかっています.
E \left(\bf v \right) = -\frac{1}{2} \sum_i^N \sum_j^N w_{ij} v_i v_j + \sum_i \theta_i v_i

そこで, 覚えさせたいパターンがエネルギー関数の極小値になるようにネットワークの結合荷重を調整するわけですね. パターンを覚えさせる場合結合荷重は以下のように決定します.

w_{ij} = \left\{  \begin{array}{ll}  \sum_{\bf v \in  V} v_i v_j  & (i \neq j) \\  0 & (i = j)  \end{array}  \right .

ここで, V = \{ {\bf v}_1, {\bf v}_2, \cdots {\bf v}_P \}はネットワークに覚えさせるパターン{\bf v} \in \{-1, 1\}^Nの集合です. これはニューロンが同じ出力をしていた場合それらのニューロン間の結合荷重を増加させそうでない場合は減少させる, ヘブ則という学習則で結合荷重を決定していることになります. ネットワークに覚えさせることのできるパターンの個数は, ニューロン数Nの15%程度となっています.

Goでの実装

ニューロンひとつを表現するNeuron構造体は以下のように定義しています.

type Neuron struct {
    id        int
    weights   map[*Neuron]float32 // 結合荷重
    inAxons   map[*Neuron]Axon    // 入力channel
    outAxons  map[*Neuron]Axon    // 出力channel
    v         float32             // このニューロンの出力値
    vChan     chan float32        // 出力値を指定するchannel
    th        float32            
    trainMode bool           
}

Hopfield networkは完全グラフとして表現できるので, ニューロン間の全結合を表現するためN(N-1)個の容量1のchannelを用意します. また, ニューロンに値を流し込むN個の容量1のchannel vChanを作成します. あるNeuronの出力channelはあるNeuronの入力channelになるので, それを考慮してNeuron間をchannelで結合する(NeuronのinAxons, outAxonsを設定する)関数を定義し, Hopfield networkを構築します. 結果として, 例えばニューロンが4個のHopfield networkは以下の図のように構築されます.

gopfield_channel

想起をする際は, vChanでNeuronの出力値を設定したあと, Mainのgoroutineが全Neuronのgoroutineを起動し, 概要で示した更新規則を適用していきます. ニューロン間の結合は容量1のchannelなので, あるニューロンは自身に出力する他のニューロンの更新作業がすべて終わらないとブロックされ更新を行うことができなくなります. つまり, すべての入力がそろったニューロンから随時goroutineによって出力の更新処理が行われていくことになります. これはランダムにニューロンを選択する手順とみなすことができます.

n.v = <-n.vChan                                                          
                                                                         
for it := 0; it < iter; it++ {                                                                                                                    
    for neuron, axon := range n.outAxons {                               
        axon <- n.v                                                      
    }                                                                    
                                                                         
    var s float32                                                        
    for neuron, axon := range n.inAxons {                                
        s += n.weights[neuron] * <-axon                                  
    }                                                                    
                                                                         
    s -= n.th                                                            
                                                                         
    var v float32 = -1                                                   
    if s > 0 {                                                           
        v = 1                                                            
    }                                                                    
    n.v = v                                                              
}                                                                        

学習をする際は, Neuronを学習モードにして更新を行うgoroutineをすべて起動し, 各パターンに対応するNeuronの出力をvChanに流し込む, という流れで行います. vChanで流し込まれた出力値がNeuronに設定され, 全出力channelに出力されます. 各入力channelから他のNeuronの出力を受け取ったNeuronは自身の出力値とその値を比べ, ヘブ則により結合荷重を調整します. これは学習パターンの個数だけ繰り返されます.

finish := make(chan bool, len(h.Neurons))

for _, neuron := range h.Neurons {
    neuron.Run(len(pats), finish)
}

for _, pat := range pats {
    for i, v := range pat {
        h.Neurons[i].Feed(v)
    }
}

for i := 0; i < len(h.Neurons); i++ {
    <-finish
}

ニューロンひとつの更新処理をひとつのgoroutineで行ったことにより, 学習するときも想起するときも更新の時間軸方向に関するループだけがgoroutineに含まれ, 空間方向に関するループが存在しないことに注意してください.

動かしてみる

N=25個のニューロンからなるネットワークを構築し以下の3つのパターンを覚えさせます.

pats := [][]float32{
    []float32{
        1, 1, 1, 1, 1,
        -1, 1, -1, 1, -1,
        1, 1, 1, 1, 1,
        1, -1, 1, -1, 1,
        1, 1, 1, 1, 1,
    },
    []float32{
        -1, -1, 1, 1, 1,
        1, 1, 1, -1, -1,
        -1, -1, 1, 1, 1,
        1, 1, 1, -1, -1,
        -1, -1, 1, 1, 1,
    },
    []float32{
        1, -1, 1, -1, 1,
        -1, 1, -1, 1, -1,
        1, -1, 1, -1, 1,
        -1, 1, -1, 1, -1,
        1, -1, 1, -1, 1,
    },
}

その状態でニューロンに出力値を与えパターンが想起されるかためしてみます. それぞれの初期状態のパターンとして以下のパターンを入力します. これは覚えさせたパターンの20%を反転させたものになっています.

initPats := [][]float32{
    []float32{
        -1, 1, 1, 1, 1,
        -1, -1, -1, 1, -1,
        1, -1, 1, 1, 1,
        1, -1, -1, -1, 1,
        1, 1, 1, -1, 1,
    },
    []float32{
        -1, -1, 1, -1, 1,
        1, -1, 1, -1, -1,
        -1, 1, 1, 1, 1,
        1, 1, 1, 1, -1,
        -1, -1, 1, -1, 1,
    },
    []float32{
        1, -1, -1, -1, 1,
        -1, 1, 1, 1, -1,
        1, 1, 1, -1, 1,
        -1, 1, -1, -1, -1,
        1, -1, -1, -1, 1,
    },
}

ニューロンの出力が-1, 1の場合はそれぞれ白丸, 黒丸で表示しています. 結果は以下に示したように, 覚えさせたパターンを想起できていることがわかります.

Connectting between neuron 0 to neuron 1
Connectting between neuron 0 to neuron 2
Connectting between neuron 0 to neuron 3
Connectting between neuron 0 to neuron 4
Connectting between neuron 0 to neuron 5
Connectting between neuron 0 to neuron 6

...

neuron 14 : input from 11 before
neuron 14 : input from 11 after
neuron 14 : input from 16 before
neuron 14 : input from 16 after
neuron 14 : input from 19 before
neuron 14 : input from 19 after
neuron 14 : finish
●●●●●
○●○●○
●●●●●
●○●○●
●●●●●
energy = -284
neuron 0 : start
neuron 0 : it = 0
neuron 0 : output to 7 before
neuron 0 : output to 7 after
neuron 0 : output to 9 before
neuron 0 : output to 9 after
neuron 0 : output to 18 before
neuron 0 : output to 18 after

...

neuron 16 : input from 0 before
neuron 16 : input from 0 after
neuron 16 : input from 1 before
neuron 16 : input from 1 after
neuron 16 : input from 2 before
neuron 16 : input from 2 after
neuron 16 : finish
○○●●●
●●●○○
○○●●●
●●●○○
○○●●●
energy = -280
neuron 0 : start
neuron 0 : it = 0
neuron 0 : output to 7 before
neuron 0 : output to 7 after
neuron 0 : output to 9 before
neuron 0 : output to 9 after
neuron 0 : output to 18 before
neuron 0 : output to 18 after

...

neuron 1 : input from 0 before
neuron 1 : input from 0 after
neuron 1 : input from 4 before
neuron 1 : input from 4 after
neuron 1 : input from 21 before
neuron 1 : input from 21 after
neuron 1 : finish
●○●○●
○●○●○
●○●○●
○●○●○
●○●○●
energy = -280

まとめ

goroutineをひとつのニューロン, ニューロン間の結合をchannelとして表現することで, Hopfield networkを構築するというすごく無駄なことをしました. ネットワーク越しにchannelを扱えるようにするnetchanというパッケージもあるようなので, 複数のコンピュータを用いて上記の方法で巨大なHopfield networkを構築してみるのも, もっと無駄で面白いかもしれません.

ソースはhttps://github.com/horiken4/gopfieldに置いてあるので, 気になった人は参照してください.

広告
カテゴリー: Code, Go, Machine Learning パーマリンク

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト /  変更 )

Google フォト

Google アカウントを使ってコメントしています。 ログアウト /  変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト /  変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト /  変更 )

%s と連携中