Blog

Markov-Chain-Monte-Carlo-Verfahren — ohne Mathematik

Für viele von uns ist die Bayes’sche Statistik bestenfalls Zauberei, schlimmstenfalls völlig subjektiver Unsinn. Unter den charakteristischen Merkmalen des Bayes’schen Ansatzes sind die Methoden des Markov-Chain-Monte-Carlo-Verfahrens besonders geheimnisvoll. Sie sind zwar mathematisch aufwändig und rechenintensiv, aber die Grundüberlegung dahinter – wie so vieles in der Statistik – kann intuitiv verständlich gemacht werden.

Monte was?

Also, was ist das Markov-Chain-Monte-Carlo-Verfahren (meist abgekürzt als MCMC)? Die kurze (und mathematische) Antwort lautet:

MCMC werden verwendet, um eine a-posteriori Verteilung eines Parameters zu schätzen, indem Zufallsstichproben aus einem Wahrscheinlichkeitsraum gezogen werden.

Soweit, so gut. Aber was heißt das genau?

Terminologie

Beginnen wir mit ein wenig Terminologie. Ein Parameter ist nur eine Zahl, die ein Phänomen zusammenfasst, das uns interessiert. Im Allgemeinen verwenden wir Statistiken zur Schätzung von Parametern. Zum Beispiel, wenn wir über die Größe der menschlichen Erwachsenen mehr wissen wollen, könnte unser Parameter die durchschnittliche Körpergröße in Zentimeter sein. Eine Verteilung ist eine mathematische Darstellung jedes möglichen Wertes unseres Parameters und wie wahrscheinlich es ist, dass wir ihn beobachten. Das bekannteste Beispiel ist die Glockenkurve:

In der Bayes’schen Statistik haben Verteilungen eine zusätzliche Bedeutung. Anstatt nur die Werte eines Parameters darzustellen und wie wahrscheinlich es ist, dass jeder einzelne der wahre Wert ist, denkt ein Bayesianer bei einer Verteilung, an eine Darstellung die unseren Glauben an einen Parameter beschreibt. Daher zeigt die Glockenkurve oben, dass wir ziemlich sicher sind, dass der Wert dieses bestimmten Parameters ziemlich nahe bei Null liegt, da dort die Kurve ihren Höhepunkt hat, aber wir denken, dass es eine gleiche Wahrscheinlichkeit gibt, dass der wahre Wert über oder unter diesem Wert liegt.

Wie sich herausstellt, gibt es einige Dinge in der Natur, die normalverteilt sind (ein Grund auch, weshalb die Normalverteilung so wichtig in der Statistik ist). Die Körpergröße (für ein Geschlecht) beispielsweise. So könnte eine Person beispielsweise davon ausgehen, dass die Körpergröße von Männern wie in der Verteilung unten aussieht:

Aber die Person lebte scheinbar unter Riesen, denn sie geht von einer durchschnittlichen Körpergröße von 190 cm aus!

Gehen wir nun davon aus, dass wir es jetzt genau wissen wollen und Männer in ganz Deutschland vermessen haben. Die Männer in der Stichprobe waren dabei allesamt zwischen 155 cm und 185 cm groß. Die Verteilung der von uns tatsächlich gemessenen Körpergrößen unserer Stichprobe ist im Diagramm unten in blau aufgetragen:

In Bayes’scher Statistik wird die Verteilung, die unsere Überzeugungen über einen Parameter repräsentiert, als Prior bezeichnet, da sie unsere Überzeugungen erfasst, bevor wir irgendwelche Daten gesehen haben. Die Likelihood-Verteilung hingegen umfasst die beobachteten Daten. Sie stellt die von uns beobachteten Daten dar und ordnet ihnen eine Wahrscheinlichkeit zu, die Likelihood, also eine Wahrscheinlichkeit, dass jeder Parameter die Daten erklärt, die wir beobachten. Die Schätzung des Parameterwertes, der die Likelihood-Verteilung maximiert, beantwortet nur die Frage: Welcher Parameterwert würde es am wahrscheinlichsten machen, die beobachteten Daten zu beobachten?

Der Schlüssel dieser Analyse liegt allerdings darin, dass wir die Prior-Verteilung und die Likelihood-Verteilung miteinander kombinieren und eine a-posteriori Verteilung bestimmen. Dies sagt uns, welche Parameterwerte die Chance maximieren, die jeweiligen Daten, unter Berücksichtigung unserer bisherigen Überzeugungen zu beobachten. In unserem Fall sieht die a-posteriori Verteilung so aus (unten in grün):

Oben stellt die grüne Kurve die a posteriori Verteilung dar (auch Posterior genannt). Man kann sie sich als eine Art Durchschnitt der Prior- und Likelihood-Verteilungen vorstellen. Da der Prior kürzer und weiter gestreut ist, stellt sie eine Reihe von Überzeugungen dar, die weniger sicher über den wahren Wert der durchschnittlichen menschlichen Größe sind. Unterdessen fasst die Likelihood-Verteilung die Daten in einem relativ engen Bereich zusammen, so dass sie eine sicherere Vermutung über den wahren Parameterwert darstellt.

Bei zwei Glockenkurven ist die Berechnung der a posteriori Verteilung sehr einfach. Es gibt eine einfache Gleichung, um beides zu kombinieren. Aber was ist, wenn unsere Prior- und Likelihood-Verteilungen nicht so konventionell sind? Manchmal ist es am genauesten, unsere Priors und Posteriors mit Hilfe von Verteilungen zu modellieren, die keine benutzerfreundliche Form haben. Was wäre beispielsweise, wenn unsere Likelihood-Verteilung am besten durch eine Verteilung mit zwei Maxima repräsentiert würde, und wir aus irgendeinem Grund einen wirklich verrückten Prior erklären wollten, so wie unten?

Wie schon zuvor gibt es auch hier eine a posteriori Verteilung, die die Wahrscheinlichkeit für jeden Parameterwert angibt. Aber anders als zuvor, ist es für diese Verteilung unmöglich sie analytisch zu bestimmen. Hier kommen MCMC-Methoden ins Spiel.

MCMC-Methoden erlauben es uns, die Form einer Posterior-Verteilung abzuschätzen, falls wir sie nicht direkt berechnen können. Erinnern wir uns, dass MCMC für die Markov-Chain-Monte-Carlo steht. Um zu verstehen, wie sie funktionieren, werde wir uns zuerst Monte-Carlo-Simulationen anschauen und dann Markov-Ketten diskutieren.

Monte-Carlo-Simulationen

Monte-Carlo-Simulationen sind eine Möglichkeit, einen konstanten Parameter durch wiederholtes Erzeugen von Zufallszahlen zu schätzen. Die Monte-Carlo-Simulationen liefern eine Annäherung an einen Parameter, bei dem eine direkte Berechnung unmöglich oder unverhältnismässig wäre.

Schauen wir uns mal hierfür ein Beispiel an. Angenommen, wir möchten die Fläche des folgenden Kreises schätzen:

Da wir wissen, welche Länge und Höhe das Quadrat hat, können wir dessen Fläche einfach als 10.000 cm² berechnen. Für den Kreis wird es schon schwieriger. Hier können wir jedoch 20 Punkte zufällig innerhalb des Quadrats fallen lassen. Dann zählen wir den Anteil der Punkte, die in den Kreis fielen, und multiplizieren diesen mit der Fläche des Quadrats. Diese Zahl ist eine ziemlich gute Annäherung an die Fläche des Kreises.

Da 16 der 20 Punkte innerhalb des Kreises liegen, sieht es so aus, als wäre der Kreis etwa 8.000 cm². Nicht schlecht für eine Monte-Carlo-Simulation mit nur 20 Zufallspunkten. Nur zum Vergleich: Der Kreis hat tatsächlich eine Fläche von 7853 cm².

Aber wie sieht es mit komplexeren Flächen aus? Dasselbe Prinzip kann auch verwendet werden, um beispielsweise die Fläche der Herzgleichung \(\left (y – \sqrt{|x|} \right )^2 + x^2 = 4\) zu berechnen:

Monte-Carlo-Simulationen werden nicht nur zur Abschätzung der Fläche schwieriger Formen eingesetzt. Durch die Generierung vieler Zufallszahlen können sehr komplizierte Prozesse modelliert werden. In der Praxis werden sie verwendet, um das Wetter vorherzusagen oder die Wahrscheinlichkeit eines Wahlsieges einzuschätzen. Auch im Bereich der künstlichen Intelligenzoder zum knacken von Codes werden MCMC-Verfahren eingesetzt.

Markov-Ketten

Das zweite Element zum Verständnis von MCMC-Methoden sind Markov-Ketten. Dabei handelt es sich lediglich um Abfolgen von Ereignissen, die in einem wahrscheinlichen Zusammenhang zueinander stehen. Jedes Ereignis kommt aus einer Reihe von Ergebnissen, und jedes Ergebnis bestimmt, welches Ergebnis als nächstes eintritt, entsprechend einer festen Reihe von Wahrscheinlichkeiten.

Ein wichtiges Merkmal von Markov-Ketten ist, dass sie gedächtnislos sind: Alles, was man braucht, um das nächste Ereignis vorherzusagen, ist im aktuellen Zustand verfügbar, und keine neuen Informationen kommen von der Kenntnis der Vergangenheit der Ereignisse hinzu. Das nächste Ergebnis hängt also nur vom aktuellen Zustand ab und nicht von einem der vorhergehenden Ergebnisse.

Ein Spiel wie Roulette zeigt diese Gedächtnislosigkeit, oder Markov-Eigenschaft. Ein Spieler setzt immer nur auf seine Glückszahl und denkt, dass mit jedem Mal, dass sie nicht drangekommen ist, die Wahrscheinlichkeit steigt, dass sie beim nächsten Mal drankommt. Dies ist allerdings ein Fehlschluss, den jedes Spiel ist unabhängig von dem vorherigen. Aber nur wenige Dinge in der realen Welt funktionieren tatsächlich so. Dennoch sind Markov-Ketten mächtige Werkzeuge, um die Welt zu verstehen.

Im 19. Jahrhundert wurde die Glockenkurve als typisches Muster in der Natur beobachtet. (Wir haben zum Beispiel oben festgestellt, dass menschliche Körpergrößen einer Glockenkurve folgen.) Pavel Nekrasov, ein russischer Mathematiker und Theologe, argumentierte, dass die Glockenkurve und ganz allgemein das Gesetz der großen Zahlen einfach Artefakte von Kinderspielen und trivialen Rätseln seien, bei denen jedes Ereignis völlig unabhängig sei. Er dachte, dass gegenseitige Abhängigkeiten in der realen Welt, wie menschliche Handlungen, nicht mit einfachen mathematischen Mustern oder Verteilungen in Einklang zu bringen seinen.

Andrey Markov, nach dem Markov-Ketten benannt sind, versuchte zu beweisen, dass auch nicht-unabhängige Ereignisse Mustern folgen können. Eines seiner bekanntesten Beispiele erforderte das Zählen von Tausenden von Zwei-Buchstaben-Paaren aus einem Werk der russischen Poesie. Anhand dieser Paare berechnete er die bedingte Wahrscheinlichkeit jedes Buchstaben. Das heißt, bei einem bestimmten vorhergehenden Buchstaben oder Leerzeichen gab es eine gewisse Chance, dass der nächste Buchstabe ein A, ein B oder ein Leerzeichen sein würde. Mit diesen Wahrscheinlichkeiten war Markov in der Lage, eine beliebig lange Folge von Zeichen zu simulieren. Das war eine Markov-Kette. Obwohl die ersten paar Zeichen weitgehend von der Wahl des Anfangszeichens bestimmt werden, zeigte Markov, dass sich die Verteilung der Zeichen langfristig in einem Muster niederschlägt. So entsprechen auch voneinander abhängige Ereignisse, wenn sie festen Wahrscheinlichkeiten unterliegen, einem Durchschnitt.

Beispiel: Wettervorhersage

Nehmen wir als Beispiel die Wettervorhersage. Tatsächlich werden MCMC-Verfahren auch in einigen Wettermodellen eingesetzt, um Vorhersagen zu treffen. Wir sammeln Daten über das Wetter für einen längeren Zeitraum. Dabei gehen wir davon aus, dass das Wetter zu einem bestimmten Zeitpunkt alles ist, was wir brauchen, um das Wetter  für den nächsten Zeitpunkt vorherzusagen. Anhand unserer Aufzeichnungen stellen wir fest, dass wenn es sonnig ist, eine 80 %-ige Chance besteht, dass es auch wieder sonnig wird, eine 15 %-ige Chance, dass es danach wolkig wird und mit einer Wahrscheinlichkeit von 5 % wird es nach einem sonnigen Tag regnen. Diese und alle anderen Wahrscheinlichkeiten haben sind in dem Diagramm unten eingetragen:Jetzt wollen wir wissen, wie das Wetter nach einem sonnigen Tag sein wird. Aber da unsere Vorhersagen nur auf einer einzigen Wetterbeobachtung beruht, ist es realistisch zu glauben, dass sie nicht sehr gut sein werden. Im Sommer, zum Beispiel, ist es wahrscheinlicher, dass einem sonnigen Tag ein weiterer sonniger Tag folgt, als im Herbst oder Winter. Die Markov-Eigenschaft gilt also in der Regel nicht für die reale Welt.

Wenn wir die Markov-Kette für Tausende von Wiederholungen laufen lassen, ergibt sich jedoch die langfristige Vorhersage, welches Wetter wir langfristig haben werden. Noch wichtiger ist, dass diese Vorhersage überhaupt nicht davon beeinflusst wird, mit welchem Wetter wir begonnen haben! Intuitiv macht das auch Sinn: Es spielt keine Rolle, wie das Wetter zu einem bestimmten Zeitpunkt ist, um zu simulieren, wie das Wetter langfristig im Allgemeinen aussehen wird. So können Markov-Ketten wie eine schlechte Alternative erscheinen, das Verhalten einer Zufallsvariable über einen kürzeren Zeitraum zu modellieren, aber verwendet werden, um die langfristige Tendenz dieser Variable zu berechnen, vorausgesetzt wir kennen die Wahrscheinlichkeiten, die ihr Verhalten regeln.

MCMC-Methoden

Jetzt, wo wir uns Monte Carlo Methoden und Markov-Ketten ein wenig beschäftigt haben, bringen wir im nächsten Teil beides zusammen.

Erinnern wir uns, dass wir mithilfe von MCMC-Methoden einen Parameter des Posteriors schätzen wollten, die durchschnittliche Körpergröße.

Wir wissen, dass die posteriore Verteilung irgendwo im Definitionsbereich unserer a-priori- und Likelihood-Verteilung liegt, aber aus welchem Grund auch immer, können wir sie nicht direkt berechnen. Mit Hilfe von MCMC-Methoden ziehen wir jetzt Stichproben aus der posterioren Verteilung und berechnen dann Statistiken (wie den Durchschnitt) der gezogenen Stichproben.

Zu Beginn wählen MCMC-Methoden einen zufälligen Parameterwert aus, der berücksichtigt werden soll. Die Simulation wird weitere Zufallswerte erzeugen (dies ist der Monte-Carlo-Teil), jedoch unter der Voraussetzung, dass eine Regelmäßigkeit zur Bestimmung des Wertes eines guten Parameters existiert. Der Trick ist, dass man für ein Paar von Parameterwerten berechnen kann, welcher der besserer Parameterwert ist, indem man berechnet, wie wahrscheinlich es ist, dass jeder Wert die Daten erklärt, wenn man unsere a priori Verteilung berücksichtigt. Wenn ein zufällig generierter Parameterwert besser ist als der letzte, wird er mit einer bestimmten Wahrscheinlichkeit zur Kette der Parameterwerte hinzuaddiert, die durch seine Verbesserung bestimmt wird (dies ist der Markov-Ketten-Teil).

Um dies visuell zu erklären, erinnern wir uns daran, dass die Höhe einer Verteilung bei einem bestimmten Wert die Wahrscheinlichkeit darstellt, diesen Wert zu beobachten. Daher können wir uns vorstellen, dass unsere Parameterwerte (die x-Achse) Bereiche mit hoher und niedriger Wahrscheinlichkeit aufweisen, die auf der y-Achse dargestellt sind. Für einen einzelnen Parameter beginnen die MCMC-Methoden mit einer Zufallsstichprobe entlang der x-Achse:

Da die Zufallsstichproben festen Wahrscheinlichkeiten folgen, neigen sie dazu, sich nach einiger Zeit im Bereich der höchsten Wahrscheinlichkeit für den Parameter, für den wir uns interessieren, zu konzentrieren:

Nach erfolgter Konvergenz liefert die MCMC-Stichprobe eine Reihe von Punkten, die Proben aus der posterioren Verteilung sind. Wenn  wir dann noch ein Histogramm um diese Punkte zeichnen, können jede beliebige Statistik berechnen:

Jede Statistik, die auf der Grundlage der durch MCMC-Simulationen erzeugten Stichproben berechnet wird, ist unsere beste Schätzung dieser Statistik über die wahre posteriore Verteilung.

MCMC-Methoden können auch verwendet werden, um die posteriore Verteilung von mehr als einem Parameter abzuschätzen (z.B. Körpergröße und Gewicht des Menschen). Für n Parameter gibt es Regionen mit hoher Wahrscheinlichkeit im n-dimensionalen Raum, in denen bestimmte Sätze von Parameterwerten die beobachteten Daten besser erklären. Daher können wir uns MCMC-Methoden auch als Verfahren vorstellen, die Zufallsstichproben innerhalb eines Wahrsscheinlichkeitsraumes ziehen, um eine posteriore Verteilung zu approximieren.