交換モンテカルロ法における
交換率とカルバック距離の関係について
永田賢二 渡辺澄夫
東京工業大学 知能システム科学専攻
東京工業大学 精密工学研究所
発表概要
1.
2.
3.
4.
交換モンテカルロ法
交換モンテカルロ法の設計
主定理
考察・まとめ
<参考文献>
伊庭幸人他 「計算統計Ⅱ マルコフ連鎖モンテカルロ法とその周辺」、岩波書店
1.交換モンテカルロ法[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)
1.交換モンテカルロ法
<アルゴリズム>
以下の2種類の更新を交互に実行する。
1.メトロポリス法やギブスサンプラーなどの従来のMCMC法により、
それぞれの分布 P(wk | tk )からのサンプリングを並列に実行する。
2.上記の操作に加えて、適当なステップごとにサンプル 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 を交換率と呼ぶことにする。
1.交換モンテカルロ法
<従来のMCMC法>
P (w)
<交換モンテカルロ法>
P( w1 | t1 )
P(w2 | t2 )
P(w3 | t3 )
P(w4 | t4 )
1.交換モンテカルロ法
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.
交換モンテカルロ法
交換モンテカルロ法の設計
主定理
考察・まとめ
2.交換モンテカルロ法の設計
<温度パラメータの設定>
交換率との関わり
r  expn(tk 1  tk )H (wk 1 )  H (wk )
•細かく刻むと ・・・ 用意するサンプル系列数が増える ⇒ 計算量が膨大!
•粗く刻むと
・・・ サンプルが交換される割合が減る ⇒ 効率が悪くなる!
サンプル交換の割合(平均交換率)が、各温度間でほぼ一定になるように
温度パラメータを設定することが望ましい。
2.交換モンテカルロ法の設計
<対称カルバック距離>
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 )
<性質>
1.P(wk | tk )  P(wk 1 | tk 1 ) における log r の期待値 E[logr ] との間に
E[logr ]  I (tk , tk 1 ) が成り立つ。
2.自由エネルギー
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.
交換モンテカルロ法
交換モンテカルロ法の設計
主定理
考察・まとめ
3.主定理
<問題設定>
以下の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
3.主定理
<定理1>
対称カルバック距離
I
は、
n   において以下に収束する。
2




t
 t   t


I     1   O    
 t  
t
 t  


2
Im z
 :有理数
 ( z )   H ( w)   ( w)dw
z

0
Re z
3.主定理
<定理1の証明の概要>

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
3.主定理
<定理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
3.主定理
<定理2の証明の概要>
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.
交換モンテカルロ法
交換モンテカルロ法の設計
主定理
考察・まとめ
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
4.考察
<両者の性質および関係>
 t 
対称カルバック距離: I   

 t 
2
 t
  t  2  
1   O    
 t  

t



2


| t | 2(2 )

t


平均交換率: J  1 
 O   

2
 t  
t 4  ( )


1、対称カルバック距離が一定になるように温度パラメータを設定することで、
平均交換率も一定になる。
2、その際の温度パラメータは等比数列になる。
3、対称カルバック距離は2次形式であるのに対し、
平均交換率は1次形式である。
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
4.考察
<目標分布の形状と温度パラメータの設定>
 :大
 :小
特異モデルにおける
ベイズ事後分布
特異モデルにおけるベイズ学習では、
交換モンテカルロ法が特に有効である。
4.まとめ

n   (低温極限)における対称カルバック距離と平均交

換率を解明することで、両者の性質および関係を明らかにし
た。
結果として、以下のことが明らかになった。



対称カルバック距離を一定にするように温度パラメータを設定するこ
とで、平均交換率も一定になる。
その際の温度パラメータの設定は等比数列になる。
今後の課題


本定理に基づいた交換モンテカルロ法の設計法の構築
ベイズ学習などの実問題への適用
ダウンロード

発表資料(ppt版)