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