Monte karlo metode I primene u bioinformatici master rad

2.2 Različiti pristupi rešavanja problema

Koliko su gore navedeni problemi kompleksni svedoči broj različitih metoda za njihovo rešavanje, kao i to da za određene probleme postoje rešenja samo u prostoru manjih dimenzija. Neke od ovih metoda se konstantno razvijaju i njihovo istraživanje traje i danas, što je slučaj sa metodama Markovljevih lanaca. Kako bismo ih lakše opisali podelićemo metode u određene kategorije [3].

Prvoj kategoriji pripadaju numeričke metode koje problem izračunavanja očekivanja i različitih varijacija rešavaju direktnim izračunavanjem. Na primer, izračunavanje očekivanja u konačnom prostoru će se vršiti sumiranjem jednačine (1.1), ali ovakvo izračunavanje je skoro nemoguće u prostoru većih dimenzije zbog eksponencijalnog rasta potrebnog vremena. Slična situacija je i u slučaju neprekidne raspodele koja zahteva izračunavanje integrala. Čak i neke novije metode numeričke integracije se ne mogu primeniti u rešavanju iznetih problema zbog toga što je u određenim delovima prostora vrednost integrala skoro jednaka 0, a u drugim, manjim delovima izuzetno velika.

Drugi pristup je ocenjivanje očekivanja pomoću Monte Karlo formule:

ukoliko možemo vršiti uzorkovanje iz raspodele definisane preko funkcije U nekim slučajevima uzorkovanje nije moguće izvesti direktno, ali je moguće primeniti tehniku uzorkovanja odbacivanjem (eng. rejection sampling) koja se zasniva na generisanju nezavisnih uzoraka iz pomoću uzorkovanja pristupačnije raspodele gde se dobijeni uzorci odbacuju ukoliko ne zadovoljavaju određene uslove. Da bi se primenio ovaj metod, moramo odabrati funkciju takvu da za svako i neku konstantu (važi Uzorke iz raspodele sa gustinom određujemo tako što iteriramo kroz sledeće korake:

• 
  generišemo uzorak iz raspodele sa gustinom i odredimo broj Uniform[0,1]
  
• 
  izračunamo i prihvatamo ukoliko važi .
  

Ukoliko uzorak nije prihvaćen postupak nastavljamo sve dok ne naiđemo na uzorak koji će biti prihvaćen.



Slika 1: Metoda uzorkovanja odbacivanjem.

Posmatrana funcija f(x) je predstavljena crvenom linijom, a pomoćna funkcija M*g(x) plavom, dok zelene tačke predstavljaju uzorke koji se prihvataju.
Efikasnost ove metode zavisi od toga koliko često se generisani uzorci odbacuju, odnostno koliko dobro funkcija aproksimira funkciju Kod nekih kompleksnijih problema skoro da je nemoguće odrediti prikladnu funkciju i konstantu za koju će važiti , a da se pri tom ne smanji verovatnoća prihvatanja. Zbog toga ova metoda nije primenljiva kod komplikovanijih problema, ali postoje razne njene varijacije koje prevazilaze opisana ograničenja.

Još jedan značajan metod Monte Karlo ocenjivanja očekivanja je uzorkovanje po značajnosti, pomoću kojeg se očekivanje izračunava biranjem funkcija gustine , koja ne mora biti normalizovana i iz koje se lako mogu uzimati uzorci, a koja predstavlja aproksimaciju ciljane funkcije Za razliku od metode uzorkovanja odbacivanjem, jedini uslov kod ove metode je da funkcija bude različita od 0 kad god je različita od 0. Sada možemo izračunati očekivanje funkcije na sledeći način:

gde predstavlja očekivanje funkcije u odnosu na raspodelu zadatu preko funkcije a u odnosu na raspodeli zadatu preko . Monte Karlo ocena očekivanja u zavisnosti od funkcije bi bila:

gde su uzorci iz raspodele date preko Metod uzorkovanja po značajnosti izračunava srednju vrednost funkcije u uzorkovanim tačkama i ocenjuje njihovu značajnost na osnovu toga koliko se predložena raspodela razlikuje od ciljane raspodele što opisuje vrednost težine značajnosti (eng. importance weight) . Ovaj metod takođe ima svoje nedostatke, jer nije uvek lako pronaći funkciju koja je bliska funkciji a u nekim slučajevima se čak može dogoditi da ni jedna od tačaka iz predložene raspodele se ne može uzeti kao uzorak za ciljanu raspodelu.

Poslednju grupu čine Monte Karlo metode zasnovane na Markovljevim lancima koje predstavljaju kombinaciju opisanih metoda tj. uzorkovanja i potrage za delovima sa najvećom verovatnoćom, a njihov princip rada će biti predstavljen u nastavku.