交換モンテカルロ法における熱浴型交換率の解析永田賢二渡辺澄夫東京工業大学発表概要  研究背景    解析    交換モンテカルロ法交換モンテカルロ法の設計先行研究の解析結果本研究の解析結果考察・まとめ発表概要  研究背景    解析    交換モンテカルロ法交換モンテカルロ法の設計先行研究の解析結果本研究の解析結果考察・まとめ交換モンテカルロ法[Hukushima,96] ＜交換モンテカルロ法＞従来のMCMC法の問題点である、「収束の遅さ」を改善したアルゴリズム MCMC法・・・ある確率分布に法則収束するサンプル系列を生成するアルゴリズム。「計算量が膨大なこと」や「収束判定が難しいこと」が問題点として知られている。 <交換モンテカルロ法の応用例> スピングラス・シミュレーションタンパク質の構造解析組み合わせ最適化問題ベイズ学習交換モンテカルロ法[Hukushima,96] 以下の目標分布からサンプリングすることを考える。 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法によるサンプリング] メトロポリス法やギブスサンプラーなどの従来のMCMC法により、それぞれの分布 p(wk | tk )からのサンプリングを並列に実行する。２．[隣り合った温度間でのサンプルの交換] 上記の操作に加えて、適当なステップごとにサンプル wk と wk 1 を確率 u で交換する。以後、 u を交換率と呼ぶことにする。交換モンテカルロ法＜交換率の種類＞１．メトロポリス型交換率 u1  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 ) ２．熱浴型交換率 pwk 1 | t k  pwk | t k 1  u2  pwk | t k  pwk 1 | t k 1   pwk 1 | t k  pwk | t k 1  1 n   1  tanh t k 1  t k H wk 1   H wk  2 2  交換モンテカルロ法＜従来のMCMC法＞ p (w) ＜交換モンテカルロ法＞ p( w1 | t1 ) p(w2 | t2 ) p(w3 | t3 ) p(w4 | t4 ) 発表概要  研究背景    解析    交換モンテカルロ法交換モンテカルロ法の設計先行研究の解析結果本研究の解析結果考察・まとめ交換モンテカルロ法の設計＜温度パラメータの設定＞交換率との関わり r  expn(tk 1  tk )H (wk 1 )  H (wk ) 1 n  u2  1  tanh tk 1  tk H wk 1   H wk  2 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 ) ＜性質＞１．p(wk | tk )  p(wk 1 | tk 1 ) における log r の期待値 E[logr ] との間に E[logr ]  I (tk , tk 1 ) が成り立つ。２．自由エネルギー F (t )   log  exp( ntH ( w)) ( w)dw との間に  2 F (tk ) 2   I (tk , tk 1 )  t  t が成り立つ。 k 1 k t 2 目的  n  （低温極限）における対称カルバック距離と平均交換率の漸近挙動を解明する。  それぞれの性質、関係を明らかにする。  最適な温度パラメータの設定を提案する。発表概要  研究背景    解析    交換モンテカルロ法交換モンテカルロ法の設計先行研究の解析結果本研究の解析結果考察・まとめ問題設定以下の2つの確率分布間で交換モンテカルロ法を行った場合を考える。 p1 w  pw | t  p2 w  pw | t  t  w R  ＜対称カルバック距離＞ d  t  t  p1 ( w1 ) p2 ( w2 ) I   p1 ( w1 ) log dw1   p2 ( w2 ) log dw2 p2 ( w1 ) p1 ( w2 ) ＜平均交換率＞ J1    u1 p1 ( w1 ) p2 ( w2 )dw1dw2 J 2    u2 p1 ( w1 ) p2 ( w2 )dw1dw2 (メトロポリス型) (熱浴型) 先行研究＜定理1＞[NC研究会、2006] 対称カルバック距離 I 、メトロポリス型平均交換率 J1 は、 n   において以下に収束する。  t   t  2   1   O      t    t      t  2  | t |   12  J1  1   O     t   t       t  I     t  2 Im z  ：有理数  ( z )   H ( w)   ( w)dw z  0 Re z 主定理＜定理2＞熱浴型平均交換率 J2 は、 n   において以下に収束する。 2 3  1    t   t   J 2  1     O  2  2 t   t   Im z  ：有理数  ( z )   H ( w)   ( w)dw z  0 Re z 主定理の証明の概略 f w | t  pw | t   , f w | t   exp ntH w w Z nt  nt  H w2   H w1  f w1 | t  f w2 | t  t  J   dw1  dw2 tanh  2  * 2 とすると、 J 2    u2 p( w1 | t ) p( w2 | t  t )dw1dw2  1 J 2*  1   2  Z ntZ nt  t  と表せる。主定理の証明の概略＜補題＞[Watanabe,2001] 状態密度関数 V s  は、 s  0 において以下の漸近形を持つ。 V s     s  H w wdw  cs  1  log s  m 1 この補題より c 2 log nt * J2  nt2 2  m 1 clog nt Z nt  nt m1   2  t  2   t 3       O       2  t   t      2 3  1    t   t   J 2  1     O  2  2 t   t   発表概要  研究背景    解析    交換モンテカルロ法交換モンテカルロ法の設計先行研究の解析結果本研究の解析結果考察・まとめ考察 2    t   t  t    対称カルバック距離： I     1   O      t t  t         t  2  | t | (  12 ) メトロポリス型平均交換率： J1  1   O     t   t   ( )   2 1    t   t  熱浴型平均交換率： J 2  1     O   2 2 t   t  2 3     １、対称カルバック距離が一定になるように温度パラメータを設定することで、平均交換率も一定になる。２、その際の温度パラメータは等比数列になる。３、得られた定理から J1  J 2であるため、交換率としてメトロポリス型を用いるほうがアルゴリズムの効率がよくなる。まとめ   低温極限の場合における熱浴型平均交換率の漸近挙動を解明した。結果として、以下のことが明らかになった。     対称カルバック距離が一定になるように温度パラメータを設定することで、熱浴型平均交換率も一定になる。その際の温度パラメータは等比数列になる。交換率としてメトロポリス型を用いるほうがアルゴリズムの効率がよくなる。今後の課題   得られた理論の検証階層モデルにおけるベイズ学習などへの応用