Warum ist die Hamilton-Dynamik in MCMC in einigen Fällen besser als der Vorschlag für ein zufälliges Gehen?

Die Hamilton-Dynamik ist in einigen Fällen immer besser als der zufällige Spaziergang im Metropolis-Algorithmus. Könnte jemand den Grund mit einfachen Worten ohne zu viel Mathematik erklären?

Lassen Sie mich zunächst feststellen, dass ich nicht glaube, dass die Akzeptanzrate für HMC (Hamiltonian Monte Carlo) immer höher ist als für den Metropolis-Algorithmus. Wie von @JuhoKokkala festgestellt, ist die Akzeptanzrate von Metropolis einstellbar und eine hohe Akzeptanzrate bedeutet nicht, dass Ihr Algorithmus die posteriore Verteilung gut erforscht. Wenn Sie nur eine extrem enge Angebotsverteilung verwenden (z. B. mit einem sehr kleinen ), erhalten Sie eine extrem hohe Akzeptanzrate. aber nur, weil Sie im Grunde immer am selben Ort bleiben, ohne die vollständige posteriore Verteilung zu erkunden.$T(q|q')=\mathcal{N}(q',\sigma I)$$\sigma$

Was ich denke, dass Sie wirklich fragen (und wenn ich Recht habe, dann bearbeiten Sie bitte Ihre Frage entsprechend), ist, warum Hamiltonian Monte Carlo (in einigen Fällen) eine bessere Leistung als Metropolis hat. Mit "besserer Leistung" meine ich, dass für viele Anwendungen, wenn Sie eine von HMC erzeugte Kette mit einer vom Metropolis-Algorithmus erzeugten Kette gleicher Länge (gleiche Anzahl von Proben ) vergleichen, die HMC-Kette früher einen stabilen Zustand erreicht als die Metropolis-Kette, findet einen niedrigeren Wert für die negative Log-Wahrscheinlichkeit (oder einen ähnlichen Wert, aber in weniger Iterationen), die effektive Stichprobengröße ist kleiner, die Autokorrelation der Stichproben nimmt mit der Verzögerung schneller ab usw.$N$

Ich werde versuchen, eine Vorstellung davon zu geben, warum dies geschieht, ohne zu sehr auf mathematische Details einzugehen. Denken Sie also zunächst daran, dass MCMC-Algorithmen im Allgemeinen nützlich sind, um hochdimensionale Integrale (Erwartungen) einer Funktion (oder mehrerer Funktionen) in Bezug auf eine Zieldichte berechnen, insbesondere wenn wir keine haben eine Möglichkeit, direkt von der Zieldichte abzutasten:$f$$\pi(q)$

$\mathbb{E}_{\pi}{[f]}=\int_{\mathcal{Q}} f(q)\pi(q)\text{d}q_1\dots\text{d}q_d$

Dabei ist der Vektor von Parametern, von denen und abhängen, und ist der Parameterraum. In hohen Dimensionen ist das Volumen des Parameterraums, das am meisten zum obigen Integral beiträgt, nicht die Nachbarschaft des Modus von (dh es ist kein enges Volumen um die MLE-Schätzung von ), weil hier ist groß, aber das Volumen ist sehr klein.$q$$d$$f$$\pi$$\mathcal{Q}$$\pi(q)$$q$$\pi(q)$

Angenommen, Sie möchten den durchschnittlichen Abstand eines Punktes vom Ursprung von berechnen , wenn seine Koordinaten unabhängige Gaußsche Variablen mit dem Mittelwert Null und der Einheitsvarianz sind. Dann wird das obige Integral:$q$$\mathbb{R}^d$

$\mathbb{E}_{\pi}{[X]}=\int_{\mathcal{Q}} ||q||(2\pi)^{-d/2}\exp{(-||q||^2/2)}\text{d}q_1\dots\text{d}q_d$

Nun hat die Zieldichte offensichtlich ein Maximum bei 0. Jedoch durch Ändern zu sphärischen Koordinaten und Einführung vonkönnen Sie sehen, dass der Integrand proportional zu . Diese Funktion hat offensichtlich ein Maximum in einiger Entfernung vom Ursprung. Der Bereich innerhalb von der am meisten zum Wert des Integrals beiträgt, wird als typische Menge bezeichnet , und für dieses Integral ist die typische Menge eine Kugelschale mit dem Radius . r = | | q | | r d - 1 exp ( - r 2 / 2 ) d R Q R & agr; $\pi(q)=(2\pi)^{-d/2}\exp{(-||q||^2/2)}$$r=||q||$$r^{d-1}\exp{(-r^2/2)} \text{d}r$$\mathcal{Q}$$R\propto\sqrt{d}$

Nun kann man zeigen, dass unter idealen Bedingungen die von MCMC erzeugte Markov-Kette zuerst zu einem Punkt in der typischen Menge konvergiert, dann die gesamte Menge untersucht und schließlich die Details der Menge weiter untersucht. Auf diese Weise wird die MCMC-Schätzung der Erwartung immer genauer, wobei Verzerrung und Varianz mit zunehmender Anzahl von Schritten abnehmen.

Wenn jedoch die Geometrie des typischen Satzes kompliziert ist (z. B. wenn er einen Höcker in zwei Dimensionen aufweist), hat der Standard-Metropolis-Algorithmus für zufällige Spaziergänge große Schwierigkeiten, die "pathologischen" Details des Satzes zu untersuchen. Es neigt dazu, zufällig "um" diese Regionen zu springen, ohne sie zu erkunden. In der Praxis bedeutet dies, dass der geschätzte Wert für das Integral dazu neigt, um den korrekten Wert zu schwingen, und das Unterbrechen der Kette bei einer endlichen Anzahl von Schritten zu einer stark verzerrten Schätzung führt.

Der Hamilton-Monte-Carlo versucht, dieses Problem zu überwinden, indem er die in der Zielverteilung enthaltenen Informationen (in ihrem Gradienten) verwendet, um den Vorschlag über einen neuen Stichprobenpunkt zu informieren, anstatt einfach eine Angebotsverteilung zu verwenden, die nicht mit dem Zielpunkt zusammenhängt. Deshalb sagen wir, dass HMC die Ableitungen der Zielverteilung verwendet, um den Parameterraum effizienter zu erkunden. Der Gradient der Zielverteilung allein reicht jedoch nicht aus, um den Vorschlagsschritt zu informieren. Wie im Beispiel der durchschnittlichen Entfernung eines zufälligen Punktes vom Ursprung von$\mathbb{R}^d$Der Gradient der Zielverteilung an sich lenkt uns in Richtung des Verteilungsmodus, aber der Bereich um den Modus ist nicht unbedingt der Bereich, der am meisten zum obigen Integral beiträgt, dh es ist nicht die typische Menge.

Um die richtige Richtung zu erhalten, führen wir in HMC einen zusätzlichen Satz von Variablen ein, die als Impulsvariablen bezeichnet werden. Hier kann ein physikalisches Analog helfen. Ein Satellit, der um einen Planeten kreist, bleibt nur dann in einer stabilen Umlaufbahn, wenn sein Impuls den "richtigen" Wert hat. Andernfalls driftet er entweder in den offenen Raum oder wird durch Anziehungskraft auf den Planeten gezogen (spielt hier die Rolle) des Gradienten der Zieldichte, der in Richtung des Modus "zieht"). Auf die gleiche Weise haben die Impulsparameter die Aufgabe, die neuen Samples innerhalb des typischen Satzes zu halten, anstatt sie in Richtung der Schwänze oder in Richtung des Modus treiben zu lassen.

Dies ist eine kleine Zusammenfassung eines sehr interessanten Papiers von Michael Betancourt über die Erklärung des Hamiltonian Monte Carlo ohne übermäßige Mathematik. Das wesentlich detailliertere Papier finden Sie hier .

Eine Sache, die das Papier nicht detailliert genug behandelt, IMO, ist, wann und warum HMC schlechter abschneiden kann als Metropolis mit zufälligem Spaziergang. Dies passiert nicht oft (nach meiner begrenzten Erfahrung), aber es kann passieren. Schließlich führen Sie Farbverläufe ein, die Ihnen helfen, sich im hochdimensionalen Parameterraum zurechtzufinden, aber Sie verdoppeln auch die Dimensionalität des Problems. Theoretisch könnte es vorkommen, dass die Verlangsamung aufgrund der Zunahme der Dimensionalität die Beschleunigung überwindet, die durch die Ausnutzung von Gradienten gegeben ist. Auch (und dies wird in der Veröffentlichung behandelt), wenn der typische Satz Bereiche mit hoher Krümmung aufweist, kann die HMC "überschießen", dh sie könnte sehr weit entfernt in den Schwänzen unbrauchbare Punkte abtasten, die nichts zur Erwartung beitragen. Jedoch, Dies führt zu einer Instabilität des symplektischen Integrators, der in der Praxis zur numerischen Implementierung von HMC verwendet wird. Somit ist diese Art von Problem leicht zu diagnostizieren.

Wie @JuhoKokkala in den Kommentaren erwähnt hat, führt eine hohe Akzeptanzrate nicht unbedingt zu einer guten Leistung. Die Akzeptanzrate von Metropolis Hastings kann durch Verringern der Angebotsverteilung erhöht werden. Dies führt jedoch dazu, dass kleinere Schritte unternommen werden, wodurch das Erkunden der Zielverteilung länger dauert. In der Praxis gibt es einen Kompromiss zwischen Schrittgröße und Akzeptanzrate, und ein angemessenes Gleichgewicht ist erforderlich, um eine gute Leistung zu erzielen.

Der Hamiltonianer Monte Carlo ist tendenziell besser als Metropolis Hastings, da er mit höherer Akzeptanzwahrscheinlichkeit weiter entfernte Punkte erreichen kann. Die Frage ist also: Warum hat HMC für weiter entfernte Punkte tendenziell eine höhere Akzeptanzwahrscheinlichkeit als MH ?

MH hat Probleme, entfernte Punkte zu erreichen, da seine Vorschläge ohne Verwendung von Informationen über die Zielverteilung gemacht werden. Die Angebotsverteilung ist typischerweise isotrop (z. B. ein symmetrischer Gaußscher Wert). Daher versucht der Algorithmus an jedem Punkt, eine zufällige Strecke in eine zufällige Richtung zu bewegen. Wenn der Abstand relativ zu der Geschwindigkeit, mit der sich die Zielverteilung in dieser Richtung ändert, gering ist, besteht eine gute Chance, dass die Dichte an den aktuellen und neuen Punkten ähnlich ist, was zumindest eine vernünftige Chance auf Akzeptanz bietet. Über größere Entfernungen hat sich die Zielverteilung möglicherweise relativ zum aktuellen Punkt erheblich geändert. Daher ist die Wahrscheinlichkeit, zufällig einen Punkt mit ähnlicher oder (hoffentlich) höherer Dichte zu finden, gering, insbesondere wenn die Dimensionalität zunimmt. Wenn zum Beispiel der aktuelle Punkt auf einem schmalen Grat liegt, gibt es '

Im Gegensatz dazu nutzt HMC die Struktur der Zielverteilung. Man kann sich vorstellen, dass sein Vorschlagsmechanismus eine physikalische Analogie verwendet, wie in Neal (2012) beschrieben. Stellen Sie sich einen Puck vor, der auf einer hügeligen, reibungslosen Oberfläche gleitet. Die Position des Pucks repräsentiert den aktuellen Punkt und die Höhe der Oberfläche repräsentiert das negative Protokoll der Zielverteilung. Um einen neuen vorgeschlagenen Punkt zu erhalten, erhält der Puck einen Impuls mit zufälliger Richtung und Größe, und seine Dynamik wird dann simuliert, wenn er über die Oberfläche gleitet. Der Puck beschleunigt in Abfahrtsrichtung und bremst in Aufwärtsrichtung ab (möglicherweise stoppt er sogar und rutscht wieder bergab). Trajektorien, die sich seitwärts entlang der Wand eines Tals bewegen, werden nach unten gebogen. Die Landschaft selbst beeinflusst also die Flugbahn und zieht sie in Richtung Regionen mit höherer Wahrscheinlichkeit. Momentum kann es dem Puck ermöglichen, über kleine Hügel zu kämmen und auch kleine Becken zu überschießen. Die Position des Pucks nach einigen Zeitschritten ergibt den neuen vorgeschlagenen Punkt, der unter Verwendung der Standard-Metropolis-Regel akzeptiert oder abgelehnt wird. Durch die Nutzung der Zielverteilung (und ihres Gradienten) kann HMC entfernte Punkte mit hohen Akzeptanzraten erreichen.

Hier ist eine gute Bewertung:

Neal (2012) . MCMC mit Hamilton-Dynamik.

Als lose Antwort (die anscheinend das ist, wonach Sie suchen) berücksichtigen Hamilton-Methoden die Ableitung der Log-Wahrscheinlichkeit, während dies beim Standard-MH-Algorithmus nicht der Fall ist.