Metropolis-Hastings algoritme

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 21. maj 2017; verifikation kræver 1 redigering .

Metropolis-Hastings- algoritmen er en samplingsalgoritme , der hovedsageligt bruges til komplekse distributionsfunktioner . Det ligner en del varianssamplingalgoritmen , men her ændres hjælpefordelingsfunktionen over tid. Algoritmen blev først udgivet af Nicholas Metropolis i 1953 , og derefter generaliseret af C. Hastings i 1970 . Gibbs-sampling er et specialtilfælde af Metropolis-Hastings-algoritmen og er mere populær på grund af dens enkelhed og hastighed, selvom den er sjældnere anvendelig.

Metropolis-Hastings-algoritmen giver dig mulighed for at prøve enhver distributionsfunktion. Det er baseret på oprettelsen af en Markov-kæde , det vil sige, ved hvert trin i algoritmen afhænger den nye valgte værdi kun af den forrige . Algoritmen bruger en hjælpefordelingsfunktion afhængig af , for hvilken det er let at generere en stikprøve (for eksempel normalfordelingen ). Ved hvert trin genereres en tilfældig værdi for denne funktion . Så med sandsynlighed $x^{t+1}$ ${\displaystyle x^{t))$ $Q(x'|x^{t})$ ${\displaystyle x^{t))$ $x'$

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

(eller med sandsynlighed 1 hvis ), den valgte værdi accepteres som ny: , ellers er den gamle tilbage: . $u>1$ $x^{t+1}=x'$ ${\displaystyle x^{t+1}=x^{t))$

For eksempel, hvis vi tager normalfordelingsfunktionen som en hjælpefunktion, så

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

En sådan funktion producerer en ny værdi afhængigt af værdien i det foregående trin. I starten krævede Metropolis-algoritmen, at hjælpefunktionen var symmetrisk: , men Hastings-generaliseringen fjerner denne begrænsning. $Q(x',x^{t})=Q(x^{t},x')$

Algoritme

Antag, at vi allerede har valgt en tilfældig værdi . For at vælge den næste værdi skal du først få en tilfældig værdi for funktionen . Så finder vi produktet , hvor ${\displaystyle x^{t))$ $x'$ $Q(x'|x^{t})$ ${\displaystyle a=a_{1}a_{2))$

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

er forholdet mellem sandsynligheden mellem den mellemliggende værdi og den foregående, og

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

er forholdet mellem sandsynligheden for at gå fra til eller tilbage. Hvis den er symmetrisk, så er den anden faktor lig med 1. Den tilfældige værdi ved det nye trin vælges i henhold til reglen: $x'$ ${\displaystyle x^{t))$ $Q$

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

{\begin{matrix}{\mbox{and if }}a<1:&\\&x^{t+1}=\left\{{\begin{matrix}x'{\mbox{ med sandsynlighed }}a\\x^{t}{\mbox{ med sandsynlighed }}1-a.\end{matrix}}\right.\end{matrix}}

Algoritmen starter fra en tilfældig værdi , og kører først "tomgang" et antal trin for at "glemme" om den oprindelige værdi. $x^0$

Algoritmen fungerer bedst, når formen af hjælpefunktionen er tæt på formen af den objektive funktion . Dette er dog ofte umuligt at opnå på forhånd. For at løse dette problem indstilles hjælpefunktionen under algoritmens forberedende fase. For en normalfordeling skal du for eksempel justere dens parameter , så andelen af "accepterede" tilfældige værdier (det vil sige dem, for hvilke ) er tæt på 60%. Hvis det er for lille, vil værdierne være for tæt, og acceptraten vil være høj. Hvis den er for stor, vil nye værdier med stor sandsynlighed springe ud i zonerne med lav sandsynlighed , hvorfor andelen af accepterede værdier vil være lav. $P$ $\sigma ^{2}$ $x^{t+1}=x'$ $\sigma ^{2}$ $\sigma ^{2}$ $P$