In der Statistik und in der statistischen Physik ist der Algorithmus der Metropole-Hastings eine Kette von Markov Monte Carlo (MCMC) Methode, für eine Folge von zufälligen Proben von einem Wahrscheinlichkeitsvertrieb zu erhalten, für den direkte Stichprobenerhebung schwierig ist. Diese Folge kann verwendet werden, um dem Vertrieb näher zu kommen (d. h., einen histogram zu erzeugen), oder ein Integral (wie ein erwarteter Wert) zu schätzen. Metropole-Hastings und andere MCMC Algorithmen werden allgemein verwendet, um vom mehrdimensionalen Vertrieb besonders auszufallen, wenn die Zahl von Dimensionen hoch ist. Für den einzeln-dimensionalen Vertrieb sind andere Methoden gewöhnlich verfügbar (z.B anpassungsfähige Verwerfungsstichprobenerhebung), der unabhängige Proben vom Vertrieb direkt zurückgeben kann, und vom Problem von aufeinander autobezogenen Proben frei ist, das MCMC Methoden innewohnend ist.

Geschichte

Der Algorithmus wurde nach Nicholas Metropolis genannt, der ein Autor zusammen mit Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller und Edward Teller der 1953-Papiergleichung von Staatsberechnungen durch Schnelle Rechenmaschinen war, die zuerst den Algorithmus für den spezifischen Fall des Vertriebs von Boltzmann vorgeschlagen haben; und W. Keith Hastings, der es zum allgemeineren Fall 1970 erweitert hat. Es gibt Meinungsverschiedenheit über den Kredit für die Entdeckung des Algorithmus.

Edward Teller stellt in seinen Lebenserinnerungen dass die fünf Autoren des 1953-Papiers gearbeiteter fest

zusammen seit "Tagen (und Nächte)".

M. Rosenbluth, in einer mündlichen Geschichte registriert kurz vor seinem Tod

Kredite E. Erzähler mit dem Aufstellen des

ursprüngliches Problem, selbst mit dem Lösen davon und A.W. Rosenbluth (seine Frau) mit

Programmierung des Computers. Gemäß der M. Rosenbluth,

weder Metropole noch A.H. Teller haben in jedem Fall teilgenommen.

Die Rechnung von Rosenbluth von Ereignissen wird durch andere zeitgenössische Erinnerungen unterstützt.

Der Gibbs, der Algorithmus probiert, ist ein spezieller Fall des Algorithmus der Metropole-Hastings, der gewöhnlich schneller und leichter ist zu verwenden, aber weniger allgemein anwendbar ist.

Intuition

Der Algorithmus der Metropole-Hastings kann Proben von jedem Wahrscheinlichkeitsvertrieb ziehen, nur dass eine zur Dichte proportionale Funktion verlangend, berechenbar sein. In Bayesian Anwendungen ist der Normalisierungsfaktor häufig äußerst schwierig zu rechnen, so ist die Fähigkeit, eine Probe zu erzeugen, ohne diese Konstante der Proportionalität zu wissen, eine wichtige Eigenschaft davon und anderen allgemein verwendeten ausfallenden Algorithmen.

Die allgemeine Idee vom Algorithmus ist, eine Reihe von Proben zu erzeugen, die in einer Kette von Markov verbunden werden (wo jede Probe nur mit der direkt vorhergehenden Probe aufeinander bezogen wird). In genug langen Zeiten vergleicht der Vertrieb der erzeugten Proben den Vertrieb. Der Algorithmus arbeitet im Wesentlichen wie folgt (das ist wirklich eine Beschreibung des Metropole-Algorithmus, ein spezieller Fall der Metropole-Hastings):

• Picken Sie erstens eine willkürliche Wahrscheinlichkeitsdichte auf (die Vorschlag-Dichte oder der springende Vertrieb), der einen neuen Musterwert gegeben ein Musterwert andeutet. Für den einfachen Metropole-Algorithmus beschrieben hier muss diese Vorschlag-Dichte darin symmetrisch sein. Ein allgemein verwendeter symmetrischer springender Vertrieb ist ein Vertrieb von Gaussian, der daran in den Mittelpunkt gestellt ist, der dazu neigt, sich zu Punkten in der Nähe zu bewegen (und so den Wahrscheinlichkeitsraum das Verwenden eines zufälligen Spaziergangs erforscht).
• Fangen Sie außerdem mit einem willkürlichen Punkt als die erste Probe an.
• Dann, um eine neue Probe gegeben die neuste Probe zurückzugeben, gehen wir wie folgt weiter:

1. Erzeugen Sie einen vorgeschlagenen neuen Musterwert vom springenden Vertrieb.
2. Berechnen Sie das Annahmeverhältnis.
3. Wenn, akzeptieren Sie, indem Sie untergehen.
4. Akzeptieren Sie sonst mit der Wahrscheinlichkeit. D. h. picken Sie eine gleichförmig verteilte Zufallszahl zwischen 0 und 1, und wenn gesetzt, auf, gehen Sie sonst unter.

Dieser Algorithmus geht weiter, indem er zufällig versucht wird, sich über den Beispielraum manchmal zu bewegen, die Bewegungen akzeptierend und manchmal im Platz bleibend. Bemerken Sie, dass das Annahmeverhältnis anzeigt, wie wahrscheinlich die neue vorgeschlagene Probe in Bezug auf die aktuelle Probe gemäß dem Vertrieb ist. Wenn wir versuchen, sich zu einem Punkt zu bewegen, der wahrscheinlicher ist als der vorhandene Punkt (d. h. ein Punkt in einem Gebiet der höheren Dichte), werden wir immer die Bewegung akzeptieren. Jedoch, wenn wir versuchen, sich zu einem weniger wahrscheinlichen Punkt zu bewegen, werden wir manchmal die Bewegung zurückweisen, und je mehr der Verhältnisfall in der Wahrscheinlichkeit, desto wahrscheinlicher wir den neuen Punkt zurückweisen sollen. So werden wir dazu neigen, in zu bleiben (und große Anzahl von Proben von zurückzugeben), dichte Gebiete, nur gelegentlich den Besuch von Gebieten der niedrigen Dichte. Intuitiv ist das, warum dieser Algorithmus arbeitet, und Proben zurückgibt, die dem gewünschten Vertrieb folgen.

Im Vergleich zu einem Algorithmus wie anpassungsfähige Verwerfung, die ausfällt, der direkt unabhängige Proben von einem Vertrieb erzeugt, haben Metropole-Hastings und andere MCMC Algorithmen mehrere Nachteile:

• Die Proben werden aufeinander bezogen. Wenn auch über die lange Sicht sie wirklich richtig folgen, wird eine Reihe nahe gelegener Proben mit einander aufeinander bezogen und nicht richtig den Vertrieb widerspiegeln. Das bedeutet, dass, wenn wir eine Reihe unabhängiger Proben wollen, wir die Mehrheit von Proben wegwerfen und nur jede n-te Probe, für einen Wert von n (normalerweise bestimmt nehmen müssen, indem wir die Autokorrelation zwischen angrenzenden Proben untersuchen). Autokorrelation kann durch die Erhöhung der springenden Breite reduziert werden (die durchschnittliche Größe eines Sprungs, der mit der Abweichung des springenden Vertriebs verbunden ist), aber das wird auch die Wahrscheinlichkeit der Verwerfung des vorgeschlagenen Sprungs vergrößern. Zu groß oder eine zu kleine springende Größe wird zu einem langsamen Mischen Kette von Markov, d. h. ein hoch aufeinander bezogener Satz von Proben führen, so dass eine sehr hohe Zahl von Proben erforderlich sein wird, um eine angemessene Schätzung jedes gewünschten Eigentums des Vertriebs zu bekommen.
• Obwohl die Kette von Markov schließlich zum gewünschten Vertrieb zusammenläuft, können die anfänglichen Proben einem sehr verschiedenen Vertrieb besonders folgen, wenn der Startpunkt in einem Gebiet der niedrigen Dichte ist. Infolgedessen ist eine Brandwunde - in der Periode normalerweise notwendig, wo eine anfängliche Zahl von Proben (z.B die ersten ungefähr 1,000) weggeworfen wird.

Andererseits leiden einfachste Verwerfungsstichprobenerhebungsmethoden unter dem "Fluch von dimensionality", wo die Wahrscheinlichkeit der Verwerfung exponential als eine Funktion der Zahl von Dimensionen zunimmt. Metropole-Hastings, zusammen mit anderen MCMC Methoden, hat dieses Problem in solchem Maße nicht, und ist so häufig die einzigen verfügbaren Lösungen, wenn die Zahl von Dimensionen des zu probierenden Vertriebs hoch ist. Infolgedessen sind MCMC Methoden häufig die Methoden der Wahl, um Proben von hierarchischen Modellen von Bayesian und anderen hoch-dimensionalen statistischen Modellen verwendet heutzutage in vielen Disziplinen zu erzeugen.

Im multivariate Vertrieb schließt der klassische Algorithmus der Metropole-Hastings, wie beschrieben, oben Auswahl eines neuen mehrdimensionalen Beispielpunkts ein. Wenn die Zahl von Dimensionen hoch ist, findend, dass der richtige springende Vertrieb, um zu verwenden, schwierig sein kann, weil sich die verschiedenen individuellen Dimensionen auf sehr verschiedene Weisen und die springende Breite benehmen (sieh oben) muss "gerade Recht" für alle Dimensionen sofort sein, um das übermäßig langsame Mischen zu vermeiden. Eine alternative Annäherung, die häufig besser in solchen Situationen arbeitet, die als Gibbs bekannt sind, der ausfällt, ist mit Auswahl einer neuen Probe für jede Dimension getrennt von anderen verbunden, anstatt eine Probe für alle Dimensionen sofort zu wählen. Das ist besonders anwendbar, wenn der multivariate Vertrieb aus einer Reihe individueller zufälliger Variablen zusammengesetzt wird, in denen jede Variable auf nur einer kleinen Zahl von anderen Variablen bedingt wird, wie in den meisten typischen hierarchischen Modellen der Fall ist. Die individuellen Variablen werden dann einer nach dem anderen mit jeder Variable probiert, die auf den neusten Werten ganz andere bedingt ist. Verschiedene Algorithmen können verwendet werden, um diese individuellen Proben abhängig von der genauen Form des multivariate Vertriebs zu wählen: Einige Möglichkeiten sind anpassungsfähige Verwerfungsstichprobenerhebung, ein eindimensionaler Schritt der Metropole-Hastings oder Scheibe-Stichprobenerhebung.

Übersicht

In der Größenordnung von der erzeugten Kette von Markov, um zum gewünschten Vertrieb zusammenzulaufen, muss es zwei Bedingungen erfüllen: Ergodicity und Bedingung des Gleichgewichtes, das allgemein erhalten wird, wenn es ausführlich berichtetes Gleichgewicht (eine stärkere Bedingung) erfüllt. Die ergodicity Bedingung stellt sicher, dass höchstens ein asymptotischer Vertrieb besteht. Die ausführliche Gleichgewicht-Bedingung stellt sicher, dass dort mindestens ein asymptotischer Vertrieb besteht.

Eine Kette von Markov erzeugt einen neuen Staat

das hängt nur vom vorherigen Staat ab. Der Algorithmus verwendet eine Vorschlag-Dichte

, der vom aktuellen Staat abhängt, um eine neue vorgeschlagene Probe zu erzeugen.

Dieser Vorschlag wird als der folgende Wert , wenn gezogen, von "akzeptiert"

, die Rechteckverteilung, befriedigt

:

\alpha

Wenn der Vorschlag nicht akzeptiert wird, dann wird der aktuelle Wert dessen wiederholt:.

Zum Beispiel konnte die Vorschlag-Dichte eine auf den aktuellen Staat in den Mittelpunkt gestellte Funktion von Gaussian sein:

:

Q (x'; x_t) \sim N (x_t, \sigma^2 I) \, \!

</Mathematik>

das Lesen als die Wahrscheinlichkeitsdichte-Funktion für den gegebenen der vorherige Wert. Diese Vorschlag-Dichte würde Proben erzeugen, die um den aktuellen Staat mit der Abweichung in den Mittelpunkt gestellt sind. Der ursprüngliche Metropole-Algorithmus fordert auf, dass die Vorschlag-Dichte symmetrisch ist; die Generalisation durch Hastings hebt diese Beschränkung. Es ist auch erlaubt für, überhaupt nicht abzuhängen, in welchem Fall der Algorithmus "Unabhängigkeitskettenmetropole-Hastings" (im Vergleich mit der "Zufälligen Spaziergang-Metropole-Hastings") genannt wird. Die Unabhängigkeitskette kann der M-H Algorithmus mit einer passenden Vorschlag-Dichte-Funktion Serienkorrelation reduzieren und höhere Leistungsfähigkeit anbieten als die zufällige Spaziergang-Version, aber man verlangt einige a priori Kenntnisse des Vertriebs.

Schrittweise Instruktionen

Nehmen Sie an, dass der neuste probierte Wert ist. Um dem Algorithmus der Metropole-Hastings zu folgen, ziehen wir als nächstes einen neuen Vorschlag-Staat mit der Wahrscheinlichkeitsdichte, und berechnen einen Wert

:

a = a_1 a_2 \,

</Mathematik>

wo

:

a_1 = \frac {P (x')} {P (x_t)} \, \!

</Mathematik>

ist das Wahrscheinlichkeitsverhältnis zwischen der vorgeschlagenen Probe und der vorherigen Probe und

dem:

a_2 = \frac {Q (x_t; x')} {Q (x'; x_t) }\

</Mathematik>

ist das Verhältnis der Vorschlag-Dichte in zwei Richtungen (von zu und umgekehrt).

Das ist 1 gleich, wenn die Vorschlag-Dichte symmetrisch ist.

Dann wird der neue Staat gemäß den folgenden Regeln gewählt.

:

\begin {Matrix-}\

\mbox {Wenn} ein \geq 1: & \\

& x_ {t+1} = x',

\end {Matrix-}\

</Mathematik>:\begin {Matrix-}\

\mbox {sonst} & \\

& x_ {t+1} = \left\{\

\begin {Matrix-}\

x '\mbox {mit der Wahrscheinlichkeit} \\

x_t\mbox {mit der Wahrscheinlichkeit} 1-a.

\end {Matrix-}\

\right.

\end {Matrix-}\</Mathematik>

Die Kette von Markov wird von einem willkürlichen Anfangswert angefangen, und der Algorithmus wird für viele Wiederholungen geführt, bis dieser anfängliche Staat "vergessen" wird.

Diese Proben, die verworfen werden, sind als Brandwunde - darin bekannt. Der restliche Satz von akzeptierten Werten dessen vertritt eine Probe vom Vertrieb.

Der Algorithmus arbeitet am besten, wenn die Vorschlag-Dichte die Gestalt des Zielvertriebs vergleicht, von dem direkte Stichprobenerhebung schwierig ist, der ist.

Wenn eine Vorschlag-Dichte von Gaussian verwendet wird, muss der Abweichungsparameter während der Brandwunde - in der Periode abgestimmt werden.

Das wird gewöhnlich durch das Rechnen der Annahmerate getan, die der Bruchteil von vorgeschlagenen Proben ist, der in einem Fenster der letzten Proben akzeptiert wird.

Die gewünschte Annahmerate hängt vom Zielvertrieb ab, jedoch ist es theoretisch gezeigt worden, dass die ideale Annahmequote für einen dimensionalen Vertrieb von Gaussian etwa 50 % ist, zu etwa 23 % für - dimensionaler Zielvertrieb von Gaussian abnehmend.

Wenn zu klein ist, wird sich die Kette langsam vermischen (d. h. die Annahmerate wird hoch sein, aber aufeinander folgende Proben werden den Raum langsam bewegen, und die Kette wird nur langsam zu zusammenlaufen). Andererseits,

wenn zu groß ist, wird die Annahmerate sehr niedrig sein, weil die Vorschläge wahrscheinlich in Gebieten der viel niedrigeren Wahrscheinlichkeitsdichte landen werden, so wird sehr klein sein, und wieder wird die Kette sehr langsam zusammenlaufen.

Siehe auch

• Das vorgetäuschte Ausglühen
• Ausführliches Gleichgewicht
• Metropole des vielfachen Versuchs
• Metropole-Licht transportiert
• Gibbs, der ausfällt

Referenzen

• Bernd A. Berg. Kette von Markov Monte Carlo Simulations und Ihre Statistische Analyse. Singapur, Wissenschaftlicher Welt-2004.
• Siddhartha Chib und Edward Greenberg: "Den Algorithmus der Metropole-Hastings verstehend". Amerikanischer Statistiker, 49 (4), 327-335, 1995
• Bolstad, William M. (2010) Verstehende Rechenbetonte Bayesian Statistik, internationale Standardbuchnummer von John Wiley 0-470-04609-8

Links

• Algorithmus der Metropole-Hastings auf xβ\
• Durchführung von Matlab der Metropole-Hastings