| dbpedia-owl:abstract
|
- Markov chain Monte Carlo (MCMC) methods (which include random walk Monte Carlo methods) are a class of algorithms for sampling from probability distributions based on constructing a Markov chain that has the desired distribution as its equilibrium distribution. The state of the chain after a large number of steps is then used as a sample of the desired distribution. The quality of the sample improves as a function of the number of steps. Usually it is not hard to construct a Markov chain with the desired properties. The more difficult problem is to determine how many steps are needed to converge to the stationary distribution within an acceptable error. A good chain will have rapid mixing—the stationary distribution is reached quickly starting from an arbitrary position—described further under Markov chain mixing time. Typical use of MCMC sampling can only approximate the target distribution, as there is always some residual effect of the starting position. More sophisticated MCMC-based algorithms such as coupling from the past can produce exact samples, at the cost of additional computation and an unbounded (though finite in expectation) running time. The most common application of these algorithms is numerically calculating multi-dimensional integrals. In these methods, an ensemble of "walkers" moves around randomly. At each point where the walker steps, the integrand value at that point is counted towards the integral. The walker then may make a number of tentative steps around the area, looking for a place with reasonably high contribution to the integral to move into next. Random walk methods are a kind of random simulation or Monte Carlo method. However, whereas the random samples of the integrand used in a conventional Monte Carlo integration are statistically independent, those used in MCMC are correlated. A Markov chain is constructed in such a way as to have the integrand as its equilibrium distribution. Surprisingly, this is often easy to do. Multi-dimensional integrals often arise in Bayesian statistics, computational physics, computational biology and computational linguistics, so Markov chain Monte Carlo methods are widely used in those fields. For example, see Gill and Robert & Casella.
- Markov-Chain-Monte-Carlo-Verfahren (kurz MCMC-Verfahren; seltener auch Markov-Ketten-Monte-Carlo-Verfahren) sind eine Klasse von Algorithmen, die Stichproben aus Wahrscheinlichkeitsverteilungen ziehen. Dies geschieht auf der Basis der Konstruktion einer Markow-Kette, welche die erwünschte Verteilung als ihre stationäre Verteilung aufweist. Der Zustand der Kette nach einer großen Zahl von Schritten wird dann als Stichprobe der erwünschten Verteilung benutzt. Die Qualität der Stichprobe steigt mit zunehmender Zahl der Schritte. MCMC-Verfahren erzeugen Systeme im kanonischen Zustand. Eine ausreichende, aber nicht nötige, Bedingung, dass ein MCMC-Verfahren den kanonischen Zustand als stationäre Verteilung aufweist, ist die Detailed Balance-Eigenschaft. Üblicherweise gelingt es leicht, eine Markow-Kette mit den erwünschten Eigenschaften zu konstruieren. Das schwierigere Problem ist es, zu ermitteln, wie viele Schritte nötig sind, um Konvergenz zur stationären Verteilung mit akzeptablem Fehler zu erreichen bzw. den Algorithmus so zu gestalten, dass möglichst effektiv, unabhängige Systemzustände generiert werden. Eine gute Kette mit einer gut gewählten Anfangsverteilung wird schnell konvergieren, d.h. die stationäre Verteilung wird schnell erreicht. Bei typischer Anwendung von MCMC-Verfahren kann die Zielverteilung nur näherungsweise erreicht werden, da es immer einen gewissen Resteffekt der Anfangsverteilung gibt. Häufige Anwendungen dieser Algorithmen findet sich bei der numerischen Berechnung mehrdimensionaler Integrale. Diese finden sich oft im Rahmen der Bayesianischen Statistik sowie rechnerischen Anwendungen in der Physik und der Biologie.
- マルコフ連鎖モンテカルロ法 (Markov chain Monte Carlo methods)(以下、MCMC と表記) とは、求める確率分布を均衡分布として持つマルコフ連鎖を作成することを基に確率分布のサンプリングを行うアルゴリズムの総称である。M-H アルゴリズムやギブスサンプリングなどのランダムウォーク法もこれに含まれる。充分に多くの回数の試行を行った後のマルコフ連鎖の状態は求める目標分布の標本として用いられる。試行の回数を増やすとともにサンプルの品質も向上する。 求められる特性を持つマルコフ連鎖を作成することは通常難しくない。問題は許容できる誤差内で定常分布に収束する試行の回数を決めることである。適する連鎖は任意の位置から始めて定常分布に速く達し、これを高速混合(rapid mixing)とよぶ。 典型的なMCMCは常にある程度の初期値の影響が残るため目標分布しか近似することができない。CFTP法(coupling from the past)など、より洗練されたMCMCベースのアルゴリズムは完全標本を作成することができるが、より多くの計算と(期待値では有限だが)限界のない実行時間を要する。 このアルゴリズムの最も一般的な応用は多重積分を数量的に計算することである。ランダムに歩き回る粒子の集団を想定し、粒子が点を通過するたびに、その点の被積分関数の値を積分に加算する。粒子は次に積分への貢献が高い所を探して複数の仮の動作をする。このような方法はランダムウォーク法とよばれ、これは乱数的なシミュレーションつまりモンテカルロ法の一種である。従来のモンテカルロ法で用いられる被積分関数のランダムな標本が独立であるのに対して、MCMCで用いられる標本は相関がある。被積分関数を均衡分布と持つようなマルコフ連鎖を作成する必要があるが、多くの場合において容易に行うことができる。 多重積分はベイズ統計学、計算物理学、計算生物学などにしばしば現れるため、そのような分野でMCMC法も広くつかわれている。例として、Gillや Robert & Casella を参照せよ。
- Les méthodes MCMC (pour Markov chain Monte Carlo) sont une classe de méthodes d'échantillonnage à partir de distributions de probabilité. Ces méthodes se basent sur le parcours de chaînes de Markov qui ont pour lois stationnaires les distributions à échantillonner. Certaines méthodes utilisent des marches aléatoires sur les chaînes de Markov, alors que d'autres algorithmes, plus complexes, introduisent des contraintes sur les parcours pour essayer d'accélérer la convergence Ces méthodes sont notamment appliquées dans le cadre de l'inférence bayésienne.
|
