Monte karlo metode I primene u bioinformatici master rad

4. GIBSOV UZORKIVAČ

4.1 Uvod

Gibsov algoritam je naziv dobio po fizičaru Josiah Willard Gibbs-u, a predstavljen je 1984. godine, osam decenija nakon njegove smrti, od strane braće Stjuart i Donald Geman (eng. Stuart and Donald Geman) [22]. U svojoj osnovnoj verziji ovaj algoritam je predstavljao specijalan slučaj Metropolis-Hestingovog algoritma, ali se danas smatra za generalnu osnovu uzorkovanja iz velikog skupa promenljivih, a Metropolis algoritam (kao i drugi pogodni algoritami) se može koristiti za implementaciju određenih koraka uzorkovanja.

Gibsov uzorkivač se koristi ukoliko je nepoznata zajednička raspodela ili je teško vršiti direktno uzorkovanje, dok je uslovna raspodela poznata i jednostavna za uzorkovanje. Kao i ostali MKML algoritmi, i Gibsov uzorkivač generiše od uzoraka Markovljev lanac gde je svaki sledeći u korelaciji sa predhodnim uzorkom. Kako bi se dobili nezavisni uzorci potrebno je "prorediti" dobijeni rezultat, kao i odbaciti početne uzorke koji ne odgovaraju željenoj raspodeli. Prednost ovog algoritma u odnosu na ostale je to što prati lokalnu dinamiku ciljane raspodele, a i u mnogim slučajevima predstavlja povoljniji način uzorkvanja od ostalih algoritama. Implementacija Gibsovog algoritma uzorkovanja biće predstavljena u narednom poglavlju gde će biti predstavljeni i neki primeri upotrebe ove metode.

4.2 Gibsov algoritam uzorkovanja

Gibsov algoritam predstavlja specijalnu MKML šemu, čija je glavna karakteristika konstruisanje Markovljevog lanca spajanjem sekvenci uslovnih raspodela duž različitih pravaca (obično duž koordinatnih osa).

Pretpostavimo da možemo slučajnu promenljivu raščlaniti na komponenti (npr. x =), a zatim odaberemo jednu od koordinata, recimo , i "popravimo" je sa novim uzorkom , uzetim iz uslovne raspodele , gde je ). Na osnovu algoritma, Gibsovu strategiju uzorkovanja možemo podeliti na dva tipa koja ćemo sada opisati.

Gibsov uzorkivač slučajnim skeniranjem. Neka je nakon t iteracija , t+1. iteracija sastoji iz sledećih koraka:

• 
  nasumično izaberemo koordinatu prema zadatom vektoru verovatnoća (npr. ())
  
• 
  odredimo iz uslovne raspodele i ostavimo ostale komponente nepromenjene tj. da važi:
  

Gibsov uzorkivač sa sistematskim skeniranjem. Neka je , u t+1.iteraciji:

• 
  odredimo iz uslovne raspodele
  

za .

Lako se može proveriti da nakon svakog koraka bilo kojeg algoritma raspodela ostaje invarijantna. Da bismo ovo dokazali neka je , tada prati marginalnu raspodelu i zato važi:

što znači da nova konfiguracija i dalje prati ciljanu raspodelu Takođe se može pokazati da lanac formiran Gibsovim uzorkivačem geometrijski konvergira i da je stopa konvergencije povezana sa korelacijom promenljivih. Ova stopa konvergencije se kontroliše maksimalnom korelacijom između dve uzastopne iteracije, a Liu, Wong i Kong su istraživali kako grupisanje ovih usko povezanih komponenti može poboljšati efikasnost Gibsovog algoritma [23].

Jednostavna promena uslovnog ažuriranja konfiguracije može poboljšati Gibsov uzorkivač: svaki korak Gibsovog algoritma možemo posmatrati kao slučajno premeštanje trenutnog stanja duž odabranog pravca (kod Metropolis algoritma koristili smo termin perturbacija stanja x). Na primer, ukoliko je odabran pravac prve koordinate, tada se slučajno premeštanje predstavlja na sledeći način:

gde je slučajno izabran broj iz odgovarajuće raspodele. Ukoliko seizabere tako da važi tada je invarijantna.

Popularnost Gibsovog algoritma u statistici proizilazi iz upotrebe uslovne raspodele u svakoj iteraciji. Njenu osnovnu teoriju je predstavio Liu, a Gelfand i Smith su demonstrirali upotrebu uslovne raspodele u mnogim Bajesovim izračunavanjima i izračunavanjima verovatnoće [24].