Marginalized Beam Search Algorithms for Hierarchical HMMs
Xuechun Xu Joakim Jaldén
Inferring a state sequence from a sequence of measurements is a fundamental
problem in bioinformatics and natural language processing. The Viterbi and the
Beam Search (BS) algorithms are popular inference methods, but they have
limitations when applied to Hierarchical Hidden Markov Models (HHMMs), where
the interest lies in the outer state sequence. The Viterbi algorithm can not
infer outer states without inner states, while the BS algorithm requires
marginalization over prohibitively large state spaces. We propose two new
algorithms to overcome these limitations: the greedy marginalized BS algorithm
and the local focus BS algorithm. We show that they approximate the most likely
outer state sequence with higher performance than the Viterbi algorithm, and we
evaluate the performance of these algorithms on an explicit duration HMM with
simulation and nanopore base calling data.