Monte karlo metode I primene u bioinformatici master rad

3. METROPOLIS ALGORITAM

3.1 Uvod

Metrpolis algoritam predstavlja jedan od Monte Karlo algoritama koji se danas najčešće koristi, a ime je dobio po svom autoru Nikolas Metropolisu [5]. Ovaj algoritam ima ogroman uticaj na razvoj nauke i u širokoj je upotrebi u oblasti statistike, fizike, ekonomije i računarskih nauka. Najkritičniji korak pri razvijanju efikasne Monte Karlo metode je simulacija odgovarajuće raspodele verovatnoće . Kada nije moguće direktno generisati nezavisne uzorke iz raspodele , tada se obično koristi strategija uzorkovanja po značajnosti u kojoj se slučajni uzorci generišu iz predložene probne raspodele i skaliraju prema količniku značaja ili se generišu statistički zavisni uzorci koristeći MKML (Monte Karlo Markovljevi Lanci) metodu.

Pretpostavimo da se sve raspodele verovatnoće mogu zapisati u obliku = , gde je konstanta normalizacije Z nepoznata. Zapravo Z je poznata i predstavlja vrednost integrala Z = čije izračunavanje je glavni problem simulacije raspodele Kako bi rešio ovaj problem, Metropolis predstavlja algoritam koji nadograđuje Markovljev proces uzorkovanja iz raspodele [5]. Iako je jednostavan, ovaj algoritam je veoma moćan, a razne njegove varijacije i proširenja su pronašla široku upotrebu u različitim naučnim oblastima.

Metropolis algoritam se može koristiti za generisanje slučajnih uzoraka iz bilo koje ciljane raspodele , bez obzira na analitičnu kompleksnost i dimenziju. Iako je ova tvrdnja tačna u teoriji, jedan od potecijalnih problema Monte Karlo metoda baziranih na Markovljevim lancima je to što su rezultujući uzorci često u velikoj korelaciji. Procena razultata kod ovakvih uzoraka znatno varira u odnosu na nezavisne uzorke, pa se zbog toga i dalje prave različiti pokušaji kako bi se ovo ograničenje prevazišlo.

3.2 Metropolis algoritam

Osnovna ideja Metropolis algoritma je da simulira Markovljev lanac u prostoru S tako da stacionarna raspodela lanca bude ciljana raspodela π. Kod tradicionalnih analiza Markovljevih lanaca pravila prelaza¹ su obično data, a nepoznata je stacionarna raspodela, dok je kod Monte Karlo Markovljevih lanaca poznata ravnotežna raspodela, a pravila prelaza se opisuju tako da se ta ravnoteža postigne. Metropolis algoritam koristi predloženu raspodelu koja zavisi od trenutnog stanja sistema . Počevši od bilo koje konfiguracije , Metropolis algoritam se sastoji od iteracije kroz sledeća dva koraka:

K1: Predložimo slučajnu nepristrasnu promenu (eng. unbiased perturbation) trenutnog stanja

tako da generiše novo stanje . je generisana iz simetrične funkcije verovatnoće prelaska² T() (koja se često naziva predložena funkcija ili probna funkcija, . Nakon ovoga izračunamo promenu:

.

K2: Generišimo slučajni broj U Uniform. Neka je = ako važi

U,

a = inače.

Ova dva koraka zapravo opisuju sledeći postupak: (a) napraviti malu promenu trenutne konfiguracije, (b) a zatim izračunati "poboljšanje" posmatrane funkcije. Nakon ovoga, (c) generisati slučajni broj U, (d) na osnovu kojeg će se nova konfiguracija usvojiti ukoliko je manji ili jednak od "poboljšanja". Prema tome određivanje M uzoraka iz ciljane raspodele se postiže izvršavanjem sledećeg pseudokoda [15]:

1. 
   t = 0
   
2. 
   generisati početno stanje
   
3. 
   dokle god je t < M:
   

t = t + 1

generisati novo stanje x′ iz predložene raspodele T

izračunati verovatnoću prihvatanja

odrediti slučajni broj U iz uniformne raspdele U(0,1)

ukoliko je , x′

u suprotnom

Iz navedenog se vidi da je Metropolis algoritam konstruisan na osnovu strategije pokušaja i pogrešaka. Kako su svi prihvaćeni uzorci u korelaciji, jer uzorak ima verovatnoću raspodele koja zavisi od , to se ovaj algoritam mora ponavljati priličan broj puta kako bi se dobili nezavisni uzorci raspodele.

Metropolis, kao i ostali naučnici, su ograni

ili svoj izbor "pravila promene" samo na simetrične funkcije, što znači da je verovatnoća dobijanje x' perturbacijom x jednaka verovatnoći dobijanja x perturbacijom x'. Matematički se ova restrikcija može zapisati kao:

.

Primer: Pretpostavimo da želimo da odredimo uzorke iz nenormalizovane Studentove raspodele = koristeći Metropolisov algoritam. Prvi korak predstavlja određivanje početnog stanja, i neka to bude broj , dok ćemo za probnu raspodelu uzeti normalnu raspodelu Na Slici 2 je predstavljen rezultat nakon 5000 iteracija uzorkovanja (M = 5000), gde su uzorci dobijeni Metropolisovim algoritmom predstavljeni crnom linijom, a ciljana raspodela crvenom, pa se jasno može videti da uzorci prate zadatu raspodelu.

Slika 2: Odnos uzoraka dobijenih Metropolisovim algoritmom i zadate raspodele p(x).