メトロポリス・ヘイスティングス法
数学や物理において、メトロポリス・ヘイスティングス法(もしくは M-H アルゴリズム)("Metropolis-Hastings algorithm")　は直接サンプリングするのが難しい確率分布から統計標本の配列を生成するのに用いられるマルコフ連鎖を構築するのに用いられる手法である。この配列はマルコフ連鎖モンテカルロ法において、目標分布の近似（ヒストグラム）として用いられたり、期待値のような積分計算を必要とするものに用いられる。
このアルゴリズムは1953年にボルツマン分布のための特殊形で発表したニコラス・メトロポリスと 1970年にそれを一般化した W.K. ヘイスティングスにちなんで名づけられた。ギブスサンプリング法はM-H アルゴリズムの特殊形であり、通常より高速で、簡易に利用することができるが、応用範囲は狭まる。
M-H アルゴリズムは、確率分布formula_1 の確率密度関数に比例する関数が計算できるならば、
いかなる確率分布 formula_1 からでもサンプルを得ることができる。
ベイジアンの応用においては正規化係数を計算するのが非常に難しいため、得たい確率分布に一致する必要がなく、その密度関数に比例すればいい点はM-H アルゴリズムの大きな長所である。
M-H アルゴリズムはサンプル列を生成する。
サンプルがあればあるほど、そのサンプル分布は目標の分布P(x)を近似することになる。
サンプルは反復して生成され、次のサンプルが生成される確率は現在のサンプルにのみ依存する。（このサンプル列はマルコフ連鎖である。）
このサンプルの選択方法がアルゴリズムの重要な点である。候補となるサンプルはある確率で採択か棄却が決まる。
採択とは候補となるサンプルが次のステップで使用されることで、棄却とは次のステップでも現在のサンプルが使用されることである。この採択確率はP(x)に関する現在のサンプルと次のサンプルの尤度を比較して決定される。
以下では簡単な説明のために、M-H アルゴリズムの１例であるメトロポリスアルゴリズムを示す。
メトロポリスアルゴリズム
formula_3を目標分布formula_4に比例する関数とする。このアルゴリズムは移動したり、ある点にとどまったりを繰り返しランダムにサンプル空間を動きまわる。採択率は、提案分布と現在のサンプルにしたがって生成されるサンプルがどれだけ採択されうるかを表す。現在のサンプルよりも次のサンプルの確率が高ければ、必ず次のサンプルを採択する。しかし次のサンプルの確率が高くない場合、ある確率で移動せずにサンプルを棄却する。このため、高い確率密度の領域からは多くのサンプルを、また低い確率の領域は少ないサンプルを生成することになる。直感的にはこれがアルゴリズムの仕組みであり、目的の確率分布に従ったサンプルを生成する方法である。
分布から直接独立サンプルを生成するM-H アルゴリズムや他のMCMCアルゴリズムなどの適応的棄却サンプリング
と比べいくつかの短所がある。
長い時間サンプルを生成しても、近接したサンプルは相関をもち、分布を正しく反映したものではない。これは独立したサンプルを得たい場合、多くのサンプルを捨てなければならないことを意味し、formula_28個飛ばしでサンプルを集めたりする。このformula_28の値は通常は近接サンプル間の自己相関を計算し決められる。サンプルされる領域を広げると自己相関は減少させることができるが、提案されたサンプルの棄却確率を増加させることになる。適切なジャンプサイズではない場合、遅い混合のマルコフ連鎖となる。これはつまり、サンプルが高い相関をもつことで目標とする分布を精確に推定するために非常に多くのサンプルが必要となることを意味する。このアルゴリズムで生成されたマルコフ連鎖が目標の分布に収束されることは保証されているが、
初期値が低い確率の領域であったり、初期値が悪いとうまくいかない場合がある。その対策としてburn-inの期間は通常は必要である。そのため、始めの数千、万サンプルは捨てられる。
多くの棄却サンプリング法は次元の呪いの影響を受ける。次元の呪いとは棄却確率が次元数の関数として指数関数的に増加することである。他のMCMC法と同様にM-Hアルゴリズムではこの次元の問題を同程度には持たないため、サンプル空間の次元が高い場合には唯一の可能な解法となる。そのためMCMC法は、現在では多くの分野で使用されている階層ベイズモデルや高次元な統計モデルからのサンプルを生成する方法として選ばれている。
次元が高い場合には、個々の次元ごとに異なった振る舞いをすることや、遅い混合を避けるためにすべての次元に関して適切なジャンプの大きさを決定することが問題となるため、提案分布を適切に選択することが自体が困難である。
そのような状況でしばしば取られる代替案としてはギブスサンプリングがある。ギブスサンプリングは、すべての次元から一度にサンプルするのではなく、個々の次元に関してサンプリングを行う。
これは多くの典型な階層モデルにあるように、少数の変数が他の変数を条件付けている場合には有効な方法である。
個々の変数は他の変数に関して条件づけされて１度にサンプリングされる。
他には適応的棄却サンプリング、一次元M-H ステップ、スライスサンプリングが考えられる。
提案密度 formula_30 が formula_31 に一切依存しないことも可能であり、その場合はアルゴリズムは「独立連鎖メトロポリス・ヘイスティングス法」という(それ以外は「酔歩連鎖メトロポリス・ヘイスティングス法」である)。
ふさわしい提案分布を持った独立連鎖M-Hアルゴリズムは酔歩連鎖法よりも高い精度があるが、目標分布に関して"アプリオリ"の知識を必要とする。
M-H アルゴリズムは目標確率分布formula_4に従ったサンプルの生成を行うことが目的である。
これを達成するために、漸近的に唯一の定常分布π(x)に収束するマルコフ連鎖を用いる。
マルコフ過程は、２つの状態間の遷移確率formula_33によって一意に定義される。
２つの条件が満たされるとき、マルコフ過程は定常分布formula_34をもつ。
これはマルコフ過程のエルゴード性から保証される。エルゴード性はすべての状態が非周期的（aperiodic）でありかつ正再帰でなければならない。非周期とは系が固定距離である状態にもどることができないことであり、正再帰とは非ゼロの確率である全ての状態に遷移可能である。
M-H アルゴリズムは遷移確率の構成により、上記の２つの条件を満たすようにマルコフ過程を設計することができる。
導出を詳細釣り合い条件から始める、
formula_45
これは、以下のように書き換えられる。
formula_46.
通常の手法として遷移確率を提案確率分布と採択確率分布に分解する。提案分布formula_47はformula_9が与えられたときの状態formula_37を提案する条件付き確率であり、採択確率formula_50はformula_9が与えられたときの状態formula_37を採択する条件付き確率である。
formula_53
この関係を以前の式に代入して以下の式を得る。
formula_54 .
次のステップとして、この式を満たす採択率を選ぶことが必要である。よくある選択として、メトロポリス選択が知られ以下の式で得られる。この値はアルゴリズムの実装に必要な値である。
formula_55
この式が前の式を満たすことは、formula_56 /formula_57かformula_57/formula_56 の少なくとも片方 が1以上になることから確認できる。
また、これはformula_56とformula_57を一般性を失うことなく入れ替えることができるからである。
実装の観点からはMetropolis–Hastings アルゴリズムは以下のステップから成り立っている。サンプルを適切に集めるためには、formula_68は提案分布や採択率とが別に決められ、ステップ４においてサンプルが相関していないことが必要である。マルコフ過程の自己相関時間の時間のオーダーによる。
一般的にこのパラメータの決定は簡単ではないことは重要な点である。問題に対して適切にパラメータは決定されるべきである。分布に関する知識が全くない場合には一様分布が提案分布として選ばれることもある。この場合、状態formula_9と状態formula_37はいつも相関しないためにformula_68の値はformula_73に設定される。
現時点のサンプル値は formula_74 であるとする。
メトロポリス・ヘイスティングス法では、次のサンプルformula_37は
確率密度関数 formula_76 に従い生成される。
そして以下の値を計算する。
ここで、
はサンプルの候補 formula_79 とその一つ前のサンプル formula_74 の尤度比であり、
は２つの提案分布(formula_74 から formula_79 へとその逆方向)の比率である。
提案分布が状態に関して対称の場合は formula_84 は 1 となる。
次に、以下のルールにもとづき新しい状態 formula_85 が選択される。
formula_86 の場合:
formula_88 の場合:
マルコフ連鎖はランダムな初期値 formula_93 から開始され、初期値が「忘れられる」まで、多くの試行を繰り返す。この間の標本は棄てられ、"burn-in"(機械や回路を通電した直後の安定しない状態からの比喩、初期通電)とよばれる。
burn-in'後の値 formula_9 の集合は、分布 formula_4 からのサンプルを表す。
M-Hアルゴリズムは提案分布 formula_96の形が、直接サンプリングが困難である目標分布 formula_1 の形と類似している場合、つまり formula_98 のときにうまくアルゴリズムが動作する。
しかし、多くの場合目標分布の形は未知である。
ガウス分布の提案分布 formula_99 が用いられる場合は、分散パラメータの formula_100 が burn-in 期間のうちに調整される必要がある。これは通常、"採択率"を計算することで行われる。採択率とは formula_101個のサンプルのうち採択されたサンプルの割合である。要求される採択率は目標分布によって異なる。理論的には、一次元ガウス分布を目標分布とすると理想的な採択率は約50% であり、N次元ガウス分布の目標分布では約 23% であることが知られている。
formula_100 が小さすぎるとサンプリング列は低速混合をおこす。
つまり採択率が高くなり標本空間の移動が遅くなる。
そのため formula_1 への収束が遅くなる。
逆に formula_100 が大きすぎると、
採択率が低すぎサンプルが確率密度の低い所に移動してしまい formula_105 が非常に小さくなってしまう。
このため formula_1 への収束が遅くなる。
したがって、提案分布のパラメータを調整し"採択率"を適切にする必要がある。M-H アルゴリズムの一例として
MCMCではない方法
モンテカルロEMアルゴリズム：EステップをサンプリングにしたEMアルゴリズム。