1. 序章

このチュートリアルでは、マルコフ連鎖モンテカルロアルゴリズム（MCMC）について説明します。 ランダムサンプルから分布を概算する方法です。 具体的には、マルコフ連鎖と呼ばれる確率モデルを使用します。 MCMCの一種であるいわゆるメトロポリス・ヘイスティングスアルゴリズムを具体的に見ていきます。

2. マルコフ連鎖とは何ですか？

マルコフ連鎖は、ある状態から別の状態に移行する可能性の高さの説明です。この移行の確率は、それによって前の状態にのみ依存します。 これらの転送確率は既知である必要があることに注意してください。そうでない場合、隠れマルコフモデルが正しい選択である可能性があります。 マルコフ連鎖がどのように機能するかを明確にするために、例を見てみましょう。

2.1. 例

毎日メニューを変更するレストランがあります。 シェフはとてもシンプルな人なので、彼が作る料理は魚かパスタだけです。 彼が調理する食品の選択は、次の確率で説明できます。

は、Aが昨日の食べ物Bを与えられた今日の食べ物であることを意味します。たとえば、昨日すでに調理された魚を与えられたシェフが魚を調理する確率は20％です。

2.2. 平衡状態

マルコフ連鎖の言語におけるもう1つの重要な用語は、平衡状態です。 マルコフ連鎖の定義を見ると、1週間後、またはそれ以上の将来に魚が発生する可能性がどの程度高くなるかがわかります。 この確率を計算するために、テーブルを行列に変換します。

     

ここで、前日からの料理を前提として、1週間の魚の確率を計算します。 これを行うには、行列をそれ自体で7回乗算するだけです。

   

これで、このマトリックスは将来さらに遠くでどのように動作するのでしょうか。 答えは、この行列は、それ自体で十分な回数乗算された後、いわゆる平衡状態に達するということです。 したがって、マトリックスはそれ以上自己乗算した後も変化しなくなります。次の図では、前日の魚を想定した確率を確認できます。前日は非常に似ています：

その理由は、平衡行列でわかるように、同じ平衡確率を持っているためです。

   

すべてのマルコフ連鎖が定常状態にあるわけではないことに注意してください。 この条件を満たすものを構築する方法については、後で説明します。

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

以下では、MCMCアルゴリズムの一種であるいわゆるメトロポリス・ヘイスティングアルゴリズムについて説明します。 私たちの目標は、サンプルを抽出する分布に比例する分布を見つけることです。これをと呼びましょう。

そのために、マルコフ連鎖を利用して、前に描いたサンプルの1つがどの程度確率であるかをモデル化します。マルコフ連鎖の説明ですでに見たように、この確率を形式化できます。なので：

、最後のサンプルであり、現在のサンプルです。 アルゴリズムを詳しく調べてみましょう。

3.1. メトロポリス-ヘイスティング

アルゴリズムを段階的に見ていきましょう。

すでに述べたように、必要なのはサンプル関数と、アルゴリズムに反復させたいいくつかのステップだけです。 MCMCは、十分な数のステップの後、常にターゲット分布に収束するように構築されます。

アルゴリズムから取得するのは、マルコフ連鎖がその定常分布と状態の配列にどれだけ近いかを示す受け入れ率です。 状態は、最後のサンプルが与えられたときに現在のサンプルを取得する確率を表します。 したがって、これは0から1までの数値です。 後で、状態の配列からヒストグラムを作成して、ターゲット分布を受け取ることができます。

まず、開始点として乱数を生成します。これをと呼びます。

これに続いて、ループをステップスルーし、毎回次のステップを実行します。

  • 以前のディストリビューションから新しいサンプルを生成し、プラグインします
  • 古いサンプルを前提として、新しいサンプルの可能性を確認します。 ご覧のとおり、を使用しています。つまり、描画する分布のスケーリングは重要ではありません。 したがって、結果として、後部を知らなくても計算可能になります
  • この条件付き確率が、マルコフ連鎖に状態を追加するのに十分高いかどうかを確認します。 そうでない場合は、古い状態をチェーンに追加します。 次に、新しい現在の状態を使用して、新しいサンプルを生成します。 この手順は、ランダムウォークとも呼ばれます。

このアルゴリズムを使用すると、確率の高い領域から確率の低い領域に変更するたびに、受け入れ確率が低くなるため、確率の高い領域にとどまることができます。

3.2. 受け入れ確率

Metropolis-Hastingsアルゴリズムの中心には、受け入れ確率があります。 どうすればそのような式を導き出すことができますか？ そしてさらに重要なのは、それが事後分布に向かって収束することをどのように保証できるかということです。

最初からマルコフの例に戻ると、チェーンが平衡状態にあることを思い出します。 この状態は定常状態とも呼ばれます。 これをアルゴリズムからマルコフ連鎖に適用すると、連鎖が定常状態に収束するにつれて、ターゲット分布に向かって収束することに注意してください。

マルコフ連鎖が静止状態に収束するには、次の平衡条件を満たす必要があります。

   

これは次のように書くことができます：

   

これに続いて、いわゆる受け入れ分布を定義することができます。 それは状態を受け入れる確率を記述し、によって形式化することができます

   

.

与えられた状態を受け入れる確率を記述します。 したがって、次のように定式化できます。

   

.

最後のステップでは、サンプルを受け入れるための基準を選択するだけです。 メトロポリスの受け入れ基準を選択します。

   

3.3. おもちゃの例

結果として得られるマルコフ連鎖で何ができるかを確認し、メトロポリス-ヘイスティングスアルゴリズムのアプリケーションの見通しをつかむために、例を見てみましょう。 この問題については、分散が3の正規分布のサンプルを使用します。

プロットでは、事後分布の確率密度関数を確認できます。 この分布は直接わかりません。それに比例し、サンプリングする数値関数のみがわかります。

次のステップでは、この分布からサンプリングし、結果のマルコフ連鎖のヒストグラムをプロットします。

5000ステップ後、サンプルが事後分布に向かって収束し始める様子をすでに確認できます。

100 000ステップ後、サンプルがどれだけうまく収束するかを確認できます。

他の興味深い例には、すなわち メッセージの復号化およびモンテカルロ木探索。

4. 他のサンプリングアルゴリズムとの比較

MCMCアルゴリズムを使用して1D分布からサンプリングしましたが、その主な用途は多次元問題の分布分析にあります。 1Dの場合の主な欠点は、サンプルが相関しているという事実にあります。したがって、サンプリング解像度が低くなります。 これは、適応棄却サンプリングなどの他のタイプのサンプリングアルゴリズムによって解決できます。

MCMCアルゴリズムで発生する別の課題は、マルコフ連鎖がターゲット分布に向かってどれだけ速く収束するかです。 このプロパティは、パラメータの数とMCMCアルゴリズムの構成に大きく依存します。 ハミルトニアンモンテカルロアルゴリズムは、サンプル間に大きなステップを生成することでこの課題を解決し、さらにサンプル間の相関を小さくします。

5. 結論

この記事では、MCMCアルゴリズム、具体的にはメトロポリス-ヘイスティングス変種を段階的に説明しました。 分布からサンプルを選択することにより、マルコフ連鎖を作成する方法を見てきました。 さらに、このチェーンが事後分布に向かって収束することを証明しました。 続いて、具体的な例でアルゴリズムを適用する方法と、他の方法と比較する方法について説明しました。