交換モンテカルロ法における交換率カルバック距離

交換モンテカルロ法における
交換率とカルバック距離の関係について
永田賢二渡辺澄夫
東京工業大学知能システム科学専攻
東京工業大学精密工学研究所
発表概要
1.
2.
3.
4.
交換モンテカルロ法
交換モンテカルロ法の設計
主定理
考察・まとめ
＜参考文献＞
伊庭幸人他「計算統計Ⅱ マルコフ連鎖モンテカルロ法とその周辺」、岩波書店
１．交換モンテカルロ法[Hukushima,96]
＜MCMC法＞
ある確率分布に法則収束する
サンプル系列を生成するアルゴリズム
1
目標分布： P ( w) 
exp(nH ( w)) ( w)
Z ( n)
( w R d )
交換モンテカルロ法では、以下の同時分布からのサンプリングを考える。
K
tk : k  1,, K：温度パラメータ
P( w1 ,, wK )   P( wk | tk )
k 1
1
P( w | t ) 
exp(ntH ( w)) ( w)
Z (nt)
１．交換モンテカルロ法
＜アルゴリズム＞
以下の2種類の更新を交互に実行する。
１．メトロポリス法やギブスサンプラーなどの従来のMCMC法により、
それぞれの分布 P(wk | tk )からのサンプリングを並列に実行する。
２．上記の操作に加えて、適当なステップごとにサンプル wk と wk 1 を
確率 u  min(1, r ) で交換する。
P( wk 1 | tk ) P( wk | tk 1 )
r
 expn(tk 1  tk )H ( wk 1 )  H ( wk ) 
P( wk | tk ) P( wk 1 | tk 1 )
以後、
u を交換率と呼ぶことにする。
１．交換モンテカルロ法
＜従来のMCMC法＞
P (w)
＜交換モンテカルロ法＞
P( w1 | t1 )
P(w2 | t2 )
P(w3 | t3 )
P(w4 | t4 )
１．交換モンテカルロ法
1
P( w | t ) 
exp(ntH ( w)) ( w)
Z ( n)
u  min(1, r )
r  expn(tk 1  tk )H (wk 1 )  H (wk )
w  x, y R 2
n  1000
t0
H (w)  x 2 y 2
 (w) :標準正規分布
0  t 1
t 1
発表概要
1.
2.
3.
4.
交換モンテカルロ法
交換モンテカルロ法の設計
主定理
考察・まとめ
２．交換モンテカルロ法の設計
＜温度パラメータの設定＞
交換率との関わり
r  expn(tk 1  tk )H (wk 1 )  H (wk )
•細かく刻むと・・・用意するサンプル系列数が増える ⇒ 計算量が膨大！
•粗く刻むと
・・・サンプルが交換される割合が減る ⇒ 効率が悪くなる！
サンプル交換の割合（平均交換率）が、各温度間でほぼ一定になるように
温度パラメータを設定することが望ましい。
２．交換モンテカルロ法の設計
＜対称カルバック距離＞
P( wk | tk )
P( wk 1 | tk 1 )
I (tk , tk 1 )   P( wk | tk ) log
dwk   P( wk 1 | tk 1 ) log
dwk 1
P( wk | tk 1 )
P( wk 1 | tk )
＜性質＞
１．P(wk | tk )  P(wk 1 | tk 1 ) における log r の期待値 E[logr ] との間に
E[logr ]  I (tk , tk 1 ) が成り立つ。
２．自由エネルギー
F (nt )   log  exp( ntH ( w)) ( w)dw
 2 F (nt)
2


I (tk , tk 1 ) 
t

t
k 1
k
t 2
との間に
目的

n  （低温極限）における対称カルバック
距離と平均交換率を解明する。

両者の性質および関係を明らかにする。
発表概要
1.
2.
3.
4.
交換モンテカルロ法
交換モンテカルロ法の設計
主定理
考察・まとめ
３．主定理
＜問題設定＞
以下の2つの確率分布間で交換モンテカルロ法を行った場合を考える。
1
d
P1 ( w) 
exp(ntH ( w)) ( w)
( w R )
Z (nt)
1
P2 ( w) 
exp(n(t  t ) H ( w)) ( w)
Z (n(t  t ))
＜対称カルバック距離＞
P1 (w1 )
P2 (w2 )
I   P1 ( w1 ) log
dw1   P2 ( w2 ) log
dw2
P2 ( w1 )
P1 (w2 )
＜平均交換率＞
J    uP1 ( w1 ) P2 ( w2 ) dw1dw2
３．主定理
＜定理１＞
対称カルバック距離
I
は、
n   において以下に収束する。
2




t
 t   t


I     1   O    
 t  
t
 t  


2
Im z
 ：有理数
 ( z )   H ( w)   ( w)dw
z

0
Re z
３．主定理
＜定理１の証明の概要＞

I  nt  H ( w1 ) P1 ( w1 )dw1   H ( w2 ) P2 ( w2 )dw2


ds s exp nts  s  H ( w)  ( w)dw

nt  H ( w) P ( w)dw  nt
 ds exp nts  s  H (w) (w)dw
0
1


t

t
0
 1
m 1



s

H
(
w
)

(
w
)
dw

cs
(

log
s
)

[Watanabe,2001]
2



t 

t
 t
 t   t


 I   
     1   O    

t
 t t  t 
 t  
 t  
2
３．主定理
＜定理２＞
平均交換率
J
は、
n 
において以下に収束する。
2


| t | 2(2 )

t


J  1
 O   

2
 t  
t 4  ( )


Im z
 ：有理数
 ( z )   H ( w)   ( w)dw
z

0
Re z
３．主定理
＜定理２の証明の概要＞
u  min1, r 
t  0 のとき、交換率 u の定義から
J 
H ( w1 )  H ( w2 )
P1 ( w1 ) P2 ( w2 )dw1dw2  
H ( w1 )  H ( w2 )
 2
H ( w1 )  H ( w2 )

 2


0

0
r
P1 ( w2 ) P2 ( w1 )
P1 ( w1 ) P2 ( w2 )
 expnt H ( w2 )  H ( w1 ) 
r P1 ( w1 ) P2 ( w2 )dw1dw2
P1 ( w1 ) P2 ( w2 )dw1dw2
ds2  ds1 e  nts1 e  n (t  t ) s2   s1  H ( w1 )  ( w1 )dw1   s2  H ( w2 )  ( w2 )dw2
s2
0

ds2  ds1 e  nts1 e  n (t  t ) s2   s1  H ( w1 )  ( w1 )dw1   s2  H ( w2 )  ( w2 )dw2
0
  t  2 
t 2(2 )
 1
 O   

2
 t  
t 4  ( )


発表概要
1.
2.
3.
4.
交換モンテカルロ法
交換モンテカルロ法の設計
主定理
考察・まとめ
４．考察
本定理の適用範囲
n 
w  x, y R 2
n  1000
t0
密度の大半が H (w) の基底状態の
周りに集中している
H (w)  x 2 y 2
 (w) :標準正規分布
0  t 1
t 1
４．考察
＜両者の性質および関係＞
 t 
対称カルバック距離： I   

 t 
2
 t
  t  2  
1   O    
 t  

t



2


| t | 2(2 )

t


平均交換率： J  1 
 O   

2
 t  
t 4  ( )


１、対称カルバック距離が一定になるように温度パラメータを設定することで、
平均交換率も一定になる。
２、その際の温度パラメータは等比数列になる。
３、対称カルバック距離は２次形式であるのに対し、
平均交換率は１次形式である。
４．考察
＜目標分布の形状と温度パラメータの設定＞
  t  2 
| t | 2(2 )
J  1
 O   

2
 t  
t 4  ( )


1.4
1.2
1
0.8
0.6
0.4
0.2
0
0
 ：大
 ：小
t
：小
t
t
：大
t
1
2
3
4
5
サンプル系列の数：多
サンプル系列の数：少
6
４．考察
＜目標分布の形状と温度パラメータの設定＞
 ：大
 ：小
特異モデルにおける
ベイズ事後分布
特異モデルにおけるベイズ学習では、
交換モンテカルロ法が特に有効である。
４．まとめ

n   （低温極限）における対称カルバック距離と平均交

換率を解明することで、両者の性質および関係を明らかにし
た。
結果として、以下のことが明らかになった。



対称カルバック距離を一定にするように温度パラメータを設定するこ
とで、平均交換率も一定になる。
その際の温度パラメータの設定は等比数列になる。
今後の課題


本定理に基づいた交換モンテカルロ法の設計法の構築
ベイズ学習などの実問題への適用

Download Report