Metropoli-Hastings-algoritmi

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 21. toukokuuta 2017 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Metropolis-Hastings- algoritmi on näytteenottoalgoritmi , jota käytetään pääasiassa monimutkaisiin jakelufunktioihin . Se on jossain määrin samanlainen kuin varianssinäytteenottoalgoritmi , mutta tässä apujakaumafunktio muuttuu ajan myötä. Algoritmin julkaisi ensimmäisenä Nicholas Metropolis vuonna 1953 , ja sitten C. Hastings yleisti vuonna 1970 . Gibbs-näytteenotto on Metropolis-Hastings-algoritmin erikoistapaus, ja se on suositumpi yksinkertaisuutensa ja nopeudensa vuoksi, vaikkakin harvemmin sovellettavissa.

Metropolis-Hastings-algoritmin avulla voit ottaa näytteitä mistä tahansa jakelufunktiosta. Se perustuu Markov-ketjun luomiseen, eli jokaisessa algoritmin vaiheessa valittu uusi arvo riippuu vain edellisestä . Algoritmi käyttää apujakaumafunktiota riippuen , jolle on helppo muodostaa näyte (esimerkiksi normaalijakauma ). Jokaisessa vaiheessa tälle funktiolle luodaan satunnainen arvo . Siis todennäköisyydellä $x^{t+1}$ ${\näyttötyyli x^{t))$ $Q(x'|x^{t})$ ${\näyttötyyli x^{t))$ $x'$

$u={\frac {P(x')Q(x^{t}|x')}{P(x^{t})Q(x'|x^{t)))))$

(tai todennäköisyydellä 1, jos ), valittu arvo hyväksytään uudeksi: , muuten vanha jätetään: . $u>1$ $x^{t+1}=x'$ ${\displaystyle x^{t+1}=x^{t))$

Esimerkiksi jos otamme normaalijakauman funktion apufunktiona, niin

$Q(x'|x^{t})\sim N(x^{t},\sigma ^{2}I).$

Tällainen funktio tuottaa uuden arvon riippuen edellisen vaiheen arvosta. Aluksi Metropolis-algoritmi vaati, että apufunktio on symmetrinen: , mutta Hastingsin yleistys poistaa tämän rajoituksen. $Q(x',x^{t})=Q(x^{t},x')$

Algoritmi

Oletetaan, että olemme jo valinneet satunnaisen arvon . Seuraavan arvon valitsemiseksi hanki ensin satunnainen arvo funktiolle . Sitten löydämme tuotteen , missä ${\näyttötyyli x^{t))$ $x'$ $Q(x'|x^{t})$ ${\displaystyle a=a_{1}a_{2))$

$a_{1}={\frac {P(x')}{P(x^{t))}}$

on väliarvon ja edellisen todennäköisyyksien suhde, ja

$a_{2}={\frac {Q(x^{t}|x')}{Q(x'|x^{t})))$

on todennäköisyyksien suhde toiselle tai takaisin. Jos se on symmetrinen, niin toinen kerroin on yhtä suuri kuin 1. Satunnaisarvo uudessa vaiheessa valitaan säännön mukaan: $x'$ ${\näyttötyyli x^{t))$ $K$

{\begin{matrix}{\mbox{If }}a\geq 1:&\\&x^{t+1}=x',\end{matrix}}

{\begin{matrix}{\mbox{ja jos }}a<1:&\\&x^{t+1}=\left\{{\begin{matrix}x'{\mbox{ todennäköisyydellä }}a\\x^{t}{\mbox{ todennäköisyydellä }}1-a.\end{matrix}}\right.\end{matrix}}

Algoritmi alkaa satunnaisesta arvosta ja suorittaa ensin "tyhjäkäynnillä" useita vaiheita "unohdakseen" alkuarvon. $x^0$

Algoritmi toimii parhaiten, kun apufunktion muoto on lähellä kohdefunktion muotoa . Tämä on kuitenkin usein mahdotonta saavuttaa etukäteen. Tämän ongelman ratkaisemiseksi aputoiminto viritetään algoritmin valmisteluvaiheessa. Säädä esimerkiksi normaalijakaumaa varten sen parametria niin, että "hyväksyttyjen" satunnaisarvojen osuus (eli ne, joille ) on lähellä 60%. Jos se on liian pieni, arvot ovat liian lähellä ja hyväksymisaste on korkea. Jos se on liian suuri, niin suurella todennäköisyydellä uudet arvot hyppäävät ulos pienen todennäköisyyden vyöhykkeille , minkä vuoksi hyväksyttyjen arvojen osuus on pieni. $P$ $\sigma ^{2}$ $x^{t+1}=x'$ $\sigma ^{2}$ $\sigma ^{2}$ $P$