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ä

$$A(\theta^*\vert\theta) = \min \left\{ \frac{p(\theta^*) Q(\t... ...ert\theta^*)} {p(\theta) Q(\theta^*\vert\theta)}, 1 \right\},$$ (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

$$K(\theta,\theta^*) = A(\theta^*\vert\theta) Q(\theta^*\vert\theta)$$ (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

$$A(\theta^*\vert\theta) = \min \left\{ p(\theta^*)/p(\theta), 1 \right\}$$ (11)

2.

Satunnaiskävely. Satunnaiskävelyksi kutsutaan Markovin ketjua, jonka tuottamat näytteet ovat muotoa $\theta^{(n+1)} = \theta^{(n)} + w_n$,jossa w_n 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 f_w on w_n: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.