next up previous contents
Next: Gibbs-otanta Up: MCMC-menetelmät Previous: Markovin ketjut

Metropolis-Hastings -algoritmi

Metropolis-Hastings -algoritmilla voidaan tuottaa näytteitä jakaumasta $p(\theta)$, jonka arvoja voidaan laskea normalisointivakiota vaille. Algoritmissa arvotaan ensin alkupiste $\theta^{(0)}$ jostakin kohdejakaumaa approksimoivasta jakaumasta. Tämän jälkeen toistetaan seuraavia askelia, kunnes halutun kokoinen otos on tuotettu:

1.
Olkoon nykyinen piste $\theta$. Arvotaan ehdokasjakaumasta $Q(\theta^*\vert\theta)$ uusi kandidaattipiste $\theta^*$.
2.
Hyväksytään kandidaattipiste todennäköisyydellä
\begin{displaymath}
A(\theta^*\vert\theta) = \min \left\{ \frac{p(\theta^*) Q(\t...
 ...ert\theta^*)}
 {p(\theta) Q(\theta^*\vert\theta)},
 1 \right\},\end{displaymath} (9)

Eli käytännössä ensin arvotaan luku $u \sim U(0,1)$. Jos $u < A(\theta^*\vert\theta)$, niin laitetaan $\theta^*$ talteen ja asetetaan $\theta\leftarrow \theta^*$. Muussa tapauksessa kandidaattipiste hylätään.

Algoritmin toimivuus voidaan todeta huomaamalla, että hyväksyttyjen pisteiden jakauman määräämän Markovin ketjun

\begin{displaymath}
K(\theta,\theta^*) = A(\theta^*\vert\theta) Q(\theta^*\vert\theta)\end{displaymath} (10)

stationäärinen jakauma on $p(\theta)$. Tämä seuraa siitä, että tiukempi tasapainoehto on voimassa, eli Markovin ketju on ajassa kääntyvä:


Ehdokasjakaumasta voidaan käyttää useita erilaisia muotoja:

1.
Symmetrinen ehdokasjakauma. Markovin ketjun ydintä $K(\theta,\theta^*)$ kutsutaan symmetriseksi jos $K(\theta,\theta^*) = K(\theta^*,\theta)$.Ns. Metropolis-algoritmissa ehdokasfunktio riippuu vain nykyisen ja kandidaattipisteen etäisyydestä $\vert\theta- \theta^*\vert$, jolloin $Q(\theta^*\vert\theta) = Q(\theta\vert\theta^*)$. Tällöin Metropolis-Hastings -ehto supistuu muotoon
\begin{displaymath}
A(\theta^*\vert\theta) = \min \left\{ p(\theta^*)/p(\theta), 1 \right\}\end{displaymath} (11)

2.
Satunnaiskävely. Satunnaiskävelyksi kutsutaan Markovin ketjua, jonka tuottamat näytteet ovat muotoa $\theta^{(n+1)} = \theta^{(n)} + w_n$,jossa wn ei riipu itse ketjusta. Ehdokasfunktiossa satunnaiskävely tarkoittaa sitä, että sen arvo riippuu vain kandidaattipisteen ja nykyisen pisteen erotuksesta $Q(\theta^*\vert\theta) = f_w(\theta^* - \theta)$, jossa fw on wn:n jakauman tiheysfunktio.

3.
Riippumattomat ketjut (indepedence chains). Tässä tapauksessa siirtymätodennäköisyydet eivät riipu ketjun edellisestä sijainnista $\theta$, eli $Q(\theta^*\vert\theta) = f(\theta^*)$.Funktion f kannattaa tällöin olla mahdollisimman lähellä kohdejakaumaa $\pi$. Jos ne ovat samat, otanta tapahtuu suoraan jakaumasta $\pi$ ja Metropolis-Hastings -ehdon todennäköisyys on aina tasan 1.

4.
Muita menetelmiä. Yleisin muunnelma algoritmista on Gibbs-otanta , josta on kerrottu enemmän dokumentin seuraavassa osassa. Myös Stokastisen Dynamiikan menetelmä ja Hybridi Monte Carlo voidaan tulkita Metropolis-Hastings -algoritmin variaatioiksi.


next up previous contents
Next: Gibbs-otanta Up: MCMC-menetelmät Previous: Markovin ketjut
Simo Särkkä
8/23/1999