Warum sollten wir uns für ein schnelles Mischen in MCMC-Ketten interessieren?

Wenn wir mit der Markov-Kette Monte Carlo arbeiten, um Rückschlüsse zu ziehen, brauchen wir eine Kette, die sich schnell mischt, dh die Unterstützung der hinteren Verteilung schnell durchwandert. Aber ich verstehe nicht, warum wir diese Eigenschaft brauchen, denn nach meinem Verständnis sollten und werden sich die akzeptierten Kandidatenzeichnungen auf den Teil mit der hohen Dichte der posterioren Verteilung konzentrieren. Wenn das, was ich verstehe, wahr ist, wollen wir dann immer noch, dass sich die Kette durch den Träger bewegt (der den Teil mit niedriger Dichte enthält)?

Wenn ich MCMC für die Optimierung verwende, muss ich mich trotzdem um schnelles Mischen kümmern und warum?

Vielen Dank für Ihre Meinung!

mcmc qkhhly
quelle

In der MCMC-Literatur ist bekannt, dass eine geometrisch ergodische Markov-Kette einen exponentiell schnellen Alpha-Mischungszerfall aufweist. Es ist unklar, wie X_ {n} schnell zur Zielverteilung konvergieren und dennoch eine hohe Korrelation zwischen aufeinanderfolgenden Stichproben aufrechterhalten kann. Gibt es einfache Beispiele? Vielen Dank für alle Eingaben!

Antworten:

Der ideale Monte-Carlo-Algorithmus verwendet unabhängige aufeinanderfolgende Zufallswerte. In MCMC sind aufeinanderfolgende Werte nicht unabhängig, was die Konvergenz der Methode langsamer macht als im idealen Monte Carlo. Je schneller es sich jedoch mischt, desto schneller fällt die Abhängigkeit in aufeinanderfolgenden Iterationen ab¹ und desto schneller konvergiert es.

¹ Ich meine hier, dass die aufeinanderfolgenden Werte schnell "fast unabhängig" vom Ausgangszustand sind, oder vielmehr, dass bei gegebenem Wert an einem Punkt die Werte schnell "fast unabhängig" von wenn wächst; Also, wie qkhhly in den Kommentaren sagt, "bleibt die Kette nicht in einer bestimmten Region des Staatsraums stecken". $X_n$ $X_{ń+k}$ $X_n$ $k$

Bearbeiten: Ich denke, das folgende Beispiel kann helfen

Stellen Sie sich vor, Sie möchten den Mittelwert der Gleichverteilung auf durch MCMC schätzen . Sie beginnen mit der geordneten Sequenz ; Bei jedem Schritt wählten Sie Elemente in der Sequenz und mischten sie nach dem Zufallsprinzip. Bei jedem Schritt wird das Element an Position 1 aufgezeichnet. dies konvergiert zur gleichmäßigen Verteilung. Der Wert von steuert die Mischgeschwindigkeit: Wenn , ist es langsam; Wenn , sind die aufeinanderfolgenden Elemente unabhängig und das Mischen ist schnell. $\{1, \dots, n\}$ $(1, \dots, n)$ $k>2$ $k$ $k=2$ $k=n$

Hier ist eine R-Funktion für diesen MCMC-Algorithmus:

mcmc <- function(n, k = 2, N = 5000)
{
  x <- 1:n;
  res <- numeric(N)
  for(i in 1:N)
  {
    swap <- sample(1:n, k)
    x[swap] <- sample(x[swap],k);
    res[i] <- x[1];
  }
  return(res);
}

Wenden wir es für an und zeichnen die sukzessive Schätzung des Mittelwerts entlang der MCMC-Iterationen auf: $n = 99$ $\mu = 50$

n <- 99; mu <- sum(1:n)/n;

mcmc(n) -> r1
plot(cumsum(r1)/1:length(r1), type="l", ylim=c(0,n), ylab="mean")
abline(mu,0,lty=2)

mcmc(n,round(n/2)) -> r2
lines(1:length(r2), cumsum(r2)/1:length(r2), col="blue")

mcmc(n,n) -> r3
lines(1:length(r3), cumsum(r3)/1:length(r3), col="red")

legend("topleft", c("k = 2", paste("k =",round(n/2)), paste("k =",n)), col=c("black","blue","red"), lwd=1)

mcmc Konvergenz

Sie können hier sehen, dass für (in Schwarz) die Konvergenz langsam ist; für (in blau) ist es schneller, aber immer noch langsamer als mit (in rot). $k=2$ $k=50$ $k=99$

Sie können auch ein Histogramm für die Verteilung des geschätzten Mittelwerts nach einer festgelegten Anzahl von Iterationen zeichnen, z. B. 100 Iterationen:

K <- 5000;
M1 <- numeric(K)
M2 <- numeric(K)
M3 <- numeric(K)
for(i in 1:K)
{
  M1[i] <- mean(mcmc(n,2,100));
  M2[i] <- mean(mcmc(n,round(n/2),100));
  M3[i] <- mean(mcmc(n,n,100));
}

dev.new()
par(mfrow=c(3,1))
hist(M1, xlim=c(0,n), freq=FALSE)
hist(M2, xlim=c(0,n), freq=FALSE)
hist(M3, xlim=c(0,n), freq=FALSE)

Histogramme

$k=2$ $k=50$ $k=99$

> mean(M1)
[1] 19.046
> mean(M2)
[1] 49.51611
> mean(M3)
[1] 50.09301
> sd(M2)
[1] 5.013053
> sd(M3)
[1] 2.829185

Elvis
quelle

Ich denke nicht, dass die Aussage "Je schneller es sich mischt, desto schneller klingt die Abhängigkeit in aufeinanderfolgenden Iterationen ab" richtig ist. Aufeinanderfolgende Iterationen hängen beispielsweise immer vom Metropolis-Hastings-Algorithmus ab. Das Mischen hängt davon ab, wie schnell Ihre Samples zur Zielverteilung konvergieren und nicht davon, wie abhängig aufeinanderfolgende Iterationen sind.

Makro

Dies ist das Gleiche: Wenn es schnell zur Zielverteilung konvergiert, nimmt die Abhängigkeit vom Anfangszustand schnell ab ... dies ist natürlich an jedem Punkt der Kette gleich (der als Anfangszustand gewählt werden könnte). Ich denke, der letzte Teil des obigen Beispiels ist für diesen Aspekt aufschlussreich.

Elvis

Ja, die Abhängigkeit vom Anfangszustand zerfällt, nicht unbedingt die Abhängigkeit zwischen aufeinanderfolgenden Iterationen.

Makro

Ich schrieb "in aufeinanderfolgenden Iterationen", nicht "zwischen". Ich meine wirklich "mit" ... das ist mehrdeutig, ich werde korrigieren.

Elvis

Ich denke, ich verstehe, was schnelles Mischen bedeutet. Es ist nicht so, dass sich die Kette zu jedem Teil der Unterstützung der Zielverteilung bewegt. Es geht vielmehr darum, dass die Kette nicht in einem bestimmten Teil des Trägers steckt.

Qkhhly

$(X_n)$ $\alpha$

α (n) = sup_{A, B} {| P (X_{0} \in A, X_{n} \in \cap B) - P (X_{0} \in A) P (X_{n} \in B)}, n \in N,

$\alpha(n) = \sup_{A,B} \left\{\,|P(X_0\in A,X_n\in\cap B) - P(X_0\in A)P(X_n\in B)\right\}\,, n\in \mathbb{N}\,,$

(X_{n})

$(X_n)$

π

$\pi$

Darüber hinaus ist die Unabhängigkeit zwischen den nur in einigen Einstellungen relevant. Im Hinblick auf die Integration ist die negative Korrelation (auch als antithetische Simulation bezeichnet ) der Unabhängigkeit überlegen. $X_n$

Über deinen speziellen Kommentar dazu

... der angenommene Kandidat sollte und wird sich auf den Teil mit der hohen Dichte der posterioren Verteilung konzentrieren. Wenn das, was ich verstehe, wahr ist, wollen wir dann immer noch, dass sich die Kette durch den Träger bewegt (der den Teil mit niedriger Dichte enthält)?

Die MCMC-Kette untersucht das Ziel genau proportional zu seiner Höhe (im stationären Bereich) und verbringt in der Tat mehr Zeit in den Bereichen mit höherer Dichte. Dass die Kette Regionen niedrigerer Dichte durchqueren muss, ist relevant, wenn das Target mehrere Komponenten hoher Dichte aufweist, die durch Regionen niedriger Dichte getrennt sind. (Dies wird auch als multimodale Einstellung bezeichnet.) Langsames Mischen kann die Kette daran hindern, solche Regionen mit niedriger Dichte zu überqueren. Die einzigen Regionen die Kette niemals besuchen sollte, sind die Regionen mit einer Wahrscheinlichkeit von Null unter der Zielverteilung. $(X_n)$

Xi'an
quelle

+1 Vielen Dank für den Kommentar zur antithetischen Simulation, das ist cool

Elvis

@ Xi'an (+1): Dies ist die erste klare Definition von ( -) Mischen , dass ich finde, zwei Fragen (1) gibt es andere Arten von Misch besided Mischen und (2) Gibt es praktisch brauchbare Maße, weil ich nicht sehe, wie ich die Vermischung meiner Kette mit diesem Supremum in der Definition berechnen kann. Als nächstes sehe ich, dass für die Konvergenz nicht ausreicht, gibt es Konvergenzmaße?

α

$\alpha$

α -

$\alpha-$

α \to 0

$\alpha \to 0$

Es gibt verschiedene Arten des Mischens wie Mischen und Mischen. In Verbindung mit MCMC und Zitieren von Wikipedia ist ein streng stationärer Markov-Prozess genau dann eine β-Mischung, wenn es sich um eine aperiodisch wiederkehrende Harris-Kette handelt.

ρ

$\rho$

β

$\beta$

Xi'an

Die Vermutungen, die den Wunsch nach einer schnell mischenden Kette auslösen, lauten, dass Sie sich für die Rechenzeit interessieren und eine repräsentative Probe vom posterior wünschen. Ersteres hängt von der Komplexität des Problems ab: Wenn Sie ein kleines / einfaches Problem haben, spielt es möglicherweise keine Rolle, ob Ihr Algorithmus effizient ist. Letzteres ist sehr wichtig, wenn Sie an posteriorer Unsicherheit interessiert sind oder den posterioren Mittelwert mit hoher Präzision kennen. Wenn Sie sich jedoch nicht für eine repräsentative Probe des Seitenzahns interessieren, weil Sie nur MCMC verwenden, um eine ungefähre Optimierung durchzuführen, ist dies für Sie möglicherweise nicht sehr wichtig.

Ben Lauderdale
quelle