Eșantionarea respingerii

În analiza numerică și statisticile de calcul , eșantionarea respingerii este o tehnică de bază utilizată pentru a genera observații dintr-o distribuție . De asemenea, este denumită în mod obișnuit metoda acceptant-respingere sau „algoritm accept-respingere ”.

Eșantionarea respingerii se bazează pe faptul că, pentru a eșantiona o variabilă aleatorie într-o dimensiune, se poate efectua o eșantionare uniformă aleatorie a graficului cartezian bidimensional și păstra eșantioanele în regiune sub graficul funcției sale de densitate. ^[1] ^[2] ^[3] Rețineți că această proprietate poate fi extinsă la funcții N-dimensionale.

Descriere

Pentru a vizualiza rațiunea din spatele eșantionării respingerii, imaginați-vă graficarea funcției de densitate a unei variabile aleatorii pe o placă dreptunghiulară mare și aruncarea de săgeți. Să presupunem că săgețile sunt distribuite uniform în jurul planșei. Acum scoateți toate săgețile care se află în afara zonei de sub curbă. Săgețile rămase vor fi distribuite uniform în zona de sub curbă și pozițiile axei x ale acestor săgeți vor fi distribuite în funcție de densitatea variabilei aleatorii. Acest lucru se datorează faptului că există mai mult spațiu pentru darts să aterizeze acolo unde curba este cea mai mare și, prin urmare, densitatea probabilității este mai mare.

Exemplul descris tocmai este o formă particulară de eșantionare de respingere în care distribuția propunerii este uniformă (deci graficul său este un dreptunghi). Forma generală de eșantionare prin respingere presupune că tabelul din exemplul anterior nu este neapărat dreptunghiular, ci este modelat în funcție de o anumită distribuție din care eșantionarea este ușoară (de exemplu, folosind eșantionarea prin inversare ) și că este cel puțin la fel de mare ca punctul mai mare decât distribuția din care dorim să prelevăm. Dacă acest lucru nu este adevărat, pot exista părți din zona pe care dorim să o prelevăm și care nu pot fi atinse. Eșantionarea respingerii funcționează după cum urmează:

Eșantionează un punct de pe axa x din distribuția propunerii .
Desenați o linie verticală în această poziție x, până la curba de distribuție a propunerii .
Eșantioane uniform de-a lungul acestei linii de la 0 la maximul funcției densității probabilității . Dacă valoarea eșantionată este mai mare decât valoarea de distribuție dorită pe această linie verticală, reveniți la pasul 1.

Acest algoritm poate fi folosit pentru a preleva probe din zona de sub orice curbă, indiferent dacă integrala funcției are valoarea 1. De fapt, scalarea unei funcții cu o constantă nu are niciun efect asupra pozițiilor x eșantionate. Prin urmare, algoritmul poate fi folosit pentru a preleva eșantioane dintr-o distribuție a cărei constantă de normalizare este necunoscută, ceea ce este comun în statisticile de calcul .

Ca un exemplu geometric simplu, să presupunem că vrem să generăm un punct aleatoriu în cercul unității. Primul pas este generarea unui punct candidat ( $(x,y)$ ${\ displaystyle (x, y)}$ $(X y)$ $X, y$ ${\ displaystyle x, y}$ ${\ displaystyle x, y}$ ) unde este $X$ ${\ displaystyle x}$ ${\ displaystyle x}$ $X$ ${\ displaystyle x}$ $X$ Și $y$ ${\ displaystyle y}$ ${\ displaystyle y}$ $y$ ${\ displaystyle y}$ ${\ displaystyle y}$ sunt independente și distribuite uniform între -1 și 1. Dacă $x^{2}+y^{2}\leq 1$ ${\ displaystyle x ^ {2} + y ^ {2} \ leq 1}$ ${\ displaystyle x ^ {2} + y ^ {2} \ leq 1}$ atunci punctul se află în interiorul cercului unității și este acceptat, altfel este respins și se generează un nou candidat.

Un exemplu mai complicat utilizat pentru a genera în mod eficient numere pseudorandom distribuite în mod normal este algoritmul ziggurat .

Algoritm

Algoritmul de eșantionare de respingere generează valori de eșantionare dintr-o distribuție țintă $X$ ${\ displaystyle X}$ $X$ cu funcție de densitate de probabilitate arbitrară $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ folosind o distribuție a propunerii $Da$ ${\ displaystyle Y}$ ${\ displaystyle Y}$ cu densitate de probabilitate $g(x)$ ${\ displaystyle g (x)}$ ${\ displaystyle g (x)}$ .

Algoritmul (folosit de John von Neumann și datând din Buffon și acul său ) pentru a obține un eșantion din distribuție $X$ ${\ displaystyle X}$ ${\ displaystyle X}$ cu densitate $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ folosind probe din distribuție $Da$ ${\ displaystyle Y}$ ${\ displaystyle Y}$ cu densitate $g(x)$ ${\ displaystyle g (x)}$ ${\ displaystyle g (x)}$ este următorul:

Probă ${\textstyle y}$ ${\ textstyle y}$ ${\ textstyle y}$ din distribuție $Da$ ${\ displaystyle Y}$ $Da$ și un eșantion ${\textstyle u}$ ${\ textstyle u}$ ${\ textstyle u}$ începând de la $\mathrm {Unif} (0,1)$ ${\ displaystyle \ mathrm {Unif} (0,1)}$ ${\ displaystyle \ mathrm {Unif} (0,1)}$ (distribuție uniformă pe interval $[0,1]$ ${\ displaystyle [0,1]}$ $[0,1]$ ).
Verifica daca $tu$ $<$ $f$ $($ $y$ $)$ $/$ $M.$ $g$ $($ $y$ $)$ {\ textstyle u <f (y) / Mg (y)} ${\ textstyle u <f (y) / Mg (y)}$ cu $1$ $<$ $M.$ $<$ $\infty$ {\ displaystyle 1 <M <\ infty} ${\ displaystyle 1 <M <\ infty}$ pe sprijinul $X$ {\ displaystyle X} ${\ displaystyle X}$ :
- dacă este adevărat, acceptă $y$ ${\ displaystyle y}$ ${\ displaystyle y}$ ca un eșantion extras din $f(x)$ ${\ displaystyle f (x)}$ $f (x)$ ;
- în caz contrar, respinge valoarea $y$ ${\ displaystyle y}$ ${\ displaystyle y}$ și revine la pasul anterior (faza de eșantionare).

Dezavantaje

Principala problemă cu algoritmul de eșantionare de respingere este că poate genera un număr foarte mare de eșantioane care sunt apoi aruncate, mai ales dacă funcția eșantionată este concentrată într-o anumită regiune. Pentru multe distribuții, această problemă poate fi rezolvată folosind o versiune adaptivă a algoritmului (a se vedea eșantionarea respingerii adaptive ). În alte dimensiuni, este necesar să se utilizeze abordări diferite, cum ar fi metodele Markov Chain Monte Carlo , inclusiv eșantionarea Metropolis sau eșantionarea Gibbs .

Notă

^ George Casella, Christian P. Robert și Martin T. Wells, scheme de eșantionare generalizate Accept-Reject , Institute of Mathematical Statistics, 2004, pp. 342–347, DOI : 10.1214 / lnms / 1196285403 , ISBN 9780940600614 .
^ Radford M. Neal, Slice Sampling , în Annals of Statistics , vol. 31, n. 3, 2003, pp. 705–767, DOI : 10.1214 / aos / 1056562461 .
^ Christopher Bishop, 11.4: Eșantionare de felii , în Recunoașterea modelelor și învățarea automată , Springer , 2006, ISBN 978-0-387-31073-2 .

Elemente conexe

[1] George Casella, Christian P. Robert și Martin T. Wells, scheme de eșantionare generalizate Accept-Reject , Institute of Mathematical Statistics, 2004, pp. 342–347, DOI : 10.1214 / lnms / 1196285403 , ISBN 9780940600614 .

[radford03-2] Radford M. Neal, Slice Sampling , în Annals of Statistics , vol. 31, n. 3, 2003, pp. 705–767, DOI : 10.1214 / aos / 1056562461 .

[bishop06-3] Christopher Bishop, 11.4: Eșantionare de felii , în Recunoașterea modelelor și învățarea automată , Springer , 2006, ISBN 978-0-387-31073-2 .

[1]

[2]

[3]