MCMC-Verfahren

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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 hinreichende, aber nicht notwendige, Bedingung, dass ein MCMC-Verfahren den kanonischen Zustand als stationäre Verteilung aufweist, ist die Detailed Balance-Eigenschaft.

Konvergenz des Metropolis-Hastings-Algorithmus.Die blaue Verteilung soll durch die Orangene approximiert werden.

Üblicherweise gelingt es leicht, eine Markow-Kette mit den erwünschten Eigenschaften zu konstruieren. Das Schwierigere 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 finden sich bei der numerischen Berechnung mehrdimensionaler Integrale. Diese finden sich oft im Rahmen der Bayesschen Statistik sowie rechnerischen Anwendungen in der Physik (beispielsweise der Statistischen Physik oder Pfadintegralen in der Quantenfeldtheorie) und der Biologie/Bioinformatik (bei der Proteinstrukturvorhersage).

Beispiel[Bearbeiten]

Angenommen, wir können eine diskrete Gleichverteilung auf  \{0,1\} simulieren. Dies entspricht dem Wurf einer fairen Münze mit  P(\{1\})=P(\{0\})=0{,}5 , wobei "1=Kopf" und "0=Zahl" sein soll. Nun wollen wir aber eine Verteilung auf  S=\{1,2,3 \} simulieren mit  P_Z(\{1\})=0{,}2 und  P_Z(\{2\})=P_Z(\{3\})=0{,}4 . Dazu definieren wir eine Markow-Kette, bei der alle Übergangswahrscheinlichkeiten simuliert werden können (sprich 0,5 , 0 oder 1 sind) und die die Verteilung  P_Z als stationäre Verteilung hat. Folgendes Vorgehen bildet eine Markow-Kette, welche die Voraussetzungen erfüllt: Befindet man sich im Zustand 1, gehe nach 2. Befindet man sich im Zustand 2, werfe eine Münze. Zeigt sie Kopf, gehe zu 3, ansonsten verharre in der 2. Befindet man sich im Zustand 3, werfe eine Münze. Zeigt sie Kopf, gehe zu 1, ansonsten verharre in der 3. Diese Markow-Kette wird durch die folgende Übergangsmatrix beschrieben:

M = \begin{bmatrix}
0 & 1 & 0  \\
0 & 0{,}5 & 0{,}5 \\
0{,}5 & 0 & 0{,}5 
\end{bmatrix}.

Es gilt, dass  M^3 >0 ist, die Markow-Kette also irreduzibel und aperiodisch ist, und daher konvergiert die Markow-Kette für jede beliebige Startverteilung  v_0 gegen die stationäre Verteilung  \pi=P_Z

Für die Simulation starten wir nun im Zustand 1. In der Tabelle findet sich jeweils der Simulationsschritt, dann die exakte Aufenthaltswahrscheinlichkeit in der 1. Diese konvergiert nach Voraussetzung gegen 0,2. In der letzten Spalte steht die relative Häufigkeit der 1 bei Eintausend Simulationen. Diese nähert sich im Laufe der Zeit der stationären Verteilung an. Lässt man also die Simulation lange laufen und lässt sich dann ein Ergebnis ausgeben, so ist diese Stichprobe  P_Z verteilt.

Schritte  k  P(X_k=1) Relative Häufigkeit der 1
in Tausend Simulationen
0 1 1
1 0 0
2 0 0
3 0,25 0,228
4 0,25 0,271
5 0,185 0,173
6 0,185 0,176
7 0,2031 0,236
8 0,2031 0,180
9 0,1992 0,202
10 0,1992 0,171
11 0,2002 0,205
12 0,2002 0,198
13 0,2000 0,190
14 0,2000 0,206

Algorithmen[Bearbeiten]

Beispiele für Markov-Chain-Monte-Carlo-Verfahren sind:

  • Metropolisalgorithmus: Das lokale Verfahren erzeugt Zufallsbewegungen, die mit einer gewissen Wahrscheinlichkeit akzeptiert oder zurückgewiesen werden. Es ist einfach zu implementieren, hat jedoch den Nachteil einer hohen Autokorrelation der erzeugten Systemzustände.
  • Gibbs-Sampling (auch Wärmebadalgorithmus genannt): Das lokale Verfahren ist ein Sonderfall des Metropolis-Hastings-Algorithmus, bei dem die Zustände entsprechend der lokalen Wahrscheinlichkeitsverteilung erzeugt werden.
  • Hybrid-Monte-Carlo-Algorithmus: Das Verfahren stellt eine Kombination aus Molekulardynamik und Zufallsbewegung her. Die Molekulardynamik wird benutzt, um effizient neue, unabhängige Zustände zu erzeugen, die mit einer gewissen Wahrscheinlichkeit akzeptiert oder zurückgewiesen werden.
  • Clusteralgorithmen: Hierbei handelt es sich um spezielle, nicht-lokale Verfahren, die die Autokorrelationzeiten und damit das so genannte Critical Slowing down, vermeiden. Sie wurden erstmals von Swendsen und Wang für das Potts-Modell eingeführt. Allerdings sind nur wenige Systeme bekannt, für welche das Verfahren implementiert werden konnte.
  • Over-Relaxation-Verfahren

Literatur[Bearbeiten]

  • Jeff Gill: Bayesian methods: a social and behavioral sciences approach. Second Edition, Chapman and Hall/CRC, London 2008, ISBN 978-1-58488-562-7.
  •  N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller und E. Teller: Equation of State Calculations by Fast Computing Machines. In: Journal of Chemical Physics. 21, 1953, S. 1087-1092, doi:10.1063/1.1699114.
  •  W.K. Hastings: Monte Carlo Sampling Methods Using Markov Chains and Their Applications. In: Biometrika. 57, 1970, S. 97-109.
  •  R.H. Swendsen, J.-S. Wang: Nonuniversal critical dynamics in Monte Carlo simulations. In: Phys. Rev. Lett.. 58, 1987, S. 86.
  •  S.L. Adler: Overrelaxation method for Monte Carlo evaluation of the partition function for multiquadratic actions. In: Phys. Rev. D. 23, 1988, S. 2901.
  • Thomas Müller-Gronbach, Erich Novak, Klaus Ritter: Monte Carlo-Algorithmen. Springer-Verlag, Berlin 2012, ISBN 978-3-540-89140-6, Kapitel 6, S. 179-244.