混沌系工学特論 #1

情報科学研究科 井上純一
URL : http://chaosweb.complex.eng.hokudai.ac.jp/~j_inoue/

平成17年10月17日 第1回講義

確率を用いた柔らかな情報処理
http://chaosweb.complex.eng.hokudai.ac.jp/~j_inoue/
統計力学の方法に基づくアルゴリズムの構築と性能評価

単位 : 神経細胞
ネットワーク : 脳

単位 : 画素
ネットワーク : デジタル画像

単位 : スピン
ネットワーク : 磁石

確率的にふるまう要素がネットワークをなして全体が情報処理系を形成している
そのような題材としては・・・

ニューラルネット（連想記憶、学習）、画像修復 / 誤り訂正符号、最適化問題、スペクトル拡散通信、ゲーム理論、植物ネットワーク、etc….

共通する数理構造+J

エネルギー関数E = −∑ J ij Si S jSi+J

強磁性体+J+J<ij >+J
結合が符号も含めて空間的にランダム

スピングラス+J

スピングラスフラストレーション+J
最適なスピン配置が一意に決まらない-J

スピン（小磁石）の「ガラス」

エネルギー関数の多谷構造、熱平衡状態への緩和が遅い、空間的なスピンの「凍結」
多くの特徴的な性質
その解析手法は情報科学をはじめとする様々な問題に用いられつつある

情報統計力学

組み合わせ最適化問題
2分割問題を例に{a , a ,....., a ,..., a } = {1.5, 7.5,10,..., 2.3,....,19}
12j

N

各アイテムをアイテム価値の総和が等しくなるように2つのグループに分けるA2

A1
次のエネルギー関数を最小化 :エネルギー関数が最小となるようにN

E = ∑ aj − ∑ aj = ∑ ajsja j ∈ A1a j ∈ A2j =1s j ∈ {−1,1}を割り当てる

アイテム数の増加とともに解候補が組み合わせ論的に増大する

4準位エネルギーを持つ2体系の最適化
E ( s1 , s2 ) = − Js1s2 − h1s1 − h2 s2

最小エネルギー状態は自明で(1,1)ε1 = E (1,1) = − J − h1 − h2
ε 2 = E (1, −1) = J − h1 + h2
ε 3 = E (−1,1) = J + h1 − h2
ε 4 = E (−1, −1) = − J + h1 + h2
J = 1.0, h1 = 0.5, h2 = 0.1と選ぶとε1 < ε 4 < ε 2 < ε 3エネルギー4準位

状態はたったの4通り

ノイズを利用したアルゴリズム
E = − Js1s2 − h1s1 − h2 s2

ノイズを利用したアルゴリズム(1) 各時刻で任意にs1 , s2の1つを選び、その符号を変える。
→ →'この前後の状態を s , s

エネルギーが増加するプロセスもある確率で許すと書く。
→'→（2） (1)の前後でのエネルギー差 : ΔE = E ( s ) − E ( s ) を計算し、ΔE < 0ならば新しい状態を採用

ΔE > 0でも確率

ΔEe −ΔE / T で新しい状態を採用(3) (1)(2)を繰り返す

P( s1 , s2 ) の時間発展を調べてみる⇒ 定常状態が存在するか ? 存在するならどのような分布か ?

アンサンブルという考え方
一つのシステムの動きを追うのではなく、同じエネルギー関数をもつ複数のシステム（アンサンブル）の振る舞いを調べる
N個のシステムの中の↑↑の割合で↑↑の存在確率を定める

システム1 : ↑↑ ↑↑ ↑↓ ↓↓ ↓↑ ↑↑ ↓↑ ↑↑システム2 : ↑↑ ↓↑ ↑↓ ↓↓ ↓↑ ↓↑ ↓↑ ↑↑…………………………………………………….
システムN : ↓↑ ↑↑ ↑↓ ↑↓ ↓↑ ↑↑ ↓↑ ↑↑時間の進む向き
各状態の存在確率をこれで評価する

P1 = P(1,1) =アンサンブルの中で(1,1)をとるシステムの数アンサンブルを構成するシステムの総数

計算機シミュレーションで感じをつかむ↑↑をとる確率N = 10000, T = 1得られる定常確率はエネルギー準位

ε1 < ε 4 < ε 2 < ε 3 を反映している↓↓をとる確率定常分布↑↓をとる確率↓↑をとる確率e − E ( s1 , s2 ) / TP( s1 , s2 ) =z
導出は講義ノート参照

いくつかのノイズレベルでの発展と定常状態最適化問題の立場からはP(uu ) = P1 = 1となればOKT = 0 に固定してアルゴリズムを動作させたらどうか ?

e − E ( s1 , s2 ) / T
P ( s1 , s2 ) =Z

ノイズがほとんどゼロのアルゴリズム予想される平衡分布
食い違いが出るアルゴリズムから得られる結果アルゴリズムから得られる結果食い違いが出る予想される平衡分布(-1,-1)から（1,1)に移るには必ず(-1.1)を経由しなければならない。
(-1,-1)の滞在時間 :1/ e−2( J − h2 ) / T=e180

事実上、(-1.-1)に落ち込んだら最後、脱出することはできないノイズレベルと初期状態依存性

T = 0.01
平衡状態が初期状態に依存しない（エルゴード性）

T = 1.0

状態間の遷移確率がほとんどゼロのため初期状態に依存した平衡状態が得られる（十分な時間後には平衡状態に到達）

ノイズを各ノイズレベルでの平衡状態を保ちつつ徐々にゼロに制御すれば、初期状態の設定は直前に生成された平衡分布のそれを用いることになるので、うまくいくのではないか？
エネルギー準位を反映した

P1 > P4 > P2 > P3

は各ノイズレベルで保たれるアニーリングの効果
T ∼ 1/ t
はやくノイズレベルを落としすぎて、ノイズセロの場合と同じ問題が生じている

順調に望ましい定常状態に向かっているT ∼ 1/ log t

最適なノイズのスケジューリング （導出は講義ノート) :Topt ∼ 1/ log t
これよりもゆっくりとノイズを下げれば、十分な時間の後、確率1で最小エネルギー状態が求まる

平衡状態と物理量の期待値[ノイズを用いたアルゴリズム]を動作させることで、平衡分布 ：P( s1 , s2 ) =e→

( Js1s2 + h1s1 + h2 s2 ) / T∑ ∑e( Js1s2 + h1s1 + h2 s2 ) / T

s1 =±1 s2 =±1=e−E ( s ) /T→− E ( s ) /Te∑→s =±1→E ( s ) = − Js1s2 − h1s2 − h2 s2

ボルツマン分布が得られる。 1つのシステムの長時間平均はエルゴード性が満たされる条件下で上記平衡分布でのアンサンブル平均で置き換えることができる

A = limτ →∞1 τA = ∑ ∑ A( s , s ) P( s , s ) = A∑
τt =0ts1 =±1 s2 =±11212

自由エネルギーと期待値分配関数と呼ばれる平衡分布の規格化因子⎛β ( Js1s2 + h1s2 + h2 s2 ) ⎞自由エネルギー ： F = −T log ⎜ ∑ ∑ e⎟⎝ s1 =± s2 =±1⎠
内部エネルギー等はエントロピー∂E =(β F )∂βのように自由エネルギー経由で求めることができる

内部エネルギー

自由エネルギー

詳細は講義ノート