サンプリング

サンプリング 公立小松大学 藤田 一寿

期待値の評価をしたい • 実用的な興味あるほとんどの確率モデルに対して，厳密な推論は手に負えない ため，何らかの形の近似に頼る必要がある． • ある種の応用においては非観測変数の事後分布そのものを直接知りたいことも あるが，ほとんどの状況では，事後分布は例えば予測に使うために期待値を評 価する目的で，もっぱら必要とされる． • そのため，ここで取り扱う基本的な問題は，ある関数𝑓 𝑧 の確率分布𝑝 𝑧 のも とでの期待値𝐸 𝑓 の計算に関する事である． • 𝐸 𝑓 = ∫ 𝑓 𝐳 𝑝 𝐳 𝑑𝑧 • これは，解析的な手法を用いて厳密に評価するには複雑すぎると仮定する．

サンプリング法の背後にある一般的なアイデア • サンプリング法の背後にある一般的なアイデアは，分布𝑝 𝐳 から独立に抽出されたサンプルセット 𝐳 𝑙 𝑙 = 1, … , 𝐿 を得ることである． • これにより，期待値を有限和で近似できる． 1 • 𝑓መ = σ𝐿𝑙=1 𝑓 𝐳 𝑙 𝐿 መ • サンプル𝑧 𝑙 が分布𝑝 𝑧 に従って抽出される限り，𝐸 𝑓መ = 𝐸 𝑓 が成り立ち，推定量𝑓は正しい平均を持つ． • 推定量の分散は 1 • var 𝑓መ = 𝐸 𝑓 − 𝐸 𝑓 2 𝐿 • となる．そのため，推定量の精度は𝑧の次元に依存せず，原理的には比較的少数のサンプル𝐳 𝑙 で高い精度が 達成出来る． • しかし，問題はサンプル 𝐳 𝑙 が独立でないかも知れず，有効なサンプルサイズが見かけのサンプルサイズよ りもずっと少ないかも知れない． • また， 𝑝 𝐳 が大きい領域で𝑓 𝐳 が小さく，逆に 𝑝 𝐳 が小さい領域で𝑓 𝐳 が大きいならば，期待値は小さな確 率の領域から大きな影響を受ける．これ，十分精度を得るためには比較的大きなサンプルサイズが必要とな ることを意味する．

分散の計算 2 𝐿 1 ෍𝑓 𝐳 𝑙 𝐿 var 𝑓መ = 𝐸 𝑓መ 2 − 𝐸 2 𝑓መ = 𝐸 − 𝐸2 𝑓 𝑙=1 1 = 2𝐸 𝐿 𝐿 𝐿 1 ෍𝑓 𝐳 𝑙 𝑁 1 ෍𝑓 𝐳𝑚 𝑁 𝑙=1 1 = 2𝐸 ෍ 𝑓 𝐳 𝑙 𝐿 𝑙=1𝐿 − 𝐸2 𝑓 𝑚=1 𝐿 ෍𝑓 𝐳𝑚 𝑙≠𝑚 𝑁 + ෍ 𝑓2 𝑧 𝑙 − 𝐸2 𝑓 𝑙=1 1 1 2 2 2 𝐿 𝐿 − 1 𝐸 𝑓 + 𝐿𝐸 𝑓 − 𝐸 𝑓 = 𝐿 − 1 𝐸 2 𝑓 + 𝐸 𝑓 2 − 𝐿𝐸 2 𝑓 2 𝐿 𝐿 1 1 1 = 𝐸 𝑓 2 − 𝐸 2 𝑓 = var 𝑓 = 𝐸 𝑓 − 𝐸 𝑓 2 𝐿 𝐿 𝐿 =

伝承サンプリング

伝承サンプリング • 𝐾個のノードを持つ観測変数の無い有向非循環グラフを考える． • このグラフに対応する同時分布は • 𝑝 𝐱 = ς𝐾 𝑘 𝑝 𝑥𝑘 pa 𝑘 • で与えられる．𝐱 = 𝑥1 , … , 𝑥𝐾 で，pa 𝑘 はノード𝑘の親ノード集合 を表す． • 変数の番号付けは，自分より小さい番号を持つノードへのリンク が無いようにされているとする． • 我々の目的は，この同時分布に従うサンプル𝑥ො1, … , 𝑥ො𝐾 を発生させ ることにある．

伝承サンプリング • この目的を達成するには，単純に番号の最も小さいノードから順にサンプルを 発生させれば良い． • まず，はじめに分布𝑝 𝑥1 に従うサンプルを発生させ，これを𝑥ො1 とする． • サンプルの発生を番号順に行う．ただし，pa 𝑘 の値にはサンプリングされた値 を用いる． • 最後の変数𝑥𝐾 までサンプルを発生されば，全変数について同時分布に従うサ ンプルが一つ発生させたことになる．

乱数生成 • 非一様分布から乱数を生成する方法を考える． • 一様分布の乱数発生源はすでに手元にあるとする． • 𝑧が区間 0,1 で一様に分布し，ある関数𝑓 ⋅ を用いて𝑧の値を𝑦 = 𝑓 𝑧 のように 変換するとする．𝑦の分布は次に従う． • 𝑝 𝑦 =𝑝 𝑧 𝑑𝑧 𝑑𝑦 • 𝑧は一様分布だから，𝑝 𝑧 = 1である． • ここで， 𝑝 𝑦 を積分することで 𝑝 𝑦 =𝑝 𝑧 置換積分 𝑦 𝑧 • 𝑧 = ℎ 𝑦 = ∫−∞ 𝑝 𝑦ො 𝑑𝑦ො = ∫−∞ 𝑝 𝑓 𝑧Ƹ • が得られる． 𝑑𝑓 𝑧Ƹ 𝑑𝑧Ƹ 𝑧 𝑑𝑧Ƹ = ∫−∞ 𝑝 𝑦ො 𝑑𝑧 から 𝑑𝑦 𝑧 𝑑𝑦ො 𝑑 𝑧 Ƹ = 𝑝 𝑧Ƹ 𝑑𝑧Ƹ ∫ −∞ 𝑑𝑧Ƹ

乱数生成 𝑦 • 𝑧 = ℎ 𝑦 = ∫−∞ 𝑝 𝑦ො 𝑑𝑦ො • この式から，𝑦 = ℎ−1 𝑧 が分かる． • つまり，求めたい分布𝑝 𝑦 の不定積分の逆関数を用いて，一様分布の乱数を変 換する必要がある．

計算詳細 𝑦 = 𝑓 𝑧 より， 𝑑𝑦 𝑓 𝑧 = 𝑑𝑧 𝑑𝑧 𝑑𝑦 𝑑𝑦 = 𝑑𝑧 𝑑𝑧 確率は規格化されているので ∞ ∞ න 𝑝 𝑧 𝑑𝑧 = න 𝑝 𝑦 𝑑𝑦 = 1 −∞ これを𝑥を𝑦で置換すると ∞ ∞ 𝑝 𝑓 −1 𝑦 න 𝑝 𝑧 𝑑𝑧 = න よって， −∞ −∞ −∞ ∞ 𝑑𝑧 𝑑𝑦 = න 𝑝 𝑦 𝑑𝑦 = 1 𝑑𝑦 −∞ 𝑑𝑧 =𝑝 𝑦 𝑑𝑦 𝑑𝑧 𝑝 𝑦 =𝑝 𝑧 𝑑𝑦 𝑝 𝑓 −1 𝑦

指数分布の場合 • 指数分布 • 𝑝 𝑦 = 𝜆 exp −𝜆𝑦 • を考えてみる．ここで0 ≤ 𝑦 < ∞である．𝑧は 𝑦 • 𝑧 = ℎ 𝑦 = ∫0 𝜆 exp −𝜆𝑦ො 𝑑𝑦ො = − exp −𝜆𝑦ො 𝑦 0 = 1 − exp −𝜆𝑦 • となる．よって次の逆関数を用いれば，一様分布する変数𝑧から指数分布に従 う乱数を生成することが出来る． • 𝑦 = ℎ−1 𝑧 = −𝜆−1 ln 1 − 𝑧 𝑧 = 1 − exp −𝜆𝑦 exp −𝜆𝑦 = 1 − 𝑧 −𝜆𝑦 = ln 1 − 𝑧

コーシー分布の場合 • コーシー分布 •𝑝 𝑦 = 1 1 𝜋 1+𝑦2 • を考えてみる． 𝑦 1 1 1 1 −1 𝑥 𝑑 𝑦 ො = + tan 2 𝜋 1+𝑦ො 2 𝜋 • 𝑧 = ℎ 𝑦 = ∫−∞ • となる．よって次の逆関数を用いれば，一様分布する変数𝑧から指数分布に従 う乱数を生成することが出来る． • 𝑦 = ℎ−1 𝑧 = tan 𝜋 𝑧 − 1 2

棄却サンプリング

棄却サンプリング • 単純で標準的な分布ではない分布𝑝 𝐳 からサンプリングしたいが，直接𝑝 𝐳 か らサンプリングすることが困難であるとする． • さらに，任意の与えられた𝐳の値について𝑝 𝐳 を求めることは，規格化定数𝑍を 除き容易であるとする．つまり， •𝑝 𝑧 = 1 𝑝෤ 𝑧 𝑍𝑝 • において 𝑝෤ 𝑧 は容易に求まるが，𝑍𝑝 は分からないとする． • 例えば，統計力学において分配関数𝑍𝑝 は分からないが𝑒 −𝐸 𝑥 は求まるということがあ る．

棄却サンプリング • 棄却サンプリングを適用するには，まず，用意にサンプルを抽出できる，より 簡単なサンプリング分布𝑞 𝑧 を必要とする． • 𝑞 𝑧 は，提案分布(proposal distributio)と呼ばれることもある． • 次に，定数𝑘を導入し，𝑧のすべての値に対して𝑘𝑞 𝑧 ≥ 𝑝෤ 𝑧 が成り立つように その値を決める． • 𝑘𝑞 𝑧 は比較関数と呼ばれる．

棄却サンプリングのステップ • ステップ1 • 乱数𝑧0 を分布𝑞 𝑧 から生成する． • ステップ2 • 乱数𝑢0 を区間 0, 𝑘𝑞 𝑧0 上の一様分布から生成する． • この乱数は，𝑘𝑞 𝑧 の下側で一様分布する． • ステップ3 • 𝑢0 > 𝑝෤ 𝑧0 ならばサンプルは棄却され，層でなければ𝑢0 は保持される． • すなわち，𝑢0が図の灰色の領域に入っていれば棄却される．

重点サンプリング

重点サンプリング 1 • 期待値の有限和近似 𝑓መ = σ𝐿𝑙=1 𝑓 𝐳 𝑙 を計算するためには，分布𝑝 𝐳 からのサ 𝐿 ンプルが抽出できなくてはいけない． • 𝑝 𝐳 から直接サンプリングすることは現実的ではないが，与えられた任意の𝐳 の値について𝑝 𝐳 は簡単に計算できるとする． • 期待値を計算するための単純な方法の一つは，𝑧空間を均一のグリッドで離散 化し，積分を総和の形で計算することである． 1 𝐿 • 𝐸 𝑓 ≃ σ𝐿𝑙=1 𝑝 𝐳 𝑙 𝑓 𝐳 𝑙

重点サンプリング • 重点サンプリングでも提案分布𝑞 𝐳 を用いる． • 期待値は𝑞 𝐳 から抽出されたサンプル 𝐳 𝑙 上の有限和の形で表される． 𝐸 𝑓 = න𝑓 𝐳 𝑝 𝐳 𝑑𝐳 = න𝑓 𝐳 𝑝 𝐳 𝑞 𝐳 𝑑𝐳 𝑞 𝐳 𝐿 𝑝 𝐳𝑙 1 𝑙 ≃ ෍ 𝑓 𝐳 𝐿 𝑞 𝐳𝑙 𝑙=1 𝑝 𝐳𝑙 • 𝑟𝑙 = 𝑞 𝐳𝑙 を重要度重みと呼び，求めたいものと異なった分布からサンプリン グすることで生じてしまうバイアスを補正する．．

重点サンプリング • 分布𝑝 𝐳 が𝑝 𝐳 = 𝑝(𝐳)/𝑍 ෤ ෤ 𝑝 のように，正規化定数𝑍𝑝 はよくわからないが𝑝(𝐳)は 容易に計算できる場合はよくある． • 同様に，同じ性質を持つ重点サンプリングの分布𝑞 𝐳 = 𝑞(𝐳)/𝑍 ෤ 𝑞 を持ちたい． • そうすると，次の式が得られる． 𝐸 𝑓 = න𝑓 𝐳 𝑝 𝐳 𝑑𝐳 𝑍𝑞 𝑝(𝐳) ෤ න𝑓 𝐳 = 𝑞 𝐳 𝑑𝐳 𝑍𝑝 𝑞(𝐳) ෤ 𝐿 𝑍𝑞 1 𝑝෤ 𝐳 𝑙 𝑙 ≃ ෍ 𝑓 𝐳 𝑍𝑝 𝐿 𝑞෤ 𝐳 𝑙 𝑙=1 𝐿 𝑍𝑞 1 = ෍ 𝑟𝑙ǁ 𝑓 𝐳 𝑙 𝑍𝑝 𝐿 𝑙=1

重点サンプリング • 同じサンプル集合を用い正規化項の比率 𝑍𝑞 𝑍𝑝 を評価できる． 𝑍𝑝 1 1 𝑝෤ 𝐳 1 𝑝෤ 𝐳 = න𝑝෤ 𝐳 𝑑𝐳 = න 𝑞 𝐳 𝑑𝐳 = න 𝑞 𝐳 𝑑𝐳 𝑍𝑞 𝑍𝑞 𝑍𝑞 𝑞 𝐳 𝑍𝑞 𝑞෤ 𝐳 𝑍𝑞 𝐿 𝑝෤ 𝐳 𝑙 𝑝෤ 𝐳 1 =න 𝑞 𝐳 𝑑𝐳 ≃ ෍ 𝑞෤ 𝐳 𝐿 𝑞෤ 𝐳 𝑙 𝑙=1 • したがって，次のようになる． • 𝐸 𝑓 ≃ σ𝐿𝑙=1 𝑤𝑙 𝑓 𝐳 𝑙 • ここで， 𝑝෤ 𝐳 𝑙 /𝑞 𝐳 𝑙 • 𝑤𝑙 = σ =σ ෤𝑚 ෤ 𝐳 𝒎 /𝑞 𝐳 𝑚 𝑚=1 𝑟 𝑚=1 𝑝 𝑟෤𝑙 𝐿 1 = ෍ 𝑟𝑙ǁ 𝐿 𝑙=1 𝐿 𝐿 𝑍𝑞 1 𝑟𝑙ǁ 𝑓 𝐳 𝑙 𝑍𝑝 𝐿 𝑙=1 𝑙=1 𝑍𝑞 1 1 1 𝑟𝑙ǁ 𝑤𝑙 = 𝑟𝑙ǁ = 𝑟𝑙ǁ = 1 σ𝑚=1 𝑟𝑚 𝑍𝑝 𝐿 ǁ σ ǁ 𝐿 𝐿 𝑚=1 𝑟𝑚 𝑝෤ 𝐳 𝑙 /𝑞෤ 𝐳 𝑙 = σ𝑚=1 𝑝෤ 𝐳 𝒎 /𝑞෤ 𝐳 𝑚 𝑝෤ 𝐳 𝑙 𝑍𝑞 /𝑞 𝐳 𝑙 = σ𝑚=1 𝑝෤ 𝐳 𝒎 𝑍𝑞 /𝑞 𝐳 𝑚 ෍ 𝑤𝑙 𝑓 𝐳 𝑙 =෍

SIR • 棄却サンプリングでは，適切な𝑘を決めなければならない． • 求めたい分布 𝑝 𝐳 よりサンプリング分布𝑘𝑞 𝐳 を確実に大きくする𝑘の値では，受理 実が非実用的なほど小さくなるだろう． • SIR(sampling-importance-resampling)アプローチも，サンプリング分布𝑞 𝐳 を用いるが，定数𝑘を用いる必要がない • SIRは次の２つのステップから成る． • ステップ1 • 𝐿個のサンプル𝐳1 , … , 𝐳𝐿 が𝑞 𝐳 から抽出される． • ステップ2 • 各サンプルについて𝑤𝑙 = σ 𝑝෤ 𝐳 𝑙 /𝑞 𝐳 𝑙 𝑚=1 𝑝෤ 𝐳 𝒎 /𝑞 𝐳 𝑚 を計算し， 𝐿個のサンプルが離散分布 𝐳1 , … , 𝐳𝐿 から重み 𝑤1 , … , 𝑤𝐿 で与えられる確率に従って抽出される．

SIR • 再サンプルされた値の累積分布は σ𝑙 𝐼 𝑧 𝑙 ≤ 𝑎 𝑝෤ 𝐳 𝑙 /𝑞 𝐳 𝑙 𝑝 𝑧 ≤ 𝑎 = ෍ 𝑤𝑙 = σ𝑚=1 𝑝෤ 𝐳 𝒎 /𝑞 𝐳 𝑚 𝑙 𝑙:𝑧 ≤𝑎 • 𝐼 ⋅ は指示関数で引数が真のとき1，そうでなければ0となる． • 𝐿 → ∞のっ極限を取り，分布に適切な正規性を仮定することで，サンプリング 分布に従って重み付けされた積分で和を書き換えることが出来る． ∫ 𝑝 𝑧≤𝑎 = 𝐼 𝑧 ≤ 𝑎 𝑝෤ 𝑧 𝑞 𝑧 𝑑𝑧 ∫ 𝐼 𝑧 ≤ 𝑎 𝑝෤ 𝑧 𝑑𝑧 𝑞 𝑧 = = න𝐼 𝑧 ≤ 𝑎 𝑝 𝑧 𝑑𝑧 𝑝෤ 𝒛 𝑝෤ 𝒛 𝑑𝑧 ∫ 𝑞 𝑧 𝑑𝑧 ∫ 𝑞 𝑧 • つまり，累積分布を求めるために，𝑝 𝑧 の正規化は必要ない．

モンテカルロEMアルゴリズム • EMアルゴリズムで，Eステップを解析的に実行できないモデルに対して，サンプリ ング法を用いてEステップを近似することが出来る． • 隠れ変数𝐙，観測変数𝐗，パラメタ𝜽を持つモデルを考える． • Mステップで𝜽に関して最適化される関数は完全データの対数尤度の期待値である． • 𝑄 𝜽, 𝜽old = ∫ 𝑝 𝐙 𝐗, 𝜽old ln 𝑝 𝐙, 𝐗 𝜽 𝑑𝐙 • サンプリング法を用いて，事後分布の現在の推定𝑝 𝐙 𝐗, 𝜽old から抽出されたサンプ ル𝑍𝑙 の有限和を用いて積分を近似できる． 1 • 𝑄 𝜽, 𝜽old ⋍ 𝐿 σ𝐿𝑙=1 ln 𝑝 𝐙 𝒍 , 𝐗 𝜽 • その後𝑄関数はMステップで通常の方法で最適化される． • この手続きはモンテカルロEMアルゴリズムと呼ばれる．

モンテカルロEMアルゴリズム • このアルゴリズムを事前分布𝑝 𝜽 が定義されれいるときに𝜽の事後分布のモー ド（MAP推定値）を見つける問題に適用できる． • これを実現するには，Mステップを実行する前に，単に𝑝 𝜃 を𝑄 𝜽, 𝜽old に追 加すれば良い．

確率的EM • 有限の混合モデルを考え，各Eステップで一つのサンプルしか抽出しない確率的 EMという手法がある． • ここで，隠れ変数𝐙は𝐾個の混合要素のうちのどの要素が各データ点を生成する かを表現するとし，𝐗はデータ集合を表すとする． • 例えば，混合ガウス分布の場合，隠れ変数𝐙はどのガウス分布から生成されたかを表す インディケータである．つまり， 𝐙はone-hotである． • Eステップでは，𝐙の一つのサンプルが事後分布𝑝 𝐙 𝐗, 𝜽old から抽出される． • 𝐙は𝐾要素×データ点数の行列である．これは各データ点を混合要素の一つへhard assignmentした結果を表す． • Mステップでは，事後分布に対するサンプル近似を用いて，モデルのパラメタを 通常のEMアルゴリズムのように更新する．

IPアルゴリズム • パラメタベクトル𝜽の事後分布からサンプリングしたいとする． • 本当は，同時事後分布か𝑝 𝜽, 𝐙 𝐗 からサンプリングしたいが，計算量的に難 しいとする． • さらに，パラメータの事後分布𝑝 𝜃 𝐙, 𝐗 からサンプリングすることは比較的 簡単であるとする． • これらから，Iステップ（imputation step）とPステップ(posterior step)と呼 ばれる2つのステップを交互に行うデータ拡張アルゴリズムが導かれる．

IPアルゴリズム • Iステップ • 𝑝 𝐙 𝐗 からサンプリングしたいが，直接できないとする． • 𝑝 𝐙 𝐗 = ∫ 𝑝 𝐙 𝜽, 𝐗 𝑝 𝜽 𝐗 𝑑𝜽の関係に着目し，まず， 𝑝 𝜽 𝐗 の現在の推定を 利用しサンプル 𝜽 𝑙 𝑙 = 1, … , 𝐿 を抽出する． • 次に，これを用い 𝑝 𝐙 𝜽, 𝐗 からサンプル𝐙 𝑙 を抽出する． • Pステップ • 𝑝 𝜃 𝑋 = ∫ 𝑝 𝜃 𝑍, 𝑋 𝑝 𝑍 𝑋 𝑑𝑍が与えられたとき，サンプル𝑍を用いて𝜃の事後 分布に対する推定をする． 1 • 𝑝 𝜃 𝑋 ≃ σ𝐿𝑙=1 𝑝 𝜃 𝑍, 𝑋 𝐿

マルコフ連鎖モンテカルロ

マルコフ連鎖モンテカルロ • マルコフ連鎖モンテカルロは，様々な種類の分布からサンプリングすることを 可能にし，サンプル空間の次元数が大きくなってもよく機能する． • マルコフ連鎖モンテカルロも提案分布からサンプリングを行う． • しかし，現在の状態𝐳 𝜏 を保持し，提案分布は𝑞 𝐳 𝐳 𝜏 とする． • このため，サンプルの系列𝐳 1 , 𝐳 2 , …はマルコフ連鎖をなす． • ここでも，𝑝 𝐳 = 𝑝෤ 𝐳 /𝑍𝑝 と考える．𝑍𝑝 の値は分からないかもしれないが， 𝑝෤ 𝐳 は簡単に計算できるとする． • 提案分布はサンプルを直接簡単に抽出できるように十分単純なものを選ぶ． • アルゴリズムの各サイクルで，サンプル候補𝐳 ⋆ を提案分布から生成し適切な基 準に従ってサンプルを受理する．

Metropilisアルゴリズム • 対象な提案分布を用意する． • つまり，𝐳A， 𝐳𝐵 のすべての値に対し𝑞 𝒛𝐴 𝒛𝐵 = 𝑞 𝒛𝐵 𝒛𝐴 であると仮定する． • サンプル候補は次の確率で受理される． • 𝐴 𝐳 ⋆, 𝐳 𝜏 𝑝෤ 𝐳⋆ 𝑝 𝐳𝜏 = min 1, ෤ • これは，区間 0,1 の一様分布から乱数𝑢を選択し，𝐴 𝐳 ⋆, 𝐳 𝜏 > 𝑢の場合にサンプルを受理する ことで達成される． • 𝐳 𝜏 から𝐳⋆へのステップが𝑝 𝐳 を増加させるのならば，𝐳⋆ は必ず受理される． • サンプル候補が受理された場合，𝑧 (𝜏+1) = 𝑧 ∗とする． • 破棄された場合は， 𝑧 (𝜏+1) = 𝑧 (𝜏) とする． • 棄却された場合，サンプルの複数のコピーが存在することになる． • 連続したサンプルは高い相関を持つ．もし，独立なサンプルを得たい場合は，連続したサンプ ルから𝑀個おきのサンプル取り出しそれを保持すれば良い．𝑀が十分大きければ，保持したサ ンプルは実際上の目的ではどんな場合でも独立と考えて良い．

受け入れ確率 𝐴 𝐳 𝜏+1 , 𝐳 𝜏 • 提案分布は𝑞 𝒛𝐴 𝒛𝐵 = 𝑞 𝒛𝐵 𝒛𝐴 であると仮定する． • マルコフ連鎖の遷移確率は • 𝑇 𝐳 𝜏 → 𝐳 𝜏+1 • マルコフ連鎖が定常状態における確率変数の値の出現確率（不変分布）が対象分布𝑝 𝒛 になれば良いと考えるから，詳細釣り合い条件は • 𝑝 𝐳 𝜏 𝑇 𝐳 𝜏 → 𝐳 𝜏+1 • 𝑝 𝐳 𝜏 𝑞 𝐳 𝜏+1 • 𝑝 𝐳 𝜏 𝐴 𝐳 𝜏+1 , 𝐳 𝜏 • この式が成り立つには， • 𝐴 𝐳 𝜏+1 , 𝐳 𝜏 • もしくは • 𝐴 𝐳 𝜏+1 , 𝐳 𝜏 • でなければならない．つまり， 𝐴 𝐳 𝜏+1 , 𝐳 𝜏 • 𝐴 𝐳 𝜏+1 , 𝐳 𝜏 は確率だから，0から1の値しか取れない．よって，受け入れ確率は次のようになる． • 𝐴 𝐳 𝜏+1 , 𝐳 𝜏 = 𝑞 𝐳 𝜏+1 = 𝐳 𝜏 𝐴 𝐳 𝜏+1 , 𝐳 𝜏 と表す． = 𝑝 𝐳 𝜏+1 𝑇 𝐳 𝜏+1 → 𝐳 𝜏 𝐳 𝜏 𝐴 𝐳 𝜏+1 , 𝐳 𝜏 = 𝑝 𝐳 𝜏+1 𝑞 𝐳 𝜏 𝐳 𝜏+1 𝐴 𝐳 𝜏 , 𝐳 𝜏+1 = 𝑝 𝐳 𝜏+1 𝐴 𝐳 𝜏 , 𝐳 𝜏+1 𝑝 𝐳 𝜏+1 𝑝 𝐳𝜏 , 𝐴 𝐳 𝜏 , 𝐳 𝜏+1 = 1, 𝐴 𝐳 𝜏 , 𝐳 𝜏+1 = min 1, 𝑝 𝐳 𝜏+1 𝑝 𝐳𝜏 = =1 𝑝 𝐳𝜏 𝑝 𝐳 𝜏+1 = 𝑝 𝐳 𝜏+1 𝑝 𝐳𝜏 or 1である．

1次マルコフ連鎖 • 1次マルコフ連鎖とは，確率変数の系列𝐳 1 , … , 𝐳 𝑀 が𝑚 ∈ 1, … , 𝑀 − 1 につい て次の条件付き独立性が成り立つものとして定義される． • 𝑝 𝐳 𝑚+1 𝐳 1 ,…,𝐳 𝑚 = 𝑝 𝐳 𝑚+1 𝐳𝑚 • １次マルコフ連鎖は，初期変数の確率分布𝑝 𝐳 0 と遷移確率𝑇𝑚 𝐳 1 , 𝐳 1 𝑝 𝐳 𝑚+1 ≡ 𝐳 𝑚 の形で後続変数の条件付き確率を与えることで指定できる． • すべての遷移確率が同じマルコフ連鎖は均一マルコフ連鎖と呼ばれる．

不変 • 特定の変数の周辺確率は連鎖における一つ前の変数の周辺確率を用いて表され る． • 𝑝 𝐳 𝑚+1 = σ𝐳 𝑚 𝑝 𝐳 𝑚+1 𝐳𝑚 𝑝 𝐳𝑚 • これが各ステップで変わらないとき，その分布はその連鎖に関して不変，ある いは定常であると呼ばれる． • 均一マルコフ連鎖のおいて， • 𝑝⋆ 𝐳 = σ𝐳′ 𝑇 𝐳 ′ , 𝐳 𝑝⋆ 𝐳 ′ • が成り立つ場合，分布𝑝⋆ 𝐳 は不変である． 式だけ見ると同時分布を周辺化している ように見えるのでいつも不変になるよう に思えるが，不変でない場合はどんなと きだろうか？ 例えば，周期的な連鎖，時間変化する遷 移行列，吸収状態がある場合など不変で ない．

不変であることの保証 • 求めたい分布𝑝 𝐳 が不変分布であることを保証する十分条件は，分布 𝑝⋆ 𝐳 に ついて • 𝑝⋆ 𝐳 𝑇 𝐳, 𝐳 ′ = 𝑝⋆ 𝐳 ′ 𝑇 𝐳 ′ , 𝐳 • で定義される詳細釣り合い条件(detailed balance)が満たされるように遷移確 率を選ぶことである． • 詳細釣り合い条件を満たす遷移確率が，その分布を不変にすることは， • σ𝐳′ 𝑝⋆ 𝐳 ′ 𝑇 𝐳 ′ , 𝐳 = σ𝐳′ 𝑝⋆ 𝐳 𝑇 𝐳, 𝐳 ′ = 𝑝⋆ 𝐳 σ𝐳′ 𝑝 𝐳 ′ ∣ 𝐳 = 𝑝⋆ 𝐳 • が成り立つことで分かる． • 詳細釣り合い条件を満たすマルコフ連鎖は可逆であると呼ばれる．

平衡分布 • 我々の目的は，与えられた分布からのサンプリングをマルコフ連鎖を用いて行 うことである． • 求めたい分布が不変分布となるようなマルコフ連鎖を用意すれば，これを達成 することができる． • しかし，𝑚 → ∞のとき，初期分布𝑝 𝐳 0 によらず，分布𝑝 𝐳 𝑚 が求めたい不 変分布 𝑝⋆ 𝐳 に収束する必要もある． • この性質はエルゴード性と呼ばれ，このとき不変分布は平衡分布と呼ばれる．

Metropolis-Hasting アルゴリ ズム

Metropolis-Hastingアルゴリズム • アルゴリズムのある特定のステップ𝜏を考える． • 現在の状況が𝐳 𝜏 であるとき，分布𝑞𝑘 𝐳 𝐳 𝜏 からサンプル𝐳 ⋆ を抽出し，確率 𝐴𝑘 𝐳 ⋆ , 𝐳 𝜏 に従って受理する． • 𝐴𝑘 𝐳 ⋆ , 𝐳 𝜏 𝑝෤ 𝐳⋆ 𝑞𝑘 𝐳 𝜏 𝐳⋆ = min 1, 𝑝෤ 𝐳 𝜏 𝑞𝑘 𝐳 ⋆ 𝐳 𝜏 • 𝑘は考えられる可能な遷移の集合の要素を表すラベルである． • 遷移確率が対象であれば，Metropolis-Hasting規準は，Metropolis規準と合致 する． 𝑝෤ 𝐳 は正規化されていない近似分布もしくは目標分布と思う． 遷移行列（マルコフ連鎖）を複数想定している．

詳細釣り合い条件 • 次に詳細釣り合い条件を計算してみる．釣り合い上限は次のとおりである． • 𝑝 𝐳 𝑇 𝐳, 𝐳 ′ = 𝑝 𝐳 ′ 𝑇 𝐳′ , 𝐳 • Metropolis-Hastingアルゴリズムでは， 𝑝 𝐳 𝑇 𝐳, 𝐳′ は • 𝑝 𝐳 𝑇 𝐳, 𝐳′ = 𝑝 𝐳 𝑞𝑘 𝐳′ 𝒛 𝐴𝑘 𝒛′ , 𝒛 • である．これは𝐳 ′ が𝐳からサンプルされる確率である． 𝑝 𝐳′ 𝑞𝑘 𝒛 𝒛′ 𝑝 𝐳 𝑞𝑘 𝐳′ 𝒛 𝑝 𝐳 𝑞𝑘 𝐳′ 𝒛 𝑝 𝐳′ 𝑞𝑘 𝒛 𝒛′ = min 𝑝 𝐳 𝑞𝑘 𝐳 𝐳′ , = min 𝑝 𝐳 𝑞𝑘 𝐳′ 𝒛 , 𝑝 𝐳′ 𝑞𝑘 𝒛 𝒛′ 𝑝 𝐳 𝑞𝑘 𝐳′ 𝒛 𝑝 𝐳 𝑞𝑘 𝐳′ 𝒛 = 𝑝 𝐳′ 𝑞𝑘 𝐳 𝜏 𝐳′ min , 1 = 𝑝 𝐳′ 𝑞𝑘 𝒛 𝒛′ 𝐴𝑘 𝐳, 𝒛′ 𝑝 𝐳′ 𝑞𝑘 𝒛 𝒛′ 𝑝 𝐳 𝑞𝑘 𝐳′ 𝒛 𝐴𝑘 𝐳′ , 𝐳 = 𝑝 𝐳 𝑞𝑘 𝐳′ 𝒛 min 1, • よって， 𝑝 𝐳 𝑇 𝐳, 𝐳′ = 𝑝 𝐳 𝑇 𝐳′ , 𝐳 が成り立つので，詳細釣り合い条件を満たす． 同時にMetropolis-Hastingアルゴリズムで定義される • マルコフ連鎖での𝑝 𝐳 は不変分布である．

ギブスサンプリング

ギブスサンプリング • サンプリングしたい確率分布𝑝 𝑧 = 𝑝 𝑧1 , … , 𝑧𝑀 を考える． • そして，マルコフ連鎖の初期状態としてある状態を選択したとする． • ギブスサンプリングでは，各ステップで1つの変数の値が置き換えられる． • 1つの変数を更新するとき，残りの変数の値を固定した条件での，対象の変数の条件 付き確率に従って抽出した値を用いる． • つまり，𝑧𝑖 を分布p(𝑧𝑖 ∣ 𝒛\𝑖 )から抽出された値で置き換える． 𝒛\𝑖 は𝑧1 , … , 𝑧𝑀 から𝑧𝑖 を 除いたものを表す．

変数が３つの場合 • 例えば，３変数の分布𝑝 𝑥1 , 𝑥2 , 𝑥3 があるとする． 𝜏 𝜏 𝜏 • アルゴリズムのステップ𝜏で，値 𝑧1 ， 𝑧2 ， 𝑧3 が得ているとする． 𝜏 𝜏 • まず， z1 を条件付き分布𝑝 z1 𝑧2 , 𝑧3 𝜏+1 からサンプリングした値 z1 に置 き換える． 𝜏+1 を用い， z2 を条件付き分布𝑝 z2 𝑧1 𝜏+1 に置き換える． 𝜏+1 と z2 • 次に z1 た値 z2 • 次に z1 𝜏+1 𝜏+1 𝜏 からサンプリングし , 𝑧3 𝜏+1 を用い， z3 を条件付き分布𝑝 z3 𝑧1 プリングした値に置き換える． • この作業を３つの変数について順番に繰り返す． 𝜏+1 , 𝑧2 からサン

ギブスサンプリングが使える条件 • 分布𝑝 𝒛 がギブスサンプリングの各ステップにおいて不変であり，故にマルコ フ連鎖全体でも不変である． • エルゴード性を満たす． • エルゴード製の十分条件 • 条件付き分布の確率が０とならない． • ０となる場合があれば，繰り返し計算によって，いずれ変数ベクトルがある値に収束し，サ ンプリングをしても同じ値しか出なくなる． • ０でなければ，𝑧空間での任意の点へ別の点から到達可能である．

ギブスサンプリングとMetropolis-Hastingsアルゴリズム • ギブスサンプリングはMetropolis-Hastingsアルゴリズムの特別な場合として得る ことができる． • Metropolis-Hastingサンプリングにおける一つのステップで，変数𝑧𝑘 を扱い，残り の変数𝒛\kを固定し，𝒛から 𝒛⋆ への遷移確率が𝑞𝑘 𝒛⋆ ∣ 𝒛 = 𝑝 𝑧𝑘⋆ 𝒛\k で与えられる と考える． • ギブスサンプリングでは，１つの 変数𝑧𝑘 のみ変更されるため， 𝒛⋆\k = 𝐳\kである． • また，𝑝 𝒛 = 𝑝 𝑧𝑘 𝐳\k 𝑝 𝐳\k である． • よって，Metropolis-Hastingにおける受理確率を決定する因子は次のようになる． • 𝐴 𝒛⋆ , 𝒛 𝑝 𝒛⋆ 𝑞𝑘 𝒛 𝒛⋆ = 𝑝 𝒛 𝑞 𝒛⋆ 𝒛 𝑘 ⋆ ⋆ ⋆ 𝑝 𝑧𝑘 𝒛\k 𝑝 𝒛⋆\k 𝑝 𝑧𝑘 𝒛\k = ⋆ 𝑝 𝑧𝑘 𝐳\k 𝑝 𝐳\k 𝑝 𝑧𝑘 𝐳\k ⋆ 𝑝 𝑧𝑘 𝐳\k 𝑝 𝐳\k 𝑝 𝑧𝑘 𝐳\k = ⋆ 𝑝 𝑧𝑘 𝐳\k 𝑝 𝐳\k 𝑝 𝑧𝑘 𝐳\k • よって，Metropolis-Hastingsステップは常に受理される． =1