混沌系工学特論 #2

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

平成17年10月24日 第2回講義

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

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

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

確率的にふるまう要素がネットワークをなして全体が情報処理系を形成している

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

今回、次回はこの関係に着目していく

そのような題材としては・・・

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

デジタルデータの転送と復元※ 古文書/文献の復元等では時間経過による劣化を伝送路で表すものとする

デジタル画像劣化されたデジタル画像

確率モデルで表現

{τ }

伝送路符号
ビット列
011000101001000001001{ξ }復元されたデジタル画像

ノイズの乗ったビット列

復号

{σ }

100111001010001001001

復号
011000110010001001001
復元されたビット列

デジタル画像の情報表現
0001
0101
1110

デジタル2値画像

白→0
黒→1として各画像を符号

テキストファイル (inoue.pbm) の中身

変換

ξi → 2ξi − 1

により、白→－1、黒→＋1で表現する

P1

２値画像のタグ200 200
11111111010010101
11111111111111111
10101001111111111
・・・・・・・・・・・・・・・・・・・・・・・・・・・

画像のサイズ（２００×２００）

画像データ本体

画像の「小磁石」による表現

劣化過程の確率モデル化
1-p+1+12元対称通信路のグラフ表現

pp-1

1-p-1

条件つき確率表現

P({τ } | {ξ }) = P(τ1 ,τ 2 ,...,τ N | ξ1 , ξ2 ,..., ξ N )劣化されたピクセル列

原画像のピクセル列

2元対称通信路の条件つき確率表現

各ピクセルの劣化過程が独立ならばP (τ i = ξi | ξi ) = e βτ 2cosh ( βτ ) = 1 − pexp ( βττ iξi )P({τ } | {ξ }) = ∏2cosh( βτ )iP (τ i = −ξi | ξi ) = e − βτ 2cosh ( βτ ) = p

劣化過程の確率モデル

12⎛ 1− p ⎞⎟p⎝⎠βτ = log ⎜ベイズの公式と事後確率
尤度（ゆうど）
事後確率分布P ({σ } | {τ }) =原画像のピクセル列の推定値

事前確率分布P({τ } | {σ }) P ({σ } )∑{σ } P({τ } | {σ }) P ({σ })ベイズの公式

尤度は劣化過程の確率モデル
2元対称通信路であることが既知ならば未知な変数を含む

exp ( h τ iσ i )P ({τ } | {σ } ) = ∏2cosh ( h )i
事前分布の選び方は全く任意である

画像データの特徴を生かして適切に選択する必要がある画像データの事前分布と事後確率
強磁性体の確率モデル

P ({σ } ) =(exp J ∑ <ij > σ iσ j

∑σ exp ( J ∑<ij >)σ iσ j)スナップショット

T=1/J=1.15※ どの温度のスナップショットの張り合わせで表現するか？
⇒ どのように J を決めるか？
（この方法は後に説明する）

P ({σ } | {τ } ) =T=1/J=2.15

T=1/J=3.15

ベイズの公式から求まる事後確率

exp(− H eff ), H eff = − J ∑ <ij > σ iσ j − h∑ i τ iσ i∑{σ } exp ( − H eff )画像復元問題のエネルギー関数

ノイズを利用したアルゴリズム
前回の復習

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 ) の時間発展を調べてみる⇒ 定常状態が存在するか ? 存在するならどのような分布か ?

スナップショットの作り方
マルコフ連鎖モンテカルロ法（MCMC法）

E = − J ∑ <ij > σ iσ j エネルギーが増加

ノイズを利用したアルゴリズムの多変数版(1) 各時刻で任意にσi

この前後の状態をするプロセスもある確率で許すを1つを選び、その符号を変える。

σ ,σ ′ と書く。

（2） (1)の前後でのエネルギー差 :ΔE = E (σ ′) − E (σ ) を計算し、 ΔE

ΔE < 0ならば新しい状態を採用

ΔE > 0でも確率

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

P ({σ }) の時間発展を調べてみる
P ({σ } ) =平衡状態では(exp J ∑ <ij > σ iσ j

∑σ exp ( J ∑<ij >)σ iσ j) 1/J=1.15

最大事後確率推定
事後確率エネルギー関数P ({σ } | {τ } ) =exp(− H eff ), H eff = − J ∑ <ij > σ iσ j − h∑ i τ iσ i∑{σ } exp ( − H eff )エネルギー関数最小⇒ シミュレーテッド・アニーリングで最適化

事後確率最大画像復元が最適化問題として定式化される
このパラメータTを温度としたアニーリング

劣化画像データは与えられている{})(P ({σ } ) =∑ exp (T { J ∑ σ σ + h∑ τ σ })exp T −1 J ∑ <ij > σ iσ j + h∑ i τ iσ i−1σ<ij >iji ii※ J および h の決め方は次回。今回は既知とする

アニーリング法による画像復元の実例
エネルギー誤り率

シミュレーテッド・アニーリング
によるエネルギー関数の時間変化

シミュレーテッド・アニーリング
によるビット誤り率の時間変化アニーリング・スケジュール

T (t ) ∼ 3
モンテカルロ・ステップ

原画像

J,h は真の値に固定

tモンテカルロ・ステップ

劣化画像

復元画像

確率モデルのパラメータ推定
事後確率は次のように書けるが・・・{})(P ({σ } ) =∑ exp (T { J ∑ σ σ + h∑ τ σ })exp T −1 J ∑ <ij > σ iσ j + h∑ i τ iσ i−1

σ

<ij >

+1-1

どの J で指定されるスナップショットの張り合わせで画像を表現するのか

未知

この決め方は次回説明する

iji ii1-pp pP p+1-11-p

劣化率 h がどのくらいなのか

用いることのできるのは劣化画像についての情報のみ

未知