Algoritm Metropolis-Hastings

Intrare principală: lanțul Markov Monte Carlo .

Algoritmul Metropolis-Hastings este o metodă MCMC utilizată pentru a genera valori $x_{1},x_{2},\ldots ,x_{n}$ ${\ displaystyle x_ {1}, x_ {2}, \ ldots, x_ {n}}$ ${\ displaystyle x_ {1}, x_ {2}, \ ldots, x_ {n}}$ care au o distribuție $p(x)$ ${\ displaystyle p (x)}$ $p (x)$ fixat în prealabil. Nu necesită această distribuție $p(x)$ ${\ displaystyle p (x)}$ $p (x)$ este cunoscut, este suficient ca o funcție să fie cunoscută $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ proporțional cu $p(x).$ ${\ displaystyle p (x).}$ ${\ displaystyle p (x).}$ Această cerință slabă ne permite să folosim algoritmul Metropolis-Hastings, în statistica bayesiană, pentru a preleva din distribuții a posteriori a căror integrală este prea dificilă sau imposibilă de calculat analitic.

Metoda a fost descrisă de Hastings în 1970 ca o generalizare a algoritmului Metropolis din 1953.

Algoritmul Metropolis

Pentru a înțelege algoritmul general este util să învățați mai întâi pe cel original, numit Metropolis.

Metoda se bazează pe generarea de valori „propuse” care sunt acceptate sau respinse pentru a converge la distribuție $p(x)$ ${\ displaystyle p (x)}$ $p (x)$ dorit. Are nevoie de o funcție $f(x)\propto p(x)$ ${\ displaystyle f (x) \ propto p (x)}$ ${\ displaystyle f (x) \ propto p (x)}$ și o distribuție de propuneri $J(x^{*}|x_{i})$ ${\ displaystyle J (x ^ {*} | x_ {i})}$ ${\ displaystyle J (x ^ {*} | x_ {i})}$ simetric, adică respectând proprietatea $J(x^{*}|x_{i})=J(x_{i}|x^{*})$ ${\ displaystyle J (x ^ {*} | x_ {i}) = J (x_ {i} | x ^ {*})}$ ${\ displaystyle J (x ^ {*} | x_ {i}) = J (x_ {i} | x ^ {*})}$ . Cele mai comune alegeri pentru distribuirea propunerilor sunt normale ${\mathcal {N}}(x_{i},\delta ^{2})$ ${\ displaystyle {\ mathcal {N}} (x_ {i}, \ delta ^ {2})}$ ${\ displaystyle {\ mathcal {N}} (x_ {i}, \ delta ^ {2})}$ și uniforma $unif(x_{i}-\delta ,x_{i}+\delta )$ ${\ displaystyle unif (x_ {i} - \ delta, x_ {i} + \ delta)}$ ${\ displaystyle unif (x_ {i} - \ delta, x_ {i} + \ delta)}$ , unde delta este un parametru care trebuie specificat înainte de începerea algoritmului.

Fiecare iterație a algoritmului Metropolis constă din următorii pași:

se extrage o nouă valoare $x^{*}$ ${\ displaystyle x ^ {*}}$ $x ^ {*}$ din distribuirea propunerii $J(x^{*}|x_{i})$ ${\ displaystyle J (x ^ {*} | x_ {i})}$ ${\ displaystyle J (x ^ {*} | x_ {i})}$ ;
se calculează raportul $w={\frac {f(x^{*})}{f(x_{i})}}={\frac {p(x^{*})}{p(x_{i})}}$ ${\ displaystyle w = {\ frac {f (x ^ {*})} {f (x_ {i})}} = {\ frac {p (x ^ {*})} {p (x_ {i}) }}}$ ${\ displaystyle w = {\ frac {f (x ^ {*})} {f (x_ {i})}} = {\ frac {p (x ^ {*})} {p (x_ {i}) }}}$ ;
de sine $w\geq 1$ ${\ displaystyle w \ geq 1}$ ${\ displaystyle w \ geq 1}$ accepți noua valoare $x^{*}=x_{i+1}$ ${\ displaystyle x ^ {*} = x_ {i + 1}}$ ${\ displaystyle x ^ {*} = x_ {i + 1}}$ ;
dacă în schimb $w$ $<$ $1$ {\ displaystyle w <1} ${\ displaystyle w <1}$ noua valoare trebuie acceptată cu probabilitate $w$ {\ displaystyle w} $w$ . Apoi este generat un număr aleatoriu $r$ {\ displaystyle r} $r$ distribuite uniform în interval $[$ $0$ $,$ $1$ $]$ {\ displaystyle [0,1]} $[0, 1]$ ;
1. de sine $r<w$ ${\ displaystyle r <w}$ ${\ displaystyle r <w}$ accepți noua valoare $x^{*}=x_{i+1}$ ${\ displaystyle x ^ {*} = x_ {i + 1}}$ ${\ displaystyle x ^ {*} = x_ {i + 1}}$ ;
2. în caz contrar, noua valoare este respinsă și apare $x_{i+1}=x_{i}$ ${\ displaystyle x_ {i + 1} = x_ {i}}$ ${\ displaystyle x_ {i + 1} = x_ {i}}$ .

Pentru a genera o succesiune de $Nu.$ ${\ displaystyle N}$ $Nu.$ elementele repetă acești pași $Nu.$ ${\ displaystyle N}$ $Nu.$ ori începând de la o valoare inițială $x_{0},$ ${\ displaystyle x_ {0},}$ ${\ displaystyle x_ {0},}$ ales în mod arbitrar.

Pentru a avea o estimare bună de $p(x)$ ${\ displaystyle p (x)}$ $p (x)$ este necesar să se genereze secvențe destul de lungi. Alegerea parametrului $\delta$ ${\ displaystyle \ delta}$ $\ delta$ poate fi crucial, dacă este prea mare, doar o mică parte din valorile de testare propuse vor fi acceptate. Dacă, pe de altă parte, este prea mic, lanțul se va deplasa foarte încet și valorile vor fi extrem de autocorelate .

În consecință, fiind $\delta$ ${\ displaystyle \ delta}$ $\ delta$ dependent de forma și scara de $p(x),$ ${\ displaystyle p (x),}$ ${\ displaystyle p (x),}$ trebuie calibrat corect din când în când; pentru estimarea sa este posibil să se procedeze prin aproximare succesivă astfel încât, odată fixată o deltă, numărul valorilor acceptate să fie o treime din total. Alegerea valorii inițiale este, de asemenea, foarte importantă, în general, este mai bine să porniți de la valori de $X$ ${\ displaystyle x}$ $X$ astfel încât $p(x)$ ${\ displaystyle p (x)}$ $p (x)$ asumă valori maxime pentru a avea o bună statistică în zonele cele mai probabile.

Caz multivariat

Algoritmul descris mai sus funcționează exact atât în cazul unic, cât și în cazul multivariat, dar există o a doua abordare a cazului multivariant, deosebit de interesantă atunci când se studiază generalizarea Metropolis-Hastings. În loc să genereze un nou vector la fiecare iterație $x^{*}$ ${\ displaystyle x ^ {*}}$ $x ^ {*}$ și pentru a-l accepta sau respinge în întregime, este posibil să se ia în considerare separat fiecare element al $x=(x_{1},\ldots ,x_{n})$ ${\ displaystyle x = (x_ {1}, \ ldots, x_ {n})}$ ${\ displaystyle x = (x_ {1}, \ ldots, x_ {n})}$ și generând separat o nouă valoare pentru fiecare dintre aceste elemente printr-o distribuție simetrică $J_{j}(x_{j}^{*}|x_{j})$ ${\ displaystyle J_ {j} (x_ {j} ^ {*} | x_ {j})}$ ${\ displaystyle J_ {j} (x_ {j} ^ {*} | x_ {j})}$ să accepte sau să respingi apoi această valoare individual, pentru a o defini $x_{i+1}.$ ${\ displaystyle x_ {i + 1}.}$ ${\ displaystyle x_ {i + 1}.}$

Algoritm Metropolis-Hastings

Algoritmul Metropolis necesită, pentru a garanta convergența sa limită, ca distribuția propunerii să fie simetrică. Această condiție limitează efectiv procesul care generează valorile propuse la domeniul plimbărilor aleatorii . Hastings (1970) a propus o generalizare a algoritmului Metropolis care permite alegerea oricărui tip de propunere.

Algoritmul Metropolis-Hastings continuă în același mod ca și predecesorul său, dar nu necesită simetria distribuției propunerii . Această relaxare a presupunerilor necesită o schimbare în definiția relației $w$ ${\ displaystyle w}$ $w$ , care se redefinește ca fiind $w={\frac {J(x_{i}|x^{*})}{J(x^{*}|x_{i})}}{\frac {f(x^{*})}{f(x_{i})}}={\frac {J(x_{i}|x^{*})}{J(x^{*}|x_{i})}}{\frac {p(x^{*})}{p(x_{i})}}$ ${\ displaystyle w = {\ frac {J (x_ {i} | x ^ {*})} {J (x ^ {*} | x_ {i})}} {\ frac {f (x ^ {*} )} {f (x_ {i})}} = {\ frac {J (x_ {i} | x ^ {*})} {J (x ^ {*} | x_ {i})}} {\ frac {p (x ^ {*})} {p (x_ {i})}}}$ ${\ displaystyle w = {\ frac {J (x_ {i} | x ^ {*})} {J (x ^ {*} | x_ {i})}} {\ frac {f (x ^ {*} )} {f (x_ {i})}} = {\ frac {J (x_ {i} | x ^ {*})} {J (x ^ {*} | x_ {i})}} {\ frac {p (x ^ {*})} {p (x_ {i})}}}$ . Restul algoritmului rămâne neschimbat.

Timpuri caracteristice

Pentru ca algoritmul să piardă memoria datelor inițiale și să convergă către distribuția de eșantionat, este necesar să se efectueze un număr inițial de iterații: acest număr este definit ca timp de termalizare . În mod similar, în calculul erorilor este necesar să se ia în considerare un timp de corelație , care are în vedere autocorelația dintre două eșantionări succesive.

Bibliografie

Hoff, Peter D., Un prim curs în metodele statistice bayesiene , Springer, 2009, ISBN 9780387924076 ,OCLC 432708578 . Adus la 28 decembrie 2018 .
Nicholas Metropolis și colab. , Equation of State Calculs by Fast Computing Machines , în Journal of Chemical Physics , 1953, DOI : 10.1063 / 1.1699114 . Adus la 28 decembrie 2018 .
( EN ) WK Hastings, metode de eșantionare Monte Carlo folosind lanțuri Markov și aplicațiile acestora , în Biometrika , vol. 57, nr. 1, 1 aprilie 1970, pp. 97-109, DOI : 10.1093 / biomet / 57.1.97 . Adus la 28 decembrie 2018 .

Elemente conexe

Portalul de matematică

Portalul de statistici