Baum-Welch Algorithm for Markov Models Using Algebraic Decision Diagrams
Term
4. term
Education
Publication year
2025
Submitted on
2025-06-05
Pages
17
Abstract
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.
Keywords
Documents