Por que devemos nos preocupar com a mistura rápida nas cadeias MCMC?

21

Ao trabalhar com a cadeia de Markov Monte Carlo para extrair inferência, precisamos de uma cadeia que se misture rapidamente, ou seja, mova rapidamente o suporte da distribuição posterior. Mas não entendo por que precisamos dessa propriedade, porque, pelo que entendi, o candiado aceito deve e se concentrará na parte de alta densidade da distribuição posterior. Se o que eu entendo é verdade, ainda queremos que a corrente se mova através do suporte (que inclui a parte de baixa densidade)?

Além disso, se estou usando o MCMC para fazer otimização, ainda preciso me preocupar com a mistura rápida e por quê?

Obrigado por compartilhar seus pensamentos!

qkhhly
fonte
Sabe-se na literatura do MCMC que quando uma cadeia de Markov é geometricamente ergódica, ela apresenta decaimento exponencialmente rápido da mistura alfa. Não estou claro como X_ {n} poderia convergir rapidamente para a distribuição de destino e ainda assim manter alta correlação entre amostras sucessivas. Existem exemplos simples? Obrigado por todas as entradas!

Respostas:

16

O algoritmo ideal de Monte Carlo usa valores aleatórios sucessivos independentes . No MCMC, os valores sucessivos não são independentes, o que faz com que o método converja mais lentamente que o Monte Carlo ideal; no entanto, quanto mais rápido ele se mistura, mais rapidamente a dependência decai em iterações sucessivas¹ e mais rápido converge.

¹ Quero dizer aqui que os valores sucessivos são rapidamente "quase independentes" do estado inicial, ou melhor, dado o valor em um ponto, os valores tornam-se rapidamente "quase independentes" de medida que cresce; então, como qkhhly diz nos comentários, "a cadeia não fica presa em uma determinada região do espaço do estado".X ń + K X N kXnXń+kXnk

Editar: acho que o exemplo a seguir pode ajudar

Imagine que você deseja estimar a média da distribuição uniforme em pelo MCMC. Você começa com a sequência ordenada ; em cada etapa, você escolhe elementos na sequência e os embaralha aleatoriamente. Em cada etapa, o elemento na posição 1 é registrado; isso converge para a distribuição uniforme. O valor de controla a rapidez da mistura: quando , é lento; quando , os elementos sucessivos são independentes e a mistura é rápida.( 1 , , n ) k > 2 k k = 2 k = n{1,,n}(1,,n)k>2kk=2k=n

Aqui está uma função 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);
}

Vamos aplicá-lo para e plotar a estimativa sucessiva da média ao longo das iterações do MCMC:μ = 50n=99μ=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)

convergência mcmc

Você pode ver aqui que para (em preto), a convergência é lenta; para (em azul), que é mais rápido, mas ainda mais lenta do que com (a vermelho).k = 50 k = 99k=2k=50k=99

Você também pode plotar um histograma para a distribuição da média estimada após um número fixo de iterações, por exemplo, 100 iterações:

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)

histogramas

Você pode ver que, com (M1), a influência do valor inicial após 100 iterações fornece apenas um resultado terrível. Com , parece ok, com desvio padrão ainda maior do que com . Aqui estão os meios e sd:k = 50 k = 99k=2k=50k=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
fonte
4
Eu não acho que a afirmação "quanto mais rápido ela se mistura, mais rápida a dependência decai em iterações sucessivas" está correta. As iterações sucessivas sempre serão dependentes usando o algoritmo Metropolis-Hastings, por exemplo. A mistura tem a ver com a rapidez com que suas amostras convergem para a distribuição de destino, não com a dependência das iterações sucessivas.
Macro
É o mesmo: se convergir rapidamente para a distribuição de destino, a dependência do estado inicial decai rapidamente ... é claro que será a mesma em qualquer ponto da cadeia (que poderia ter sido escolhido como um estado inicial). Eu acho que a parte final do exemplo acima é esclarecedora para esse aspecto.
Elvis
1
Sim, a dependência do estado inicial decai, não necessariamente a dependência entre iterações sucessivas.
macro
Eu escrevi "em iterações sucessivas", não "entre". Eu realmente quero dizer "junto" ... isso é ambíguo, eu vou corrigir.
Elvis
2
Eu acho que entendo o que mistura rapidamente significa. Não é que a cadeia se mova para todas as partes do suporte à distribuição de destino. Pelo contrário, é mais sobre a cadeia não presa em determinada parte do suporte.
Qkhhly
10

(Xn)α

α(n)=supA,B{|P(X0A,XnB)P(X0A)P(XnB)},nN,
(Xn)π

Xn

Sobre o seu comentário específico que

... o candidato aceito deve e deve se concentrar na parte de alta densidade da distribuição posterior. Se o que eu entendo é verdade, ainda queremos que a corrente se mova através do suporte (que inclui a parte de baixa densidade)?

(Xn)

Xi'an
fonte
1
+1 Muito obrigado pelo comentário sobre a simulação antitética, isso é legal
Elvis
ααα0
ρβ
3

As suposições que motivam o desejo de uma cadeia de mistura rápida são que você se preocupa com o tempo de computação e que deseja uma amostra representativa da parte posterior. O primeiro dependerá da complexidade do problema: se você tiver um problema pequeno / simples, pode não interessar muito se o seu algoritmo é eficiente. O último é muito importante se você estiver interessado em incerteza posterior ou conhecer a média posterior com alta precisão. No entanto, se você não se importa em ter uma amostra representativa da parte posterior porque está apenas usando o MCMC para fazer uma otimização aproximada, isso pode não ser muito importante para você.

Ben Lauderdale
fonte