Markov Chain Monte Carlo - Methoden: Herleitung, Beweis und Implementierung

In seiner Arbeit beschäftigt sich der Autor mit der Markov Chain Monte Carlo , auch abgekürzt als MCMC. Dabei handelt es sich um eine Monte Carlo Methode. Allen Monte Carlo Methoden ist gemein, dass sie von einer mehr oder minder komplizierten Verteilung zufällige Szenarien erzeugen. Diese Szenarien werden dann genutzt um Aussagen über Erwartungswerte oder andere Kennzahlen der Verteilung zu treffen. Diese Aussagen sind natürlich nur zu gebrauchen, wenn man sehr viele zufällig erzeugte Szenarien auswertet. Die Methode kommt also immer dann zum Einsatz, wenn es nicht möglich ist, aus der Verteilung der Szenarien direkt Rückschlüsse auf die statistischen Kennzahlen der Verteilung zu ziehen, weder auf analytischem Wege, noch durch numerische Integration (bei sehr vielen Dimensionen steigt der Aufwand rapide an).
Markov Chain Monte Carlo ist nun eine spezielle Monte Carlo Methode unter Zuhilfenahme von Markovketten. Diese kommt immer dann zum Einsatz, wenn es nicht möglich ist, von einer Verteilung auf einfache Weise Szenarien zu erzeugen. Eine Markovkette fängt bei einem Zustand an und geht von einem bestimmten Zustand mit einer bestimmten Wahrscheinlichkeit zu einem anderen Zustand über. Diese Übergangswahrscheinlichkeiten stehen in einer Übergangsmatrix. Der Knackpunkt ist nun, dass diese Form der Zustandsgenerierung oft einfacher zu implementieren ist, als direkt auf eine Verteilung zurückzugreifen. In der Arbeit gibt es mehrere konkrete Beispiele für den Einsatz solcher Methoden. Quelltexte der Implementierungen sind beigefügt.

Leseprobe:

Textprobe:
Kapitel 4.1: Problemstellung in diesem Abschnitt interessieren wir uns für Algorithmen, um Zählprobleme zu lösen. Um einige generelle Techniken zu zeigen, sollten wir uns noch mal dem Beispiel mit den möglichen q-Färbungen eines Graphen aus dem letzten Abschnitt zu wenden. Insbesondere werden wir sehen, wie sich die MCMC-Technik als nützlich in diesem Kontext erweist. Wenn man naiv an das Problem herangehen würde, könnte man glauben, das Problemlösen zu können, indem man einfach alle möglichen Konfigurationen, also Elemente von {1,...,q} V, in lexikographischer Reihenfolge durch geht und dann alle davon zählt, bei denen es sich um zulässige Konfigurationen handelt. Leider handelt es sich hierbei um einen sehr zeitaufwendigen Algorithmus, denn die Elemente von {1,...,q} V wachsen exponentiell mit der Mächtigkeit von V an. Insbesondere sind wir deshalb hier interessiert, Algorithmen zu finden, die eine polynomiale Laufzeit besitzen. Das bedeutet, dass ein Polynom p (k) in der Größe k des Problems existiert, sodass die Laufzeit begrenzt ist durch p (k), für jede Instanz des Problems der Größe k. Das ist dasselbe, wie nach Algorithmen zu fragen, deren Laufzeit durch Ck begrenzt ist, für irgendwelche Konstanten C und . In vielen Fällen können wir aber noch nicht einmal das erreichen und müssen uns mit Algorithmen zufriedengeben, die die Mächtigkeit der Menge aproximieren, d.h. deren Ausgabe sich irgendwo zwischen (1 )N und (1+ ) N befindet, wenn N die wahre Mächtigkeit der Menge ist. Die Fehlertoleranz erhält der Algorithmus als Eingabe, sodass der Fehler beliebig klein werden kann, wenn man dadurch eine größere Laufzeit in kauf nimmt, die aber immer durch ein Polynom p (k) in der Größe des Problems begrenzt ist. Leider können wir in vielen Fällen aber noch nicht einmal sicherstellen, dass sich das Ergebnis des Algorithmus immer innerhalb der vorgegbenen Fehlerschranken bewegt, sondern dies nur mit einer Wahrscheinlichkeit von 23 der Fall ist. Das bedeutet, dass wenn wir dem Algorithmus als Eingabe geben, dieser folgende Eigenschaften besitzt: 1. Mit einer Wahrscheinlichkeit von mindestens 23, gibt der Algorithmus eine Antwort im Bereich (1 ) N und (1+ ) N aus, wobei N die wahre Antwort des Zählproblems darstellt. 2. Für jedes 0 existiert ein Polynom p (k) in der Größe k des Problems, sodass für jedes Auftreten des Problems der Größe k der Algorithmus in höchstens p (k) Schritten terminiert. Ein solcher Algorithmus heißt zufälliges Polynom-Zeit Approximations-Schema. Dieser Abschnittbeschäftigt sich mit der Konstruktion eines solchen Schemas für die q-Färbungen von Graphen.