相互結合型のネットワーク
浅川伸一 <[email protected]>
相互結合型のネットワークの更新方法として、同期的更新と非同期的更新 の２種類が存在する。後述するホップフィールドのモデルは非同期更新であ り、アソシアトロンは同期更新である。離散的時間変化 (t = 0, 1, 2, . . .) を考 えて話を進めると、同期的更新とは時刻 t から 時刻 t + 1 へ移るとき全ユ ニットの状態が同時に更新されることを意味し、非同期的更新とは任意の時 刻では一つのユニットの状態が変化することをいう。1
簡単な例
簡単のため図 1 のような 3 つのユニット x1, x2, x3 が相互に結合している 場合を考える。x1 と x2 との結合が互いに抑制性 (−1) であり、他は結合は 興奮性 (+1) である。任意の２つのユニット A, B を考えて、A→B の結合係 -1 1 -1 1 1 1 x3 x2 x1 図 1: 簡単な相互結合のネットワーク 数の大きさが B→A と同じであるとき、対象結合という。対象結合でないユ ニットの組が一つでもあれば非対称結合のネットワークと言う。図 1 の結合 係数は W = 0 −1 1 −1 0 1 1 1 0 , (1) のように行列表現が可能である。W の i 行 j 列目の要素 wij は j 番目の ユニットから i 番目のユニットへの結合強度である。時刻 t における 3 つ のユニットの状態を (x1(t), x2(t), x3(t))T = x(t) とすれば時刻 t + 1 における各ユニットの状態は x(t + 1) = W x(t) と表現できる。対象結合であれば wij = wjiが成り立つ。W の対格要素がゼロ wii = 0 であることは自己結合 が無いことを表している。 ユニットは 0 か 1 の 2 状態を取るマッカロック・ピッツの形式ニューロン とする。このとき、ネットワークの状態は表 1 のとおり全部で 8 とおり存在 する。 表 1: 表 1 の全状態 状態 x1 0 0 0 0 1 1 1 1 x2 0 0 1 1 0 0 1 1 x3 0 1 0 1 0 1 0 1 各ユニットの状態が 0, 1 のような離散量で、かつ離散時間で表現された相 互結合型のネットワークは、一般的な計算機モデルであるセルオートマトン (cellular automata) と類似の構造を持っていることが指摘できる。
1.1
同期的更新
図 1 で、同期的更新の場合には、(1) 式に図 1 の行列を右から掛ければ得ら れる。仮にしきい値が 0.1 だとすれば結果は以下のようになる。ユニットの 表 2: 図 1 のネットワークの同期的更新。(しきい値を 0.1 にした場合) 時刻 素子 状態 x1 0 0 0 0 1 1 1 1 t x2 0 0 1 1 0 0 1 1 x3 0 1 0 1 0 1 0 1 x1 0 1 0 0 0 1 0 1 t+1 x2 0 1 0 1 0 0 0 1 x3 0 0 1 1 1 1 1 1 状態を (x1, x2, x3) と表記し、すべての状態変化を矢印で表した状態遷移図 を図 2 に示す。図 2 中の (000),(011),(101) はこの状態から動かないので不動 点、または固定点 (fixed point) ということもある。状態 (001) と状態 (110) との間では循環することを意味し、このような状態をリミットサイクル (limit cycle) という。これらの状態は、一旦この状態になると他の状態を取ることが できなくなるので、安定であるという。また、(010),(100),(111) は状態 (001) へ引き込まれるといいこれらの状態はリミットサイクルへの引き込み領域ま100 110 111 000 011 101 001 010 図 2: 図 1 で同期的更新の場合の状態遷移図 たは流域 (basin) であるという。また、引き込まれる点 (または状態) をア トラクタ (attractor) という。アトラクタには固定点、リミットサイクルの他 に、複雑な挙動を示すカオスアトラクタと呼ばれるものも存在する。
1.2
非同期的更新
図 1 でしきい値を −0.1 に設定した場合の非同期的更新の状態遷移図を図 3 に示す。非同期更新では１度に１つの素子しか変化しないため、矢印で繋 がっている状態間では０個または１個の素子だけが変化していることが分か る。図 2 と比較して大きな特徴は、全ての状態が矢印で結ばれていることと、 矢印が右から左へと繋がっていることである。このことから、どのような状 100 110 111 001 010 000 011 101 図 3: 図1で非同期的更新の場合の状態遷移図 態から出発しても、元の状態に留まるか、もしくは右側の状態へと遷移する ことがわかる。一旦より右側の状態へと遷移すると左側へと戻ることはない。 あたかも地形図のように左側の状態は高く、右側は最も低いかのごとくであ り、すべての状態は、最も低い状態(111) へ向かって転がり落ちていくかの ようなアナロジーを用いることができる。ホップフィールドモデルでエネル ギー関数を導入する際に、この類推が正しいことを示すことにする。 (000), (110)のような状態は、初期値が(000)または (110)でない限りこれら状態へ遷移することがないという意味で “エデンの園” と呼ばれる。
2
連想記憶
私たちは「梅干し」から「すっぱい」を連想する。こうした連想をネット ワークに記銘させる場合を考える。ベクトル x = (1, 1, 1, 0)T で「梅干し」を 表し、y = (1, 0, 0)T で「すっぱい」を表すとする。ここで xT は ベクトル の転置である。このとき y = W x をみたす行列 W が見つかれば連想記憶 と呼ぶことができる。ニューラルネットワークでは図 4 のように表現される。 ４次元ベクトルによって表現された入力パタン x から想起すべき３次元ベク トル y を取り出す過程と捉えることができ、記銘すべきパタンは入力層から 出力層への結合強度として表現されていると見なすことができる。いま記名 x1 x2 x3 x4 y1 y2 y3 図 4: 連想記憶のニューラルネットワーク表現 すべきパタンが m 個あるとして連想パタン対を¡x(i), y(i)¢, i = 1 . . . m と表 現すれば、j 番目の入力から k 番目の出力素子への結合強度は wjk= m X i=1 x(i)j y(i)k , (2) と表現できる。実際に (1, 0, 0, 0) (0, 1, 0, 0) (0, 0, 1, 0) (0, 0, 0, 1) → (0, 0, 1) (0, 1, 0) (0, 1, 1) (1, 0, 0) (3) のような刺激–反応対を記憶する結合強度行列 (あるいは結合係数行列という) は W = 0 0 0 1 0 1 1 0 1 0 1 0 , (4)となる。 自己想起の場合には、結合係数行列 m 行 m 列の正方行列になり、この行 列のことを自己相関行列と呼ぶ。先の例では刺激ベクトルが直交していたた めに正しく想起できたが、互いに似通った記銘パタンが複数存在する場合に は、似通ったパタンどうして誤想起が生じる。誤想起のことを雑音、または クロストークと呼ぶ。連想記憶の数学的な解析については甘利 (1978) に詳 しい。 想起を工夫して「りんご」→「まるい」→「すいか」→「あまい」→「チョ コレート」のように想起を連続的に行なうことも可能である。このことを連 鎖的想起あるいは動的想起と呼ぶ。連鎖的想起を応用すれば自由連想法など の心理モデルとなり得るだろう。
3
アソシアトロン
中野 (1979) のアソシアトロンは結合強度 (結合係数行列) が自己相関行列 であり、自己想起、連想記憶、のどちらにも用いることができる記憶装置で ある。比較的単純な数学的構造をもっているため実現が簡単で実用性が高い。 記憶のモデル、概念学習のモデルとしての応用が研究されている。 記銘すべき項目を n 次元列ベクトル s = (s1, s2, . . . , sn) で表現する。s の 各要素は −1, 0, +1 の 3 値をとり、+1 と −1 とが意味を持ち、0 は中立ある いは無意味なパターンとして扱われる。記名されるべき項目を表すニューロ ン間の結合係数は、m 個のパターンを埋め込むとして前節の (2) 式で表され る。この式と s の各要素は −1, 0, +1 しか取らないことから w の各要素も ±1 または 0 となる。想起されるパターン bs は相関行列 w を用いて b s = φ (φ (w) s) , (5) と表される。関数 φ は以下のようなしきい値関数である。 φ(x) = +1, x > 0 0, x = 0 −1, x < 0 , (6) 自己想起の場合には、記銘されているパタンと類似した入力に対して記銘パ タンが想起されることに対応し、一方連想想起では、入力パタンを手がかり (キーワード) と想起すべき内容 (ボディー) に分けてキーワードとボディー部 分をすべてゼロにした入力ベクトルをアソシアトロンに入力し、ボディー部 分に現われる情報を想起内容として取り出せば良い。4
ホップフィールドモデル
ホップフィールド (Hopfield & Tank, 1985)1 モデルの特徴は、
1. ユニット間の結合係数が対称。wij = wjiただし wij = 0 すなわち自己 結合係数は存在しない 2. ユニットの状態変化は非同期的、一回に任意の一つのユニットしか状態 変化しない。 n 個の 2 値ユニットを考える xi = 0, 1 (i = 1, 2, . . . , n)。このネットワー クの状態は 2n 個存在し、幾何学的には n 次元超立方体の頂点に対応する。 時刻 t(= 0, 1, 2, . . .) におけるユニット i への入力を ui(t), 出力を xi(t) とす れば時刻 t + 1 での出力 xi(t + 1) は、結合荷重 wij としきい値 θi(t) を用い て次のように表現される xi(t + 1) = 1, if ui(t) > 0 xi(t), if ui(t) = 0 0, if ui(t) ≤ 0 (7) ui(t) = n X j=1 wijxj(t) − θi(t) (8) すなわち、各ユニットの i は、他のユニット j からの入力 xj(t) の重み付き 和 n X j=1 wijxj(t) がしきい値 θi(t) より大きければ 1 を出力し、小さければ 0 を出力する。ホップフィールドモデルでは、一回に一個のユニットしか変化 しないことに注意。
4.1
エネルギー関数
ホップフィールドは、ネットワークの状態を表す次のエネルギー関数を導 入し、 E = −1 2 n X i=1 n X j=1 wijxixj+ n X j=1 θixi, (9) 式 (7) と式 (8) で定義される状態変化規則に従ってネットワークを動作させ たとき式 (9) で定義されるエネルギー関数が必ず減少することを示した。 このことを確かめるために、ネットワークの状態が変化したときにエネル ギー関数がどのように変化するかを調べてみる。エネルギー関数を k 番目の 1http://dope.caltech.edu/ユニットに関する項とそれ以外の項に分けて、変形すると E = −1 2 n X i6=k n X j6=k wijxixj+ n X j6=k θixi −1 2xk n X j wkjxj−1 2xk X i wikxi+ θkxk (10) いま、ある時刻 t から t+1 の間に k 番目のユニットの出力が xk(t) → xk(t + 1) (11) に変化したものとする。このとき ∆xk = xk(t + 1) − xk(t) は 1 か -1 である。 このような ∆xk の変化による状態変化に伴うエネルギー関数の変化 ∆Ek は、 非同期的変化の仮定により k 番目のユニット以外は変化しないので ∆Ek = − 1 2 Ã n X i=1 wkjxj+ n X i=1 wikxi ! ∆xk+ θk∆xk = − n X j=1 wkj+ wjk 2 xj ∆xk+ θk∆xk (12) となる。wij = wji であることに注意して ∆Ek= − n X j=1 wkjxj− θk ∆xk (13) と表される。右辺のカッコ内は uk であるから ∆Ek = −uk∆xk (14) と書くことができる。式 (7) の状態変化規則から ∆xk > 0 のときは xk が 0 → 1 に変化したことを表しているので uk > 0 であるから ∆Ek < 0 であ る。反対に ∆xk< 0 のときは xkが 1 → 0 に変化したことになるので uk< 0 だから ∆Ek < 0 である。∆xk = 0 のときは ∆Ek = 0 なので、全ての場合 について ∆Ek ≤ 0 (15) となる。
4.2
最適化問題
4.2.1 巡回セールスマン問題巡回セールスマン問題 (Traveling salesman problem:TSP) とは、あるセー ルスマンが、いくつかの都市を順番に一度ずつ訪問し、最後に出発点に戻っ
て来るときに最短の距離で各都市を訪問するための順路を決定する問題であ る。訪問すべき都市の数を N とすると、すべての組合せ数は2NN ! になるので 訪問すべき都市数が増加すると極端に難しい問題となる。 いま A,B,C,D,E の 5 都市を訪問する TSP を考える。まず都市の数の 2 乗 25 個のニューロンを用意する。行方向に都市、列方向に訪問順序をとると すれば、のような表は BACED の順序で都市を訪問することを表している。 訪問順序 都市 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 X 行 i 列のニューロンの出力を xXi と表し、都市 X と 都市 Y との距離を dXY と表すことにすると、 1. 同じ都市を２度訪問しない条件 (同一行に 1 は一つしかない) X X X i X j6=i xXixXj= 0 (16) 2. 同時に２都市を訪問できない条件 (同一列に 1 は一つだけ) X i X X X Y 6=X xXixY i= 0 (17) 3. 全ての都市を訪問する条件 (すべての 1 を足し合わせると都市数に一致 する) X X X i xXi= N (18) という条件のもとで、次の目的関数 (経路の総距離にあたる) 1 2 X X X Y 6=X X i dXYxXi(xY,i−1+ xY,i+1) (19) を最小にする問題となる。エネルギー関数は、これらの制約条件のもとで目
的関数を最小にする制約付最小化の問題になる。 E = A 2 X X X i X j6=i xXixXj +B 2 X i X X X Y 6=X xXixY i +C 2 Ã X X X i xXi− N ! +D 2 X X X Y 6=X X i dXYxXi(xY,i−1+ xY,i+1) (20) ホップフィールドは A = B = 500, C = 200, D = 500, N = 15 として計算し ている。 E = −1 2 X Xi X Y j wXi,Y jxXixY j+ X Xi θXixXi (21) と比較すれば、 wXi,Y j= −AδXY (1 − δij) − Bδij(1 − δXY) −C − DdXY(δj,i+1+ δj,i−1) θXi= −CN (22) となる。ここで δij はクロネッカーのデルタ δij= ( 1, if i = j, 0, if i 6= j (23) である。実際に programing するときには u.i dt = − ui τ + X j=1 nwijxj− θi (24) を十分に小さい ∆ui, ∆t で近似して ∆ui = −ui τ + X j=1 nwijxj− θi ∆ (25) という近似差分を用いて ui を ui(t + 1) = ui(t) + ∆ui (26) の漸化式で更新すればよい。 4.2.2 連想記憶 ホップフィールドは彼のモデルが連想記憶に適用できることを示しました。 ネットワークが記名すべきパターンベクトルを 0, 1 ではなく −1, 1 をとるも
のとする2。ネットワークに記憶させたいパターン数を P 個、s 番目のパター ンを xs= (xs1, xs2, . . . , xsn) (s = 1, 2, . . . , P ) とする。パターン s を記憶する とは、そのパターンに対するエネルギー関数を最小化することに相当する。 しきい値を 0 としたときパターン xs に関するエネルギー関数 Es= − 1 2 n X i=1 n X j=1 ws ijxsixsj (27) を最小化するもっとも簡単な方法は、Es が x2ix2 j に依存するように wsij を 設定するばよい3。wsij = xsixsj とすれば Es= − 1 2 n X i=1 n X j=1 wsijxsixsj= − 1 2 n X i=1 n X j=1 (xsi)2 ¡ xsj ¢2 (28) となる (相関行列)。 すべてのパターンについての結合係数は、 wij= P X s=1 ws ij= P X s=1 xs ixsj (29) によって近似的に求めるめることができる。記憶すべきパターンが似ていた り、パターンベクトルの次元数 n に対してパターン数 P の数が多すぎると 正しき記憶できないことがある。このパターン間の相互干渉のことをクロス トークという。ホップフィールドは記憶できるパターン数はユニット数の 15 % 程度であることを示した。 相関行列を用いてホップフィールドネットの結合強度を決定する方法に対 し、一般化逆行列 generalized inverse matrix の概念を導入し、クロストーク を生じさせないようパターンを直交化して記憶する方法が提案されている。一 般化逆行列にはいくつかの定義があるが、ムーア–ペンローズ Moore–Penrose の定義を用いることにすれば、 Z+=³ZTZ´−1ZT (30) 記名するパターンを£ξ1, ξ2, . . . , ξp¤のように並べてできる N × P 行列を X としたとき W は一般化逆行列を用いて以下のように求められる。 W = XX+= X ³ XTX ´−1 XT (31) なおネットワークの状態変化を行なうには、W を結合強度行列として 7 を 用いればよい。 20, 1 の値をとる n 次元ベクトルは w ij= p X s=1 (2xs i− 1) 2xsj− 1 にすればよい。 3x iは -1 か 1 だが、x2i は常に正
5
結合強度の求め方
ホップフィールドネットの結合強度をエネルギー関数から求める方法。こ の方法は与えられた問題が最適化問題に置き換えられるときに有効で、最小 化する目的関数とネットワークのエネルギー関数を比較することで結合強度 を求める。 説明を簡単にするために、ホップフィールドネットに与えられたアナログ 値を 4 ビットのディジタル値に変換する A/D 変換問題を考える。ネットワー クは 4 ユニットで構成され、それらの状態 x0x1x2x3は変換後のディジタル 値 (0 or 1) を表すものとする。また、変換するアナログ値はネットワークの 外部入力として提示される。このようなネットワークが A/D 変換器として 機能を持つためには、入力されるアナログ値 a とすると、以下のエネルギー 関数を最小化すればよい。 E = 1 2 Ã a − 3 X i=0 xi2i !2 + 1 2 3 X i=0 22ixi(1 − xi) = 1 2 3 X i=0 3 X j6=i=0 ¡ −2i+j¢x ixj− 3 X i=0 ¡ −22i−1+ 2ia¢x i+ 1 2 a 2 (32) ここで 3 X j6=i=0 は 0 から 3 までで i に等しくない添字 j に関して加え合わせる ことを意味する。wij = 0 で外部入力 Ii 考慮したネットワークのエネルギー 関数は E = 1 2 3 X i=0 3 X j6=i=0 wijxixj− 3 X i=0 xiIi (33) 式 (32) と式 (33) とを比較すると wij = −2(i+j) (i 6= j) (34) Ii = −2(2i−1)+ 2ia (35) 与えれたエネルギー関数がリアプノフ関数 Lyapunov function の条件を満 たすように、エネルギー関数から直接的にネットワークダイナミックスを求 める方法もある。これは、まず式 (32) の時間微分を求めて dE dt = − 3 X i=0 dxi dt 3 X j6=i=0 −2(i+j)x j− 2(2i−1)+ 2ia (36) ネットワークのエネルギーが時間とともに減少するためには dEdt ≤ 0 の関係 が常に満たされればよい。このためには、以下に示すようにdui dt を式 (36) の[ ] 内の式に等しくすればよい dui dt = 3 X j6=i=0 −2(i+j)x j− 2(2i−1)+ 2ia (i = 0, 1, . . . , 3) (37) xi= f (ui) (38) このとき dE dt = − 3 X i=0 dxi dt dui dt = − 3 X i=0 f0(u i) µ dui dt ¶2 (39) となり f (ui) を単調増加関数とすれば dEdt < 0 が満たされることがわかる。 この結果は先の式と一致する。
文献
甘利俊一 (1978). 神経回路網の数理. 東京: 産業図書. 中野馨 (1979). アソシアトロン —連想記憶のモデルと知的情報処理. 東京: 昭晃堂.Hopfield, J. J. & Tank, D. W. (1985). Neural computation of decisions in optimization problems. Biological Cybernetics, 52, 141–152.
