Document

パターン認識と学習のアルゴリズム
上坂吉則
尾関和彦
文一総合出版
宮崎大輔2003年9月19日（金）PBVセミナー
9 ホップフィールドマシン
決定論的最小値探索機械
巡回セールスマン問題
組み合わせ的最適化問題
都市
距離d(A,B)
円順列(m-1)!/2
距離d(E,A)
都市
都市
都市
距離d(D,E)
距離d(B,C)
距離d(C,D)
都市
最小値探索
• 目的関数F(x)が最小となるxを求めたい
• 目的関数FをエネルギーEとみなして解く
（Fは離散的、Eは連続的）
• 力学系 dxi  (1  x 2 ) E
(i  1,, n)
dt
i
x  ( x1 ,, xn )
xi
• エネルギーは時間経過とともに減少する dE  0
dt
• xは漸近安定であるとする lim x(t )  x 
つまりx*に限りなく近づく t 
• この方法は、解に限りなく近づくが、解には一致しない
→アルゴリズム上、解に十分近づいたら解に一致させる
• アルゴリズムは、適当な初期値から、力学系（微分方程式）を
Euler法やRunge-Kutta法などでxを動かしていく
dx
つまり、
x (t   )  x (t )   i
i
i
dt
F ( x, y)  axy  bx  cy  d
( x, y  1)
適用例１
E ( x, y)  axy  bx  cy  d
(  x, y  )
+1
+1
-1
-1
適用例２
巡回ルートの長さ
• 訪れる都市の順序  (1),, (m), (1)
• 総距離 L( )  d ( (1), (2))    d ( (m 1), (m))  d ( (m), (1))   d ( (i), (i  1))
m
i 1
m
L( )  d ( (1), (m))  d ( (2), (1))    d ( (m), (m  1))   d ( (i), (i  1))
i 1
d ( (i), (i  1))   d ( X , Y ) x( X , i) x(Y , i  1)
X
Y
X
Y
d ( (i), (i  1))   d ( X , Y ) x( X , i) x(Y , i  1)
• 総距離
1  (i)  Xのとき
x( X , i )  
0 その他のとき
2L( )   d ( X , Y ) x( X , i){x(Y , i  1)  x(Y , i 1)}
i
X
Y
巡回セールスマン問題の目的関数
• i番目に訪れる都市は１つでなければならない
＝x(A,i),x(B,i),…の内ちょうど１つが1で他がすべて0
• ある都市には一回しか訪れることができない
＝x(X,1),…,x(X,m)の内ちょうど１つが1で他がすべて0
  x( X , i) x(Y , i)    x( X , i) x( X , j)  0
i
X Y ( X )
X
i
j ( i )
2


  x( X , i)  m   0
 X i

• 目的関数
F ( x)  A
i
 x( X , i) x(Y , i)  B  x( X , i) x( X , j)
X Y ( X )
X
i
j ( i )
2


C   x( X , i )  m 
 X i

 d ( X , Y ) x( X , i ){x(Y , i  1)  x(Y , i  1)}
i
X
Y
総距離
巡回セールス問題の実験結果
ニューラルネットによる最小値探索
• 以上のアルゴリズムをニューラルネットでも実現でき
る
– 詳細は省略
10 アニーリングとボルツマンマシン
確率論的最小値探索機械
シミュレーテッド・アニーリング
• アニーリング（焼きなまし）
– 物質を高温に熱し、その後徐々に温度を下げていくとエネ
ルギー順位の低い安定な素材が得られることがある
• その現象をシミュレート
– 関数の最小値を求める
最適分布
• 以下のような分布q0を最適分布という
– 最小値が1個の場合
• q0(x)=1
xが最小値のとき
• q0(x)=0
xが最小値じゃないとき
– 最小値が2個(x1,x2)の場合
• q0(x1)=0.5
• q0(x2)=0.5
• q0(x)=0
xがx1でもx2でもないとき
– 最小値がn個の場合
• 上記の例から大体想像できるっしょ？
• 最適分布が与えられれば最小値を100%求めうる
ギブス分布（ボルツマン分布）
• ギブス分布（ボルツマン分布）
1
1
qT ( x)  exp(  F ( x))
Z
T
• Zは定数[xでの総和を1にする正規化定数]
• Tは定数[温度]
• 温度を低くするとギブス分布は最適分布に近づく
lim qT  q0
T 0
摂動行列
•
以下を満たすPを摂動行列
と言う
– P(x,y): Pのx行y列成分
1. x, y : P( x, y)  0
2. x : P( x, x)  0
P( x, y)  1
3. x : 
y
4. x, y : P( x, y)  P( y, x)
s
5. x, y s : P ( x, y)  0
•
例
1.
2.
3.
4.
5.
全ての要素が0以上
対角成分が0
各行は0+1/3+1/3+1/3=1
対称
 0 1 3 1 3 1 3
1 3 0 1 3 1 3

P
1 3 1 3 0 1 3


1
3
1
3
1
3
0


1 3
2 9
2
P 
2 9

2 9
29
13
29
29
29
29
13
29
2 9
2 9
0
2 9

1 3
受理行列
• x行y列成分が以下のAT(x,y)である行列ATを受理行
列という

  F ( y )  F ( x)  
AT ( x, y)  min1, exp 
 
T
 
 

ギブス行列
• 摂動行列の成分P(x,y)と受理行列の成分AT(x,y)を
使って以下のGT(x,y)を成分とする行列GTをギブス
行列という
 P( x, y ) AT ( x, y )

GT ( x, y )  1 
P( x, y ) AT ( x, y )

 y (  x )
x≠yのとき[対角成分以外]
x=yのとき [対角成分]
マルコフ連鎖
• ギブス行列の要素GT(x,y)は0以上1以下であり、各
行の総和を取ると1になる
→ギブス行列の要素を確率とみなそう
• 確率分布Pを以下のように定める
P( X (t  1)  y | X (t )  x)  GT ( x, y)
“システムが時刻tで状態xにあるときに、時刻t+1で状
態yに推移する条件付き確率がGT(x,y)である”
• このように、システムのある時刻の状態の確率分布
が1時刻前の状態で決まり、それ以前にどんな状態
にあったかには無関係だという性質をもつ確率変数
列X(0),X(1),…,X(t),…をマルコフ連鎖という
シミュレーテッド・アニーリングのからくり
• 以下のベクトルpを状態確率分布という
– 時刻tにおいて状態が
 x1である確率

x2である確率

p (t ) 



 xmである確率






t 1
• 時刻t+1の状態確率分布は p(t  1)  GT p(t )  GT p(0)
• 任意の状態確率分布p(0)は時刻の経過とともにギブ
m
lim
G
p(0)  qT
T
ス分布に近づく
m 
• さらに温度を低くすれば最適分布に近づく
lim lim GTm p(0)  q0
T 0 m 
一様でないアニーリング
• 温度Tが小さくなると局所解に留まりやすくなる
→温度は時間経過とともに少しずつ減らしていく
→（時間的に）一様でないマルコフ連鎖
• この場合でも、状態確率分布は時間経過とともに最
適分布に近づくことが示せる
lim p (t )  q0
t 
巡回セールスマン問題
ボルツマンマシン
• 以上のアニーリング機械をニューラルネットで実現し
たものをボルツマンマシンという
– 詳細は省略
次回予告
宮崎の次回の発表
• 次のうちのどれか
– ニューメリカルレシピ
– コンピュータビジョン –技術評論と将来展望– その他（テンソル、ウェーブレット、レベルセット、ガボール
変換、MCMC、サポートベクターマシン、etc）
宮崎の発表の目的
• 基盤となる知識を提供する
– 「その知識が一体何の役に立つの？」と思うかもしれない
– コンピュータビジョンの分野に実際にどのように利用されて
いるかは、他の人にゆずる or CVLセミナーにゆずる
– CVLセミナーと同じような内容なら意味なし
• CVLセミナーは応用中心：論文紹介がメイン
• CVLセミナーだけで十分、勉強会は不要って事になる
• 技術やアルゴリズムの紹介だけをする
–
–
–
–
広く浅く
自分の研究に必要な技術は自分で勉強したほうがいい
他の人の発表を聞く時に役立てばそれでいい
独学で勉強する際の手助けとなれればそれでいい
(c) Daisuke Miyazaki 2003
All rights reserved.
http://www.cvl.iis.u-tokyo.ac.jp/

Download Report