マルコフ連鎖モンテカルロ(MCMC)法とベイズ推定
MCMCは「マルコフ連鎖モンテカルロ法」(Markov Chain Monte Carlo Method)の略で、多変量の確率分布からサンプルを抽出する(乱数を発生する)ためのアルゴリズムの一つとなる。
MCMCは単なる計算方であり、タスクを解くためには、MCMCで解ける様に問題を整理する作業(統計モデリング)が必要となる。算数の文章題で、加減乗算の計算そのものより「何を計算するか」が肝心なのと同様なものとなる。
最小二乗法で曲線をあてはめたり、最尤法で確率分布のパラメータを推定するのに必要なものは「行列の分解」や「最適化」となる。それらは目的が「一つの決まった曲線や数字」(点推定値)を直接求めるものである為で、それに対してベイズ統計では「答」はまず「事後分布」という「分布」の形で与えられる。そこで、分布からのサンプルを生成するMCMCとの相性が抜群となる。点推定値や誤差、予測区間など、最終的に必要な情報はMCMCで生成した多数のサンプルから求める。
MCMCと最適化の違いは、MCMCがずっと動き続けてサンプリングを生成するのに対して、最適化はどこか(うまくいくときには本当の最適解、うまくいかないときは曲初回)で止まる。実際には、MCMCも最適化に近い動きをすることもあるが、その場合でも最適解のまわりでいつまでも「ごにょごにょ」と動いて、ベイズの意味での誤差を表現する。MCMCの「収束」とは、分布の収束なので、ある一点二位ってそこで止まると言う意味ではない。
MCMCは確率分布を扱う汎用の手法で、統計物理や頻度論的な統計学でも使われる。逆にベイズ統計では、ラプラス近似、カルマンフィルタ、逐次モンテカルロ法、変分ベイズ法などいろいろな計算法が使われていて、MCMCはその中の一つとなる。
MCMCは大雑把に言うと、数値的に一様乱数を生成して、それを使った単純な操作の繰り返しで、状態(確率変数の値)をランダムにちょっとずつ変えていくものとなる。そのやり方で「ギブス・サンプラー」「メトロポリス法」「ハミルトニアン・モンテカルロ法」などの様々なアプローチがある。そういった確率的操作の繰り返しをうまく設計して、狙った分布(ベイズ統計なら事後分布)からのサンプリングを実現する。
MCMCを使う上での注意点は、MCMCが「乱数を使った単純な繰り返しで確率密度の大きいところを探しながら、サンプルを生成する」という手法となるので、実際の例でうまく動くかどうかは結果オーライの面がある。「数字を大小の順に並び替える」といったアルゴリズムでは、ソースコードを見れば動きが完全にわかるが、それらとは扱いが異なり、実行結果を見て挙動がおかしい場合は、モデルやデータ、やろうとしていることにどこか無理があることが多いので、それらを振り返ってMCMCの挙動との関係をチェックすることが必要になる。
本ブログではMCMCに関して以下について述べる。
実装
マルコフ連鎖モンテカルロ法(Markov Chain Monte Carlo, MCMC)は、確率分布からのサンプリングや積分計算を行うための統計的手法となる。MCMCは、マルコフ連鎖(Markov Chain)とモンテカルロ法(Monte Carlo)の組み合わせとなる。ここでは、このMCMCに対して、様々なアルゴリズムと適用事例および実装例について述べている。
ベイズ推定のような複雑な複率分布の積分計算を解析的に行うことは困難であり、マルコフ連鎖モンテカルロ(Markov Chain Monte Carlo;MCMC)法がよく用いられる。これは基本的な乱択アルゴリズムの一種で、最も単純なモンテカルロ法は、パラメータの候補として乱数を発生し、その乱数に対応する確率(積分)を計算するものだが、このような総当たり的な手法では、パラメータの数が増えると爆発的に計算量が増え効率的でないのに対して、完全にランダムではなく、ひとつ前の乱数を元に少しずつ確率の大きな値を探索(マルコフ確率場の探索)しつつ次の乱数次の乱数を発生するアルゴリズムとなる。
以前、Rstanについては紹介したが、PythonでのMCMCの実装としてはPystan、PyMC3がある。また、Rstanは2020年から更新されておらず、StanチームもCmdStanを奨励しているらしいことから、今回はCmdStanのrのラッパーであるCmdStanrと同様にCmdStanのシンプルなラッパーであるclj-stanについて述べてみたいと思う。
今回は具体的なアルゴリズムであるメトロポリス法の概要について述べる。
メトロポリス法では、初期値x(0)から次のような手順で、x(1)、x(2)、…、x(k)、x(k+1),…を構成する。(1)実数Δxをランダムに選び、x’=x(k)+Δxをx(k+1)の候補として提案する。ただし、詳細釣り合い条件を満たすためにΔxと-Δxが同じ確率で現れるものとする。(今回は、適当なc>0を選んで-cと+cの間の一様乱数を生成することにする)、(2)メトロポリステスト:0と1の間の一様乱数rを生成し、𝑟<𝑒𝑆(𝑥(𝑘))−𝑆(𝑥′)なら提案を受理してx(k+1)=x’と更新する。さもなくば、提案を棄却してx(k+1)=x(k)とする。
さらに、C言語を使った具体的なメトロポリス法のコードについて述べる
メトロポリス法を使ったシミュレーションとして、2つのガウス分布を重ねたもの、半円とガウス分布を重ねたものについて適用し、ステップ数とシミュレーション結果の関係等に対する考察を行う。
- 確率積分計算の為のMCMC法(1):多変数メトロポリスアルゴリズム
今回はMCMC法が威力を発揮する「次元の呪い」を持つ多変数の場合について述べ、多変数になることで生じる注意点や新しいアルゴリズムについて述べる。
一変数のメトロポリス法を多変数に拡張するには、まず変数を(x1,x2,…,xn)とする。ここで、多変数になったことで、サンプルの集め方に大きく分けて二つの選択肢が出てくる。一つは「まとめて更新」、もう一つは「一つずつ更新」となる。
変数がたくさんある場合「まとめて更新」では、ステップ幅ciを小さくとらないと更新確率が小さくなってしまう。それと比べて「一つずつ更新」ではステップ幅を比較的大きく保つことが可能となる。
本ブログではまとめて更新アルゴリズムのC言語コードを具体的に述べている。
- 確率積分計算の為のMCMC法(2):メトロポリス法以外のアルゴリズム(HMC法)
今回はメトロポリス法以外のアルゴリズムであるHMC(Hybrid Monte Calro法、あるいはHamiltonian Monte Carlo法)について述べる。
HMC法の、名前の由来は、メトロポリス法と分子動力学法という二つの異なる手法を組み合わせた「ハイブリッド(Hybrid)」なモンテカルロ法(MC)だという意味になる。また物理学におけるハミルトニアンの運動方程式とそれに現れるハミルトニアンという量の類似物を使うという意味でHamiltonian Monte Carloとも呼ばれる。
本ブログではHMC法の具体的なC言語のコードについて述べている。
- 確率積分計算の為のMCMC法(3):メトロポリス法以外のアルゴリズム(ギブスサンプリング、MH法)
今回はギブスサンプリングとMH法について述べる。今回述べるギブスサンプリング(物理業界では熱浴法とも呼ばれる)は、適用できる場面は限られるが、適用可能な場合には効率が良いアルゴリズムとなる。これはベイズ統計等の比較的素直な分布に対して適用可能な事が多い。
まずはシンプルなガウス分布に対するアルゴリズムをベースにC言語でのコードについて述べる。ギブスサンプリングではメトロポリステストがない分だけシンプルなコードとなる。
理論と応用
MCMC法は様々な分野に応用が効く数値計算のテクニックとなる。数値計算の中でもそれらが力を発揮するシーンとしては「複雑な積分をしたい」と「複雑な確率の計算をしたい」というもので、歴史的には物理の分野で広く用いられてきた。近年では、統計学の重要な道具として定着し、統計学的手法が重要な機械学習、金融などの分野でも用いられるようになっている。
量子物理学、ベイズ統計、組み合わせ最適化問題などの応用問題は、分野の違いはあったとしても、多くの問題が最終的には確率と期待値の問題に帰着され、MCMC法がその威力を発揮する。そのためある程度MCMC法の基礎を理解しておけば、分野に関係なく自分で調べたいことができた時に、目的に合わせたコードが書け、他人の書いた複雑なアルゴリズムも理解できるようになる。
ここではそれらを理解できるためのベースとして、まずなぜMCMC法が必要なのか、またMCMC法の基本的な理論(確率と期待値とモンテカルロ法(乱数によるアプローチ))について述べる。
- MCMC法の一般論:モンテカルロ法にマルコフ連鎖を適用する
今回はマルコフ連鎖モンテカルロ法の一般論として前述したモンテカルロ法にマルコフ連鎖を適用することについて述べる。
マルコフ連鎖モンテカルロ法の基本条件として以下の4つがある。(1)マルコフ連鎖であること:すなわち、{x(k)}から{x(k+1)}が得られる確率が過去の履歴{x(0)}、{x(1)}、・・・、{x(k-1)}には依らず、{x(k)}だけで決まること。この確率をT({x(k)}→{x(k+1)})と表す。(Tは遷移確率(transition probability)を表す)、(2)既約性:あらゆる変数の組{x}、{x’}は有限回のステップで移り合うことが可能、(3)非周期性:ステップ数nsで{x}から{x}に戻ってくることができるとする。nsとしては色々な値が考えられるが、その最大公約数を周期と呼ぶ。すべての{x}に対して周期が1である時、そのようなマルコフ鎖は非周期的であると言う、詳細釣り合い条件(詳細平衡条件):あらゆる{x}、{x’}に対して遷移確率TがP({x})・T({x}→{x’}) = P({x’})・T({x’}→{x}) →を満たすこと。
これらが成り立つ確率分布関数の元でモンテカルロ(ランダムサンプリング)法を行う。
- マルコフ連鎖モンテカルロ法の応用例 (1):ベイズ推定
今回はマルコフ連鎖モンテカルロ法の応用例について述べる。
まずマルコフ連鎖モンテカルロ法の統計学への応用について述べる。ここで確率計算の作用関数が与えられれば、マルコフ連鎖モンテカルロ法で尤度は計算できる。今回の例ではメトロポリス法、HMC法、ギブスサンプリング法のどれを使っても容易に計算できる。
メトロポリス法とHMC法は、もっと複雑な分布に対しても適用できるだけではなく、それほど頭を使わないでプログラムを書けるという点でも非常に優れている。
ギブスサンプリング法は、プログラムを書くのは手間がかかるが、パラメータ調節の必要がないので、類似の問題を何度も解く必要がある場合やすでに誰かの書いたプログラムをそのまま使える場合にはギブスサンプリング法が有効となる。
- マルコフ連鎖モンテカルロ法の応用例(2):イジング、組み合わせ最適化、素粒子物理
今回はイジング、組み合わせ最適化、素粒子物理等の応用について述べる。大学の物理(統計力学)の授業で定番のスピン(小さな磁石)が載った格子点の最適化を考えるイジング模型について述べる。(物理現象の相変化のシミュレーション)
次に組合せ最適化の典型的な問題である巡回セールスマン問題にマルコフ連鎖モンテカルロ法を適用したものについて述べる。
マルコフ連鎖モンテカルロ法(MCMC)では、局所解にひっかかるような問題では、単純なアルゴリズムだとうまく答えが出ない場合がある。これらに対する対策として、まず「動かし方を工夫して、たくさんの要素を同時に動かす」というものがある。たとえば、分割表のサンプリングでは代数幾何などを利用して複雑な動かし方が研究されていたり、ラテン方陣でも研究が行われている。
これに対して最も手軽に実装できる方法が、シミュレーテッド・アニーリング法であり、それらを改良した、分布からのサンプリングを正しく行う手法群(拡張アンサンブル法)であるレプリカ交換モンテカルロ法となる。
コメント
[…] 自然言語処理等に活用される確率生成モデルで用いられるマルコフ連鎖モンテカルロ法(MCMC)について述べられた「ゼロからできるＭＣＭＣ マルコフ連鎖モンテカルロ法の実践的入門」より。今回はMCMCの導入のための確率と期待値とモンテカルロ法について述べる。 […]
[…] 確率関数の積分等に用いられるマルコフ連鎖モンテカルロ | Deus Ex Machina より: 2021年12月23日 7:28 PM […]
[…] 自然言語処理等に活用される確率生成モデルで用いられるマルコフ連鎖モンテカルロ法(MCMC)について述べられた「ゼロからできるＭＣＭＣ マルコフ連鎖モンテカルロ法の実践的入門」より。前回はメトロポリス法以外のアルゴリズムであるHMC法について述べた。今回はギブスサンプリングとMH法について述べる。 […]
[…] 本ブログでは以下のページにこのMCMCの原理、実装(アルゴリズム)、ベイズ推定や組合せ最適化等の応用について述べている。 […]
[…] 機械学習技術サマリー 確率生成モデルサマリー マルコフ連鎖モンテカルロ法サマリー 時系列データ解析サマリー […]
[…] 機械学習技術サマリー 確率生成モデルサマリー マルコフ連鎖モンテカルロ法サマリー […]
[…] マルコフ連鎖モンテカルロ(MCMC)法とは […]
[…] 自然言語処理等に活用される確率生成モデルで用いられるマルコフ連鎖モンテカルロ法(MCMC)について述べられた「ゼロからできるＭＣＭＣ マルコフ連鎖モンテカルロ法の実践的入門」より。前回はマルコフ連鎖モンテカルロ法の一般論としてモンテカルロ法へのマルコフ連鎖の適用について述べた。今回は具体的なアルゴリズムであるメトロポリス法の概要について述べる。 […]
[…] 機械学習技術サマリー 人工知能技術サマリー 自然言語処理技術サマリー 確率的生成モデルサマリー マルコフ連鎖モンテカルロ法サマリー アルゴリズムサマリー デジタルトランスフォーメーション技術サマリー […]
[…] 機械学習技術サマリー 人工知能技術サマリー 自然言語処理技術サマリー 確率的生成モデルサマリー マルコフ連鎖モンテカルロ法サマリー アルゴリズムサマリー デジタルトランスフォーメーション技術サマリー […]
[…] 機械学習技術サマリー 人工知能技術サマリー 自然言語処理技術サマリー 確率的生成モデルサマリー マルコフ連鎖モンテカルロ法サマリー アルゴリズムサマリー デジタルトランスフォーメーション技術サマリー […]
[…] 自然言語処理等に活用される確率生成モデルで用いられるマルコフ連鎖モンテカルロ法(MCMC)について述べられた「ゼロからできるＭＣＭＣ マルコフ連鎖モンテカルロ法の実践的入門」より。前回はメトロポリス法以外のアルゴリズムであるギブスサンプリングとMH法について述べた。今回はマルコフ連鎖モンテカルロ法の応用例について述べる。 […]
[…] 自然言語処理等に活用される確率生成モデルで用いられるマルコフ連鎖モンテカルロ法(MCMC)について述べられた「ゼロからできるＭＣＭＣ マルコフ連鎖モンテカルロ法の実践的入門」より。前回はマルコフ連鎖モンテカルロ法の応用例としてベイズ推定について述べた。今回はイジング、組み合わせ最適化、素粒子物理等の応用について述べる。 […]
[…] 機械学習技術サマリー 人工知能技術サマリー デジタルトランスフォーメーション技術サマリー 自然言語処理技術サマリー マルコフ連鎖モンテカルロ法サマリー 深層学習技術サマリー 確率生成モデルサマリー トピックモデルサマリー […]
[…] 機械学習技術サマリー 人工知能技術サマリー デジタルトランスフォーメーション技術サマリー 自然言語処理技術サマリー マルコフ連鎖モンテカルロ法サマリー 深層学習技術サマリー 確率生成モデルサマリー トピックモデルサマリー […]
[…] 機械学習技術サマリー 人工知能技術サマリー デジタルトランスフォーメーション技術サマリー 自然言語処理技術サマリー マルコフ連鎖モンテカルロ法サマリー 深層学習技術サマリー 確率生成モデルサマリー トピックモデルサマリー […]
[…] 機械学習技術サマリー 人工知能技術サマリー デジタルトランスフォーメーション技術サマリー 自然言語処理技術サマリー マルコフ連鎖モンテカルロ法サマリー 深層学習技術サマリー 確率生成モデルサマリー トピックモデルサマリー […]
[…] 機械学習技術サマリー 人工知能技術サマリー デジタルトランスフォーメーション技術サマリー 自然言語処理技術サマリー マルコフ連鎖モンテカルロ法サマリー 深層学習技術サマリー 確率生成モデルサマリー トピックモデルサマリー […]
[…] 機械学習技術サマリー 人工知能技術サマリー デジタルトランスフォーメーション技術サマリー 自然言語処理技術サマリー マルコフ連鎖モンテカルロ法サマリー 深層学習技術サマリー 確率生成モデルサマリー トピックモデルサマリー […]
[…] 機械学習技術サマリー 人工知能技術サマリー デジタルトランスフォーメーション技術サマリー 自然言語処理技術サマリー マルコフ連鎖モンテカルロ法サマリー 深層学習技術サマリー 確率生成モデルサマリー トピックモデルサマリー […]
[…] 機械学習技術サマリー 人工知能技術サマリー デジタルトランスフォーメーション技術サマリー 自然言語処理技術サマリー マルコフ連鎖モンテカルロ法サマリー 深層学習技術サマリー 確率生成モデルサマリー トピックモデルサマリー […]
[…] 機械学習技術サマリー 人工知能技術サマリー デジタルトランスフォーメーション技術サマリー 自然言語処理技術サマリー マルコフ連鎖モンテカルロ法サマリー 深層学習技術サマリー ノンパラメトリックベイズとガウス過程 確率的生成モデルサマリー […]
[…] 機械学習技術サマリー 人工知能技術サマリー デジタルトランスフォーメーション技術サマリー 自然言語処理技術サマリー マルコフ連鎖モンテカルロ法サマリー 深層学習技術サマリー ノンパラメトリックベイズとガウス過程 確率的生成モデルサマリー […]
[…] 機械学習技術サマリー 人工知能技術サマリー デジタルトランスフォーメーション技術サマリー 確率的生成モデルサマリー ベイズ推論とMCMCのフリーソフト マルコフ連鎖モンテカルロ法サマリー […]
[…] 機械学習技術 人工知能技術 デジタルトランスフォーメーション技術 自然言語処理技術 マルコフ連鎖モンテカルロ法 深層学習技術 確率生成モデル […]
[…] 機械学習技術 人工知能技術 デジタルトランスフォーメーション技術 自然言語処理技術 マルコフ連鎖モンテカルロ法 深層学習技術 確率生成モデル トピックモデル […]
[…] 機械学習技術 人工知能技術 デジタルトランスフォーメーション技術 自然言語処理技術 マルコフ連鎖モンテカルロ法 深層学習技術 確率生成モデル トピックモデル […]
[…] 機械学習技術 人工知能技術 デジタルトランスフォーメーション技術 自然言語処理技術 マルコフ連鎖モンテカルロ法 深層学習技術 確率生成モデル トピックモデル […]
[…] 機械学習技術 人工知能技術 デジタルトランスフォーメーション技術 自然言語処理技術 マルコフ連鎖モンテカルロ法 深層学習技術 確率生成モデル トピックモデル […]
[…] <マルコフ連鎖モンテカルロ(MCMC)法> […]
[…] 機械学習技術 人工知能技術 デジタルトランスフォーメーション技術 自然言語処理技術 マルコフ連鎖モンテカルロ法 深層学習技術 ノンパラメトリックベイズとガウス過程 確率的生成モデル […]
[…] 機械学習技術 人工知能技術 デジタルトランスフォーメーション技術 自然言語処理技術 マルコフ連鎖モンテカルロ法 深層学習技術 ノンパラメトリックベイズとガウス過程 異常検知と変化検知技術 時系列データ解析 確率的生成モデル […]
[…] なお、ギブスサンプリングを含めたMCMCの詳細に関してはマルコフ連鎖モンテカルロ法にて、グラフィカルモデルの詳細に関しては、ベイズ推論とグラフィカルモデルによる機械学習にて […]
[…] ムは、パラメータ空間を効率的に探索し、事後分布からのサンプルを生成することができる。MCMCの詳細に関しては”マルコフ連鎖モンテカルロ(MCMC)法とベイズ推定“を参照のこと。 […]
[…] 画像情報処理技術 ベイズモデリングの世界 自然言語処理技術 マルコフ連鎖モンテカルロ法 知識情報処理 深層学習技術 強化学習 説明できる機械学習 […]
[…] アルゴリズム 自然言語処理技術 深層学習技術 トピックモデル マルコフ連鎖モンテカルロ法 python R言語 異常検知・変化検知技術 時系列データ解析 […]
[…] 自然言語技術 人工知能技術 デジタルトランスフォーメーション技術 マルコフ連鎖モンテカルロ法 深層学習技術 確率生成モデル トピックモデル オントロジー技術 […]
[…] “マルコフ連鎖モンテカルロ(MCMC)法とベイズ推定“にも述べられているモンテカルロ法は、確率的な手法を用いて数値的に解析する手法であり、ベイズ推定などの確率モデルの解 […]
[…] アルゴリズム 自然言語処理技術 深層学習技術 トピックモデル マルコフ連鎖モンテカルロ法 python R言語 異常検知・変化検知技術 時系列データ解析 […]