Monte karlo metode I primene u bioinformatici master rad

3.4 Specijalni Metropolis algoritmi

Kako bismo ilustrovali praktičnost Metropolis - Hestingovog algoritma opisaćemo nekoliko njegovih specijalnih slučajeva koji se najčešće pronalaze u literaturi.

3.4.1 Slučajno kretanje

Slučajno kretanje je jedan od MKML algoritama koji je danas najčešće u upotrebi, a koji je prvi put opisan u Metropolisovom radu 1953. godine [5]. Pretpostavićemo da je ciljana raspodela definisana na -dimenzionalnom Euklidovom prostoru . Metod slučajnog kretanja se zasniva na lokalnom istraživanju okoline trenutne vrednosti Markovljevog lanca. Ideja ove impelemntacije je da se odabere uzorak takav da je:

gde je slučajna promena (perturbacija) sa raspodelom koja ne zavisi od npr. uniformna ili normalna raspodela predstavlja predloženu raspodelu i oblika je , a Markovljev lanac izveden pomoću ove raspodele se naziva slučajno kretanje ukoliko je simetrična.

Metropolis algoritam slučajnog kretanja se sastoji iz iteracije kroz sledeće korake [11]:

• 
  Odabrati i izračunati
  

• 
  Odabrati i izračunati
  

Kao što se vidi iz algoritma verovatnoća prihvatanja koraka ne zavisi od , ali menjanje ove funcije se odražava na opseg vrednosti i stopu prihvatanja. Često se ovaj metod koristi u ograničenim domenima, pa kada je van tog domena, tada je verovatnoća prihvatanja jednaka 0, što znači da se ovaj uzorak odbacuje, a trenutna vrednost lanca se duplira. Zbog ovoga, ukoliko funkcija često generiše uzorke van domena dolazi do stagniranja lanca.

Primer slučajnog kretanja je dao Hesting u pokušaju generisanja normalne raspodele sa predloženom uniformnom raspodelom . Verovatnoća prihvatanja je tada jednaka

Na Slici 3 su prikazani rezultati ovog problema sa uzorkom od 5000 tačaka i gde se tačno vidi razlika proizvedenih lanaca: previše zbijeni ili previše rašireni kandidati u zavisnosti od , kao i spora konvergencija.

Slika 3: Rezultat Hestingovog problema korišćenjem metode slučajnog kretanja.

Na levoj strani su predstavljeni rezultati korišćenjem U(-0.1,0.1), u sredini U(-1,1) i desno

U(-10,10). Gornji grafikon predstavlja poslednjih 500 iteracija, dok je na donjem prikazano kako histogram dostiže ciljanu raspodelu.

3.4.2 Metropolizovan nezavisni uzorkivač

Veoma specifičan izbor za predloženu funkciju prelaska predstavlja gustina raspodele , gde se predloženi korak generiše iz funkcije nezavisno od prethodnog stanja . Ovaj metod (eng. Metropolized Independence Sampler, skraćeno MIS) predstavlja alternativu za uzorkovanje odbacivanjem i uzorkovanje prema značaju, a sastoji se iz sledećih koraka:

• 
  Odabrati
  
• 
  Simulirati i izračunati
  

gde predstavlja težinu pri uzorkovanju po značajnosti.

Kao i kod metode odbacivanja, efikasnost ove metode zavisi od toga koliko je probna gustina blizu ciljanoj . Kako bi se obezbedile dobre performanse, preporu

uje se da gustina bude relativno dugorepa⁵ (eng. long-tailed) raspodela. Galman, Rubin i Tirni (eng. Tierney) [19] predlažu ubacivanje nekoliko koraka MIS metode u Gibs iteraciju kada je ispravno uzorkovanje iz uslovne raspodele otežano. Ova metoda je veoma korisna kod različitih Bajesovih izračunavanja kod kojih svaka uslovna gustina može biti aproksimirana veoma dobro Gausovom raspodelom.