Metropolis-Hastings algoritm

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 21 maj 2017; verifiering kräver 1 redigering .

Metropolis-Hastings- algoritmen är en samplingsalgoritm som huvudsakligen används för komplexa distributionsfunktioner . Det är något likt varianssamplingsalgoritmen , men här ändras hjälpdistributionsfunktionen över tiden. Algoritmen publicerades först av Nicholas Metropolis 1953 och generaliserades sedan av C. Hastings 1970 . Gibbs sampling är ett specialfall av Metropolis-Hastings-algoritmen och är mer populär på grund av dess enkelhet och hastighet, även om den är mindre ofta tillämplig.

Metropolis-Hastings-algoritmen låter dig prova vilken distributionsfunktion som helst. Det är baserat på skapandet av en Markov-kedja , det vill säga vid varje steg i algoritmen beror det nya värdet endast på det föregående . Algoritmen använder en hjälpdistributionsfunktion beroende på , för vilken det är lätt att generera ett sampel (till exempel normalfördelningen ). Vid varje steg genereras ett slumpmässigt värde för denna funktion . Då med sannolikhet $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 sannolikhet 1 om ), det valda värdet accepteras som nytt: , annars lämnas det gamla: . $u>1$ $x^{t+1}=x'$ ${\displaystyle x^{t+1}=x^{t))$

Till exempel, om vi tar normalfördelningsfunktionen som en hjälpfunktion, då

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

En sådan funktion ger ett nytt värde beroende på värdet i föregående steg. Från början krävde Metropolis-algoritmen att hjälpfunktionen var symmetrisk: , men Hastings-generaliseringen tar bort denna begränsning. $Q(x',x^{t})=Q(x^{t},x')$

Algoritm

Anta att vi redan har valt ett slumpmässigt värde . För att välja nästa värde, skaffa först ett slumpmässigt värde för funktionen . Sedan hittar vi produkten , var ${\displaystyle x^{t))$ $x'$ $Q(x'|x^{t})$ ${\displaystyle a=a_{1}a_{2))$

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

är förhållandet mellan sannolikheterna mellan det mellanliggande värdet och det föregående, och

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

är förhållandet mellan sannolikheterna att gå från till eller tillbaka. Om den är symmetrisk är den andra faktorn lika med 1. Det slumpmässiga värdet vid det nya steget väljs enligt regeln: $x'$ ${\displaystyle x^{t))$ $F$

{\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 sannolikhet }}a\\x^{t}{\mbox{ med sannolikhet }}1-a.\end{matrix}}\right.\end{matrix}}

Algoritmen utgår från ett slumpmässigt värde och kör först "tomgång" ett antal steg för att "glömma" det initiala värdet. $x^0$

Algoritmen fungerar bäst när hjälpfunktionens form är nära objektivfunktionens form . Detta är dock ofta omöjligt att uppnå på förhand. För att lösa detta problem ställs hjälpfunktionen in under det förberedande skedet av algoritmen. Till exempel, för en normalfördelning, justera dess parameter så att andelen "accepterade" slumpmässiga värden (det vill säga de för vilka ) är nära 60%. Om det är för litet kommer värdena att vara för nära och acceptansgraden blir hög. Om det är för stort, kommer nya värden med hög sannolikhet att hoppa ut i zonerna med låg sannolikhet , varför andelen accepterade värden kommer att vara låg. $P$ $\sigma ^{2}$ $x^{t+1}=x'$ $\sigma ^{2}$ $\sigma ^{2}$ $P$