ホップフィールド・ネットワーク

トップページ研究分野と周辺ニューラルネットワーク

米国の物理学者、J.Hopfield(カリフォルニア工科大)が1982年に提唱したニューラルネットワークで、最適化問題に応用出来る事で有名になった。
相互結合型ネットワークで、i番目の細胞からj番目の細胞への結合係数wjiと、j番目の細胞からi番目の細胞への結合係数wijは常に等しい(対称性。或る細胞間の双方向の結合係数が等しい)。
また、自己結合(wii等、或る細胞の出力がその細胞への入力となる結合)係数は0という条件を持ち、これら2つは連想記憶モデル(アソシアトロン)と同じとなる。
連想記憶モデルと異なるのは、状態の更新が非同期である事と、ネットワークのエネルギーという概念を導入している点だ。

非同期型ネットワーク

連想記憶モデル(アソシアトロン)では、全ての細胞が同時一斉に、其々の他の細胞からの入力刺激の総和を計算し、状態更新した。これを同期型ネットワークという。
これに対し、或る時刻には一つの細胞だけが他の細胞からの入力刺激の総和に基づき状態更新(出力値の変化。出力値が結果として同じ場合も含む)を行なうものを非同期型ネットワークという。
或る時刻に一つの細胞だけが状態更新し、その間、他の細胞の出力値はそのままとなる。
ホップフィールド・ネットワークでは、図のようにその時々にランダムに選ばれた細胞が状態更新する事を繰り返していく(灰色が状態更新する細胞の例)。

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

ホップフィールド・ネットワークでは、ある時刻に於ける様々な細胞の出力値に基づき、以下の量を定義している。
Eと表記されているのは、Hopfieldが物理学的なエネルギーに似ていると考えたためで、これはエネルギー関数と呼ばれている。

ここでNは細胞数、xiはi番目の細胞の出力、wijはj番目の細胞からi番目の細胞への結合係数、θiは細胞iの閾値(内部状態から引く数)を表す。第1項はΣ記号が二つ並んでいるため、ちょっと複雑に見えるが、N=3として、展開してみる。

結局、第1項は自己同士も含む、2つの細胞の全ての順列に対し、その結合係数を掛けたものの総和に-1/2を掛けている。
出力値は1か-1なので、同じ出力値を持つ細胞間の結合係数が大きいほど、第1項は小さく(-1/2を掛けたので)なる事を示している。 そして、このエネルギー関数の値は、状態変化を繰り返すに従って、小さくなっていく事が分かっている。この性質を利用して、準最適解を求める。

エネルギーがマイナス方向にしか変化しない理由

或る時刻に状態変化(出力値の変化、但し変化しない場合も含む)する細胞の番号をkとする。上記のエネルギーの定義式から、kに関する項だけを抜いてみる。

Σ記号の下に例えばj≠kとあれば、k番目だけを抜いた総和を取る事になる。従って、このように展開出来る。結果的にkが関係する項は、最後の式の第2項、第3項にまとめられる。
ホップフィールド・ネットワークでは、自己結合がゼロ(Wkk=0)である事を考慮すると、以下の等式(1)が成り立ち、さらに、結合係数の対称性(Wij=Wji)から、等式(2)が成り立つ。

エネルギー関数の第1項(係数は除く)からkに関する項を抜いた式は、結局以下のようになる。

エネルギー関数全体で、kの部分を分離した式は以下のようになる(第3項、4項がkに関する項)。

k番目の細胞の出力が変化した場合のエネルギーの変化(⊿E)は、kに係る項だけについて、時刻tと時刻t+1で、値がどう変わるかを見ればよい。kに係る項に括弧付で時間を付す。
他の細胞xjの出力は時刻tのものになる。Ukはkの内部状態を示す。

ここで、内部状態Ukが正の場合は、t+1時刻のkの出力は1になる。状態が変化したと仮定するとt時刻のkの出力は-1だったので、⊿E=-2×内部状態(正の値)となる。
内部状態Ukが負の場合は、t+1時刻のkの出力は-1になる。状態が変化したと仮定するとt時刻のkの出力は1だったので、⊿E=2×内部状態(負の値)となる。
kの状態が変化しない場合は、⊿Eは0となる。結局、エネルギーは減るか、そのままにしかならない。

巡回セールスマン問題(TSP)に応用する場合の細胞の構成

巡回セールスマン問題とは、N個の都市を全て一回ずつ訪問する場合の最短経路を求める問題。問題自体は非常に簡単だが、全ての順列の長さを比べないと最適解が分からないNP困難と呼ばれるタイプの難問だ。都市数が30ぐらいになると、コンピュータを使っても全ての順列を調べるのは何万年もかかる。
ホップフィールド・ネットワークで、この問題を解く(最適解でなくても、それに近い準最適解を求める)場合の細胞の構成は図のようになる。
都市数4の場合で、細胞を縦横4つ、計16個配置する。細胞の番号は二つの数字を組みあわせたものにする。左の数字が都市の番号(名前)、右の数字が訪問順序だ。
この縦横の並びは結合係数行列ではなく、全て細胞である事に注意する必要がある。各細胞には、普通に通し番号を付けてもいいのだが、計算の利便のために二つの数字を組み合わせたものにする。例えば、細胞番号2_3は、「2番目の都市が3番目に訪問される」可能性を表している。
細胞の状態は1又は0で、これは出力値だ。1は真実、0は偽を表す。細胞1_2の出力が1ならば、「1番目の都市は2番目に訪問される」事が正しい事を示す。
右図の例では、都市番号で「2→1→4→3」の順で訪問する経路を示している。

TSPの制約条件の関数化

巡回セールスマン問題では、以下の制約条件がある。
・同じ都市を複数回訪問してはいけない(1)
・同じ日に複数の都市は訪問できない(2)(一人で回るという前提。同時を一日単位でここでは数える)
・全ての都市を訪問しなければならない(3)
図の左は都市1を2回訪問した例、真ん中は2日目に訪問した都市が1、3の複数ある例、右は都市2を訪問しなかった例で、いずれも制約条件外の誤ったルートとなる。

これらの制約条件を、計算に乗せるために関数化する必要がある。
まず、(1)の条件については、以下のような関数を考える。Nは都市数(=日数)、tは都市番号、oとo2は日付となる。Sはその添え字の番号を持つ都市(細胞)の出力となる。
Σが3つ並ぶが、都市tについて(左のΣ)、その訪問日付がoの細胞と(真ん中のΣ)、その都市のoでない訪問日付の細胞全てについて(右のΣ)、同時に出力しているかを調べて値を足している。
同時に出力ならば、一つの都市を複数訪問する事になり、双方の出力値の積は1×1=1となる。これを全ての都市の全ての訪問日付について調べる。制約条件(1)を満たすためにはE(1)は0でなければならない。E(1)の値が大きいほど、違反(一都市複数回訪問)件数が多い事になる。

次に(2)の条件については、以下の関数を用意する。oは訪問日付、tとt2は都市番号となる。訪問日付oについて(左のΣ)、その日付で行く都市tの細胞と(真ん中のΣ)、その訪問日付のtでない都市の細胞全てについて(右のΣ)、同時に出力しているかを調べて値を足している。
同時に出力ならば、同日に複数の都市を訪問する事になり、双方の出力値の積は1×1=1となる。これを全ての訪問日付の全ての都市について調べる。制約条件(2)を満たすためにはE(2)は0でなければならない。E(2)の値が大きいほど、違反(同日複数都市訪問)件数が多い事になる。

(3)の条件については、以下の関数を用意する。全ての都市について(左のΣ)、全ての訪問日付に(右のΣ)訪問されているか(St_oが1)を調べる。制約条件を満たせば、一日に一つの都市しか訪問されないので、この二重Σの総和はNに等しくなるはずだ。
従って、総和からNを引いたものの二乗を取れば、総和が多過ぎても、少な過ぎても大きな値となる。E(3)も=0で制約条件を満たす事になる。

TSPの経路長評価関数の作成

制約条件を満たしながら、最も短い訪問経路を捜すのが、巡回セールスマン問題(TSP)の目的だ。
経路長を評価する関数として、以下を用意する(E(4)とする)。Dはその添え字にある二つの都市間の距離(各都市のx座標、y座標等からピタゴラスの定理で求める)となる。
全ての都市について(左のΣ)、その都市とは別の全ての都市との関係について(真ん中のΣ)、全ての日付において(右のΣ)以下を調べる。
或る日付(o)において、或る都市(t)が訪問されている場合(St_o=1)に、或る別の都市(t2)がその前日又は次の日に訪問されているか(o=Nの場合、o+1は1、o=1の場合、o-1はNとして計算する)。
もし訪問されていれば、()の中の出力値は1又は2(2の場合はt2に2回訪問しているが)となり、St_oが訪問されている場合はその積は1又は2となり、その二都市間の距離を掛けたものを、総和に加算していく。
経路長は、或る日付に訪問された都市から、次(又は前)の日に訪問された都市間の距離の総和なので、このような式になる。

TSPに応用する場合のエネルギー関数の作成

3つの制約条件の関数と、経路長を評価する関数を足して、TSPに応用する場合のエネルギー関数とする。
制約条件に関する項は0になる必要があるが、とりあえず、経路長と足して、小さいものほど良い経路と考える。A/2等の係数は各項の重み付けをする正数となる。
E(1)~E(4)の和は、ホップフィールド・ネットワークの一般的なエネルギー関数(上の式)の形に変形する必要がある。

ここで、上の式のXi(又はXj)に該当するものは、St_oになる(TSP用の細胞では通し番号がt_oだった)。従って、TSP用の細胞の通し番号を調べるΣは二重になり、tに関するΣとoに関するΣが並ぶ。
上の式のXiとXjの積に該当するところは、St_oとSt2_o2(t=t2、o=o2の場合も含めて)の積となる。

エネルギー関数第1項(E(1))と第2項(E(2))の変形

第1項の変形は以下のようになる。エネルギー関数の式に合わせるには、tに対するΣ、oに対するΣ、t2に対するΣ、o2に対するΣの4重Σの形にし、出力値はxixjに対応させて、St_o×St2_o2の形にする必要がある。
上段の最初の展開で、t2に関するΣを追加している。その代わりに、δt,t2という記号が入っている。このδはクロネッカーのデルタと呼ばれ、δx,yという二つの添え字を持ち、x=yのとき1、xとyが等しくないとき0を取る。
また、t2に関するΣを追加したのに伴い、St_oとSt_o2の積が、St_oとSt2_o2の積に置き換わっている。
元々E(1)は、同じ都市について、複数の違う日付の訪問があるかを調べるものだった。そこに、Σを4重にするために、必要のない違う都市(t2)のΣを追加したため、Σの内部にクロネッカーのδを置き、tとt2が一致しない場合は加算される値が0となるようにして、元の式と一致させている。
St_oとSt2_o2の積に替えても、tとt2が異なる場合は0になるので、t=t2のときしか加算されず、結果的に元の式と同じ計算をしている事になる。
次の展開(二行目)では、o2に関するΣでo2がoと等しくない、という条件を解除している。その代わり、Σの内部に(1-δo,o2)を追加している。
これも、o=o2のときに0、それ以外のときに1となる係数になるので、Σの条件でo=o2を除外するのと同じ事になる。
最後に、エネルギー関数のWに相当する数が、TSP用のエネルギー関数ではどうなるかを求めている。xixjに相当するのがSt_oSt2_o2の部分で、二重Σに相当する部分が四重Σなので、そこを抜き、係数(元の関数では-1/2)を調整して、下のような値になっている。

E(2)に関する変形も、同様の方法で行なわれる。E(1)に対する変形と同じ理屈で展開されている。

エネルギー関数第3項(E(3))の変形

E(3)に関する変形は、最初の展開は(a-b)の2乗の公式にそのまま当てはめている。
次の変形の第1項は、※印の式の展開を利用している。第2項、第3項は、そのまま係数C/2を掛けただけ。
E(3)からは、元のエネルギー関数のxixjの係数の他に、第2項からθiに該当する係数が取れる。第3項は、正の定数なので、最小化を目的とする関数に於いては無視出来る。

エネルギー関数第4項(E(4))の変形

E(4)の最初の行の変形は、o2に関するΣを追加している。これに伴いΣの内部には、St2_o2を追加している。
また、t2の都市に行く日付がtの都市に行く日付の一日前か一日後のときに出力の掛け合わせを行なうので、o2がo+1又はo-1のときにSt_oとSt2_o2の出力を掛けるように変形してある。
なお、係数Dと紛らわしいので、距離を示すDは小文字で表記している。
次の行の変形は、t2のΣのt2がtと等しくない場合は除外する条件を解除している。これに伴い、Σの内部には、tとt2が等しい場合は加算しないための(1-δt,t2)を追加している。

TSPに応用するエネルギー関数の実装

結局、TSPに応用する場合のエネルギー関数は以下のようになる。訪問都市と日付の組を表す各細胞間の結合係数は、都市間の距離に基づいて決まってくる。
A等の係数は適当に決める。St_oの初期の出力状態はランダムに決め、一つずつランダムに選んだ細胞の状態を変化させるていくと、やがてエネルギーがそれ以上減少しない定常状態になる。
その時に出力している細胞群が、最短経路探索問題の準最適解を表現している。