Applying binary decision diagrams to learn hidden Markov models
type: CreativeWork
description: 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.
abstract: 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.
author: Eva Ósk Gunnarsdóttir 1999-
language: en
keywords: Tölvunarfræði, Meistaraprófsritgerðir, Reiknirit, Verkferlar, Computer science, Algorithms
date published: 2024-01-30T11:05:26Z
date modified: 2026-07-27T20:41:01Z
provider: Reykjavík University
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: Reykjavík University

PropertyValue
property ID: Handle
value: http://hdl.handle.net/1946/46266