JNNS-DEX-SMI-玉川 公開講座 「交換モンテカルロ法とその応用」 東京工業大学大学院　総合理工学研究科 知能システム科学専攻　博士課程2年 永田賢二

交換モンテカルロ法とは？ マルコフ連鎖モンテカルロ法（MCMC法）のひとつ サンプリング 期待値計算 ＜MCMC法の主な目的＞ 乱数を用いて、確率分布を再現するための一群の手法 正規分布など、性質のわかっている分布だけでなく、離散・連続を問わず、 　様々な分布に適用できる。汎用性が高い。 交換モンテカルロ法は、従来のMCMC法の改良アルゴリズム[Hukushima,96] ＜MCMC法の主な目的＞ サンプリング 期待値計算 確率分布

MCMC法の応用例 ＜ベイズ統計＞ ＜統計物理＞ ：確率モデル ：パラメータの事前分布 データ　　が与えられたもとでのパラメータ　　の条件付き確率（事後分布） ＜統計物理＞ ギブス分布・カノニカル分布における期待値計算 ：エネルギー関数 ：温度の逆数（逆温度）

Outline マルコフ連鎖モンテカルロ法 交換モンテカルロ法 交換モンテカルロ法の設計に関する理論 メトロポリス法 マルコフ連鎖の原理 遅い緩和の問題 交換モンテカルロ法の原理 交換モンテカルロ法の設計に関する理論 温度パラメータの設定 平均交換率の理論解析

Outline マルコフ連鎖モンテカルロ法 交換モンテカルロ法 交換モンテカルロ法の設計に関する理論 メトロポリス法 マルコフ連鎖の原理 遅い緩和の問題 交換モンテカルロ法の原理 交換モンテカルロ法の設計に関する理論 温度パラメータの設定 平均交換率の理論解析

マルコフ連鎖モンテカルロ法 d次元空間上の点 が従う確率分布 が与えられているとする。 また、点 の各成分は連続値をとるものとする。 また、点　　の各成分は連続値をとるものとする。 　　　１．確率分布　　　　に従う点をサンプリング 　　　２．　の関数　　　　の確率分布　　　　についての期待値の計算　　　　

メトロポリス法 （例）以下の確率分布 に従うサンプル生成 ２． 現在の点 から、以下の式で候補 を生成する。 １． の初期値 を設定する。 （例）以下の確率分布　　　　に従うサンプル生成 ２．　現在の点　　　から、以下の式で候補　　を生成する。 １．　　の初期値　　　　を設定する。 ３．　密度の比較により、次の点　　　　を決める。 確率　　で 確率　　　　で : 平均0の一様乱数、正規乱数など

メトロポリス法 （例）以下の確率分布　　　　に従うサンプル生成 ３．　密度の比較により、次の点　　　　を決める。 確率　　で 確率　　　　で

メトロポリス法のアルゴリズム ＜確率分布 に従うサンプリング・アルゴリズム＞ １． の初期値 を適当に設定する。 ＜確率分布　　　　に従うサンプリング・アルゴリズム＞ １．　　の初期値　　　を適当に設定する。 ２．現在の点　　　から、以下の式で候補　　　を生成する。 ３．密度の比較により、次の状態　　　　を決める。 ４．ステップ２に戻り、繰り返す。 : 平均0の一様乱数、正規乱数など 確率　　で 確率　　　　で

ステップサイズ ステップサイズ：候補を選ぶ際の範囲の大きさ （例）以下の２次元の確率分布からのサンプリング ・大きすぎると・・・ ・大きすぎると、ほとんどの候補が採択されなくなる。 ・小さすぎると・・・ ・小さすぎると、一回の更新が少ないため、遠くに行きにくい。

ステップサイズ (例) 右の目標分布から1000個のサンプルを生成 ・実際には、採択される割合が40%～60%程度になるように設定 :２次元の一様分布からランダムに選ぶ。 ステップサイズ：0.05 ステップサイズ：0.5 ステップサイズ:5 ・実際には、採択される割合が40%～60%程度になるように設定 ・要素ごとに更新するのも一つの手。

「メトロポリス法」のまとめ 確率的に「候補」を選んで、それを採用するかどうかを、確率的に決定する。 目標分布の情報は、密度の比のみしか用いないため、密度さえ計算できれば、どんな分布にも適用できる。規格化されていなくても大丈夫。 ステップサイズの設定は、アルゴリズムの効率アップのために、重要。大きすぎず、小さすぎず。要素ごとの更新を考えてもいいかも。

Outline マルコフ連鎖モンテカルロ法 交換モンテカルロ法 交換モンテカルロ法の設計に関する理論 メトロポリス法 マルコフ連鎖の原理 遅い緩和の問題 交換モンテカルロ法の原理 交換モンテカルロ法の設計に関する理論 温度パラメータの設定 平均交換率の理論解析

マルコフ連鎖 マルコフ連鎖：直前の点 のみに依存して、次の点 を決定する。 ・遷移確率 ： 点 から点 に移る確率 （メトロポリス法の場合） マルコフ連鎖：直前の点　　　　のみに依存して、次の点　　　を決定する。 ・遷移確率　　　　　　　　： 点　　から点　　に移る確率 （メトロポリス法の場合） :[-D,D]の範囲の一様分布からランダムに選ぶ。 Case1: Case2: Case3:

マルコフ連鎖の原理 ＜遷移確率 が満たすべき条件＞ １．詳細つりあい条件 確率分布 に従う点がたくさんある状況を考える。 ＜遷移確率　　　　　　　　が満たすべき条件＞ １．詳細つりあい条件 確率分布　　　　に従う点がたくさんある状況を考える。 それぞれの点を更新 （左辺）：　　から　　　に移る個数 （右辺）：　　から　　　に移る個数 任意の２つの位置での 「流入」と「流出」がつりあっている。 「確率分布　　　　を不変にする」

マルコフ連鎖の原理 ＜遷移確率 が満たすべき条件＞ ２．エルゴード性 任意の2つの点 と の間の遷移確率がゼロでないか、 ＜遷移確率　　　　　　　　が満たすべき条件＞ ２．エルゴード性 任意の2つの点　　と　　の間の遷移確率がゼロでないか、 有限個のゼロでない遷移確率の積で表すことができる。 ・何回かの更新で、どこへでも 到達することが可能である。 ・どんな初期値から始めても 唯一の分布に収束する。

メトロポリス法における詳細つりあい条件 （先のメトロポリス法の場合） :[-D,D]の範囲の一様乱数 １．　　　　　　　　　の場合 ２．　　　　　　　　　　　の場合

MCMC法のアルゴリズム 遷移確率の満たすべき条件は緩くて、一意に決定できない。 MCMC法のアルゴリズムは、たくさん存在する。 （例） 詳細つりあい条件 エルゴード性 MCMC法のアルゴリズムは、たくさん存在する。 （例） メトロポリス法 メトロポリス・ヘイスティングス法 ギブスサンプラー、熱浴法 独立サンプラー ハミルトニアン・モンテカルロ法

「マルコフ連鎖の原理」のまとめ マルコフ連鎖 マルコフ連鎖の基本原理 直前の状態にのみ依存して、次の状態が決まる系列 遷移確率で特徴づけられる。 マルコフ連鎖の基本原理 詳細つりあい条件 任意の２つの位置での「流入」と「流出」がつりあっている。 エルゴード性 有限回のステップで、任意の２点間を行き来できる。 条件は緩く、いろいろなアルゴリズムが存在する。

Outline マルコフ連鎖モンテカルロ法 交換モンテカルロ法 交換モンテカルロ法の設計に関する理論 メトロポリス法 マルコフ連鎖の原理 遅い緩和の問題 交換モンテカルロ法の原理 交換モンテカルロ法の設計に関する理論 温度パラメータの設定 平均交換率の理論解析

ある確率分布に対しては、ものすごく効率が悪くなってしまう。 遅い緩和の問題 メトロポリス法の基本は、「少し変えて、選ぶかどうかを確率的に決める。」 ある確率分布に対しては、ものすごく効率が悪くなってしまう。 （例１）密度の高い領域が、いくつもあり、互いに離れている場合 （多峰性のある確率分布） ・ある領域から、他の領域に到達するには、 密度の低い領域を通る必要がある。 　　　　⇒サンプリング効率の悪化

遅い緩和の問題 （例１）基底状態が一点ではなく、次元を持った集合になっている。 （ベイズ学習でみられる問題） 基底状態：エネルギー関数　　　　　を最小にする点　　のこと ＜一点の例＞ ＜集合の例＞

拡張アンサンブル法 確率分布によっては、 サンプリング精度が悪くなり、 遷移確率が著しく小さくなる。 期待値の評価に影響を与えてしまう。 ＜実質的なエルゴード性の破れ・遅い緩和の問題＞ ＜拡張アンサンブル法＞　上記の問題を解決する一群の手法 確率分布を拡張したり、混合したものを考える。 　　・マルチカノニカル法 　　・シミュレーテッド・テンパリング法 　　・交換モンテカルロ法　[Hukushima-Nemoto,96]

交換モンテカルロ法のアイデア（温度の導入） ・確率分布　　　　に対して、 ギブス分布の場合： ＜高温状態＞ ＜低温状態＞ ・エネルギーの低い点は探せない ・大域的に行き渡れる ・常にエネルギーの低い点にいる ・局所領域に留まりやすい サンプリング中に 温度を上げ下げする。 ＜問題＞ 　　・温度を上げ下げする過程で、詳細つりあい条件を破ることになるので、 　　　目標分布からのサンプリングの保証がなくなる！

交換モンテカルロ法[Hukushima,96] 目標分布： 拡張された確率分布　　　　　 （　　: 逆温度） ＜アルゴリズム＞ 　　１．（通常の更新）それぞれの確率分布について、状態の更新 　　２．隣り合った分布間で、状態の交換を行う。

交換モンテカルロ法の詳細つりあい条件 ＜詳細つりあい条件＞ <Case1> :小 <Case2> :大

交換の採択確率 1.メトロポリス型 交換前 必ず交換する。 (1) 交換後 交換前 確率 で交換する。 (2) 交換後 2.熱浴型 確率　　で交換する。 (2) 交換後 2.熱浴型 （交換後） （交換前）

交換モンテカルロ法のイメージ <メトロポリス法> <交換モンテカルロ法> １．（通常の更新） 　　メトロポリス法により、状態の更新 ２．（状態の交換） 　　隣り合った分布間で、状態の交換 ＜交換の採択確率＞

交換モンテカルロ法の挙動（イメージ） ＜前に出した例では・・・＞ ・低温での点が、高温に移ることで、大域的なサンプリングが可能に。 ・詳細つりあいを満たしているので、サンプリングの保証つき。

交換モンテカルロ法の 実験結果の例 右の確率分布から10000個のサンプルを生成 メトロポリス法 交換モンテカルロ法

ベイズ学習での交換モンテカルロ法 ＜混合正規分布モデルにおけるベイズ学習＞ 推定 汎化誤差：真の構造と予測結果の相違 <学習データ> 　　1000個の3次元データを生成 <正規分布の数> データ生成: 4個 　　学習モデル:　10個　　 アルゴリズム 汎化誤差 Gibbs　sampler 交換法 理論値(上限)

その他の応用例 ポリマーの構造推定 タンパク質の立体構造推定 スピングラス・シミュレーション 組み合わせ最適化問題

「交換モンテカルロ法」のまとめ 遅い緩和の問題 交換モンテカルロ法の原理 密度の高い領域が複数存在し、互いに離れている場合 エネルギーの基底状態が、次元をもった集合になっている場合 交換モンテカルロ法の原理 温度パラメータを導入することで、大域的なサンプリングが可能に 同時分布の詳細つりあい条件を考える

Outline マルコフ連鎖モンテカルロ法 交換モンテカルロ法 交換モンテカルロ法の設計に関する理論 メトロポリス法 マルコフ連鎖の原理 遅い緩和の問題 交換モンテカルロ法の原理 交換モンテカルロ法の設計に関する理論 温度パラメータの設定 平均交換率の理論解析

交換法が有効に働くには・・・ ＜交換が、ある程度の確率で行われている。＞ 交換が行われないと、通常のメトロポリス法を行っているのと同じ。 ＜　　　　のヒストグラム＞ 低温 温度パラメータの値によって 交換の頻度が決まる。 高温 ＜温度パラメータの設定＞ 　　・各　　の間隔は？ 　　・温度パラメータの総数は？

温度パラメータ設定の際の基準例 ＜平均交換率＞ 各温度間で、交換が行われた頻度 ・もし、各温度で定常分布に収束していると、 ＜平均交換率＞　 　　各温度間で、交換が行われた頻度 ・もし、各温度で定常分布に収束していると、 平均交換率は、２つの温度パラメータによって定まる関数。

平均交換率の理論解析 ＜低温同士での平均交換率＞　　　　がある程度大きい状況 ：　ある点　　において、最小値　　　　　をもつ関数 ：　任意の確率分布

平均交換率の理論解析 ＜交換に関する採択確率＞ ＜平均交換率＞

メトロポリス型における平均交換率 ＜定理１＞[Nagata, 2008] 　　　平均交換率　　は、　　　　　　　　において以下の式に収束する。

熱浴型における平均交換率 ＜定理２＞[Nagata, 2008] 　　　平均交換率　　は、　　　　　　　　において以下の式に収束する。

平均交換率の挙動 平均交換率は、　　　　　　　　　　　と　　　の関数 平均交換率

平均交換率と温度パラメータ 平均交換率は、 の関数 各温度で が一定ならば、平均交換率は同じ値になる。 このとき、温度パラメータの値は、 平均交換率は、　　　　　　　　　　　の関数 各温度で　　　　　　　　が一定ならば、平均交換率は同じ値になる。 このとき、温度パラメータの値は、 指数的に区切れば、平均交換率が一定の値になる。

ってなに？ 「自由エネルギー」・「周辺対数尤度」・「確率的複雑さ」 ・ の値は、主に の性質によって定まる。 ＜正則なケース＞ 　　ってなに？ 「自由エネルギー」・「周辺対数尤度」・「確率的複雑さ」 ・　　の値は、主に　　　　の性質によって定まる。 ＜正則なケース＞ ・任意の　　において　　　　のヘッセ行列が正定値 ヘッセ行列：

ってなに？ ＜特異なケース＞ ・ヘッセ行列が縮退する が存在する場合 右の例では、 ・特異なケースでの の解析法 の極を調べる。 　　ってなに？ ＜特異なケース＞ ・ヘッセ行列が縮退する　　が存在する場合 右の例では、 ・特異なケースでの　　の解析法 　　　　の極を調べる。 代数幾何学の手法である 特異点解消を行えば求められる。

ベイズ学習での の性質 ＜汎化誤差[Watanabe, 2001]＞ 漸近形： 様々な学習モデルにおいて、 の値を求める研究がなされている。 ベイズ学習での　　の性質 ＜汎化誤差[Watanabe, 2001]＞ ：真の構造と予測分布のカルバック距離 　　予測の精度を示す尺度の一つ 漸近形： 様々な学習モデルにおいて、　　の値を求める研究がなされている。 ＜厳密解＞ ・ニューラルネットワーク　　　　　　　・縮小ランク回帰モデル ・隠れマルコフモデル　　 　　　　　　・混合二項分布モデル ＜上限値＞ ・一般混合分布モデル　　　　　　　　・ベイジアンネットワーク ・確率文脈自由文法

平均交換率の理論値の検証 ＜縮小ランク回帰モデル（線形ニューラルネットワーク）のベイズ学習＞ パラメータ パラメータの次元： 学習モデルが　　　　　　　　　　　　　　　　　のとき （真の構造は　　　　　　　）

温度パラメータ設定に関する研究 平均交換率を均等にするよう設定 関数 などの挙動をもとにした繰り返しアルゴリズム 最適な平均交換率の値 関数　　　　などの挙動をもとにした繰り返しアルゴリズム 最適な平均交換率の値 20%～25%くらいが最適らしい。 温度の端から端まで動くための時間の最小化

全体のまとめ マルコフ連鎖モンテカルロ法 交換モンテカルロ法 交換モンテカルロ法の設計に関する理論 メトロポリス法 マルコフ連鎖の原理 遅い緩和の問題 交換モンテカルロ法の原理 交換モンテカルロ法の設計に関する理論 温度パラメータの設定 平均交換率の理論解析