Kompleksnost skrivenih Markovljevih modela

master's thesis

• Author: Margareta Rudman
• Mentor: Pavle Goldstein (mentor)
• Committee member: Pavle Goldstein (predsjednik povjerenstva)
• Committee member: Juraj Šiftar (član povjerenstva)
• Committee member: Miljenko Marušić (član povjerenstva)
• Committee member: Ivica Nakić (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2014-07-11, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: skriveni Markovljev model; Viterbijev algoritam; Baum-Welch algoritam; Viterbijevo treniranje
• Keywords (english): hidden Markov model; Viterbi algorithm; Baum-Welch algorithm; Viterbi training
• Language: croatian
• URN:NBN: urn:nbn:hr:217:519340
• Study programme: Title: Mathematical Statistics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra matematike (magistar/magistra matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-02-05 14:36:10