パターンを記憶するニューラルネット，ホップフィールドネットワークを実装してみる

この記事ではニューラルネットワークの一種であるホップフィールドネットワークについて解説し簡単に実装します．
コードは[github](https://github.com/shutakahama/Hopfield_Network)にあるので興味があれば覗いていただけると嬉しいです．

## ホップフィールドネットワークとは
ホップフィールドネットワークを一言で言うと，「**全結合型のニューラルネットワーク**」です．
現在深層学習で主流になっているフィードフォーワードネットワークは，ニューロンのまとまりである層を積み重ねた構造をしており，各層から次の層への一方向の結合しか存在しません．それに対しホップフィールドネットワークは任意の2つのニューロン全てについて両方向の対称的な結合が存在しています．以下の画像のようなイメージです．

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/470270/5b72bfb8-b8a2-5ed6-02b6-9c5ee36c2cb1.png" width="300">

ホップフィールドネットワークの特徴として，特定のパターンを記憶できる事が挙げられます．いくつかのパターンを入力として学習させておくと，ノイズを含んだパターンを入力した際に元のパターンを想起する事ができます．この記事ではその連想記憶のような性質を簡単な実装で確かめてみたいと思います．

## 理論
### 構造
まずホップフィールドネットワークの構造を説明します．
N個のニューロンからなるホップフィールドネットワークを考えます．任意のニューロンのペアには結合があるので，自己結合も想定すると結合はN*N本あります．ニューロンiからニューロンjへの結合重みを$w_{ij}$とすると，重み行列は$W \in ℝ^{N \times N}$ で表せます．

各ニューロンは結合している他のニューロンからの入力を合わせて何らかの値を計算し，1か-1の値を保持します．ネットワークの出力はそれぞれのニューロンの値なので，1か-1を含んだN次元のベクトルとなります．

### 学習

記憶するパターンを$𝑥^1, x^2, ... , x^Q$のQ個とします．$x$は各要素が1か-1のN次元ベクトルであり，各要素が各ニューロンに割り当てられます．これらに対して重み行列Wを

```math
W = \frac{1}{Q}\sum_{q=1}^{Q} x^q (x^q)^T  \hspace{50pt}(1)
```
と定義します．定義上$w_{ij} = w_{ji}$となります．自己結合を考慮しない場合は$w_{ii} = 0$とすればよいです．この重みは固定され想起時には更新されません．

これで学習（というか記憶）は終わりです．一瞬ですね．

### 想起 

ネットワークの学習後，ある入力が入ってきたときに元のパターンを想起します．具体的には，元の記憶したパターンにノイズが加わったような入力から元のパターンを想起します．  
記憶パターンQ個のうち一つにある割合でノイズを加えたものをテスト入力$x \in ℝ^N$とします．各ニューロンの値を$x$の各値に初期化し，値を更新していきます．時刻tでのニューロンiの更新は

```math
\begin{align}
y_i(t) &= \sum_{j=1}^{N} w_{ij} * x_j(t) \hspace{53pt}(2) \\
x_i(t+1) &= sgn(y_i(t) - \theta_i) \hspace{50pt}(3)
\end{align}
```

で行います．sgn()は符号をみる関数，$\theta$は閾値です．$\theta$との比較によって各ニューロンの出力は1, 0, -1のいずれかの値をとります．
この更新を十分行って平衡状態に達したら終了です．

このネットワークのエネルギーは

```math
E(t) = -\frac{1}{2} \sum_{i \neq j} w_{ij}x_i(t)x_j(t) + \sum_i \theta_i x_i(t)  \hspace{40pt}(4)
```
と書けるのですが，各iについて

```math
E(t) = -\bigl(\frac{1}{2} \sum_{j} w_{ij}x_j(t) - \theta_i \bigl)x_i(t) + (x_iを含まない項)
```

と書けるため，$y_i - \theta_i$の符号によって$x_i$を更新することで更新のたびにEは単調減少することが分かります．Eが収束した地点（平衡点）が想起の完了であり，更新を繰り返すことでノイズを含んだ入力であっても記憶したパターンに収束していくことが知られています．収束した地点の各ニューロンの値が想起した出力となります．

なお更新の方法には同期型、非同期型の2つがあります．

- 同期型: 全てのニューロンを同時に更新
- 非同期型: 一つずつニューロンを更新

ホップフィールドネットワークは基本的に非同期型のことを言うようです．  

## 実装
実装のメインファイルは[hopfield_network.py (githubのリンク)](https://github.com/shutakahama/Hopfield_Network/blob/master/hopfield_network.py)です．

学習データ(記憶させるパターン)$X \in ℝ^{N \times d}$は2次元ベクトルで，d次元の学習データN個です．
実行するとまず式(1)に従いfit()関数によってパターンの学習が行われます．自己結合は0にしてあります．fit()はd*d次元の重み行列Wを返します．

```python:hopfield_network.py
def fit(self):
    self.W = np.dot(self.train_data, self.train_data.T)/self.train_num  # W = Σ x*x^T
    for i in range(self.data_size * self.data_size):
        self.W[i, i] = 0  # 対角成分0

    return self.W
```
  
テストデータはtest_make()で生成します．学習データの中からパターンを一つ選び、それにノイズを加えたものをテストデータとします．
ノイズは指定した確率で各ニューロンの値に−１をかけて反転させるようなものです．

```python:hopfield_network.py
def test_make(self, test_idx):
    # test_idxが選択した学習データのインデックス
    x_test = copy.deepcopy(self.train_data[:, test_idx])
    # 確率self.noiseで符号を反転させる
    flip = choice([1, -1], self.data_size * self.data_size, p=[1 - self.noise, self.noise])
    x_test = x_test * flip

    return x_test
```

パターンの想起はpredict_syn(), predict_asyn()によって行います．  
predict_syn()は同期更新で全てのニューロンを同時に更新します．収束の判定はエネルギー関数を使いました．

```python:hopfield_network.py
def predict_syn(self, test_data):
    e_old = float("inf")
    for _ in range(self.loop_update):  # self.loop_updateは更新の上限値
        # テストデータの更新とエネルギーの計算
        test_data = np.sign(np.dot(self.W, test_data))
        e_new = self.energy(test_data)

        # エネルギーが変化しなくなったら打ち切り
        if e_new == e_old:
            break

        e_old = e_new

    return test_data
```

後者は非同期更新で，ランダムにニューロンを１つ選びその値を更新することを繰り返します．エネルギー変化で収束を判断するのが難しかったため、ここでは単純に更新を十分な数繰り返すことにしました．

```python:hopfield_network.py
def predict_asyn(self, test_data):
    for _ in range(self.loop_update):
        num = randint(self.data_size*self.data_size)
        test_data[num] = np.sign(np.dot(self.W[num], test_data))

    return test_data
```
 
想起性能はdistance()で評価します．学習データのうち想起結果と最も距離が小さかったパターンをmin_idx，その差をmin_disとして出力します．なお距離とは，記憶パターンと出力を比べたとき値の違うニューロンの数です．

```python:hopfield_network.py
def distance(self, x):
    # 対象データと訓練データの差を計算
    x = x.reshape(self.data_size * self.data_size, 1)
    dis = np.sum(np.abs(self.train_data - x), axis=0) / 2

    # 最小の距離とそのインデックスを取り出す
    min_dis = np.min(dis)
    min_idx = np.argmin(dis)
    # print('train model = {0}, distance = {1}'.format(min_idx, min_dis))
    return min_dis, min_idx
``` 

最後にこれらを行うrun()関数はこのようになっています．self.loop_testの回数だけテストを繰り返し，想起した結果が学習パターンと完全に一致した割合を正答率accとしてカウントします．

```python:hopfield_network.py
def run(self, test_idx):
    dis = 0  # 正解と異なるマスの数
    acc = 0  # 正解率

    # 訓練データから重み行列の計算
    self.W = self.fit()

    for l in tqdm(range(self.loop_test)):
        # テストデータの作成
        test_data = self.test_make(test_idx)
        # self.plot(test_data.reshape(1, -1), 'test_{:04d}_data'.format(l))

        # テストデータからの想起
        test_predict = self.predict_syn(test_data) if self.syn else self.predict_asyn(test_data)
        # self.plot(test_data.reshape(1, -1), 'test_{:04d}_after'.format(l))

        # 正答率，距離の計算
        _dis, _ = self.distance(test_predict)
        dis += _dis
        if _dis == 0:
            acc += 1

        # print(_dis, acc)

    dis /= self.loop_test
    acc /= float(self.loop_test)
    print("distance = {0}".format(dis))
    print("accuracy = {0}".format(acc))
```

## 実験
実装したホップフィールドネットワークを使って色々な場合の挙動を実験してみました．

### データセット
記憶パターンとして[train_data.npy](https://github.com/shutakahama/Hopfield_Network/tree/master/data)に25次元ベクトルを6データ用意しました．各要素の値は1か-1のいずれかで，5*5にして描画すると以下のようになります．左から記憶パターン 1, 2, ..., 6 と呼ぶことにします．

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/470270/5d0700d1-6a0c-3c97-3a43-2fddb2b04fbb.png" width="500">

データは自由に書き換えることができますが，描画の関係上要素の数は平方数(25や36など)であることが望ましいです．

例えば，記憶パターン1についてrate = 0.1でノイズを与えた場合の結果は例えば以下のようになります．これを入力してパターン1が出力されれば成功です．

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/470270/d1d1721e-f055-d74f-550e-60bb805f195e.png" width="300">

### 実験1　記憶パターン数とノイズ割合を変えてみる

非同期更新のもと，記憶パターンの数を1個〜6個, とノイズの割合を0.05〜0.2でそれぞれ変化させて実験しました．評価指標は

 - 距離dis: 出力が記憶パターンと異なっていたマスの個数
 - 正答率acc: 記憶パターンと完全に一致していた割合

です．テストを1000回行い平均値を求めました．

<img width="600" alt="スクリーンショット 2020-06-16 17.11.44.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/470270/6ba45c27-1ff4-37d5-5bfc-e3a56cd4cb21.png">

<img width="600" alt="スクリーンショット 2020-06-16 17.12.59.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/470270/1e1d0e03-a6c5-59b6-0d2e-65eb0f4f44b1.png">

パターン数が増えるにつれて，またノイズを増やすにつれて正答率が下がり距離が大きくなっていくことがわかります．

### 実験2　ノイズを0.5や1.0にしてみる
ノイズ割合を非常に大きくした場合の実験です．記憶パターンを1つにして，ノイズの割合を0.5, 0.8, 1.0としてみました．
ここで，ノイズ割合が0.5ということはちょうど確率半分で値を反転させるので，入力は完全にランダムな値になります．またノイズ割合が1.0の場合は必ず値を反転させるので，記憶パターンとは完全に逆転した入力になります．

結果はこうなりました．

| ノイズ | 0.5 | 0.8 | 1.0
----|----|----|---- 
| 正答率(%) | 50.2 | 0.0 | 0.0
| 距離(マス) | 12.5 | 25.0 | 25.0

このネットワークで学習すると，記憶パターンが1つの場合，2個の安定化パターンが存在することがわかりました．1つは記憶パターンと同じもの，もう1つは記憶パターンを完全に反転させたものです．つまり入力が記憶パターンに近ければ元の記憶パターンに，反転させたものに近ければ反転させたものに収束するということです．

ノイズが0.5の場合はランダムな入力なので，もとのパターンと反転させたものどちらに収束するかはちょうど等確率であり，結果正答率は50%になりました．またノイズが1.0の場合は反転させたパターンと同じなので必ずそちらに収束し，正答率は0%になったというわけです．

### 実験3 同期更新してみる
ホップフィールドネットワークでは非同期更新が一般的ですが，実装の部分で説明したようにpredict_syn()を使うと同期更新できるので，非同期更新の結果と比べてみました．
記憶パターンが2個，4個のとき，同期更新と非同期更新それぞれについて，ノイズを0.0〜1.0で変えた時の正答率がこちらです．

<img width="600" alt="スクリーンショット 2020-06-17 12.31.52.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/470270/a1313df1-b77e-eb75-0450-4eb7fa8ca3ea.png">


非同期更新の方が正答率が高いです．同期型は全てのニューロンをまとめて計算するため収束は速かったのですが，その分刻みの大きい更新になり局所解にはまってしまったのかもしれません．また同期更新ではエネルギーが収束する保証がないためうまく収束しなかった可能性もあります．

### 実験4 自己結合を入れてみる
これまでの実験ではニューロンの自己結合の重みを0にしていましたが，0にせずそのままの重みにして想起させてみました．
記憶パターンが2個，4個のとき，自己結合あり・なしそれぞれについて，ノイズを0.0〜0.5で変えた時の正答率がこちらです．

<img width="600" alt="スクリーンショット 2020-06-16 17.47.09.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/470270/a773fa21-046f-32fc-e54b-dfedc55e1247.png">


記憶パターン2個だとほとんど差がありませんが，記憶パターン4個では自己結合がある方が正答率がよくなりました．自己結合がなぜ性能向上するのかはよくわからなかったのですが，例えば[こちらの論文](https://ci.nii.ac.jp/naid/110003227470)では自己結合の大きさを時間とともに変化させており，自己結合をうまく取り入れることで性能を改善させる試みもあるようです．


## まとめ
ニューラルネットの一つであるホップフィールドネットワークを実装し，記憶パターンの数やノイズ割合などを変えていくつか実験をしてみました．以下は参考にさせていただいた記事です．

- [ゼロから始めるDeepLearning_その2_ホップフィールドネットワークとは](http://rishida.hatenablog.com/entry/2014/03/03/174331)
- [Theano で Deep Learning <6の準備>: ホップフィールドネットワーク](http://sinhrks.hatenablog.com/entry/2014/12/30/221538)
- [ホップフィールド・ネットワーク](https://www.sist.ac.jp/~kanakubo/research/neuro/hopfieldnetwork.html)

ホップフィールドネットワークの仕組みはボルツマンマシンなどのベースにもなっています．フィードフォーワードネットワークとはまた違った機能や魅力があるので，今後さらに注目されるときが来るかもしれないですね．