Kompleksnost skrivenih Markovljevih modela

diplomski rad

• Autor: Margareta Rudman
• Mentor: Pavle Goldstein (mentor)
• Član povjerenstva: Pavle Goldstein (predsjednik povjerenstva)
• Član povjerenstva: Juraj Šiftar (član povjerenstva)
• Član povjerenstva: Miljenko Marušić (član povjerenstva)
• Član povjerenstva: Ivica Nakić (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2014-07-11, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu bavimo se statističkim modelom, skrivenim Markovljevim modelom (eng. hidden Markov model ili kraće HMM) za što nas je motivirala njegova primjena u radu s ljudskom genomom znanstvenika J. Ernsta i M. Kellisa. U radu dajemo formalnu definiciju skrivenog Markovljevog modela, dajemo primjere takvih modela te opisujemo algoritme koje koristimo, između ostalih i forward, backward te Viterbijev algoritam. Nakon toga implementiramo i analiziramo postupke za procjenu parametara (emisijske i tranzicijske vjerojatnosti) HMM-a: Baum-Welch algoritam i Viterbijevo treniranje. Baum-Welch algoritam se pokazao efikasniji na primjerima koje navodimo ali unatoč tome zaključujemo da ne radi u praksi zbog niza problema kao što su lokalni ekstemi i izbor inicijalnih parametara. Također, kriteriji za procjenu kompleksnosti modela koje smo promatrali, AIC i BIC, pokazali su se nekorisni.

Sažetak (engleski)

This thesis is concerned with a statistical model called hidden Markov model (HMM). We were led to this topic by the paper by J. Ernst and M. Kellis where they apply HMMs to the study of human genome. We give a formal definition of the HMM, give examples of such models and describe algorithms that are used, among others, the forward, the backward and the Viterbi algorithm. Furthermore, we implement and analyze methods for parameter estimation (emission and transition probabilities) for HMMs: the Baum-Welch algorithm and Viterbi training. The Baum-Welch algorithm turned out to be more effective than Viterbi training when tested on simulated examples that we present. However, the Baum.Welch algorithm does not work in practice because of the issues like the local maxima and the choice of the initial parameters. Finally, we apply information criteria AIC and BIC to study complexity of our models.

• Ključne riječi: skriveni Markovljev model; Viterbijev algoritam; Baum-Welch algoritam; Viterbijevo treniranje
• Ključne riječi (engleski): hidden Markov model; Viterbi algorithm; Baum-Welch algorithm; Viterbi training
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:519340
• Studijski program: Naziv: Matematička statistika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra matematike (mag. math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2019-02-05 14:36:10