連想記憶モデル（Hopfield network）の実装

（一応 physics ジャンルの投稿です）

（細かい話に興味ない人は「原理」の節を飛ばしてください）

投稿の概要

連想記憶モデル（Hopfield model）は人工知能（AI）の一種で、情報の記憶、取り出しを行うことができる。以下で述べるように、不鮮明な入力から記憶した情報を思い出すことができる。本投稿は連想記憶モデルの原理について述べ、簡単な実験を行えるプログラムを紹介する。実験結果についても簡単に述べる。なお、"Statistical Physics of Spin Glasses and Information Processing An Introduction" by Hidetoshi Nishimori¹ を参考文献としてお送りする。

連想記憶モデルとは？

連想記憶モデル（Hopfield network）は情報の記憶・思い出しを行うニューラルネットワーク。例えば、1000枚の画像をこのネットワークに記憶させる。次に、1000枚の中から1枚を選び、それにノイズをのせた画像を用意する。そして、その画像をネットワークに入力すると、徐々に元の画像が再現される。この思い出しは常に成功するのではなく、条件を満たす必要がある。

画像を思い出す様子

連想記憶は脳が記憶したり思い出したりする仕組みを参考に構築されている。そのため、各記憶素子を「ニューロン」と呼ぶ。実際の脳のニューロンは発火したりしなかったりすることで情報を保持・伝達する。本モデルでもニューロンは発火・非発火により情報の保持・伝達を行う。

原理

パターンの記憶

記憶するパターン数を $p$ とし、各ニューロンの記憶パターンを ${\xi_i^\mu}$ で表す。$\mu$ 番目の記憶パターンでは $i$ 個目のニューロンが $\xi_i^\mu$ の状態（発火・非発火）を表す：

\[\begin{equation} \xi_i^{\mu} = \begin{cases} 1 & \text{：発火} \\ -1 & \text{：非発火} \\ \end{cases} \end{equation}\]

ニューロン同士の相互作用として次の量$J_{ij}$を定義する。系は$J_{ij}$を計算することで $p$ 個のパターンがネットワークを記憶（埋め込み）する：

\[\begin{equation} J_{ij} = \frac{1}{N} \sum_{\mu = 1}^{p} \xi_i^\mu \xi_j^\mu \end{equation}\]

$N$ はニューロンの個数。$J$ は $N\times N$ の行列。また、$J_{ii} = 0$ とする。

ニューロン間のやりとり

ニューロン同士は情報のやり取りを行うことで記憶したものを思い出す。あるニューロンの状態は他のニューロンの状態により決まる。ニューロン $i$ がニューロン $j$ から受け取る信号の大きさを次のように決める：

\[\begin{equation} J_{ij}(S_j + 1) = \begin{cases} 2J_{ij} & :~S_j = +1 \\ 0 & :~S_j = -1 \\ \end{cases} \end{equation}\]

こうすると良い理由は後述。すると、ニューロン $i$ に入ってくる信号の和 $h_i$ は

\[\begin{equation} h_i = \sum_{j = 1}^{N} J_{ij}(S_j + 1) \end{equation}\]

ニューロン $i$ は入力の和があるしきい値 $\theta_i$ を超えるときに発火、そうでなければ非発火とする：

\[\begin{align} S_i(t + \Delta t) &= \mathrm{sgn}(h_i - \theta_i) \nonumber\\ &= \mathrm{sgn}\left(\sum_{j = 1}^{N} J_{ij}(S_j + 1) - \theta_i\right) \end{align}\]

ここで $\mathrm{sgn}(\cdot)$ は符号関数。簡単のために、$\theta_i = J_{ij}$ として

\[\begin{equation} S_i(t + \Delta t) = \mathrm{sgn}\left(\sum_{j = 1}^{N} J_{ij}S_j(t)\right) \end{equation}\]

思い出し

ここまで、ニューロンを使った記憶の方法・情報のやり取りの方法を説明した。この方法で本当に上手くいくのか？　上手くいくことを確認する。

思い出すとは、記憶したパターンに近いものを与えられたとき、元のパターンを復元できること。まずは、与えられるニューロンパターンが $\mu$ 番目パターンそのものの場合を考える。時刻 $t$ でニューロンたちが $\mu$ 番目のパターンそのものであるとき、時刻 $t + \Delta t$ では

\[\begin{align} S_i (t + \Delta t) &= \mathrm{sgn}\left(\sum_{j = 1}^{N} J_{ij}S_j(t)\right) \nonumber\\ &= \mathrm{sgn}\left(\sum_{j = 1}^{N} J_{ij}\xi_j^\mu\right) \nonumber\\ &= \mathrm{sgn}\left(\sum_{j = 1}^{N} \frac{1}{N}\sum_{\nu = 1}^p \xi_i^\nu \xi_j^\nu \xi_j^\mu\right) \nonumber\\ &= \mathrm{sgn}\left(\sum_{\nu = 1}^p \xi_i^\nu \frac{1}{N} \sum_{j = 1}^{N} \xi_j^\nu \xi_j^\mu\right) \end{align}\]

ここで

\[\begin{equation} \frac{1}{N} \sum_{j = 1}^{N} \xi_j^\nu \xi_j^\mu \end{equation}\]

は、$\mu = \nu$ のときは 1、$\mu \neq \nu$ のときは $N$ が十分大きければ 0 になりそう。なので、この部分はクロネッカーのデルタ $\delta_{\nu,\mu}$ になる。

\[\begin{align} S_i (t + \Delta t) &= \mathrm{sgn}\left(\sum_{\nu = 1}^p \xi_i^\nu \delta_{\nu,\mu}\right) \nonumber\\ &= \mathrm{sgn}(\xi_i^\mu) \nonumber\\ &= \xi_i^\mu \end{align}\]

確かに、時刻 $t + \Delta t$ でも系の状態はパターン $\mu$ のままであった。

次に、与えられるパターンがパターン $\mu$ から少しだけずれているときを考える。これは、系のエネルギーから定性的に説明できる。ニューロン $i$ に関して、入力信号 $h_i$ と状態 $S_i$ の積を考えると

\[\begin{align} -h_iS_i &= -\sum_j J_{ij}(S_j + 1) S_i \nonumber\\ &= -\sum_j J_{ij}S_iS_j + const. \times S_i \end{align}\]

全ての $i$ について和をとれば

\[\begin{equation} H = -\frac{1}{2}\sum_{i,j} J_{ij}S_iS_j \end{equation}\]

ただし、定数部分は適当。この $H$ に関して次のことがわかる：

$H$ は Ising model の Hamiltonian
ひとつのニューロンに関して、入力信号と状態が等しいときエネルギーは小さく、異なるときエネルギーは大きくなる
系の状態がパターンの状態と等しいとき、エネルギーは極小（各ニューロン、入力 $h_i$ と状態 $S_i$ は等しくなっているので）

従って、系の状態がパターン $\mu$ から少し異なるとき、エネルギーが極小に落ち込むように、パターン $\mu$ に近づいていく。

以上により、連想記憶モデルは記憶と思い出しが行えることがわかった。

実装

GitHub で公開している。

ここでは簡単に、記憶パートと思い出しパートを取り出して説明する。とはいえ、どちらも行列・ベクトルの計算をするだけで、それには Boost C++ Library の boost::numeric::ublas を用いた。

記憶

#define sgn(x) (x >= 0 ? 1 : -1)  // 符号関数

std::mt19937 engine(12345);  // 乱数生成器

boost::numeric::ublas::matrix<double> J(n, n);  // J 行列
std::vector<boost::numeric::ublas::vector<int>> xi(p, ublas::vector<int>(n));  // p個のパターン ξ ベクトル

for (int mu = 0; mu < p; ++mu) {  // p個のパターンに対して
    for (int i = 0; i < n; ++i) {
        if (mu != 0) xi[mu](i) = sgn((int)engine());  // (p - 1)個のパターンをランダム生成
        for (int j = 0; j <= i; ++j) {  // 行列の下三角だけ埋める
            J(i, j) += xi[mu][i] * xi[mu][j];  // ξ_i^μ × ξ_j^μ
        }
    }
}
J /= (double)n;
for (int i = 0; i < n; ++i) for (int j = 0; j < i; ++j) J(j, i) = J(i, j);  // 行列の上半分は下半分のコピー（J_ij = J_ji）

思い出し

boost::numeric::ublas::vector<double> s(n), stemp(n);  // s: 入力（元画像にノイズがのったもの）; stemp: 計算の途中結果を一次保存

for (int t = 1; t < duration; ++t) {
    // sgn(J * s)
    stemp = ublas::prod(J, s);  
    for (int i = 0; i < n; ++i) s(i) = sgn(stemp(i));
}