Ist es einfach Ich habe es versucht
Alexey Kuzmin, Direktor für Datenentwicklung und Arbeit bei DomKlik, Dozent für Datenwissenschaft in Netologie, hat einen Artikel von Rahul Agarwal übersetzt, wie Monte-Carlo-Methoden mit Markov-Ketten funktionieren, um Probleme mit einem großen Zustandsraum zu lösen.Jeder, der mit Data Science in Verbindung steht, hat jemals von Monte-Carlo-Methoden mit Markov-Ketten (MCMCs) gehört. Manchmal wird das Thema beim Studium der Bayes'schen Statistik angesprochen, manchmal bei der Arbeit mit Werkzeugen wie dem Propheten.
Aber MCMC ist schwer zu verstehen. Wann immer ich über diese Methoden las, bemerkte ich, dass die Essenz von MCMC in den tiefen Schichten des mathematischen Rauschens verborgen ist und es schwierig ist, hinter diesem Rauschen zu erkennen. Ich musste viele Stunden damit verbringen, dieses Konzept zu verstehen.
In diesem Artikel wird versucht, Monte-Carlo-Methoden mit Markov-Ketten zu erklären, damit klar wird, wofür sie verwendet werden. Ich werde mich in meinem nächsten Beitrag auf einige weitere Möglichkeiten konzentrieren, diese Methoden anzuwenden.
Also fangen wir an. MCMC besteht aus zwei Begriffen: Monte-Carlo- und Markov-Ketten. Sprechen wir über jeden von ihnen.
Monte Carlo
Im einfachsten Sinne
können Monte-Carlo-Methoden als einfache Simulationen definiert werden.
Monte Carlo Methods erhielt ihren Namen vom Monte Carlo Casino in Monaco. In vielen Kartenspielen müssen Sie die Wahrscheinlichkeit kennen, den Dealer zu gewinnen. Manchmal kann die Berechnung dieser Wahrscheinlichkeit mathematisch kompliziert oder unlösbar sein. Wir können jedoch jederzeit eine Computersimulation ausführen, um das gesamte Spiel viele Male zu spielen, und die Wahrscheinlichkeit als die Anzahl der Siege geteilt durch die Anzahl der gespielten Spiele betrachten.
Dies ist alles, was Sie über Monte-Carlo-Methoden wissen müssen. Ja, es ist nur eine einfache Modellierungstechnik mit einem ausgefallenen Namen.
Markov-Ketten
Da der Begriff MCMC aus zwei Teilen besteht, müssen Sie noch verstehen, was
Markov-Ketten sind . Bevor wir jedoch zu den Markov-Ketten übergehen, lassen Sie uns ein wenig über die Markov-Eigenschaften sprechen.
Angenommen, es gibt ein System von M-möglichen Zuständen, und Sie wechseln von einem Zustand in einen anderen. Lass dich noch nicht verwirren. Ein spezielles Beispiel für ein solches System ist das Wetter, das von heiß über kalt bis mäßig wechselt. Ein weiteres Beispiel ist der Aktienmarkt, der von einem bärischen zu einem bullischen und stagnierenden Staat springt.
Die Markov-Eigenschaft legt nahe, dass für einen gegebenen Prozess, der sich zu einem bestimmten Zeitpunkt im Zustand X
n befindet , die Wahrscheinlichkeit X
n + 1 = k (wobei k einer der M-Zustände ist, in die der Prozess gehen kann) nur von abhängt Was ist dieser Zustand im Moment. Und nicht darüber, wie es seinen aktuellen Zustand erreicht hat.
In mathematischen Begriffen können wir dies in Form der folgenden Formel schreiben:
Aus Gründen der Klarheit ist es Ihnen egal, in welcher Reihenfolge der Markt bullisch wurde. Die Wahrscheinlichkeit, dass der nächste Staat „bärisch“ sein wird, wird nur durch die Tatsache bestimmt, dass sich der Markt derzeit in einem „bullischen“ Zustand befindet. Das macht auch in der Praxis Sinn.
Ein Prozess mit einer Markov-Eigenschaft wird als Markov-Prozess bezeichnet. Warum ist die Markov-Kette wichtig? Aufgrund seiner stationären Verteilung.
Was ist stationäre Verteilung?
Ich werde versuchen, die stationäre Verteilung zu erklären, indem ich sie für das folgende Beispiel berechne. Angenommen, Sie haben einen Markov-Prozess für die Börse, wie unten gezeigt.
Sie haben eine Übergangswahrscheinlichkeitsmatrix, die die Wahrscheinlichkeit eines Übergangs vom Zustand X
i zum X
j bestimmt .
Übergangswahrscheinlichkeitsmatrix, Q.
In der transienten Wahrscheinlichkeitsmatrix Q ist die Wahrscheinlichkeit, dass der nächste Zustand "bull" ist, gegeben, wenn der aktuelle Zustand "bull" = 0,9 ist; Die Wahrscheinlichkeit, dass der nächste Zustand "bärisch" ist, wenn der aktuelle Zustand "bull" ist = 0,075. Usw.
Beginnen wir mit einem bestimmten Zustand. Unser Zustand wird durch den Vektor [Stier, Bär, Stagnation] bestimmt. Wenn wir mit einem „bärischen“ Zustand beginnen, sieht der Vektor folgendermaßen aus: [0,1,0]. Wir können die Wahrscheinlichkeitsverteilung für den nächsten Zustand berechnen, indem wir den aktuellen Zustandsvektor mit der Übergangswahrscheinlichkeitsmatrix multiplizieren.
Beachten Sie, dass sich die Wahrscheinlichkeiten zu 1 addieren.Die folgende Zustandsverteilung ergibt sich aus der Formel:
Usw. Am Ende erreichen Sie einen stationären Zustand, in dem sich der Zustand stabilisiert:
Für die oben beschriebene Übergangswahrscheinlichkeitsmatrix Q ist die stationäre Verteilung s
Sie können eine stationäre Verteilung mit dem folgenden Code erhalten:
Q = np.matrix([[0.9,0.075,0.025],[0.15,0.8,0.05],[0.25,0.25,0.5]]) init_s = np.matrix([[0, 1 , 0]]) epsilon =1 while epsilon>10e-9: next_s = np.dot(init_s,Q) epsilon = np.sqrt(np.sum(np.square(next_s - init_s))) init_s = next_s print(init_s) ------------------------------------------------------------------ matrix([[0.62499998, 0.31250002, 0.0625 ]])
Sie können auch von jedem anderen Zustand aus starten - erzielen Sie die gleiche stationäre Verteilung. Ändern Sie den Ausgangszustand im Code, wenn Sie dies sicherstellen möchten.
Jetzt können wir die Frage beantworten, warum die stationäre Verteilung so wichtig ist.
Die stationäre Verteilung ist wichtig, da damit die Wahrscheinlichkeit bestimmt werden kann, dass sich ein System zufällig in einem bestimmten Zustand befindet.
In unserem Beispiel können wir sagen, dass sich der Markt in 62,5% der Fälle in einem „bullischen“ Zustand befindet, 31,25% in einem „bärischen“ Zustand und 6,25% in einer Stagnation.
Intuitiv kann man dies als zufälliges Wandern um die Kette sehen.
Zufälliger Spaziergang
Sie befinden sich an einem bestimmten Punkt und wählen den nächsten Zustand aus, wobei Sie die Wahrscheinlichkeitsverteilung des nächsten Zustands unter Berücksichtigung des aktuellen Zustands beobachten. Wir können einige Knoten häufiger als andere besuchen, basierend auf den Wahrscheinlichkeiten dieser Knoten.
So löste Google das Suchproblem zu Beginn des Internets. Das Problem bestand darin, die Seiten nach ihrer Wichtigkeit zu sortieren. Google hat das Problem mithilfe des Pagerank-Algorithmus gelöst. Der Google Pagerank-Algorithmus sollte den Status als Seite und die Wahrscheinlichkeit einer Seite in einer stationären Verteilung als ihre relative Bedeutung betrachten.
Nun wenden wir uns direkt der Betrachtung von MCMC-Methoden zu.
Was sind Monte-Carlo-Methoden mit Markov-Ketten (MCMC)
Lassen Sie mich eine Frage stellen, bevor ich beantworte, was MCMC ist. Wir kennen die Beta-Distribution. Wir kennen seine Wahrscheinlichkeitsdichtefunktion. Aber können wir aus dieser Verteilung eine Stichprobe ziehen? Können Sie einen Weg finden, dies zu tun?
Denken Sie ...
Mit MCMC können Sie aus einer beliebigen Wahrscheinlichkeitsverteilung auswählen. Dies ist besonders wichtig, wenn Sie eine Auswahl aus der posterioren Verteilung treffen müssen.
Die Abbildung zeigt den Bayes-Satz.
Beispielsweise müssen Sie eine Probe aus einer posterioren Verteilung erstellen. Aber ist es einfach, die hintere Komponente zusammen mit der Normalisierungskonstante (Evidenz) zu berechnen? In den meisten Fällen finden Sie sie in Form eines Produkts aus Wahrscheinlichkeit und a priori Wahrscheinlichkeit. Die Berechnung der Normalisierungskonstante (p (D)) funktioniert jedoch nicht. Warum? Schauen wir uns das genauer an.
Angenommen, H nimmt nur 3 Werte an:
p (D) = p (H = H1) .p (D | H = H1) + p (H = H2) .p (D | H = H2) + p (H = H3) .p (D | H = H3)
In diesem Fall ist p (D) leicht zu berechnen. Was aber, wenn der Wert von H stetig ist? Wäre es möglich, dies so einfach zu berechnen, insbesondere wenn H unendliche Werte annehmen würde? Dazu müsste ein komplexes Integral gelöst werden.
Wir wollen eine zufällige Auswahl aus der posterioren Verteilung treffen, aber auch p (D) als Konstante betrachten.
Wikipedia
schreibt :
Monte-Carlo-Methoden mit Markov-Ketten sind eine Klasse von Algorithmen zur Abtastung aus einer Wahrscheinlichkeitsverteilung, die auf dem Aufbau einer Markov-Kette basiert, die als stationäre Verteilung die gewünschte Form hat. Der Kettenzustand nach einer Reihe von Schritten wird dann als Auswahl aus der gewünschten Verteilung verwendet. Die Probenqualität verbessert sich mit zunehmender Anzahl von Schritten.
Schauen wir uns ein Beispiel an. Angenommen, Sie benötigen ein Beispiel aus der
Beta-Distribution . Seine Dichte:
wobei C die Normalisierungskonstante ist. Eigentlich ist dies eine Funktion von α und β, aber ich möchte zeigen, dass es für eine Stichprobe aus der Beta-Verteilung nicht benötigt wird, also nehmen wir es als Konstante.
Das Beta-Verteilungsproblem ist wirklich schwierig, wenn nicht praktisch unlösbar. In der Realität müssen Sie möglicherweise mit komplexeren Verteilungsfunktionen arbeiten, und manchmal kennen Sie die Normalisierungskonstanten nicht.
MCMC-Methoden erleichtern das Leben, indem sie Algorithmen bereitstellen, mit denen eine Markov-Kette mit einer Beta-Verteilung als stationäre Verteilung erstellt werden kann, da wir aus einer gleichmäßigen Verteilung wählen können (was relativ einfach ist).
Wenn wir mit einem zufälligen Zustand beginnen und auf der Grundlage eines Algorithmus mehrmals zum nächsten Zustand übergehen, werden wir schließlich eine Markov-Kette mit einer Beta-Verteilung als stationäre Verteilung erstellen. Und die Zustände, in denen wir uns seit langer Zeit befinden, können als Beispiel aus der Beta-Distribution verwendet werden.
Einer dieser MCMC-Algorithmen ist der
Metropolis-Hastings-Algorithmus.Metropolis-Hastings-Algorithmus
Intuition:
Was ist der Zweck?
Intuitiv möchten wir ein Stück Oberfläche (unsere Markov-Kette) so entlang gehen, dass die Zeit, die wir an jedem Ort verbringen, proportional zur Höhe der Oberfläche an diesem Ort ist (die gewünschte Wahrscheinlichkeitsdichte, aus der wir eine Auswahl treffen möchten).
So möchten wir beispielsweise doppelt so viel Zeit auf einem 100 Meter hohen Hügel verbringen wie auf einem benachbarten 50 Meter hohen Hügel. Es ist gut, dass wir dies auch dann tun können, wenn wir die absoluten Höhen der Punkte auf der Oberfläche nicht kennen: Alles, was Sie wissen müssen, sind die relativen Höhen. Wenn beispielsweise die Spitze des Hügels A zweimal höher ist als die Spitze des Hügels B, möchten wir in A doppelt so viel Zeit verbringen wie auf B.
Es gibt komplexere Schemata, um neue Orte und Regeln für ihre Annahme vorzuschlagen, aber die Hauptidee lautet wie folgt:
- Wählen Sie einen neuen "vorgeschlagenen" Ort.
- Finden Sie heraus, wie hoch oder niedriger dieser Ort im Vergleich zum aktuellen ist.
- An Ort und Stelle bleiben oder an einen neuen Ort ziehen, mit einer Wahrscheinlichkeit proportional zur Höhe der Orte.
Der Zweck des MCMC besteht darin, aus einer Wahrscheinlichkeitsverteilung auszuwählen, ohne an irgendeinem Punkt seine genaue Höhe kennen zu müssen (C muss nicht bekannt sein).
Wenn der Wanderprozess korrekt eingerichtet ist, können Sie sicherstellen, dass diese Proportionalität (zwischen der aufgewendeten Zeit und der Verteilungshöhe) erreicht wird .
Algorithmus:
Lassen Sie uns nun die Aufgabe formeller definieren und beschreiben. Sei s = (s1, s2, ..., sM) die gewünschte stationäre Verteilung. Wir wollen eine Markov-Kette mit einer solchen stationären Verteilung erstellen. Wir beginnen mit einer beliebigen Markov-Kette mit M-Zuständen mit der Übergangsmatrix P, so dass pij die Wahrscheinlichkeit des Übergangs vom Zustand i nach j darstellt.
Intuitiv wissen wir, wie man die Markov-Kette durchstreift, aber die Markov-Kette hat nicht die erforderliche stationäre Verteilung. Diese Kette hat eine stationäre Verteilung (die wir nicht brauchen). Unser Ziel ist es, die Art und Weise, wie wir um die Markov-Kette herumwandern, so zu ändern, dass die Kette die gewünschte stationäre Verteilung hat.
Um dies zu tun:
- Beginnen Sie mit einem zufälligen Ausgangszustand i.
- Wählen Sie zufällig einen neuen angenommenen Zustand aus, indem Sie die Übergangswahrscheinlichkeiten in der i-ten Zeile der Übergangsmatrix P betrachten.
- Berechnen Sie ein Maß namens Entscheidungswahrscheinlichkeit, das definiert ist als: aij = min (sj.pji / si.pij, 1).
- Wirf nun eine Münze, die mit der Wahrscheinlichkeit aij auf der Oberfläche des Adlers landet. Wenn ein Adler fällt, nehmen Sie das Angebot an, gehen Sie zum nächsten Zustand über, andernfalls lehnen Sie das Angebot ab, dh bleiben Sie im aktuellen Zustand.
- Wiederholen Sie viele Male.
Nach einer großen Anzahl von Tests konvergiert diese Kette und hat eine stationäre Verteilung s. Dann können wir Kettenzustände als Stichprobe aus jeder Verteilung verwenden.
Wenn Sie dies tun, um die Beta-Verteilung abzutasten, müssen Sie nur die Wahrscheinlichkeitsdichte verwenden, um nach der Wahrscheinlichkeit zu suchen, eine Entscheidung zu treffen. Teilen Sie dazu sj durch si (dh die Normalisierungskonstante C wird aufgehoben).
Beta-Auswahl
Nun wenden wir uns dem Problem der Stichprobe aus der Beta-Distribution zu.
Eine Beta-Verteilung ist eine kontinuierliche Verteilung auf [0,1] und kann auf [0,1] unendliche Werte haben. Angenommen, eine beliebige Markov-Kette P mit unendlichen Zuständen auf [0,1] hat eine Übergangsmatrix P, so dass pij = pji = alle Elemente in der Matrix.
Wir brauchen keine Matrix P, wie wir später sehen werden, aber ich möchte, dass die Beschreibung des Problems dem von uns vorgeschlagenen Algorithmus so nahe wie möglich kommt.
- Beginnen Sie mit einem zufälligen Anfangszustand i, der aus einer Gleichverteilung auf (0,1) erhalten wird.
- Wählen Sie zufällig einen neuen angenommenen Zustand aus, indem Sie die Übergangswahrscheinlichkeiten in der i-ten Zeile der Übergangsmatrix P betrachten. Angenommen, wir wählen einen anderen Zustand Unif (0,1) als den angenommenen Zustand j.
- Berechnen Sie das Maß, das als Entscheidungswahrscheinlichkeit bezeichnet wird:
Was vereinfacht zu:
Da pji = pij und wo
- Wirf jetzt eine Münze. Mit der Wahrscheinlichkeit aij wird ein Adler fallen. Wenn ein Adler fällt, sollten Sie das Angebot annehmen, dh in den nächsten Zustand wechseln. Andernfalls lohnt es sich, das Angebot abzulehnen, dh im selben Zustand zu bleiben.
- Wiederholen Sie den Test viele Male.
Code:
Es ist Zeit, von der Theorie zur Praxis überzugehen. Wir werden unser Beta-Beispiel in Python schreiben.
impo rt rand om
Vergleichen Sie die Ergebnisse mit der tatsächlichen Beta-Verteilung.
impo rt num py as np import pylab as pl import scipy.special as ss %matplotlib inline pl.rcParams['figure.figsize'] = (17.0, 4.0)
Wie Sie sehen können, sind die Werte der Beta-Distribution sehr ähnlich. Somit hat das MCMC-Netzwerk einen stationären Zustand erreicht
Im obigen Code haben wir einen Beta-Sampler erstellt, aber das gleiche Konzept gilt für jede andere Distribution, aus der wir eine Auswahl treffen möchten.
Schlussfolgerungen
Es war ein großartiger Beitrag. Herzlichen Glückwunsch, wenn Sie es bis zum Ende gelesen haben.
MCMC-Methoden können im Wesentlichen komplex sein, bieten uns jedoch große Flexibilität. Sie können aus einer beliebigen Verteilungsfunktion auswählen, indem Sie die Auswahl über die MCMC vornehmen. Typischerweise werden diese Methoden verwendet, um Proben aus posterioren Verteilungen zu entnehmen.
Sie können MCMC auch verwenden, um Probleme mit einem großen Zustandsraum zu lösen. Zum Beispiel bei einem Rucksackproblem oder zur Entschlüsselung. Ich werde versuchen, Ihnen im
nächsten Beitrag weitere interessante Beispiele zu liefern. Bleib dran.
Von den Redakteuren