Introduction to Soft Computing （第11回目）佐藤裕二講義内容（第4回目） 1. 2. 3. 4. 5. 2値ホップフィールドモデル連想記憶への応用連続値ホップフィールドモデル巡回セールスマン問題への応用シミュレーティッドアニーリングとボルツマンマシン相互結合型ネットワークの学習(1) ホップフィールドモデル • 1982年に、Hopfield（カルフォルニア工科大学）が提案。相互結合型ネットワークの代表例。（図3.1参照） • 第１の特徴は、ユニット間の結合の荷重が対象であること。すなわち、荷重wij = wjiであること。但し、自分自身への結合は存在しない。すなわち、wii = 0が仮定されている。 • 第２の特徴は、各ユニットの状態変化は非同期であり、ある時刻において１つのユニットのみが他のユニットからの入力の重み付き総和としきい値によりユニットの状態を遷移して出力が行われること。相互結合型ネットワークの学習(1) ２値ホップフィールドモデル • 1982年にHopfieldが提案した最初の相互結合型ニューラルネットワークでは、２値のみをとるユニットを仮定。その後、連続値をとるユニットへの拡張がなされた。 • 以下、２値のユニットが相互に結合したモデルを説明する。（別紙参照）２値ホップフィールドモデル連想記憶への応用 • Hopfieldは2値ホップフィールドモデルを連想記憶に適用することを提案．不完全なパターンに対応した状態を初期状態としてネットワークを動作させて，最終的に到達したエネルギー関数の極小点に対応したパターンを想起結果とする． • 連想記憶への適用に関する基本的な考え方（テキスト54, 55頁） • 経験的には，0, 1の2値ホップフィールドモデルの記憶容量は，ユニットの個数の15%程度．従って，100個のユニットからなるネットワークでは，15個以上のパターンを記憶させると，パターンのオーバーラップによる干渉によって誤りが起りやすくなる． • McElieceらは，1987年に，十分大きなnに対して記銘ベクトルを独立にランダムに選べば，{-1, 1}の2値ホップフィールドモデルの記憶容量は，n/(2log2n)で近似されることを示している．連続値ホップフィールドモデル • 1984年にHopfieldは，2値のモデルを拡張して，連続値ホップフィールドモデルを提案． • 連続値ホップフィールドモデルは，2値のモデルと同様にn個のユニットからなり，自分自身への結合はなく，相互の結合は対称であるが，ユニットのの出力xi(t)は区間[0, 1]の任意の連続値をとるように拡張されている．さらに，ユニットiの内部状態ui(t)は，微分方程式に従って変化するものと仮定されている．（テキスト56, 57頁）２値ホップフィールドモデル巡回セールスマン問題 • 巡回セールスマン問題(traveling salesman problem: TSP)とは、ある一人のセールスマンが幾つかの都市を次々に一度ずつ訪問して最後に出発点に戻らなければならないときに、最短の距離で回る順序を決定する問題。都市の数Nの増加に伴って組合せの数N!/2Nは爆発的に増加（例えば、５都市：12通り、10都市： 181440通り）。現在でも都市数の多項式オーダーの解法は発見されていない。 • TSPは、通常のノイマン型計算機では余りにも時間がかかり過ぎて、大規模になるとお手上げの状態であった。 • そのような中、 Hopfieldがホップフィールドモデルを用いて、その解を求めたことがニューロコンピュータ研究を加速した。２値ホップフィールドモデル巡回セールスマン問題 • 巡回セールスマン問題(traveling salesman problem: TSP)への2値ホップフィールドモデルの適用方法（別紙参照）。 • 10都市の巡回セールスマン問題に対して， A=B=500, C=200, D=500, N=15, t=1, m=0.02と設定した結果 → 図3.4 シミュレーティッドアニーリングとボルツマンマシン • ホップフィールドモデルの連想記憶への適用においては，エネルギー関数の極小値の数が記憶可能なメモリの容量に対応していると考えられるので，多数の極小値が存在すうことが幸いしていた．一方，巡回セールスマン問題などの組み合わせ最適化問題を解くためには，局所的最小値に留まることなく大域的最小値に到達することが望まれる．このような問題に対処するため，2値ホップフィールドモデルの動作規則を確率的に拡張したボルツマンマシンが， 1980年代の中頃に，G.E. Hintonらにより提案された．シミュレーティッドアニーリングとボルツマンマシン • ボルツマンマシンでは，はじめは比較的高い温度から出発してネットワークを動作させて，平衡状態に到達してから，平衡状態を崩さないように徐々に温度を下げていくことで，ネットワークを局所的なエネルギー最小の状態に停留させることなく，大域的な最小値に移行させる確率を高めることが期待させる． • このような考えは，金属材料などを加熱して，徐々に温度を下げて冷却して内部の欠陥を取り除くという焼き鈍し（annealing）に類似しているので，シミュレーティッドアニーリング（simulated annealing）と呼ばれる．シミュレーティッドアニーリングのアルゴリズム手順1 温度に対する繰り返し数 t = 0 とする．初期温度 T(0) を十分に高く設定して，初期解を発生させる．手順2 各温度 T(t) に対して，定常状態になるまで，手順3, 4を繰り返す。手順3 現在の解の近傍でランダムに新しい解を生成する．手順4 目的関数値の変化分Δを計算し，Δ< 0 であれば新しい解を採択する．そうでなければ，区間 (0, 1) の一様乱数ξを発生させ， exp(-Δ / T(t)) > ξの確率で新しい解を採択する．手順5 定常状態と判定されれば手順6へ，そうでなければ，手順3 へ戻る．手順6 T(t+1) = ρT(t), 0 < ρ < 1 により，次の温度を求める．手順7 基底状態と判定されれば終了する．そうでなければ，t = t + 1 として手順2に戻る．