Product Design, Manufacturing & Innovation Resources
家 » メトロポリス・ヘイスティングスアルゴリズム

メトロポリス・ヘイスティングスアルゴリズム

1970
  • Nicholas Metropolis
  • Arianna W. Rosenbluth
  • Marshall N. Rosenbluth
  • Augusta H. Teller
  • Edward Teller
  • W. Keith Hastings
現代の研究室でメトロポリス・ヘイスティングスアルゴリズムを適用する統計学者。

(画像はイメージです)

メトロポリス・ヘイスティングスアルゴリズムは、 MCMC method for obtaining a sequence of random samples from a probability distribution for which direct sampling is difficult. At each iteration, it generates a candidate for the next sample based on the current sample. This candidate is then accepted or rejected with a certain probability, ensuring the resulting chain converges to the desired distribution.

このアルゴリズムは、 マルコフ連鎖 その定常分布が目標分布 [latex]P(x)[/latex] である。現在の状態を [latex]x_t[/latex] とする。まず、提案分布 [latex]Q(x’|x_t)[/latex] から候補状態 [latex]x'[/latex] が生成される。提案分布は、サンプリングが容易な任意の分布 (例えば、[latex]x_t[/latex] を中心とするガウス分布) である。次に、受理確率 [latex]alpha(x’, x_t)[/latex] を計算します。 [latex]alpha(x’, x_t) = minleft(1, frac{P(x’)Q(x_t|x’)}{P(x_t)Q(x’|x_t)}right)[/latex]。 [latex][0, 1][/latex] の一様分布から乱数 [latex]u[/latex] を抽出します。 [latex]u le alpha[/latex] の場合、候補は受理され、次の状態は [latex]x_{t+1} = x'[/latex] に設定されます。そうでない場合は、候補は拒否され、チェーンは現在の状態のままになります。[latex]x_{t+1} = x_t[/latex]。

この受容率の優れた点は、比例定数を除いて [latex]P(x)[/latex] を知るだけでよいことです。これは、正規化定数が分数 [latex]frac{P(x’)}{P(x_t)}[/latex] で相殺されるためです。これは、事後分布が扱いにくい周辺尤度までしかわからないことが多いベイズ統計学において非常に重要です。オリジナルのメトロポリスアルゴリズム (1953 年) は、提案分布 [latex]Q[/latex] が対称である、つまり [latex]Q(x’|x_t) = Q(x_t|x’)[/latex] という特殊なケースであり、受容確率は [latex]minleft(1, frac{P(x’)}{P(x_t)}right)[/latex] に単純化されます。ヘイスティングスの1970年の一般化により、非対称な提案分布が可能になり、アルゴリズムの適用範囲と効率が大幅に拡大しました。

UNESCO Nomenclature: 1209
統計

タイプ

ソフトウェア/アルゴリズム

混乱

実質的な

使用法

広く普及している

前駆物質

  • メトロポリスアルゴリズム(1953年)
  • マルコフ連鎖における詳細均衡理論
  • モンテカルロ 統合
  • ベイズ確率論

アプリケーション

  • シミュレーションする ボルツマン分布 統計力学において
  • 機械学習におけるベイズ推論
  • シミュレーテッドアニーリングによる複雑な最適化問題の解決
  • リスクモデリングのための計算ファイナンス
  • 信号処理 および画像再構成

特許:

NA

潜在的なイノベーションのアイデア

  • adaptive MCMC algorithms that tune the proposal distribution on the fly
  • hamiltonian monte carlo for more efficient exploration of the state space
  • reversible-jump MCMC for models with a varying number of parameters
  • pseudo-marginal MCMC for models with intractable likelihoods
  • parallel tempering to overcome getting stuck in local modes of a distribution
  • automated model selection in complex statistical problems
  • inference in deep generative models like variational autoencoders
  • probabilistic robotics for robot localization and mapping (SLAM)
  • cryptanalysis by sampling from distributions of possible keys
  • algorithmic trading strategies based on bayesian forecasting
関連キーワード:メトロポリス・ヘイスティングス法、MCMC、ベイズ統計、受容拒否、提案分布、定常分布、マルコフ連鎖、サンプリング、統計力学、シミュレーテッドアニーリング。

歴史的背景

メトロポリス・ヘイスティングスアルゴリズム

1960
1967
1967
1970
1970
1970
1970-01-01
1960
1960
1967
1970
1970
1970
1970
1973

(日付が不明または関連性がない場合、例えば「流体力学」などでは、その注目すべき出現時期の概算値が提示されます。)

10年目 周年

フルサイズの画像とダウンロードは、登録会員のみが100%無料で利用できます。