Baum-Welch Algorithm for Markov Models Using Algebraic Decision Diagrams

Hansen, Lars Emanuel ; Petersen, Daniel Runge ; Aaholm, Sebastian

4. term

Computer Science, Master

2025

2025-06-05

17 pages

The Baum-Welch (BW) algorithm is a widely used method for training Hidden Markov Models (HMMs) and Markov Chains (MCs) from observation sequences. However, traditional implementations using recursive or matrix-based methods often struggle with scalability due to redundancy and high memory consumption. This thesis proposes a novel, symbolic implementation of the BW algorithm using Algebraic Decision Diagrams (ADDs), which provide a compact and efficient representation of probabilistic models. We extend on CuPAAL, a C++ library that implements the BW algorithm entirely with ADDs, and integrate it into the Jajapy library, resulting in a new symbolic learning tool referred to as Jajapy 2. Our approach enables efficient learning from multiple observation sequences and supports both HMMs and MCs. Through experiments on models from the QComp benchmark set, we demonstrate that the symbolic implementation significantly improves performance for larger observation sets and models with repeated structures, while maintaining learning accuracy. These results affirm the potential of ADD-based symbolic computation as a scalable alternative for probabilistic model learning.

Algebraic Decision Diagrams ; Baum-Welch Algorithm ; Hidden Markov Models ; Markov Chains ; Model Checking

Download
View record in AAU Student Projects