相互結合型のネットワーク

浅川伸一

相互結合型のネットワークの更新方法として、同期的更新と非同期的更新の２種類 が存在する。後述するホップフィールドのモデルは非同期更新であり、アソシアト ロンは同期更新である。離散的時間変化( $t=0,1,2,\ldots$)を考えて話を進めると、 同期的更新とは時刻 $t$ から 時刻 $t+1$ へ移るとき全ユニットの状態が同時 に更新されることを意味し、非同期的更新とは任意の時刻では一つのユニットの 状態が変化することをいう。

簡単な例

簡単のため図1のような 3 つのユニット $x_1, x_2, x_3$ が相互に 結合している場合を考える。 $x_1$ と $x_2$ との結合が互いに抑制性($-1$) であ り、他は結合は興奮性($+1$)である。

図 1: 簡単な相互結合のネットワーク

任意の２つのユニット A, B を考えて、A $\rightarrow$B の結合係数の大きさが B $\rightarrow$A と同じであるとき、対象結合という。対象結合でないユニット の組が一つでもあれば非対称結合のネットワークと言う。図1の 結合係数は

$$\mbox{\boldmath$W$} =\left(\begin{array}{rrr} 0 & -1 & 1\\ -1 & 0 & 1\\ 1 & 1 & 0 \end{array}\right),$$ (1)

のように行列表現が可能である。 $W$ の $i$ 行 $j$ 列目の要素 $w_{ij}$ は $j$ 番目のユニットから $i$ 番目のユニットへの 結合強度である。 時刻 $t$ における $3$ つのユニットの状態を $\left(x_1(t), x_2(t), x_3(t)\right)^T=$$x$$(t)$ とすれば 時刻 $t+1$ における各ユニットの状態は $x$$(t+1)=$$Wx$$(t)$ と表現できる。 対象結合であれば $w_{ij}=w_{ji}$ が成り立つ。 $W$ の対格要素がゼロ $w_{ii}=0$ である ことは自己結合が無いことを表している。

ユニットは 0 か 1 の 2 状態を取る節のマッカ ロック・ピッツの形式ニューロンとする。このとき、ネットワークの状態は表 1のとおり全部で 8 とおり存在する。

表 1: 図1の全状態

	状態
$x_1$	0	0	0	0	1	1	1	1
$x_2$	0	0	1	1	0	0	1	1
$x_3$	0	1	0	1	0	1	0	1

各ユニットの状態が 0, 1 のような離散量で、かつ離散時間で表現された相互結 合型のネットワークは、一般的な計算機モデルであるセルオートマトン (cellular automata) と類似の構造を持っていることが指摘できる。

同期的更新

図1で、同期的更新の場合には、(1)式に図 1の行列を右から掛ければ得られる。仮にしきい値が $0.1$ だとす れば結果は以下のようになる。

表 2: 図1のネットワークの同期的更新。(しきい値を 0.1 にし た場合)

時刻	素子	状態
	$x_1$	0	0	0	0	1	1	1	1
t	$x_2$	0	0	1	1	0	0	1	1
	$x_3$	0	1	0	1	0	1	0	1
	$x_1$	0	1	0	0	0	1	0	1
t+1	$x_2$	0	1	0	1	0	0	0	1
	$x_3$	0	0	1	1	1	1	1	1

ユニットの状態を $(x_1,x_2,x_3)$ と表記し、すべての状態変化を矢印で 表した状態遷移図を図2に示す。

図 2: 図1で同期的更新の場合の状態遷移図

図2中の $(000)$,$(011)$,$(101)$ はこの状態から動かないので不動点、または固定点 (fixed point) ということもある。 状態$(001)$ と状態$(110)$ との間では循環するこ とを意味し、このような状態をリミットサイクル (limit cycle) という。 これらの状態は、一旦この状態になると他の状態を取 ることができなくなるので、安定であるという。 また、 $(010)$,$(100)$,$(111)$ は状態$(001)$へ引き込まれるといいこれらの状態はリ ミットサイクルへの引き込み領域または流域 (basin) であるという。 また、引き込まれる点 (または状態) をアトラクタ (attractor) という。アトラクタには固定点、リミットサイクルの他に、複雑な挙 動を示すカオスアトラクタと呼ばれるものも存在する。

非同期的更新

図1でしきい値を $-0.1$ に設定した場合の非同期的更新の状態遷移 図を図3に示す。非同期更新では１度に１つの素子しか変化 しないため、矢印で繋がっている状態間では０個または１個の素子だけが変化して いることが分かる。図2と比較して大きな特徴は、全ての状 態が矢印で結ばれていることと、矢印が右から左へと繋がっていることである。

図 3: 図1で非同期的更新の場合の状態遷移図

このことから、どのような状態から出発しても、元の状態に留まるか、もしくは右 側の状態へと遷移することがわかる。一旦より右側の状態へと遷移すると左側へと 戻ることはない。あたかも地形図のように左側の状態は高く、右側は最も低いかの ごとくであり、すべての状態は、最も低い状態$(111)$ へ向かって転がり落ちてい くかのようなアナロジーを用いることができる。ホップフィールドモデルでエネ ルギー関数を導入する際に、この類推が正しいことを示すことにする。

$(000)$, $(110)$ のような状態は、初期値が $(000)$ または $(110)$ でない限 りこれら状態へ遷移することがないという意味で``エデンの園''と呼ばれる。

連想記憶

私たちは「梅干し」から「すっぱい」を連想する。 こうした連想をネットワークに記銘させる場合を考える。 ベクトル $x$$=(1,1,1,0)^T$ で「梅干し」を表し、 $y$$=(1,0,0)^T$ で「すっ ぱい」を表すとする。ここで $x$$^T$ は ベクトルの転置である。 このとき $y$$=$$Wx$ をみたす行列 $W$ が見つ かれば連想記憶と呼ぶことができる。ニューラルネットワークでは図4のように 表現される。４次元ベクトルによって表現された入力パタン $x$ から想起す べき３次元ベクトル $y$ を取り出す過程と捉えることができ、記銘すべきパ タンは入力層から出力層への結合強度として表現されていると見なすことができる。

図 4: 連想記憶のニューラルネットワーク表現

いま記名すべきパタンが $m$ 個あるとして連想パタン対を $\left(\mbox{\boldmath $x$}^{(i)},\mbox{\boldmath $y$}^{(i)}\right),i=1\ldots m$ と表現すれば、$j$ 番目の 入力から $k$ 番目の出力素子への結合強度は

$$w_{jk}=\sum_{i=1}^mx^{(i)}_jy^{(i)}_k,$$ (2)

と表現できる。 実際に

$$\left(\begin{array}{c} (1,0,0,0) \ (0,1,0,0) \ (0,0,1,0) \ (0,... ...ft(\begin{array}{c} (0,0,1) \ (0,1,0) \ (0,1,1) \ (1,0,0) \end{array}\right)$$ (3)

のような刺激-反応対を記憶する結合強度行列 (あるいは結合係数行列という) は

$$\mbox{\boldmath$W$} =\left( \begin{array}{cccc} 0 & 0 & 0 & 1\\ 0 & 1 & 1 & 0\\ 1 & 0 & 1 & 0\\ \end{array} \right),$$ (4)

となる。

自己想起の場合には、結合係数行列 $m$ 行 $m$ 列の正方行列になり、この行列の ことを自己相関行列と呼ぶ。先の例では刺激ベクトルが直交していたために正しく 想起できたが、互いに似通った記銘パタンが複数存在する場合には、似通ったパタ ンどうして誤想起が生じる。誤想起のことを雑音、またはクロストークと呼ぶ。 連想記憶の数学的な解析については甘利(1978)に詳しい。

想起を工夫して「りんご」 $\rightarrow$「まるい」 $\rightarrow$「すいか」 $\rightarrow$「あまい」 $\rightarrow$「チョコレート」のように想起を連続的に 行なうことも可能である。このことを連鎖的想起あるいは動的想起と呼ぶ。連鎖的 想起を応用すれば自由連想法などの心理モデルとなり得るだろう。

アソシアトロン

中野(1979)のアソシアトロンは結合強度 (結合係数行列) が自己相関行列であり、 自己想起、連想記憶、 のどちらにも用いることができる記憶装置である。 比較的単純な数学的構造をもっているため実現が簡単で実用性が高い。 記憶のモデル、概念学習のモデルとしての応用が研究されている。

記銘すべき項目を $n$ 次元列ベクトル $s$$=\left(s_1,s_2,\ldots,s_n\right)$ で表 現する。 $s$ の各要素は $-1,0,+1$ の 3 値をとり、$+1$ と $-1$ とが意味 を持ち、0 は中立あるいは無意味なパターンとして扱われる。記名されるべき項 目を表すニューロン間の結合係数は、$m$ 個のパターンを埋め込むとして 前節の(2)式で表される。 この式と $s$ の各要素は $-1,0,+1$ しか取らないことから $w$ の各要素も $\pm1$ または 0 となる。 想起されるパターン $\widehat{\mbox{\boldmath $s$}}$ は相関行列 $w$ を用いて

$$\widehat{\mbox{\boldmath$s$}}=\phi\left(\phi\left(\mbox{\boldmath$w$}\right)\mbox{\boldmath$s$}\right),$$ (5)

と表される。関数 $\phi$ は以下のようなしきい値関数である。

$$\phi(x)=\left\{ \begin{array}{ll} +1,& x>0\ 0,& x=0\ -1,& x<0 \end{array}\right.,$$ (6)

自己想起の場合には、記銘されているパタンと類似した入力に対して記銘パタンが 想起されることに対応し、一方連想想起では、入力パタンを手がかり(キーワード )と想起すべき内容(ボディー)に分けてキーワードとボディー部分をすべてゼロに した入力ベクトルをアソシアトロンに入力し、ボディー部分に現われる情報を 想起内容として取り出せば良い。

ホップフィールドモデル

ホップフィールド(Hopfield)¹モデルの特徴は、

1. ユニット間の結合係数が対称。 $w_{ij}=w_{ji}$ ただし $w_{ij}=0$ すなわち自己結合係数は存在しない
2. ユニットの状態変化は非同期的、一回に任意の一つのユニットしか状態 変化しない。

n 個の 2 値ユニットを考える $x_i=0,1 (i=1,2,\ldots,n)$。 このネットワークの状態は $2^n$ 個存在し、 幾何学的には $n$ 次元超立方体の頂点に対応する。 時刻 $t(=0,1,2,\ldots)$ における ユニット $i$ への入力を $u_i(t)$, 出力を $x_i(t)$ とすれば 時刻 $t+1$ での出力 $x_i(t+1)$ は、結合荷重 $w_{ij}$ としきい値 $\theta_i(t)$ を用いて次のように表現される

$$x_i(t+1)=\left\{ \begin{array}{ll} 1,&\qquad\mbox{if $u_i(t)>0$}\... ...qquad\mbox{if $u_i(t)=0$}\ 0,&\qquad\mbox{if $u_i(t)\le0$} \end{array} \right.$$ (7)

$$u_i(t)=\sum_{j=1}^nw_{ij}x_j(t)-\theta_i(t)$$ (8)

すなわち、各ユニットの $i$ は、他のユニット $j$ からの入力 $x_j(t)$ の 重み付き和 $$\sum_{j=1}^nw_{ij}x_j(t)$$ がしきい値 $\theta_i(t)$ より大きければ 1 を出力し、小さければ 0 を出力する。 ホップフィールドモデルでは、一回に一個のユニットしか変化しないことに注意。

エネルギー関数

ホップフィールドは、ネットワークの状態を表す次のエネルギー関数を 導入し、

$$E = - \frac{1}{2} \sum_{i=1}^n\sum_{j=1}^nw_{ij}x_ix_j + \sum_{j=1}^n\theta_ix_i,$$ (9)

式(7) と式(8) で定義される状態変化規則に従ってネッ トワークを動作させたとき式(9)で定義されるエネルギー関数が 必ず減少することを示した。

このことを確かめるために、ネットワークの状態が変化したときにエネルギー関数 がどのように変化するかを調べてみる。 エネルギー関数を k 番目のユニットに関する項とそれ以外の項に分けて、変形す ると

$$\begin{array}{ll} E = & {\displaystyle - \frac{1}{2} \sum_{i\... ...j - \frac{1}{2}x_k \sum_{i}w_{ik}x_i + \theta_kx_k} \end{array}$$ (10)

いま、ある時刻 t から t+1 の間に k 番目のユニットの出力が

$$x_k(t) \rightarrow x_k(t+1)$$ (11)

に変化したものとする。このとき $\Delta x_k = x_k(t+1) - x_k(t)$ は 1 か -1 である。このような $\Delta x_k$ の変化による状態変化に伴うエネルギー関数の変化 $\Delta E_k$ は、非同期的変化の仮定により k 番目のユニット以外は 変化しないので

$$\begin{array}{ll} \Delta E_k & = {\displaystyle - \frac{1}{2}... ..._{jk}}{2}x_j\right)\Delta x_k + \theta_k\Delta x_k} \end{array}$$ (12)

となる。 $w_{ij}=w_{ji}$ であることに注意して

$$\Delta E_k = -\left(\sum_{j=1}^nw_{kj}x_j -\theta_k\right)\Delta x_k$$ (13)

と表される。右辺のカッコ内は $u_k$ であるから

$$\Delta E_k = - u_k \Delta x_k$$ (14)

と書くことができる。式(7) の状態変化規則から $\Delta x_k>0$ のときは $x_k$ が $0\rightarrow 1$ に変化したことを表し ているので $u_k>0$ であるから $\Delta E_k <0$ である。反対に $\Delta x_k<0$ のときは $x_k$ が $1\rightarrow 0$ に変化したことになるので $u_k <0$ だから $\Delta E_k <0$ である。 $\Delta x_k = 0$ のときは $\Delta E_k=0$ なので、全ての場合について

$$\Delta E_k \le 0$$ (15)

となる。

最適化問題

巡回セールスマン問題

巡回セールスマン問題(Traveling salesman problem:TSP)とは、あるセールスマン が、いくつかの都市を順番に一度ずつ訪問し、最後に出発点に戻って来るときに 最短の距離で各都市を訪問するための順路を決定する問題である。 訪問すべき都市の数を N とすると、すべての組合せ数は $\frac{N!}{2N}$ になるので訪問すべき都市数が増加すると極端に難しい問題とな る。

いま A,B,C,D,E の 5 都市を訪問する TSP を考える。まず都市の数の 2 乗 25 個のニューロンを用意する。行方向に都市、列方向に訪問順序をとるとすれ ば、

	訪問順序
都市	1	2	3	4	5
A	0	1	0	0	0
B	1	0	0	0	0
C	0	0	1	0	0
D	0	0	0	0	1
E	0	0	0	1	0

のような表は BACED の順序で都市を訪問することを表している。 X 行 i 列のニューロンの出力を $x_{Xi}$ と表し、都市 X と 都市 Y との 距離を $d_{XY}$ と表すことにすると、

1. 同じ都市を２度訪問しない条件(同一行に 1 は一つしかない)

   $$\sum_X\sum_i\sum_{j\ne i}x_{Xi}x_{Xj}=0$$ (16)

   
   

2. 同時に２都市を訪問できない条件(同一列に 1 は一つだけ)

   $$\sum_i\sum_X\sum_{Y\ne X}x_{Xi}x_{Yi}=0$$ (17)

   
   

3. 全ての都市を訪問する条件(すべての 1 を足し合わせると都市数に一致 する)

   $$\sum_X\sum_ix_{Xi}=N$$ (18)

   
   

という条件のもとで、次の目的関数(経路の総距離にあたる)

$$\frac{1}{2}\sum_X\sum_{Y\ne X}\sum_id_{XY}x_{Xi}\left(x_{Y,i-1}+x_{Y,i+1}\right)$$ (19)

を最小にする問題となる。エネルギー関数は、これらの制約条件のもとで 目的関数を最小にする制約付最小化の問題になる。

$$\begin{array}{ll} E=& {\displaystyle\frac{A}{2}\sum_X\sum_i\s... ...\sum_id_{XY}x_{Xi}\left(x_{Y,i-1}+x_{Y,i+1}\right)} \end{array}$$ (20)

ホップフィールドは $A=B=500, C=200, D=500, N=15$ として 計算している。

$$E=-\frac{1}{2}\sum_{Xi}\sum_{Yj}w_{Xi,Yj}x_{Xi}x_{Yj}+\sum_{Xi}\theta_{Xi}x_{Xi}$$ (21)

と比較すれば、

$$\begin{array}{ll} w_{Xi,Yj} = & - A \delta_{XY}\left(1-\delta... ...{j,i+1}+\delta_{j,i-1}\right)\\ \theta_{Xi} = & -CN \end{array}$$ (22)

となる。ここで $\delta_{ij}$ はクロネッカーのデルタ

$$\delta_{ij} = \left\{ \begin{array}{ll} 1, &\qquad\mbox{if $i=j$},\ 0, &\qquad\mbox{if $i\ne j$} \end{array}\right.$$ (23)

である。 実際に programing するときには

$$\frac{\d u_i}{dt}= - \frac{u_i}{\tau} + \sum_{j=1}{n}w_{ij}x_j-\theta_i$$ (24)

を十分に小さい $\Delta u_i$, $\Delta t$ で近似して

$$\frac{\Delta u_i}= \left(-\frac{u_i}{\tau} + \sum_{j=1}{n}w_{ij}x_j-\theta_i\right)\Delta$$ (25)

という近似差分を用いて $u_i$ を

$$u_i(t+1) = u_i(t) + \Delta u_i$$ (26)

の漸化式で更新すればよい。

連想記憶

ホップフィールドは彼のモデルが連想記憶に適用できることを示しました。 ネットワークが記名すべきパターンベクトルを ${0,1}$ ではなく ${-1,1}$ をとるものとする²。 ネットワークに記憶させたいパターン数を P 個、s 番目のパターンを $x$$^s = \left(x_1^s,x_2^s,\ldots,x_n^s\right)\;\left(s=1,2,\ldots,P\right)$ とする。 パターン s を記憶するとは、そのパターンに対するエネルギー関数を最小化す ることに相当する。しきい値を 0 としたときパターン $x$$^s$ に関するエ ネルギー関数

$$E^s = -\frac{1}{\;2\;}\sum_{i=1}^n\sum_{j=1}^nw_{ij}^sx_i^sx_j^s$$ (27)

を最小化するもっとも簡単な方法は、 $E^s$ が $x_i^2x_j^2$ に依存するように $w_{ij}^s$ を設定するばよい³。 $w_{ij}^s = x_i^sx_j^s$ とすれば

$$E^s=-\frac{1}{\;2\;}\sum_{i=1}^n\sum_{j=1}^nw_{ij}^sx_i^sx_j^s =-\frac{1}{\;2\;}\sum_{i=1}^n\sum_{j=1}^n\left(x_i^s\right)^2\left(x_j^s\right)^2$$ (28)

となる(相関行列)。

すべてのパターンについての結合係数は、

$$w_{ij} = \sum_{s=1}^Pw_{ij}^s = \sum_{s=1}^Px_i^sx_j^s$$ (29)

によって近似的に求めるめることができる。 記憶すべきパターンが似ていたり、パターンベクトルの次元数 n に対して パターン数 P の数が多すぎると正しき記憶できないことがある。 このパターン間の相互干渉のことをクロストークという。 ホップフィールドは記憶できるパターン数はユニット数の 15 % 程度である ことを示した。

相関行列を用いてホップフィールドネットの結合強度を決定する方法に対し、 一般化逆行列 generalized inverse matrix の概念を導入し、クロ ストークを生じさせないようパターンを直交化して記憶する方法が提案されてい る。一般化逆行列にはいくつかの定義があるが、ムーア-ペンローズ Moore-Penrose の定義を用いることにすれば、

$$\mbox{\boldmath$Z$} ^+ = \left(\mbox{\boldmath$Z$}^T\mbox{\boldmath$Z$}\right)^{-1}\mbox{\boldmath$Z$}^T$$ (30)

記名するパターンを $\left[{\xi^1,\xi^2,\ldots,\xi^p}\right]$ のように並べて できる $N \times P$ 行列を $X$ としたとき $W$ は一般化逆行列を 用いて以下のように求められる。

$$\mbox{\boldmath$W$} = \mbox{\boldmath$XX$} ^+ = \mbox{\boldmath$X$} \left(\mbox{\boldmath$X$}^T\mbox{\boldmath$X$}\right)^{-1}\mbox{\boldmath$X$}^T$$ (31)

なおネットワークの状態変化を行なうには、$W$ を結合強度行列として 7 を用いればよい。

結合強度の求め方

ホップフィールドネットの結合強度をエネルギー関数から求める方法。 この方法は与えられた問題が最適化問題に置き換えられるときに有効で、 最小化する目的関数とネットワークのエネルギー関数を比較することで結合強度 を求める。

説明を簡単にするために、ホップフィールドネットに与えられたアナログ値を4 ビットのディジタル値に変換する A/D 変換問題を考える。 ネットワークは 4 ユニットで構成され、それらの状態 $x_0x_1x_2x_3$ は変換 後のディジタル値 (0 or 1) を表すものとする。また、変換するアナログ値はネッ トワークの外部入力として提示される。このようなネットワークが A/D 変換器 として機能を持つためには、入力されるアナログ値 a とすると、以下のエネル ギー関数を最小化すればよい。

$$\begin{array}{ll} E&={\displaystyle \frac{1}{\;2\;}\left(a-\s... ...3\left(-2^{2i-1}+2^ia\right)x_i+\frac{1}{\;2\;}a^2} \end{array}$$ (32)

ここで ${\displaystyle\sum_{j\ne i=0}^3}$ は 0 から 3 までで $i$ に等しく ない添字 $j$ に関して加え合わせることを意味する。 $w_{ij}=0$ で外部入力 $I_i$ 考慮したネットワークのエネルギー関数は

$$E=\frac{1}{\;2\;}\sum_{i=0}^3 \sum_{j\ne i=0}^3 w_{ij}x_ix_j - \sum_{i=0}^3 x_i I_i$$ (33)

式(32) と式(33) とを比較すると

$$w_{ij} = -2^{\left(i+j\right)}\qquad\left(i\ne j\right)$$ (34)

$$I_i = -2^{\left(2i-1\right)}+2^ia$$ (35)

与えれたエネルギー関数がリアプノフ関数 Lyapunov function の条件を満たす ように、エネルギー関数から直接的にネットワークダイナミックスを求める方法 もある。これは、まず式(32) の時間微分を求めて

$$\frac{dE}{dt} = - \sum_{i=0}^3 \frac{dx_i}{dt} \left\{{\sum_{j\ne i=0}^3-2^{\left(i+j\right)}x_j - 2^{\left(2i-1\right)}+2^ia}\right\}$$ (36)

ネットワークのエネルギーが時間とともに減少するためには $\frac{dE}{dt}\le0$ の関係が常に満たされればよい。このためには、以下に示すように $\frac{du_i}{dt}$を式(36)の[ ]内の式に等しくすればよい

$$\frac{du_i}{dt} = \sum_{j\ne i=0}^3 -2^{\left(i+j\right)}x_j - 2^{\left(2i-1\right)}+2^ia\qquad\left(i=0,1,\ldots,3\right)$$ (37)

$$x_i = f(u_i)$$ (38)

このとき

$$\frac{dE}{dt} = - \sum_{i=0}^3 \frac{dx_i}{dt}\frac{du_i}{dt} = - \sum_{i=0}^3f'(u_i)\left(\frac{du_i}{dt}\right)^2$$ (39)

となり $f(u_i)$ を単調増加関数とすれば $\frac{dE}{dt}<0$ が満たされるこ とがわかる。

この結果は先の式と一致する。

脚注

... ホップフィールド(Hopfield)¹

http://dope.caltech.edu/

... をとるものとする²

0, 1 の値をとる n 次元ベクトルは $$w_{ij}=\sum_{s=1}^p \left(2x_i^s-1\right)\left(2x_j^s-1\right)$$ にすればよい。

...³

$x_i$ は -1 か 1 だが、$x_i^2$ は常に正