Eșantionare Gibbs

Intrare principală: lanțul Markov Monte Carlo .

În statistici și fizică statistică , un eșantionare Gibbs sau un eșantionator Gibbs este un algoritm MCMC pentru obținerea unei secvențe de eșantioane aleatorii dintr-o distribuție de probabilitate multivariată (adică din distribuția comună a probabilității a două sau mai multe variabile aleatoare ) atunci când eșantionarea directă se dovedește dificilă. Această secvență poate fi utilizată pentru aproximarea distribuției comune (de exemplu, pentru a genera o histogramă a distribuției); să aproximăm distribuția marginală a uneia dintre variabile sau a mai multor subseturi de variabile (de exemplu, parametri necunoscuți sau variabile latente ); sau din nou pentru a calcula o integrală (cum ar fi valoarea așteptată a uneia dintre variabile).

Eșantionarea Gibbs este utilizată în mod obișnuit ca instrument pentru efectuarea inferenței statistice , în special inferenței bayesiene . Prin natura sa, este un algoritm aleatoriu (adică un algoritm care folosește numere aleatorii și, prin urmare, poate produce rezultate distincte de fiecare dată când este rulat), și este o alternativă la algoritmii deterministici utilizați în inferența statistică, cum ar fi algoritmul variațional al lui Bayes. sau metoda de maximă probabilitate .

Introducere

Eșantionarea Gibbs poartă numele fizicianului JW Gibbs , în raport cu analogia dintre algoritmul de eșantionare și fizica statistică . Algoritmul a fost descris de frații Stuart și Donald Geman în 1984, la mai bine de opt decenii după moartea lui Gibbs. ^[1]

Eșantionarea Gibbs este aplicabilă atunci când distribuția comună nu este cunoscută în mod explicit sau este dificil de eșantionat direct, dar distribuția condiționată a fiecărei variabile este cunoscută și se presupune că este mai ușor de eșantionat. Eșantionarea Gibbs generează un eșantion pentru fiecare variabilă, la rândul său, din distribuția lor condițională pe valorile actuale ale variabilelor rămase. Se poate arăta ^[1] că secvența probelor constituie un lanț Markov și că distribuția staționară a acestui lanț este de fapt distribuția comună căutată.

În versiunea sa de bază, eșantionarea Gibbs este un caz special al algoritmului Metropolis-Hastings . Cu toate acestea, în versiunile sale extinse (a se vedea mai jos ), poate fi încorporat într-un context general de referință pentru eșantionarea seturilor mari de variabile prin eșantionarea variabilelor unice (sau, în diferite cazuri, grupuri de variabile) la rândul lor și poate încorpora Metropolis -Algoritmul Hastings (sau metode similare, cum ar fi eșantionarea stratificată ) pentru a implementa unul sau mai mulți pași de eșantionare.

Eșantionarea Gibbs este potrivită în special pentru eșantionarea distribuției posterioare a unei rețele bayesiene, deoarece acest tip de rețea este specificat de obicei printr-o colecție de distribuții condiționate.

Implementare

Să presupunem că vrem să obținem $k$ ${\ displaystyle k}$ $k$ valori $x=\{x_{1},\dots ,x_{p}\}$ ${\ displaystyle x = \ {x_ {1}, \ dots, x_ {p} \}}$ ${\ displaystyle x = \ {x_ {1}, \ dots, x_ {p} \}}$ dintr-o distribuție comună $\left.p(x_{1},\dots ,x_{p})\right.$ ${\ displaystyle \ left.p (x_ {1}, \ dots, x_ {p}) \ right.}$ ${\ displaystyle \ left.p (x_ {1}, \ dots, x_ {p}) \ right.}$ ; este cunoscut pentru fiecare $x_{j}$ ${\ displaystyle x_ {j}}$ $x_j$ componentă a $X$ ${\ displaystyle x}$ $X$ probabilitatea condițională $p(x_{j}|x_{1},\dots ,x_{j-1},x_{j+1},\dots ,x_{p})$ ${\ displaystyle p (x_ {j} | x_ {1}, \ dots, x_ {j-1}, x_ {j + 1}, \ dots, x_ {p})}$ ${\ displaystyle p (x_ {j} | x_ {1}, \ dots, x_ {j-1}, x_ {j + 1}, \ dots, x_ {p})}$ .

Notăm elementul $the$ ${\ displaystyle i}$ $the$ -thth ca. $x^{(i)}=\{x_{1}^{(i)},\dots ,x_{p}^{(i)}\}$ ${\ displaystyle x ^ {(i)} = \ {x_ {1} ^ {(i)}, \ dots, x_ {p} ^ {(i)} \}}$ ${\ displaystyle x ^ {(i)} = \ {x_ {1} ^ {(i)}, \ dots, x_ {p} ^ {(i)} \}}$ și procedați după cum urmează:

Să începem prin setarea arbitrară a valorii $x_{j}^{(0)}$ ${\ displaystyle x_ {j} ^ {(0)}}$ ${\ displaystyle x_ {j} ^ {(0)}}$ pentru fiecare variabilă $x_{j}$ ${\ displaystyle x_ {j}}$ $x_j$ .
Pentru fiecare probă $i=\{1\dots k\}$ ${\ displaystyle i = \ {1 \ dots k \}}$ ${\ displaystyle i = \ {1 \ dots k \}}$ , eșantionăm fiecare variabilă $x_{j}^{(i)}$ ${\ displaystyle x_ {j} ^ {(i)}}$ ${\ displaystyle x_ {j} ^ {(i)}}$ din distribuția condiționată $p(x_{j}^{(i)}|x_{1}^{(i)},\dots ,x_{j-1}^{(i)},x_{j+1}^{(i-1)},\dots ,x_{p}^{(i-1)})$ ${\ displaystyle p (x_ {j} ^ {(i)} | x_ {1} ^ {(i)}, \ dots, x_ {j-1} ^ {(i)}, x_ {j + 1} ^ {(i-1)}, \ dots, x_ {p} ^ {(i-1)})}$ ${\ displaystyle p (x_ {j} ^ {(i)} | x_ {1} ^ {(i)}, \ dots, x_ {j-1} ^ {(i)}, x_ {j + 1} ^ {(i-1)}, \ dots, x_ {p} ^ {(i-1)})}$ . Adică, eșantionăm fiecare variabilă a distribuției din aceasta din urmă, dar condiționând-o pe toate celelalte variabile, folosind cele mai recente valori ale acestora și actualizând variabila la noua sa valoare imediat ce a fost eșantionată.

Eșantionul extras în acest mod aproximează distribuția comună a tuturor variabilelor. Mai mult, distribuția marginală a oricărui subset de variabile poate fi aproximată pur și simplu prin examinarea valorilor extrase pentru acel subset de variabile, ignorând restul. În plus, valoarea așteptată a oricărei variabile poate fi aproximată cu o medie eșantion.

Valorile inițiale ale variabilelor pot fi determinate aleatoriu sau de către un alt algoritm, cum ar fi algoritmul de maximizare a așteptărilor.
De fapt, nu este necesar să se determine o valoare inițială pentru prima variabilă eșantionată.
Este o practică obișnuită să ignori valorile eșantionate în partea inițială (așa-numita perioadă de ardere sau „încălzire”) și apoi să iei în considerare un singur eșantion la fiecare n când sunt solicitate mediile valorilor așteptate . De exemplu, primele 1000 de eșantioane pot fi ignorate și ulterior se utilizează o singură valoare din 100 pentru calcularea, de exemplu, a unei medii, eliminând toate celelalte. Motivele pentru care procedăm în acest fel sunt că (1) eșantioanele consecutive nu sunt independente una de cealaltă, ci formează un lanț Markov cu un anumit grad de corelație; (2) distribuția staționară a lanțului Markov este distribuția comună peste variabilele dorite, dar poate dura mai mult timp pentru a fi realizată staționaritatea. Uneori, sunt necesari algoritmi suplimentari pentru a determina gradul de autocorelație dintre eșantioane și valoarea lui n (valoarea perioadei eșantioanelor stocate pentru calcule) și este necesară o anumită practică.
Procedura de recocire simulată este adesea utilizată pentru a reduce efectul mersului aleatoriu în partea inițială a procesului de eșantionare (adică tendința de a rătăci încet în spațiul de eșantionare, cu un grad ridicat de autocorelare între probe, mai degrabă decât deplasarea rapidă, ca dorit). Alte tehnici care pot reduce autocorelația sunt eșantionarea Gibbs prăbușită și supra- relaxare ordonată ; cf. mai jos.

Relația dintre distribuția condiționată și distribuția comună

În plus față de cele spuse până acum, distribuția condiționată a unei variabile date de toate celelalte este proporțională cu distribuția comună:

p(x_{j}|x_{1},\dots ,x_{j-1},x_{j+1},\dots ,x_{n})={\frac {p(x_{1},\dots ,x_{n})}{p(x_{1},\dots ,x_{j-1},x_{j+1},\dots ,x_{n})}}\propto p(x_{1},\dots ,x_{n})

{\ displaystyle p (x_ {j} | x_ {1}, \ dots, x_ {j-1}, x_ {j + 1}, \ dots, x_ {n}) = {\ frac {p (x_ {1 }, \ dots, x_ {n})} {p (x_ {1}, \ dots, x_ {j-1}, x_ {j + 1}, \ dots, x_ {n})}} \ propto p ( x_ {1}, \ dots, x_ {n})}

{\ displaystyle p (x_ {j} | x_ {1}, \ dots, x_ {j-1}, x_ {j + 1}, \ dots, x_ {n}) = {\ frac {p (x_ {1 }, \ dots, x_ {n})} {p (x_ {1}, \ dots, x_ {j-1}, x_ {j + 1}, \ dots, x_ {n})}} \ propto p ( x_ {1}, \ dots, x_ {n})}

Semnul proporționalității în acest caz înseamnă că numitorul nu este o funcție a $x_{j}$ ${\ displaystyle x_ {j}}$ $x_j$ și, prin urmare, este același pentru toate valorile $x_{j}$ ${\ displaystyle x_ {j}}$ $x_j$ . În practică, pentru a determina natura distribuției condiționate a factorului $x_{j}$ ${\ displaystyle x_ {j}}$ $x_j$ este mai ușor să luați în calcul distribuția comună în funcție de distribuțiile condiționale individuale definite prin modelul grafic al variabilelor (adică graficul asociat cu structura independenței condiționale între diferitele variabile aleatoare implicate, a se vedea și [graficul aleatoriu]), ignorați toate factori care nu sunt funcții ale $x_{j}$ ${\ displaystyle x_ {j}}$ $x_j$ (care împreună, și împreună cu numitorul definit mai sus, constituie constanta de normalizare), iar apoi la sfârșit resetați constanta de normalizare după cum este necesar. În practică, aceasta înseamnă a face una dintre cele trei alegeri:

Dacă distribuția este discretă, se calculează probabilitățile individuale ale tuturor valorilor posibile ale $x_{j}$ ${\ displaystyle x_ {j}}$ $x_j$ , și apoi adăugați pentru a găsi constanta de normalizare.
Dacă distribuția este continuă și de o formă cunoscută, constanta de normalizare este, prin urmare, cunoscută.
În alte cazuri, deoarece multe metode de eșantionare nu o necesită, constanta de normalizare poate fi de obicei ignorată.

Fundament matematic

Eșantionarea Gibbs, sub forma algoritmului descris mai sus, definește un lanț Markov reversibil cu distribuția invariantă dorită $p$ ${\ displaystyle p}$ $p$ . Acest lucru poate fi dovedit în felul următor: definim $x\sim _{j}y$ ${\ displaystyle x \ sim _ {j} y}$ ${\ displaystyle x \ sim _ {j} y}$ de sine $\left.x_{i}=y_{i}\right.$ ${\ displaystyle \ left.x_ {i} = y_ {i} \ right.}$ ${\ displaystyle \ left.x_ {i} = y_ {i} \ right.}$ pentru toți $i\neq j$ ${\ displaystyle i \ neq j}$ $i \ neq j$ și fie $\left.p_{xy}\right.$ ${\ displaystyle \ left.p_ {xy} \ right.}$ ${\ displaystyle \ left.p_ {xy} \ right.}$ probabilitatea unui salt de la $X$ ${\ displaystyle x}$ $X$ la $y$ ${\ displaystyle y}$ $y$ . Deci, șansele de tranziție sunt

p_{xy}={\begin{cases}{\frac {1}{d}}{\frac {p(y)}{\sum _{z\sim _{j}x}p(z)}}&x\sim _{j}y\\0&{\text{altrimenti}}\end{cases}}

{\ displaystyle p_ {xy} = {\ begin {cases} {\ frac {1} {d}} {\ frac {p (y)} {\ sum _ {z \ sim _ {j} x} p (z )}} & x \ sim _ {j} y \\ 0 & {\ text {altfel}} \ end {cases}}}

{\ displaystyle p_ {xy} = {\ begin {cases} {\ frac {1} {d}} {\ frac {p (y)} {\ sum _ {z \ sim _ {j} x} p (z )}} & x \ sim _ {j} y \\ 0 & {\ text {altfel}} \ end {cases}}}

Astfel

p(x)p_{xy}={\frac {1}{d}}{\frac {p(x)p(y)}{\sum _{z\sim _{j}x}p(z)}}={\frac {1}{d}}{\frac {p(y)p(x)}{\sum _{z\sim _{j}y}p(z)}}=p(y)p_{yx}

{\ displaystyle p (x) p_ {xy} = {\ frac {1} {d}} {\ frac {p (x) p (y)} {\ sum _ {z \ sim _ {j} x} p (z)}} = {\ frac {1} {d}} {\ frac {p (y) p (x)} {\ sum _ {z \ sim _ {j} y} p (z)}} = p (y) p_ {yx}}

{\ displaystyle p (x) p_ {xy} = {\ frac {1} {d}} {\ frac {p (x) p (y)} {\ sum _ {z \ sim _ {j} x} p (z)}} = {\ frac {1} {d}} {\ frac {p (y) p (x)} {\ sum _ {z \ sim _ {j} y} p (z)}} = p (y) p_ {yx}}

in aceea $x\sim _{j}y$ ${\ displaystyle x \ sim _ {j} y}$ ${\ displaystyle x \ sim _ {j} y}$ este o relație de echivalență . Prin urmare, sunt satisfăcute ecuațiile de echilibru detaliate , ceea ce implică faptul că lanțul este reversibil și că are o distribuție invariantă $\left.g\right.$ ${\ displaystyle \ left.g \ right.}$ ${\ displaystyle \ left.g \ right.}$ .

Practic, sufixul $\left.j\right.$ ${\ displaystyle \ left.j \ right.}$ ${\ displaystyle \ left.j \ right.}$ nu este ales la întâmplare și lanțul este ciclic în sufixele plasate într-o anumită ordine. În general, acest lucru este echivalent cu un proces non-staționar Markov, dar fiecare etapă va fi în continuare reversibilă și procesul în ansamblu va avea în continuare distribuția staționară dorită (atâta timp cât lanțul poate accesa toate stările în ordinea prestabilită).

Variante și extensii

Există numeroase variații ale eșantionării de bază a lui Gibbs. Scopul acestor variante este de a reduce autocorelația dintre probe suficient pentru a justifica costul asociat procesării suplimentare.

Blochează eșantionarea Gibbs

Un eșantionator de bloc Gibbs grupează două sau mai multe variabile împreună și eșantionează distribuția lor condiționată comună pentru toate variabilele rămase, mai degrabă decât eșantionarea individuală a fiecărei variabile individuale. De exemplu, într-un model Makov ascuns , un eșantionare bloc Gibbs poate preleva din toate variabilele latente prin construirea lanțului Markov într-o singură lovitură folosind algoritmul înainte-înapoi .

Eșantionarea Gibbs prăbușită

O eșantionare Gibbs prăbușită se integrează prin marginalizarea peste una sau mai multe variabile atunci când eșantionarea pentru alte variabile. De exemplu, imaginați-vă că un model constă din trei variabile A , B și C. O simplă eșantionare Gibbs ar preleva p ( A | B , C ), din p ( B | A , C ) și din p ( C | A , B ). O eșantionare Gibbs prăbușită poate înlocui etapa de eșantionare pentru A cu o eșantion prelevată din distribuția marginală p ( A | C ), cu în acest caz variabila B integrată în exterior (sfera de integrare a celorlalte două variabile). Alternativ, variabila B poate fi în totalitate prăbușită sau exclusă din faza de calcul, eșantionarea din p ( A | C ) și p ( C | A ) și nu eșantionarea completă din B. Distribuția unei variabile A care este generată atunci când o variabilă B care parametrizează distribuția A se prăbușește se numește distribuție compusă ; eșantionarea din această distribuție este în general tratabilă atunci când B este variabila conjugată a priori pentru variabila A , în special atunci când distribuțiile lui A și B sunt membri ai familiei exponențiale . Pentru mai multe informații, consultați articolul despre distribuțiile compuse sau Liu (1994). ^[2]

Implementarea unui eșantionare Gibbs prăbușită

Prăbușirea distribuțiilor Dirichlet

În modelele ierarhice bayesiene cu variabile categorice , cum ar fi modelul latent de alocare a Dirichlet și diverse alte modele utilizate în procesarea limbajului natural , este o practică obișnuită „ distribuirea Dirichlet „ din colaps ”care este de obicei folosită ca distribuție a priori pentru variabile. Rezultatul acestui colaps introduce dependențe între toate variabilele categorice dependente de o anumită distribuție Dirichlet a priori, iar distribuția comună a acestor variabile după colaps este o distribuție multinich Dirichlet . Distribuția condiționată a unei variabile categorice date în această distribuție, condiționată de celelalte variabile, ia o formă extrem de simplă care face eșantionarea Gibbs chiar mai ușoară decât dacă nu s-ar fi făcut colapsul. Regulile sunt după cum urmează:

Din prăbușirea unei distribuții Dirichlet a priori afectează numai nodurile părinte și copil ale distribuției a priori. Deoarece nodul părinte este adesea o constantă, de obicei trebuie să fie preocupați doar nodurile copil.
În afara colapsării unei distribuții Dirichlet a priori introduce dependențe între toate variabilele fiice categorice dependente de această distribuție a priori, dar nu introduce alte dependențe între variabilele fiice categorice. (Acest lucru este important de reținut, de exemplu, există mai multe distribuții Dirichlet a priori legate între ele printr-o distribuție a priori mai generală. Fiecare distribuție Dirichlet a priori poate fi prăbușită independent și afectează doar distribuțiile fiice.)
După colaps, distribuția condițională a unei variabile fiice dependente de celelalte ia o formă simplă: probabilitatea de a vedea o valoare dată este proporțională cu distribuția hiper a priori pentru acea valoare, iar numărul tuturor celorlalte noduri dependente ia aceeași valoare. Nodurile care nu depind de aceeași valoare nu trebuie numărate. Rețineți că aceeași regulă se aplică în alte metode de inferență iterativă, cum ar fi metoda variațională Bayes sau metoda de maximizare a valorii așteptate; totuși, dacă metoda implică păstrarea parțială a numărărilor, atunci conturile parțiale pentru valoarea în cauză trebuie să fie însumate pentru toate celelalte noduri dependente. Uneori, acest lucru se numește număr parțial în tot numărul așteptat (număr așteptat) sau cu un termen similar. Rețineți, de asemenea, că probabilitatea este proporțională cu valoarea rezultată; probabilitatea efectivă trebuie determinată prin normalizare pe toate valorile posibile pe care variabila categorică le poate asuma (adică prin adăugarea rezultatului calculat pentru fiecare valoare posibilă a variabilei categorice și împărțirea la această sumă a tuturor rezultatelor calculate).
Dacă un anumit nod categoric are noduri copil dependente (de exemplu, atunci când nodul este o variabilă latentă într-un model format dintr-un amestec de distribuții multiple ), valoarea calculată în pasul anterior trebuie să fie înmulțită cu probabilitățile condiționale reale ( nu o valoare calculat proporțional cu probabilitatea) tuturor nodurilor copil date de nodurile părinte. Pentru o discuție detaliată, consultați articolul Distribuție Dirichlet Multinomial .
În cazul în care apartenența la un grup predeterminat de noduri dependente de o distribuție a Dirichlet a priori se poate schimba dinamic în funcție de o altă variabilă (de exemplu o variabilă categorială indexată de o altă variabilă categorică latentă, ca într-un argument model ( model subiect ) unde de la examinarea documentelor este necesar să ne întoarcem la subiectul tratat în ele), aceleași numărări așteptate sunt calculate din nou, dar cu exactitate pentru a include setul corect de variabile. Vezi articolul lui Dirichlet despre distribuția multinomială pentru discuții suplimentare, inclusiv unul despre modelul argumentelor.

Prăbușirea altor distribuții a priori conjugate

În general, o distribuție a priori conjugată poate fi depășită, atâta timp cât nodurile copil au distribuții conjugate la aceasta. Detaliile matematice sunt discutate în articolul privind distribuțiile compuse . Dacă există un singur nod copil, rezultatul presupune adesea o distribuție cunoscută. De exemplu, prăbușirea unei varianțe distribuite ca o gamă inversă dintr-o rețea cu un singur nod copil distribuit în formă gaussiană va da naștere unei distribuții t-Student . (Pentru ceea ce contează, prăbușirea atât a mediei, cât și a varianței unui singur nod copil cu o distribuție gaussiană va da în continuare o distribuție t-Student, cu condiția ca distribuțiile primelor două să fie conjugate, de exemplu, Gaussianul celei medii, gamma -inversează varianța.)

Dacă există mai multe noduri copil, atunci toate vor deveni dependente, ca în cazul distribuției categorice a lui Dirichlet . Distribuția comună rezultată are o formă închisă care seamănă oarecum cu distribuția compusă, în ciuda faptului că include produsul unui număr de factori, unul pentru fiecare dintre nodurile copil, în ea.

De asemenea, și mai important, distribuția condiționată rezultată a unuia dintre nodurile copil date (și, de asemenea, date nodurilor părinte ale nodurilor prăbușite, dar nu date nodurilor copil ale nodurilor copil) va avea aceeași densitate ca distribuția predictivă posterioară dintre toate nodurile copil rămase. Mai mult, distribuția predictivă posterioară are aceeași densitate ca distribuția compusă de bază a nodului unic, în ciuda parametrilor diferiți. Formula generală este dată în articolul privind distribuțiile compuse .

De exemplu, având în vedere o rețea Bayes formată dintr-un set de noduri identice și independente având o distribuție Gaussiană cu medie și varianță având distribuții conjugate a priori , distribuția condițională a unui nod dată celorlalți, după compunerea atât a mediei, cât și a varianței, va fi o distribuție t-Student . În mod similar, rezultatul formării distribuției gamma a priori a unui număr de noduri de tip Poisson determină distribuția condițională pe un nod dat să presupună o distribuție binomială negativă .

În aceste cazuri în care compoziția produce o distribuție bine cunoscută, există deseori proceduri eficiente de eșantionare, iar utilizarea lor va fi (dar nu neapărat) mai eficientă decât procedura de colaps și, mai degrabă, să eșantioneze distribuțiile nodurilor copil și ale celei separate mai întâi. Cu toate acestea, în cazul în care distribuția compusului nu este bine cunoscută, s-ar putea să nu fie ușor de prelevat din ea, deoarece, în general, nu va aparține familiei distribuțiilor exponențiale și nu va fi de obicei o funcție logaritmic concavă (ceea ce ar face eșantionarea prin metoda de eșantionare ușoară cu eșantionare de respingere adaptivă și ar garanta existența unei forme închise).

Dacă nodurile copil ale nodurilor prăbușite au propriile noduri copil, distribuția condiționată a unuia dintre aceste noduri copil date de toate celelalte noduri din grafic trebuie să ia în considerare distribuția acestor noduri secundare de nivel secundar. În special, distribuția condiționată rezultată va fi proporțională cu un produs al distribuției compozite, așa cum este definit mai sus, și al distribuțiilor condiționale ale tuturor nodurilor copil date de nodurile părinte (dar nu date propriilor copii). Acest lucru rezultă din faptul că distribuția condițională completă este proporțională cu distribuția comună. Dacă copiii nodurilor prăbușite au o distribuție continuă, eșantionarea este fezabilă, indiferent dacă copiii acestor noduri copii au o distribuție continuă sau discretă. Într-adevăr, principiul implicat aici este descris în detaliu în articolul lui Dirichlet despre distribuția multinominală .

Sampler Gibbs cu o relaxare excesivă

Un eșantionator Gibbs cu sovrarilassamento a comandat (suprasolicitat ordonat) mostre la fiecare pas un număr impar fix de valori candidate $x_{j}^{(i)}$ ${\ displaystyle x_ {j} ^ {(i)}}$ ${\ displaystyle x_ {j} ^ {(i)}}$ și le sortează, împreună cu valoarea unică $x_{j}^{(i-1)}$ ${\ displaystyle x_ {j} ^ {(i-1)}}$ ${\ displaystyle x_ {j} ^ {(i-1)}}$ după o anumită ordine bine definită. De sine $x_{j}^{(i-1)}$ ${\ displaystyle x_ {j} ^ {(i-1)}}$ ${\ displaystyle x_ {j} ^ {(i-1)}}$ este cel de-al s-lea cel mai mic element din lista sortată, atunci $x_{j}^{(i)}$ ${\ displaystyle x_ {j} ^ {(i)}}$ ${\ displaystyle x_ {j} ^ {(i)}}$ este selectat ca al s-lea cel mai mare element din lista sortată. Pentru mai multe informații, consultați Neal (1995). ^[3]

Alte extensii

Eșantionarea Gibbs poate fi extinsă în diferite moduri. De exemplu, în cazul variabilelor aleatorii ale căror distribuții condiționale nu sunt ușor de eșantionat, eșantionarea poate fi efectuată cu straturile de eșantionare (eșantionarea feliilor) sau algoritmul Metropolis-Hastings . De asemenea, este posibil să se încorporeze variabile care nu sunt variabile aleatorii, dar a căror valoare este calculată deterministic din alte variabile. Astfel, pot fi încorporate modele liniare generalizate , cum ar fi regresia logistică (adică modele de entropie maximă ). (Software-ul BUGS, de exemplu, permite acest tip de amestecare a modelului).

Modul de eșec

Exemplu de distribuție patologică pentru eșantionarea Gibbs: distribuțiile condiționate de x _{1 și} x ₂ forțează lanțul să rămână într-una din cele două zone cu densitate mai mare fără a ajunge vreodată la cealaltă.

Se poate întâmpla ca două sau mai multe variabile x i de la care să se preleveze să fie puternic corelate (pozitiv sau negativ), dacă se întâmplă acest lucru, la eșantionarea din fiecare dintre aceste variabile, condiționarea celorlalte cu care este corelată va determina valoarea eșantionată să tind să nu se deplaseze niciodată din regiunea în care se află. În cazul limitativ al a două variabile perfect corelate, la eșantionarea uneia dintre ele, având în vedere că distribuția sa este considerată condiționată de cealaltă variabilă, se va extrage o valoare perfect egală cu cea a celeilalte variabile și invers, astfel încât oricare ar fi valoarea inițială este a doua dintre aceste variabile, această valoare nu se va schimba niciodată pentru întregul lanț, împiedicând convergența acestuia. Rețineți că, dacă cunoașteți (sau puteți simula) distribuția condiționată a întregului bloc de variabile conexe, problema poate fi ușor rezolvată prin configurarea unui eșantionator de blocuri Gibbs.

O a doua problemă este cunoscută sub numele de blestemul dimensionalității (un termen inventat de Richard Bellman și utilizat într-o varietate de contexte diferite, dar similare) și apare pentru probleme în care dimensionalitatea lui x este foarte mare. În aceste cazuri, regiunea cu densitate mai mare tinde să se piardă în spațiul x și, prin urmare, eșantionatorul Gibbs este puternic autocorelat. Pentru a da un exemplu simplu, o distribuție de probabilitate este definită pe un vector de 100 biți (100 variabile dihotomice), unde vectorul nul, adică cel cu toate componentele nule, are o probabilitate egală cu 1/2 în timp ce toate celelalte vectorii sunt echipabili, fiecare cu o probabilitate $(2(2^{100}-1))^{-1}$ ${\ displaystyle (2 (2 ^ {100} -1)) ^ {- 1}}$ ${\ displaystyle (2 (2 ^ {100} -1)) ^ {- 1}}$ . Dacă am dori să estimăm probabilitatea vectorului nul, ar fi suficient să efectuăm 100 sau 1000 de probe din distribuția adevărată. Am primi probabil un răspuns aproape de 1/2. Dar probabil ar fi necesare $2^{100}$ ${\ displaystyle 2 ^ {100}}$ ${\ displaystyle 2 ^ {100}}$ probe dintr-un eșantionare Gibbs pentru a obține același rezultat. Niciun computer nu ar putea face acest lucru într-un timp rezonabil.

Această problemă apare indiferent de timpul de ajustare inițial al algoritmului. Acest lucru se întâmplă deoarece în distribuția reală, vectorul nul apare la jumătate din timp. Chiar și un eșantion minim va avea în interior vectorul nul împreună cu vectori non-nul. Dar algoritmul de eșantionare Gibbs alternează pentru perioade lungi de timp generarea numai a vectorului nul (aprox $2^{99}$ ${\ displaystyle 2 ^ {99}}$ ${\ displaystyle 2 ^ {99}}$ eșantioane în serie) cu generarea de vectori diferiți de zero (într-o serie de aproximativ $2^{99}$ ${\ displaystyle 2 ^ {99}}$ ${\ displaystyle 2 ^ {99}}$ probe). Prin urmare, convergența către distribuția adevărată este extrem de lentă, necesitând mult mai mult decât $2^{99}$ ${\ displaystyle 2 ^ {99}}$ ${\ displaystyle 2 ^ {99}}$ pași, care nu sunt fezabili din punct de vedere al calculului într-o perioadă rezonabilă de timp.

Software

Programul OpenBUGS ( inferența bayesiană utilizând eșantionarea Gibbs ) face o analiză bayesiană a modelelor statistice complexe folosind lanțul Monte Carlo Markov .

JAGS ( Doar un alt eșantionator Gibbs ) este un program licențiat GPL pentru analiza modelelor ierarhice bayesiene folosind lanțul Monte Carlo Markov.

Notă

^ ^a ^b S. Geman și D. Geman , Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images , în IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. 6, nr. 6, 1984, pp. 721–741, DOI : 10.1109 / TPAMI.1984.4767596 .
^ Jun S. Liu, The Collapsed Gibbs Sampler in Bayesian Computations with Applications to a Gene Regulation Problem , în Journal of the American Statistical Association , vol. 89, nr. 427, septembrie 1994, pp. 958–966, DOI : 10.2307 / 2290921 , JSTOR 2290921 .
^ Șablon: Citați raport tehnic

Bibliografie

George Casella și Edward I. George, Explaining the Gibbs sampler , în The American Statistician , vol. 46, nr. 3, 1992, pp. 167–174, DOI : 10.2307 / 2685208 , JSTOR 2685208 . (Contiene un sommario riassuntivo e molti riferimenti.)
Alan E. Gelfand e Adrian FM Smith, Sampling-Based Approaches to Calculating Marginal Densities , in Journal of the American Statistical Association , vol. 85, n. 410, 1990, pp. 398–409, DOI : 10.2307/2289776 , JSTOR 2289776 , MR 1141740 .
Andrew Gelman , John B. Carlin, Hal S. Stern, and Donald B. Rubin. Bayesian Data Analysis . London: Chapman and Hall. First edition, 1995. (See Chapter 11.)
CP Robert and G. Casella. "Monte Carlo Statistical Methods" (second edition). New York: Springer-Verlag, 2004.
David A. Levin, Yuval Peres, and Elizabeth L. Wilmer. "Markov Chains and Mixing Times". https://web.archive.org/web/20100516063638/http://www.uoregon.edu/~dlevin/MARKOV/
Bolstad, William M. (2010) Understanding Computational Bayesian Statistics, John Wiley ISBN 978-0-470-04609-8
Christopher M. Bishop, Pattern Recognition and Machine Learning , Springer, 2006, ISBN 0-387-31073-8 .

Collegamenti esterni

The OpenBUGS Project - Bayesian inference Using Gibbs Sampling , su openbugs.info .
Una semplice spiegazione del campionamento di Gibbs può essere trovata nelle pp. 370–371 del volume del professor MacKay's Information Theory, Inference, and Learning Algorithms , disponibile per libera consultazione al sito inference o al sito dell' università di Toronto .
Un'applicazione pratica del campionamento di Gibbs in genomica. , su bayesweb.wadsworth.org . URL consultato il 27 ottobre 2011 (archiviato dall' url originale il 4 novembre 2011) .

Controllo di autorità	Thesaurus BNCF 52492 · LCCN ( EN ) sh85074842 · BNF ( FR ) cb12383654x (data)

[gelman-1] S. Geman și D. Geman , Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images , în IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. 6, nr. 6, 1984, pp. 721–741, DOI : 10.1109 / TPAMI.1984.4767596 .

[2] Jun S. Liu, The Collapsed Gibbs Sampler in Bayesian Computations with Applications to a Gene Regulation Problem , în Journal of the American Statistical Association , vol. 89, nr. 427, septembrie 1994, pp. 958–966, DOI : 10.2307 / 2290921 , JSTOR 2290921 .

[3] Șablon: Citați raport tehnic

[1]

[2]

[3]