Dlaczego powinniśmy przejmować się szybkim mieszaniem w łańcuchach MCMC?

Podczas pracy z łańcuchem Markowa Monte Carlo w celu wyciągnięcia wniosku, potrzebujemy łańcucha, który szybko się miesza, tzn. Szybko porusza się podparcie dystrybucji tylnej. Ale nie rozumiem, dlaczego potrzebujemy tej właściwości, ponieważ z tego, co rozumiem, zaakceptowane losowania kandydujące powinny i będą koncentrować się w części o dużym zagęszczeniu rozkładu bocznego. Jeśli to, co rozumiem, jest prawdą, to czy nadal chcemy, aby łańcuch poruszał się przez podporę (która obejmuje część o niskiej gęstości)?

Ponadto, jeśli korzystam z MCMC do optymalizacji, czy nadal muszę dbać o szybkie miksowanie i dlaczego?

Dziękuję ci, że wyraziłeś swoje zdanie!

mcmc qkhhly
źródło

W literaturze MCMC wiadomo, że gdy łańcuch Markowa jest geometrycznie ergodyczny, ma wykładniczo szybki rozpad mieszania alfa. Nie jestem pewien, w jaki sposób X_ {n} może szybko zbiegać się z rozkładem docelowym, a jednocześnie utrzymywać wysoką korelację między kolejnymi próbkami. Czy są jakieś proste przykłady? Dzięki za wszelkie uwagi!

Odpowiedzi:

Idealny algorytm Monte Carlo wykorzystuje niezależne kolejne losowe wartości. W MCMC kolejne wartości nie są niezależne, co powoduje, że metoda zbiega się wolniej niż idealna metoda Monte Carlo; jednak im szybciej się miesza, tym szybciej zależność zanika w kolejnych iteracjach¹ i tym szybciej się zbiega.

¹ Mam tutaj na myśli to, że kolejne wartości są szybko „prawie niezależne” od stanu początkowego, a raczej biorąc pod uwagę wartość w jednym punkcie, wartości stają się szybko „prawie niezależne” od miarę wzrostu ; więc, jak mówi qkhhly w komentarzach, „łańcuch nie utknie w pewnym obszarze przestrzeni państwowej”. $X_n$ $X_{ń+k}$ $X_n$ $k$

Edycja: Myślę, że poniższy przykład może pomóc

Wyobraź sobie, że chcesz oszacować średnią rozkładu równomiernego na według MCMC. Zaczynasz od uporządkowanej sekwencji ; na każdym kroku wybierasz elementów w sekwencji i losowo je tasujesz. Na każdym kroku zapisywany jest element w pozycji 1; zbiega się to z rozkładem równomiernym. Wartość kontroluje szybkość mieszania: gdy , jest powolna; gdy , kolejne elementy są niezależne, a mieszanie jest szybkie. $\{1, \dots, n\}$ $(1, \dots, n)$ $k>2$ $k$ $k=2$ $k=n$

Oto funkcja R dla tego algorytmu 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);
}

Zastosujmy go dla i wykreślmy kolejne oszacowanie średniej wzdłuż iteracji 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)

konwergencja mcmc

Widać tutaj, że dla (na czarno) konwergencja jest powolna; dla (na niebiesko) jest ono szybsze, ale wciąż wolniejsze niż dla (na czerwono). $k=2$ $k=50$ $k=99$

Możesz również wykreślić histogram dla rozkładu szacowanej średniej po ustalonej liczbie iteracji, np. 100 iteracji:

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)

histogramy

$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
źródło

Nie sądzę, aby stwierdzenie „im szybciej się miesza, tym szybciej zależność zanika w kolejnych iteracjach” jest poprawne. Kolejne iteracje zawsze będą zależały na przykład od algorytmu Metropolis-Hastings. Mieszanie ma związek z szybkością konwergencji próbek do rozkładu docelowego, a nie zależnością kolejnych iteracji.

Makro

To samo: jeśli zbiega się szybko z rozkładem docelowym, zależność od stanu początkowego szybko zanika ... oczywiście będzie on taki sam w dowolnym punkcie łańcucha (który mógłby zostać wybrany jako stan początkowy). Myślę, że ostatnia część powyższego przykładu jest pouczająca dla tego aspektu.

Elvis

Tak, maleje zależność od stanu początkowego, niekoniecznie zależność między kolejnymi iteracjami.

Makro

Pisałem „w kolejnych iteracjach”, a nie „pomiędzy”. Naprawdę mam na myśli „wzdłuż” ... to niejednoznaczne, poprawię.

Elvis

Myślę, że rozumiem, co oznacza szybkie miksowanie. To nie jest tak, że łańcuch przenosi się do każdej części wsparcia dystrybucji docelowej. Raczej chodzi o łańcuch, który nie utknął w pewnej części wsparcia.

qkhhly

W uzupełnieniu obu wcześniejszych odpowiedzi mieszanie jest tylko jednym aspektem konwergencji MCMC. Jest to rzeczywiście bezpośrednio związane z szybkością zapominania o wartości początkowej lub rozkładzie łańcucha Markowa . Na przykład matematyczne pojęcie mieszania jest zdefiniowane przez miarę $(X_n)$ $\alpha$

α (n) = \underset{ZA, b}{łyk} {| P. (X_{0} \in ZA, X_{n} \in \cap b) - P. (X_{0} \in ZA) 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$

$X_n$

O twoim konkretnym komentarzu, że

... zaakceptowane losowania kandydatów powinny i będą koncentrować się w części o dużej gęstości rozkładu bocznego. Jeśli to, co rozumiem, jest prawdą, to czy nadal chcemy, aby łańcuch poruszał się przez podporę (która obejmuje część o niskiej gęstości)?

$(X_n)$

Xi'an
źródło

+1 Bardzo dziękuję za komentarz na temat symulacji antytetycznej, to jest fajne

Elvis

α

$\alpha$

α -

$\alpha-$

α \to 0

$\alpha \to 0$

ρ

$\rho$

β

$\beta$

Założenia, które motywują pragnienie szybkiego mieszania łańcucha, polegają na tym, że zależy ci na czasie obliczeniowym i że chcesz reprezentatywnej próbki z tyłu. To pierwsze będzie zależeć od złożoności problemu: jeśli masz mały / prosty problem, może nie mieć znaczenia, czy Twój algorytm jest wydajny. To ostatnie jest bardzo ważne, jeśli interesuje Cię niepewność a posteriori lub znajomość środka a posteriori z dużą precyzją. Jeśli jednak nie zależy ci na reprezentatywnej próbce tylnej, ponieważ używasz MCMC do przybliżonej optymalizacji, może to nie być dla ciebie bardzo ważne.

Ben Lauderdale
źródło