Почему мы должны заботиться о быстром смешивании в цепочках MCMC?

При работе с цепью Маркова Монте-Карло, чтобы сделать вывод, нам нужна цепь, которая быстро перемешивается, т.е. быстро перемещается через опору заднего распределения. Но я не понимаю, зачем нам это свойство, потому что из того, что я понимаю, принятые кандидаты должны и будут сконцентрированы в части высокой плотности заднего распределения. Если то, что я понимаю, верно, то хотим ли мы, чтобы цепь проходила через опору (которая включает в себя часть с низкой плотностью)?

Кроме того, если я использую MCMC для оптимизации, нужно ли мне по-прежнему заботиться о быстром микшировании и почему?

Спасибо, что поделились своими мыслями!

mcmc qkhhly
источник

Из литературы MCMC известно, что когда цепь Маркова является геометрически эргодической, она экспоненциально быстро затухает при альфа-перемешивании. Мне неясно, как X_ {n} может быстро сходиться к целевому распределению, и в то же время поддерживать высокую корреляцию между последовательными выборками. Есть ли простые примеры? Спасибо за любые вклады!

Ответы:

Идеальный алгоритм Монте-Карло использует независимые последовательные случайные значения. В MCMC последовательные значения не являются независимыми, что заставляет метод сходиться медленнее, чем идеальный метод Монте-Карло; однако, чем быстрее он смешивается, тем быстрее затухает зависимость в последовательных итерациях¹ и быстрее сходится.

¹ Я имею в виду, что последовательные значения быстро «почти не зависят» от начального состояния, или, скорее, что, учитывая значение в одной точке, значения становятся быстро «почти независимыми» от с ; Итак, как говорит Кххли в комментариях, «цепочка не застревает в определенной области пространства состояний». $X_n$ $X_{ń+k}$ $X_n$ $k$

Изменить: я думаю, что следующий пример может помочь

Представьте, что вы хотите оценить среднее значение равномерного распределения по по MCMC. Вы начинаете с упорядоченной последовательности ; на каждом шаге вы выбираете элементов в последовательности и случайным образом перемешиваете их. На каждом шаге элемент в позиции 1 записывается; это сходится к равномерному распределению. Значение контролирует скорость перемешивания: когда , это медленно; когда , последовательные элементы независимы, и смешивание происходит быстро. $\{1, \dots, n\}$ $(1, \dots, n)$ $k>2$ $k$ $k=2$ $k=n$

Вот функция R для этого алгоритма 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);
}

Давайте применим его для и построим последовательную оценку среднего значения вдоль итераций MCMC: $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

Здесь вы можете видеть, что для (в черном цвете) сходимость медленная; для (синим цветом) это быстрее, но все же медленнее, чем с (красным). $k=2$ $k=50$ $k=99$

Вы также можете построить гистограмму для распределения оценочного среднего значения после фиксированного числа итераций, например, 100 итераций:

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)

гистограмм

$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

Элвис
источник

Я не думаю, что утверждение «чем быстрее оно смешивается, тем быстрее затухает зависимость в последовательных итерациях» является правильным. Например, последовательные итерации всегда будут зависеть от алгоритма Метрополиса-Гастингса. Микширование связано с тем, насколько быстро ваши образцы сходятся к целевому распределению, а не с тем, насколько зависимы последовательные итерации.

Макро

Это то же самое: если оно быстро сходится к целевому распределению, зависимость от начального состояния быстро затухает ... конечно, это будет одинаковым в любой точке цепи (которую можно было бы выбрать в качестве начального состояния). Я думаю, что последняя часть приведенного выше примера является полезным для этого аспекта.

Элвис

Да, зависимость от исходного состояния затухает, необязательно зависимость между последовательными итерациями.

Макро

Я написал «в последовательных итерациях», а не «между». Я действительно имею в виду "вместе" ... это неоднозначно, я исправлю.

Элвис

Я думаю, я понимаю, что быстро означает смешивание. Дело не в том, что цепочка движется к каждой части поддержки целевого распределения. Скорее, речь идет о цепочке, не застрявшей в определенной части поддержки.

qkhhly

$(X_n)$ $\alpha$

α (N) знак равно \underset{A, В}{вир} {| п ({Икс}_{0} \in A, {Икс}_{N} \in \cap В) - п ({Икс}_{0} \in A) п ({Икс}_{N} \in В)}, 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$

$X_n$

О вашем конкретном комментарии, который

... принятый кандидат должен и будет сконцентрирован в части высокой плотности заднего распределения. Если то, что я понимаю, верно, то хотим ли мы, чтобы цепь проходила через опору (которая включает в себя часть с низкой плотностью)?

$(X_n)$

Сиань
источник

+1 Большое спасибо за комментарий о антитезе симуляции, это круто

Elvis

α

$\alpha$

α -

$\alpha-$

α \to 0

$\alpha \to 0$

ρ

$\rho$

β

$\beta$

Предположения, которые мотивируют стремление к быстрому микшированию цепочки, заключаются в том, что вы заботитесь о вычислении времени и что вам нужна репрезентативная выборка сзади. Первое будет зависеть от сложности проблемы: если у вас небольшая / простая проблема, может не иметь большого значения, эффективен ли ваш алгоритм. Последнее очень важно, если вас интересует задняя неопределенность или вы знаете заднее среднее с высокой точностью. Однако, если вам не нужна репрезентативная выборка задней части, потому что вы просто используете MCMC для приблизительной оптимизации, это может быть не очень важно для вас.

Бен Лодердейл
источник