Wie würden Sie einem Laien Markov Chain Monte Carlo (MCMC) erklären?

Vielleicht das Konzept, warum es verwendet wird, und ein Beispiel.

Zunächst müssen wir verstehen, was eine Markov-Kette ist. Betrachten Sie das folgende Wetterbeispiel aus Wikipedia. Angenommen, das Wetter an einem bestimmten Tag kann nur in zwei Bundesstaaten eingeteilt werden: sonnig und regnerisch. Aufgrund unserer bisherigen Erfahrungen wissen wir Folgendes:

$P(\text{Next day is Sunny}\,\vert \,\text{Given today is Rainy)}=0.50$

Da das Wetter am nächsten Tag entweder sonnig oder regnerisch ist, gilt Folgendes:

$P(\text{Next day is Rainy}\,\vert \,\text{Given today is Rainy)}=0.50$

Ebenso lassen Sie:

$P(\text{Next day is Rainy}\,\vert \,\text{Given today is Sunny)}=0.10$

Daraus folgt:

$P(\text{Next day is Sunny}\,\vert \,\text{Given today is Sunny)}=0.90$

Die obigen vier Zahlen können kompakt als Übergangsmatrix dargestellt werden, die die Wahrscheinlichkeiten für den Wechsel des Wetters von einem Zustand in einen anderen wie folgt darstellt:

$P = \begin{bmatrix} & S & R \\ S& 0.9 & 0.1 \\ R& 0.5 & 0.5 \end{bmatrix}$

Wir könnten mehrere Fragen stellen, deren Antworten folgen:

F1: Wenn das Wetter heute sonnig ist, wie ist es dann wahrscheinlich morgen?

A1: Da wir nicht genau wissen, was sicher passieren wird, können wir am besten sagen, dass es mit einer Wahrscheinlichkeit von sonnig und mit regnerisch ist.$90\%$$10\%$

F2: Was ist mit zwei Tagen ab heute?

A2: Vorhersage eines Tages: sonnig, regnerisch. Deshalb in zwei Tagen:$90\%$$10\%$

Am ersten Tag kann es sonnig sein und am nächsten Tag kann es auch sonnig sein. Die Chancen dafür sind: .$0.9 \times 0.9$

Oder

Am ersten Tag kann es regnen und am zweiten sonnig sein. Die Chancen dafür sind: .$0.1 \times 0.5$

Daher ist die Wahrscheinlichkeit, dass das Wetter in zwei Tagen sonnig wird, wie folgt:

$P(\text{Sunny 2 days from now} = 0.9 \times 0.9 + 0.1 \times 0.5 = 0.81 + 0.05 = 0.86$

Ebenso ist die Wahrscheinlichkeit, dass es regnen wird:

$P(\text{Rainy 2 days from now} = 0.1 \times 0.5 + 0.9 \times 0.1 = 0.05 + 0.09 = 0.14$

In der linearen Algebra (Übergangsmatrizen) entsprechen diese Berechnungen allen Permutationen in Übergängen von einem Schritt zum nächsten (sonnig zu sonnig ( ), sonnig zu regnerisch ( ), regnerisch zu sonnig ( ) oder regnerisch-regnerisch ($S_2S$$S_2R$$R_2S$$R_2R$ )) mit ihren berechneten Wahrscheinlichkeiten:

$t+1$$t+2$$PMF$$t_0$

$n$$n$$30$

$P(\text{Sunny}) = 0.833$

und

$P(\text{Rainy}) = 0.167$

$n$$n+1$

Das obige Beispiel funktioniert nur, wenn die Zustandsübergangswahrscheinlichkeiten mehrere Bedingungen erfüllen, auf die ich hier nicht näher eingehen werde. Beachten Sie jedoch die folgenden Merkmale dieser 'schönen' Markov-Kette (schön = Übergangswahrscheinlichkeiten erfüllen Bedingungen):

Unabhängig vom Ausgangszustand werden wir schließlich eine Gleichgewichtswahrscheinlichkeitsverteilung von Zuständen erreichen.

Markov Chain Monte Carlo nutzt das obige Feature wie folgt aus:

Wir wollen zufällige Ziehungen aus einer Zielverteilung generieren. Wir identifizieren dann einen Weg, um eine 'schöne' Markov-Kette so zu konstruieren, dass ihre Gleichgewichtswahrscheinlichkeitsverteilung unsere Zielverteilung ist.

$n$

Wir approximieren dann die interessierenden Mengen (z. B. den Mittelwert), indem wir den Stichprobenmittelwert der Ziehungen nehmen, nachdem wir einige anfängliche Ziehungen, die die Monte-Carlo-Komponente sind, verworfen haben.

Es gibt verschiedene Möglichkeiten, 'schöne' Markov-Ketten zu konstruieren (zB Gibbs-Sampler, Metropolis-Hastings-Algorithmus).

Ich denke, es gibt eine nette und einfache Intuition, die man mit dem (Unabhängigkeits-Ketten-) Metropolis-Hastings-Algorithmus gewinnen kann.

Erstens, was ist das Ziel? Das Ziel von MCMC ist es, Stichproben aus einer Wahrscheinlichkeitsverteilung zu ziehen, ohne die genaue Höhe zu irgendeinem Zeitpunkt zu kennen. Die Art und Weise, wie MCMC dies erreicht, besteht darin, auf dieser Verteilung so "herumzulaufen", dass die Zeit, die an jedem Ort verbracht wird, proportional zur Höhe der Verteilung ist. Wenn der "Herumwandern" -Prozess korrekt eingerichtet ist, können Sie sicherstellen, dass diese Proportionalität (zwischen Zeitaufwand und Höhe der Verteilung) erreicht wird.

Intuitiv wollen wir auf einer (klumpigen) Oberfläche so herumlaufen, dass die Zeit, die wir an jedem Ort verbringen (oder die Anzahl der gezogenen Proben), proportional zur Höhe der Oberfläche an diesem Ort ist. So möchten wir beispielsweise doppelt so viel Zeit auf einem Hügel verbringen, der sich auf einer Höhe von 100 m befindet, wie auf einem Hügel in der Nähe, der sich auf einer Höhe von 50 m befindet. Das Schöne ist, dass wir dies auch dann tun können, wenn wir die absoluten Höhen der Punkte auf der Oberfläche nicht kennen: Alles, was wir wissen müssen, sind die relativen Höhen. Beispiel: Wenn ein Hügel A doppelt so hoch ist wie Hügel B, möchten wir doppelt so viel Zeit in A verbringen wie in B.

Die einfachste Variante des Metropolis-Hastings-Algorithmus (Independence Chain Sampling) erreicht dies wie folgt: Nehmen wir an, dass wir in jedem (diskreten) Zeitschritt einen zufälligen neuen "vorgeschlagenen" Ort auswählen (gleichmäßig über die gesamte Oberfläche ausgewählt). Wenn der vorgeschlagene Ort höher ist als der, an dem wir gerade stehen, gehen Sie dorthin. Wenn der vorgeschlagene Standort niedriger ist, bewegen Sie sich mit der Wahrscheinlichkeit p zum neuen Standort, wobei p das Verhältnis der Höhe dieses Punkts zur Höhe des aktuellen Standorts ist. (z. B. werfen Sie eine Münze mit einer Wahrscheinlichkeit von p, Kopf zu bekommen. Wenn es Kopf wird, bewegen Sie sich an den neuen Ort. Wenn es Schwanz wird, bleiben Sie wo wir sind). Führen Sie eine Liste der Orte, an denen Sie sich in jedem Zeitschritt befunden haben, und diese Liste wird (asyptotisch) den richtigen Zeitanteil in jedem Teil der Oberfläche haben.

Es gibt kompliziertere Schemata für das Vorschlagen neuer Standorte und die Regeln für deren Annahme, aber die Grundidee ist immer noch: (1) Wählen Sie einen neuen "vorgeschlagenen" Standort; (2) Finden Sie heraus, wie viel höher oder niedriger dieser Standort im Vergleich zu Ihrem aktuellen Standort ist. (3) wahrscheinlich an diesem Ort bleiben oder sich an diesem Ort auf eine Weise bewegen, die das übergeordnete Ziel, Zeit proportional zur Höhe des Ortes zu verbringen, respektiert.

Wofür ist das nützlich? Angenommen, wir haben ein Wahrscheinlichkeitsmodell des Wetters, mit dem wir A * P (Wetter) bewerten können, wobei A eine unbekannte Konstante ist. (Dies kommt häufig vor - viele Modelle lassen sich bequem so formulieren, dass Sie nicht feststellen können, was A ist.) Daher können wir P ("Regen morgen") nicht genau bewerten. Wir können jedoch den MCMC-Sampler eine Weile laufen lassen und dann fragen, welcher Anteil der Proben (oder "Standorte") im Zustand "Regen von morgen" gelandet ist. Diese Fraktion wird die (modellbasierte) probabilistische Wettervorhersage sein.

Ich würde wahrscheinlich so etwas sagen:

"Immer wenn wir über Wahrscheinlichkeiten sprechen wollen, integrieren wir wirklich eine Dichte. In der Bayes'schen Analyse sind viele der Dichten, die wir entwickeln, nicht analytisch nachvollziehbar: Sie können sie nur integrieren - wenn Sie sie überhaupt integrieren können." Stattdessen simulieren wir die Zufallsvariable sehr oft und berechnen dann die Wahrscheinlichkeiten aus unseren simulierten Zufallszahlen. Wenn wir die Wahrscheinlichkeit wissen möchten, dass X kleiner als 10 ist, zählen wir die Der Anteil der simulierten Zufallsvariablen beträgt weniger als 10 und wird als Schätzung verwendet. Dies ist der "Monte Carlo" -Teil, eine Schätzung der Wahrscheinlichkeit auf der Grundlage von Zufallszahlen. Mit genügend simulierten Zufallszahlen ist die Schätzung sehr gut, aber immer noch gut von Natur aus zufällig.

"Warum also" Markov-Kette "? Unter bestimmten technischen Bedingungen können Sie einen memorylosen Prozess (auch als markovianischer Prozess bezeichnet) generieren, der dieselbe begrenzende Verteilung aufweist wie die Zufallsvariable, die Sie simulieren möchten. Sie können jeden beliebigen von a iterieren Anzahl von verschiedenen Arten von Simulationsprozessen, die korrelierte Zufallszahlen erzeugen (basierend nur auf dem aktuellen Wert dieser Zahlen), und Sie werden garantiert, dass Sie, sobald Sie genug Ergebnisse gesammelt haben, einen Zahlenstapel erhalten, der aussieht " als ob "Sie es irgendwie geschafft hätten, unabhängige Proben aus der komplizierten Distribution zu ziehen, über die Sie wissen wollten.

"Wenn ich zum Beispiel die Wahrscheinlichkeit abschätzen möchte, dass eine normale Standardzufallsvariable kleiner als 0,5 ist, könnte ich zehntausend unabhängige Realisierungen aus einer normalen Standardverteilung generieren und die Zahl kleiner als 0,5 hochzählen; sagen wir, ich habe 6905, das sind weniger als 0,5 von insgesamt 10000 Stichproben, meine Schätzung für P (Z <0,5) wäre 0,6905, was nicht so weit vom tatsächlichen Wert entfernt ist. Dies wäre eine Monte-Carlo-Schätzung.

Die Liste der Zahlen, die ich aus der Prozedur erhalte, wird wie eine große Anzahl von Ziehungen aus etwas verteilt, das normale Zufallsvariablen erzeugt. Dies würde mir eine Markov-Ketten-Monte-Carlo-Simulation für eine normale Standard-Zufallsvariable geben. Wenn ich dies zum Schätzen von Wahrscheinlichkeiten verwenden würde, wäre das eine MCMC-Schätzung. "

Stellen Sie sich vor, Sie möchten eine bessere Strategie finden, um Ihre Freunde beim Brettspiel Monopoly zu schlagen. Vereinfachen Sie die Dinge, die im Spiel wichtig sind, auf die Frage: Auf welchen Eigenschaften landen die Menschen am meisten? Die Antwort hängt von der Struktur des Bretts, den Spielregeln und den Würfen mit zwei Würfeln ab.

Eine Möglichkeit, die Frage zu beantworten, ist diese. Folgen Sie einfach einem Stück um das Brett, während Sie die Würfel werfen und die Regeln befolgen. Zählen Sie, wie oft Sie auf einem Grundstück landen (oder programmieren Sie einen Computer, der die Arbeit für Sie erledigt). Wenn Sie genug Geduld haben oder die Regeln in Ihrem Computer gut genug programmiert haben, können Sie sich ein gutes Bild davon machen, welche Immobilien das meiste Geschäft machen. Dies sollte Ihnen helfen, öfter zu gewinnen.

Was Sie getan haben, ist eine Markov Chain Monte Carlo (MCMC) -Analyse. Die Tafel definiert die Regeln. Wo Sie als nächstes landen, hängt nur davon ab, wo Sie sich gerade befinden, nicht davon, wo Sie zuvor waren. Die spezifischen Wahrscheinlichkeiten werden durch die Verteilung der Würfe mit zwei Würfeln bestimmt. MCMC ist die Anwendung dieser Idee auf mathematische oder physikalische Systeme wie das Wetter von morgen oder wo ein durch Gasmoleküle zufällig aufgeschüttetes Pollenkorn enden wird.

OK, hier ist mein bester Versuch einer informellen und groben Erklärung.

Eine Markov-Kette ist ein zufälliger Prozess, der die Eigenschaft hat, dass die Zukunft nur vom aktuellen Status des Prozesses und nicht von der Vergangenheit abhängt, dh er ist memorylos. Ein Beispiel für einen zufälligen Prozess könnte die Börse sein. Ein Beispiel für eine Markov-Kette wäre ein Brettspiel wie Monopoly oder Snakes and Ladders, bei dem Ihre zukünftige Position (nachdem Sie den Würfel gewürfelt haben) nur davon abhängt, wo Sie vor dem Wurf angefangen haben, und nicht von einer Ihrer vorherigen Positionen. Ein Musterbeispiel für eine Markov-Kette ist der "Trunkenboldspaziergang". Stellen Sie sich jemanden vor, der betrunken ist und sich nur um einen Schritt nach links oder rechts bewegen kann. Der Betrunkene bewegt sich mit gleicher Wahrscheinlichkeit nach links oder rechts. Dies ist eine Markov-Kette, bei der die zukünftige / nächste Position des Betrunkenen nur davon abhängt, wo er sich gerade befindet.

Monte-Carlo-Methoden sind Berechnungsalgorithmen (einfach Sätze von Anweisungen), die zufällig aus einem untersuchten Prozess ausgewählt werden. Sie sind eine Möglichkeit, etwas zu schätzen, das zu schwierig oder zu zeitaufwendig ist, um es deterministisch zu finden. Sie sind im Grunde eine Form der Computersimulation eines mathematischen oder physikalischen Prozesses. Der Monte-Carlo-Spitzname stammt aus der Analogie zwischen Casino und Zufallsgenerierung. Kehren wir früher zu unserem Brettspielbeispiel zurück und möchten vielleicht wissen, ob einige Objekte auf dem Monopoly-Brett häufiger besucht werden als andere. Bei einem Monte-Carlo-Experiment werden die Würfel wiederholt gewürfelt und die Anzahl der Landungen auf jedem Grundstück gezählt. Es kann auch zur Berechnung von numerischen Integralen verwendet werden. (Sehr informell können wir uns ein Integral als den Bereich unter dem Graphen einer Funktion vorstellen. ) Die Monte-Carlo-Integration eignet sich hervorragend für hochdimensionale Funktionen, indem eine zufällige Stichprobe von Punkten der Funktion genommen und an diesen verschiedenen Punkten ein Mittelwert berechnet wird. Durch Erhöhen der Stichprobengröße sagt uns das Gesetz der großen Zahlen, dass wir die Genauigkeit unserer Approximation erhöhen können, indem wir mehr und mehr von der Funktion abdecken.

Diese beiden Konzepte können zusammengestellt werden, um einige schwierige Probleme in Bereichen wie der Bayes'schen Inferenz, der Computerbiologie usw. zu lösen, in denen mehrdimensionale Integrale berechnet werden müssen, um allgemeine Probleme zu lösen. Die Idee ist, eine Markov-Kette zu konstruieren, die nach mehreren Schritten zur gewünschten Wahrscheinlichkeitsverteilung konvergiert. Der Zustand der Kette nach einer großen Anzahl von Schritten wird dann als Probe aus der gewünschten Verteilung verwendet und der Vorgang wiederholt. Es gibt viele verschiedene MCMC-Algorithmen, die unterschiedliche Techniken zum Erzeugen der Markov-Kette verwenden. Übliche sind der Metropolis-Hastings und der Gibbs-Sampler.

Auszug aus Bayes'schen Methoden für Hacker

Die bayesianische Landschaft

$N$$N$$p_1$$p_2$

$\text{Exp}(3)$$\text{Exp}(10)$

Die folgende Visualisierung zeigt dies. Je dunkler die Farbe ist, desto wahrscheinlicher ist es, dass sich die Unbekannten an diesem Ort befinden. Umgekehrt bedeuten Bereiche mit dunklerem Blau, dass unsere Vorgänger den Unbekannten, die sich dort aufhalten, eine sehr geringe Wahrscheinlichkeit zuweisen.

Dies sind einfache Beispiele im 2D-Raum, in denen unser Gehirn Oberflächen gut verstehen kann. In der Praxis können Räume und Oberflächen, die von unseren Priors erzeugt werden, viel höher dimensioniert sein.

$X$$X$Schiebt die ursprüngliche Oberfläche nach oben, um hohe Berge zu erhalten . Dem Betrag des Hochdrückens wird durch die vorherige Wahrscheinlichkeit widerstanden, so dass eine geringere vorherige Wahrscheinlichkeit mehr Widerstand bedeutet. In dem obigen Fall mit doppelter Exponentialpriorität wäre ein Berg (oder mehrere Berge), der in der Nähe der (0,0) -Ecke ausbrechen könnte, viel höher als Berge, die näher an (5,5) ausbrechen, da es in der Nähe mehr Widerstand gibt (5,5). Der Berg oder vielleicht allgemeiner die Gebirgsketten spiegeln die hintere Wahrscheinlichkeit wider, wo die wahren Parameter wahrscheinlich gefunden werden.

$\lambda$

$\text{Uniform}(0,5)$

Der schwarze Punkt repräsentiert die wahren Parameter. Selbst mit 1 Abtastpunkt, wie oben simuliert, versuchen die Berge, den wahren Parameter zu enthalten. Die Schlussfolgerung mit einer Stichprobengröße von 1 ist natürlich unglaublich naiv, und die Auswahl einer so kleinen Stichprobengröße war nur veranschaulichend.

Mit dem MCMC die Landschaft erkunden

$N$$N$$N$von der hinteren Verteilung, nicht die Verteilung selbst. MCMC führt eine ähnliche Aufgabe aus, wie die wiederholte Frage: "Wie wahrscheinlich ist es, dass dieser Kiesel von dem Berg stammt, nach dem ich suche?", Und schließt die Aufgabe mit der Rückgabe Tausender akzeptierter Kiesel in der Hoffnung auf eine Wiederherstellung ab der ursprüngliche Berg. In MCMC- und PyMC-Jargon sind die zurückgegebenen Sequenzen von "Kieselsteinen" die Proben, die häufiger als Spuren bezeichnet werden .

Wenn ich sage, dass MCMC intelligent sucht, meine ich, dass MCMC hoffentlich in Richtung der Bereiche mit hoher posteriorer Wahrscheinlichkeit konvergiert. MCMC erforscht dazu Positionen in der Nähe und bewegt sich mit höherer Wahrscheinlichkeit in Gebiete. Auch hier ist "konvergieren" möglicherweise kein genauer Begriff, um den Fortschritt von MCMC zu beschreiben. Konvergieren bedeutet normalerweise, sich auf einen Punkt im Raum zu bewegen, aber MCMC bewegt sich auf einen breiteren Bereich im Raum zu und geht in diesem Bereich nach dem Zufallsprinzip umher und nimmt Proben von diesem Bereich auf.

Das Zurückgeben von Tausenden von Samples an den Benutzer scheint zunächst eine ineffiziente Methode zu sein, um die posterioren Verteilungen zu beschreiben. Ich würde argumentieren, dass dies äußerst effizient ist. Betrachten Sie die alternativen Möglichkeiten:

1. Um eine mathematische Formel für die "Gebirgszüge" zu erhalten, müsste eine N-dimensionale Oberfläche mit beliebigen Gipfeln und Tälern beschrieben werden.
2. Die Rückkehr zum "Gipfel" der Landschaft, während mathematisch möglich und eine sinnvolle Maßnahme als höchster Punkt der wahrscheinlichsten Schätzung der Unbekannten entspricht, ignoriert die Form der Landschaft, die wir zuvor argumentiert haben, sehr wichtig für die Bestimmung des posterioren Vertrauens in Unbekannten.

Der wahrscheinlich stärkste Grund für die Rücksendung von Proben ist neben den Berechnungsgründen, dass wir das Gesetz der großen Zahlen leicht verwenden können , um ansonsten unlösbare Probleme zu lösen. Ich verschiebe diese Diskussion auf das nächste Kapitel.

Algorithmen zur Durchführung von MCMC

Es gibt eine große Familie von Algorithmen, die MCMC ausführen. Einfacher ausgedrückt können die meisten Algorithmen auf einer hohen Ebene wie folgt ausgedrückt werden:

1. Start at current position.
2. Propose moving to a new position (investigate a pebble near you ).
3. Accept the position based on the position's adherence to the data 
and prior distributions (ask if the pebble likely came from the mountain).
4. If you accept: Move to the new position. Return to Step 1.
5. After a large number of iterations, return the positions.

Auf diese Weise bewegen wir uns in die allgemeine Richtung zu den Regionen, in denen die hinteren Verteilungen existieren, und sammeln auf der Reise sparsam Proben. Sobald wir die hintere Verteilung erreicht haben, können wir leicht Proben sammeln, da sie wahrscheinlich alle zur hinteren Verteilung gehören.

Wenn sich die aktuelle Position des MCMC-Algorithmus in einem Bereich mit äußerst geringer Wahrscheinlichkeit befindet, was häufig der Fall ist, wenn der Algorithmus beginnt (normalerweise an einer zufälligen Stelle im Raum), bewegt sich der Algorithmus an Positionen , die wahrscheinlich nicht vom posterioren Punkt stammen aber besser als alles andere in der Nähe. Somit spiegeln die ersten Schritte des Algorithmus nicht den posterioren wider.

Hier gibt es also viele Antworten, die aus Statistik- / Wahrscheinlichkeitslehrbüchern, Wikipedia usw. stammen. Ich glaube, wir haben "Laien", in denen ich arbeite. Ich denke, sie sind in der Marketingabteilung. Wenn ich ihnen irgendetwas Technisches erklären muss, wende ich die Regel "show don't tell" an. Mit dieser Regel würde ich ihnen wahrscheinlich so etwas zeigen.

Die Idee hier ist, zu versuchen, einen Algorithmus zu codieren, den ich lernen kann, zu buchstabieren - nicht indem ich alle Hunderte (Tausende?) Von Regeln lerne. Wenn Sie einem Wort, das mit einem stillen e endet, ein Ende hinzufügen, lassen Sie das letzte e fallen wenn das Ende mit einem Vokal beginnt . Ein Grund, der nicht funktioniert, ist, dass ich diese Regeln nicht kenne (ich bin mir nicht einmal sicher, ob die, die ich gerade rezitiert habe, richtig ist). Stattdessen werde ich das Buchstabieren lehren, indem ich ihm eine Reihe von richtig geschriebenen Wörtern zeige und es die Regeln aus diesen Wörtern extrahieren lasse, was mehr oder weniger die Essenz des maschinellen Lernens ist, unabhängig vom Algorithmus - Musterextraktion und Mustererkennung .

Das Erfolgskriterium ist die korrekte Schreibweise eines Wortes, das der Algorithmus noch nie gesehen hat (mir ist klar, dass dies rein zufällig passieren kann, aber den Marketing-Leuten fällt das nicht ein, also werde ich es ignorieren - und ich werde den Algorithmus haben Versuchen Sie, nicht nur ein Wort zu buchstabieren, sondern eine Menge. Es ist also unwahrscheinlich, dass wir durch ein paar glückliche Vermutungen getäuscht werden.

Vor ungefähr einer Stunde habe ich (als reine Textdatei) den Herman-Hesse-Roman Siddhartha von der exzellenten Project Gutenberg-Site heruntergeladen . Ich werde die Wörter in diesem Roman verwenden, um dem Algorithmus das Buchstabieren beizubringen.

Also habe ich den Algorithmus unten codiert, mit dem dieser Roman drei Buchstaben gleichzeitig gescannt wurde (jedes Wort hat ein zusätzliches Zeichen am Ende, das "Leerzeichen" oder das Ende des Wortes). Drei-Buchstaben-Sequenzen können Ihnen viel sagen - zum Beispiel folgt auf den Buchstaben 'q' fast immer 'u'; Die Sequenz 'ty' tritt normalerweise am Ende eines Wortes auf. z selten und so weiter. (Anmerkung: Ich hätte es genauso gut mit ganzen Wörtern füttern können, um es so zu trainieren, dass es in vollständigen Sätzen spricht - genau die gleiche Idee, nur ein paar Änderungen am Code.)

Nichts davon ist jedoch mit MCMC verbunden, was nach dem Training passiert, wenn wir dem Algorithmus ein paar zufällige Buchstaben (als Startwert) geben und er beginnt, "Wörter" zu bilden. Wie baut der Algorithmus Wörter auf? Stellen Sie sich vor, es hat den Block 'qua'; Welchen Buchstaben fügt es als nächstes hinzu? Während des Trainings konstruierte der Algorithmus aus all den Tausenden von Wörtern des Romans eine massive l * etter-sequence-Frequenzmatrix *. Irgendwo in dieser Matrix befinden sich der aus drei Buchstaben bestehende Block "qua" und die Häufigkeiten für die Zeichen, die der Sequenz folgen könnten. Der Algorithmus wählt einen Buchstaben basierend auf den Frequenzen aus, die ihm möglicherweise folgen könnten. Der Buchstabe, den der Algorithmus als Nächstes auswählt, hängt also von den letzten drei Buchstaben in seiner Wortkonstruktionswarteschlange ab.

Das ist also ein Markov-Chain-Monte-Carlo-Algorithmus.

Ich denke, der beste Weg, um zu veranschaulichen, wie es funktioniert, besteht darin, die Ergebnisse basierend auf verschiedenen Trainingsstufen zu zeigen. Das Trainingsniveau wird variiert, indem die Anzahl der Durchgänge geändert wird, die der Algorithmus während des Romans durchführt. Je mehr Durchgänge durchläuft, desto genauer sind die Buchstabenfolgen-Frequenzmatrizen. Nachfolgend sind die Ergebnisse - in Form von 100 Zeichenketten, die vom Algorithmus ausgegeben werden - nach dem Training des Romans 'Siddharta' aufgeführt.

Ein einziger Durchgang durch den Roman, Siddhartha :

Dann werickst du alle Motten ab, wenn du lebhaft bist und schlammige Haut hast, aus Angst vor seinem Sible

(Sofort hat man gelernt, fast perfekt Walisisch zu sprechen; das hatte ich nicht erwartet.)

Nach zwei Durchgängen durch den Roman:

Die ack wor prenskinith Show war ein zweifacher Anblick. Das Land, in dem Rhatingle herrschte, war das Ov dort

Nach 10 Durchgängen:

trotz aber die sollten jetzt mit ack beten haben wasser ihre hundeschmerz hebel füße nicht die schwache erinnerung

Und hier ist der Code (in Python bin ich mir fast sicher, dass dies in R mit einem MCMC-Paket, von dem es mehrere gibt, in nur 3-4 Zeilen möglich ist)

def create_words_string(raw_string) :
  """ in case I wanted to use training data in sentence/paragraph form; 
      this function will parse a raw text string into a nice list of words;
      filtering: keep only words having  more than 3 letters and remove 
      punctuation, etc.
  """
  pattern = r'\b[A-Za-z]{3,}\b'
  pat_obj = re.compile(pattern)
  words = [ word.lower() for word in pat_obj.findall(raw_string) ]
  pattern = r'\b[vixlm]+\b'
  pat_obj = re.compile(pattern)
  return " ".join([ word for word in words if not pat_obj.search(word) ])

def create_markov_dict(words_string):
  # initialize variables
  wb1, wb2, wb3 = " ", " ", " "
  l1, l2, l3 = wb1, wb2, wb3
  dx = {}
  for ch in words_string :
    dx.setdefault( (l1, l2, l3), [] ).append(ch)
    l1, l2, l3 = l2, l3, ch
  return dx

def generate_newtext(markov_dict) :
  simulated_text = ""
  l1, l2, l3 = " ", " ", " "
  for c in range(100) :
    next_letter = sample( markov_dict[(l1, l2, l3)], 1)[0]
    simulated_text += next_letter
    l1, l2, l3 = l2, l3, next_letter
  return simulated_text

if __name__=="__main__" :
  # n = number of passes through the training text
  n = 1
  q1 = create_words_string(n * raw_str)
  q2 = create_markov_dict(q1)
  q3 = generate_newtext(q2)
  print(q3)

MCMC wird typischerweise als Alternative zu rohen Monte-Carlo-Simulationstechniken verwendet. Sowohl MCMC- als auch andere Monte-Carlo-Techniken werden verwendet, um schwierige Integrale zu bewerten, aber MCMC kann allgemeiner verwendet werden.

Ein häufiges Problem in der Statistik ist beispielsweise die Berechnung des mittleren Ergebnisses in Bezug auf ein probabilistisches / stochastisches Modell. Sowohl MCMC- als auch Monte-Carlo-Techniken würden dieses Problem lösen, indem sie eine Folge von simulierten Ergebnissen erzeugen, die wir zur Schätzung des wahren Mittelwerts verwenden könnten.

Sowohl MCMC- als auch Roh-Monte-Carlo-Techniken funktionieren, da der langfristige Anteil von Simulationen, die einem bestimmten Ergebnis entsprechen, gleich * der modellierten Wahrscheinlichkeit dieses Ergebnisses ist. Daher sind die mit beiden Methoden erzielten Ergebnisse genau, wenn genügend Simulationen generiert werden.

* Ich sage gleich, obwohl ich im Allgemeinen über messbare Mengen sprechen sollte. Ein Laie würde sich wohl nicht dafür interessieren

Während Roh-Monte-Carlo viele unabhängige Simulationen beinhaltet, von denen jede gemäß der modellierten Verteilung verteilt ist, beinhaltet MCMC die Erzeugung eines zufälligen Spaziergangs, der auf lange Sicht jedes Ergebnis mit der gewünschten Häufigkeit "besucht".

Der Trick für MCMC besteht daher darin, einen zufälligen Spaziergang zu wählen, der jedes Ergebnis mit den gewünschten Langzeitfrequenzen "besucht".

Ein einfaches Beispiel könnte die Simulation eines Modells sein, das besagt, dass die Wahrscheinlichkeit für das Ergebnis "A" 0,5 und für das Ergebnis "B" 0,5 beträgt. In diesem Fall könnte ich sicher sein, dass ich nach einem großen Schritt, wenn ich den Zufallsrundgang an Position "A" gestartet und vorgeschrieben habe, dass in jedem Schritt mit einer Wahrscheinlichkeit von 0,2 (oder einer anderen Wahrscheinlichkeit, die größer als 0 ist) auf die andere Position umgeschaltet wird Anzahl der Schritte, die der Zufallsrundgang jeweils in "A" und "B" in ungefähr 50% der Schritte durchlaufen hätte - im Einklang mit den von unserem Modell vorgeschriebenen Wahrscheinlichkeiten.

Dies ist offensichtlich ein sehr langweiliges Beispiel. Es stellt sich jedoch heraus, dass MCMC häufig in Situationen anwendbar ist, in denen es schwierig ist, Standard-Monte-Carlo-Techniken oder andere Techniken anzuwenden.

Hier finden Sie einen Artikel, der die Grundlagen dessen, was es ist und warum es funktioniert, behandelt:

http://wellredd.uk/basics-markov-chain-monte-carlo/

Ich bin ein DNA-Analytiker, der zur Interpretation von DNA-Beweisen eine Software zur vollkontinuierlichen probabilistischen Genotypisierung verwendet, und ich muss einer Jury erklären, wie dies funktioniert. Zugegeben, wir vereinfachen zu stark, und ich stelle fest, dass ein Teil dieser zu starken Vereinfachung die Genauigkeit bestimmter Details beeinträchtigt, um das Gesamtverständnis zu verbessern. Aber im Kontext einer Jury, die versteht, wie dieser Prozess bei der DNA-Interpretation ohne akademische Grade und jahrelange Berufserfahrung angewendet wird, erhalten sie das Wesentliche :)

Hintergrund: Die Software verwendet das Hastings-MCMC der Metropole und ein biologisches Modell, das das bekannte Verhalten von DNA-Profilen nachahmt (das Modell basiert auf Validierungsdaten, die durch Laboranalysen vieler DNA-Profile unter bekannten Bedingungen erstellt wurden, die den in der unbekannten Fallarbeit auftretenden Bereich repräsentieren). Es gibt 8 unabhängige Ketten und wir evaluieren die Konvergenz, um zu bestimmen, ob die Einbrenn- und Postakzeptanzrate erneut erhöht werden soll (Standardeinstellung: Burnin 100k akzeptiert und Post 400k akzeptiert).

Auf die Frage der Staatsanwaltschaft / Verteidigung nach MCMC: Wir erklären, dass es sich um eine Markov-Kette (Monte Carlo) handelt, die eine spezielle Klasse / Art von Algorithmus darstellt, die zur Lösung komplexer Probleme verwendet wird Von einem Computer ausgeführte mcmc-Algorithmen arbeiten, indem sie eine Lösung vorschlagen, diese simulieren und dann bewerten, wie gut diese Simulation die tatsächlich beobachteten Evidenzdaten widerspiegelt. Eine Simulation, die gut zur Evidenzbeobachtung passt, hat eine höhere Wahrscheinlichkeit als a Simulation, die nicht gut zur Beobachtung passt ... Über viele wiederholte Abtastungen / Vermutungen vorgeschlagener Lösungen hinweg bewegen sich die Markov-Ketten von den Lösungen mit niedriger Wahrscheinlichkeit zu den Lösungen mit hoher Wahrscheinlichkeit, die das beobachtete Evidenzprofil besser passen / erklären, bis schließlich das Gleichgewicht erreicht ist erreicht,Dies bedeutet, dass der Algorithmus nur eingeschränkt in der Lage ist, neue Vorschläge abzutasten, was zu erheblich höheren Wahrscheinlichkeiten führt

Auf die Frage nach der Metropole Hastings: Wir erklären, dass es sich um eine Verfeinerung des MCMC-Algorithmus handelt, der den Entscheidungsprozess beschreibt, mit dem ein Vorschlag angenommen oder abgelehnt wird. wische nach rechts oder links ", wenn die Jury besonders jung ist !! : p Aber unter Verwendung unserer Hot / Cold-Analogie akzeptieren wir immer eine heiße Vermutung und akzeptieren gelegentlich eine kalte Vermutung zu einem Bruchteil der Zeit und erklären, warum manchmal eine kalte Vermutung akzeptiert wird, um sicherzustellen, dass die Ketten eine größere Bandbreite von Möglichkeiten haben als dagegen, vor dem tatsächlichen Gleichgewicht an einem bestimmten Vorschlag festzuhalten

Bearbeitet, um hinzuzufügen / zu verdeutlichen: Mit der Heiß / Kalt-Analogie erklären wir, dass der Anführer im Kinderspiel ein Zielobjekt / einen Zielbereich im Raum auswählt und die Spieler abwechselnd raten, in welche Richtung sie sich relativ zu ihrer aktuellen Position bewegen sollen. Der Anführer fordert sie auf, ihre Position zu ändern / den Zug zu machen, wenn es eine heiße Vermutung ist, und sie verlieren ihren Zug / bleiben in Position, wenn es eine kalte Vermutung ist. In ähnlicher Weise hängt in unserer Software die Entscheidung zum Verschieben / Akzeptieren nur von der Wahrscheinlichkeit des Vorschlags im Vergleich zur Wahrscheinlichkeit der aktuell gehaltenen Position ab. JEDOCH ist das Ziel dem Anführer im Kinderspiel vordefiniert / bekannt, wohingegen das Ziel in unserer Software ist nicht vordefiniert - es ist völlig unbekannt (auch warum es '

Wie ich schon sagte, super super einfach und absolut ohne technische Details, um das Verständnis zu verbessern - wir bemühen uns, dies auf einem mittleren Bildungsniveau zu erklären. Zögern Sie nicht, Vorschläge zu machen. Ich werde sie einarbeiten.

Diese Frage ist weit gefasst, doch die Antworten sind oft recht beiläufig. Alternativ können Sie das sehen , Papier , die eine kurze mathematische Beschreibung einer breiten Klasse von MCMC Algorithmen einschließlich Metropolis-Hastings - Algorithmen gibt, Gibbs Sampling, Metropolis-in-Gibbs und Hilfsvariablen Methoden, in Scheiben schneiden Probenahme, rekursive Vorschläge, Richtungs Probenahme, Langevin und Hamiltonian Monte Carlo, NUTS-Abtastung, pseudo-marginale Metropolis-Hastings-Algorithmen und pseudo-marginale Hamiltonian Monte Carlo, wie von den Autoren diskutiert.

Eine glaubwürdige Bewertung wird hier abgegeben

Ich werde mehr Zeit finden, um den Inhalt im Stapelaustauschformat auszuarbeiten.

$f(x,y)=z=x^2+2*x*y$$(x,y)$$f(x,y)$$f(x,y)$

$f(x,y,z,t,s,...,zzz)$

Dieses Video (ab 5:50) hat eine sehr gute Intuition.

Stellen Sie sich vor, Sie möchten Punkte auf den grünen (mehrdimensionalen) Zweigen in diesem Bild abtasten. Wenn Sie Punkte über den gesamten schwarzen Superraum werfen und deren Wert überprüfen, verschwenden Sie viel Abtast- (Such-) Energie. Daher wäre es sinnvoller, Ihre (automatisierbare) Probenahmestrategie zu steuern, um Punkte näher an den grünen Zweigen zu finden (wo es darauf ankommt). Grüne Zweige können gefunden werden, indem Sie einmal versehentlich getroffen (oder kontrolliert) werden. Der Rest des Stichprobenaufwands (rote Punkte) wird anschließend generiert. Der Grund, warum die rote zu der grünen Linie hingezogen wird, ist die Markov-Kettenübergangsmatrix, die als Sampling-Engine fungiert.

Für Laien ist MCMC eine energiesparende (kostengünstige) Probenahmemethode, insbesondere wenn in einem massiven und "dunklen" (mehrdimensionalen) Raum gearbeitet wird.