is Íslenska en English

Lokaverkefni (Meistara)

Háskólinn í Reykjavík > Tæknisvið / School of Technology > MSc Tölvunarfræðideild / Department of Computer Science >

Vinsamlegast notið þetta auðkenni þegar þið vitnið til verksins eða tengið í það: http://hdl.handle.net/1946/46266

Titill: 
  • Titill er á ensku Applying binary decision diagrams to learn hidden Markov models
  • Notkun tvíundarákvörðunarrita til að læra falin Markov líkön
Námsstig: 
  • Meistara
Útdráttur: 
  • Útdráttur er á ensku

    In this thesis, we present EM-BDD, an algorithm for learning parameters of Hidden Markov Models, by building upon the Baum-Welch (BW) algorithm’s methodology. EM-BDD utilises the Forward-Backward procedure, a cornerstone of BW, adapting it to operate on Binary Decision Diagrams (BDDs). The time and memory complexity of the algorithm is contingent on the size of the BDD, highlighting that the BDD’s size significantly depends on the variable ordering (a problem known to be NP-complete). Preliminary experiments showed that the BDD size grows exponentially with the size of the input, giving the EM-BDD algorithm the same time complexity as the BW algorithm on average. However, this does not encompass the best-case scenario, which could potentially exhibit a more favourable time complexity.

  • Í þessari ritgerð kynnum við EM-BDD, reiknirit til að læra færibreytur Faldra Markov Líkana, með því að byggja á aðferðafræði Baum-Welch (BW) reikniritsins. EM-BDD notar Fram-og-Aftur verkferillinn, grundvallaratriðið BW, aðlagar það til að starfa á Tvíundarákvörðunarritum (BDD). Tíminn og minnisflækjustig reikniritsins er háð stærð BDD, sem undirstrikar að stærð BDD fer verulega eftir breytu röðinni (vandamál sem vitað er að er NP-complete). Bráðabirgðatilraunir sýndu að BDD stærðin vex veldishraða með stærð inntaksins, sem gefur EM-BDD reikniritinu sama tímaflækju og BW reikniritið að meðaltali. Hins vegar nær þetta ekki til bestu tilvika, sem gæti hugsanlega sýnt hagstæðari tímaflækju.

Samþykkt: 
  • 30.1.2024
URI: 
  • http://hdl.handle.net/1946/46266


Skrár
Skráarnafn Stærð AðgangurLýsingSkráartegund 
MSThesis_v2_final.pdf1.76 MBOpinnHeildartextiPDFSkoða/Opna