¿Por qué debemos preocuparnos por la mezcla rápida en las cadenas MCMC?

Question

Cuando se trabaja con la cadena de Markov Monte Carlo para hacer inferencia, necesitamos una cadena que se mezcle rápidamente, es decir, que se mueva a través del soporte de la distribución posterior rápidamente. Pero no entiendo por qué necesitamos esta propiedad, porque por lo que tengo entendido, los sorteos candiatos aceptados deben y se concentran en la parte de alta densidad de la distribución posterior. Si lo que entiendo es cierto, ¿aún queremos que la cadena se mueva a través del soporte (que incluye la parte de baja densidad)?

Además, si estoy utilizando MCMC para hacer la optimización, ¿tengo que seguir preocupándome por la mezcla rápida y por qué?

Gracias por compartir sus ideas.

Answer 1

El algoritmo ideal de Monte Carlo utiliza independiente valores aleatorios sucesivos. En MCMC, los valores sucesivos no son independientes, lo que hace que el método converja más lentamente que el Monte Carlo ideal; sin embargo, cuanto más rápido se mezcle, más rápido decaerá la dependencia en las sucesivas iteraciones¹, y más rápido convergerá.

¹ Quiero decir aquí que los valores sucesivos son rápidamente "casi independientes" del estado inicial, o más bien que dado el valor $X_n$ en un momento dado, los valores $X_{ń+k}$ se vuelven rápidamente "casi independientes" de $X_n$ como $k$ crece; así, como dice qkhhly en los comentarios, "la cadena no se queda estancada en una región determinada del espacio de estados".

Edición: Creo que el siguiente ejemplo puede ayudar

Imagina que quieres estimar la media de la distribución uniforme en $\{1, \dots, n\}$ por MCMC. Se comienza con la secuencia ordenada $(1, \dots, n)$ En cada paso, usted eligió $k>2$ elementos de la secuencia y los baraja al azar. En cada paso, se registra el elemento en la posición 1; esto converge a la distribución uniforme. El valor de $k$ controla la rapidez de la mezcla: cuando $k=2$ es lento; cuando $k=n$ Los elementos sucesivos son independientes y la mezcla es rápida.

Aquí hay una función de R para este algoritmo MCMC :

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);
}

Apliquémoslo para $n = 99$ y trazar la estimación sucesiva de la media $\mu = 50$ a lo largo de las iteraciones MCMC:

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)

Aquí puede ver que para $k=2$ (en negro), la convergencia es lenta; para $k=50$ (en azul), es más rápido, pero sigue siendo más lento que con $k=99$ (en rojo).

También puede trazar un histograma para la distribución de la media estimada después de un número fijo de iteraciones, por ejemplo 100 iteraciones:

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)

Puede ver que con $k=2$ (M1), la influencia del valor inicial después de 100 iteraciones sólo da un resultado terrible. Con $k=50$ parece estar bien, con una desviación estándar aún mayor que con $k=99$ . Aquí están las medias y la sd:

> 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

Answer 2

Para completar las dos respuestas anteriores, la mezcla sólo es un aspecto de la convergencia MCMC. En efecto, está directamente relacionado con la velocidad de olvido del valor inicial o de la distribución de la cadena de Markov $(X_n)$ . Por ejemplo, la noción matemática de $\alpha$ -la mezcla se define por la medida

$$ \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}\,, $$ cuya velocidad de convergencia a cero es característica de la mezcla. Sin embargo, esta medida no está directamente relacionada con la velocidad con la que $(X_n)$ converge a la distribución objetivo $\pi$ . Se puede conseguir una convergencia muy rápida al objetivo y seguir manteniendo una alta correlación entre los elementos de la cadena.

Además, la independencia entre los $X_n$ 's sólo es relevante en algunos escenarios. Cuando se busca la integración, la correlación negativa (también conocida como simulación antitética ) es superior a la independencia.

Sobre su comentario específico de que

...las extracciones de candidatos aceptados deben concentrarse y se concentrarán en la parte de alta densidad de la distribución posterior. Si lo que entiendo es cierto, ¿aún queremos que la cadena se mueva a través del soporte (que incluye la parte de baja densidad)?

la cadena MCMC explora el objetivo en proporción exacta a su altura (en su régimen estacionario) por lo que, efectivamente, pasa más tiempo en la(s) región(es) de mayor densidad. El hecho de que la cadena deba atravesar regiones de menor densidad es relevante cuando el objetivo tiene varios componentes de alta densidad separados por regiones de baja densidad. (La mezcla lenta puede impedir que la cadena atraviese esas regiones de baja densidad. Las únicas regiones $(X_n)$ la cadena nunca debe visitar son las regiones con probabilidad cero bajo la distribución objetivo.

Answer 3

Las presunciones que motivan el deseo de una cadena de mezcla rápida son que te importa el tiempo de cálculo y que quieres una muestra representativa de la parte posterior. Lo primero dependerá de la complejidad del problema: si tienes un problema pequeño/simple, puede no importar mucho que tu algoritmo sea eficiente. Lo segundo es muy importante si le interesa la incertidumbre posterior o conocer la media posterior con alta precisión. Sin embargo, si no le importa tener una muestra representativa de la posterior porque sólo está usando MCMC para hacer una optimización aproximada, esto puede no ser muy importante para usted.