Marginalized Beam Search Algorithms for Hierarchical HMMs
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.
Code (1)
Methods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
The Segmented iHMM: A Simple, Efficient Hierarchical Infinite HMM
We propose the segmented iHMM (siHMM), a hierarchical infinite hidden Markov model (iHMM) that supports a simple, efficient inference scheme. The siHMM is well suited to segmentation problems, where the goal is to identi…
SegmentationTime SeriesTime Series AnalysisSilent HMMs: Generalized Representation of Hidden Semi-Markov Models and Hierarchical HMMs
Modeling sequence data using probabilistic finite state machines (PFSMs) is a technique that analyzes the underlying dynamics in sequences of symbols. Hidden semi-Markov models (HSMMs) and hierarchical hidden Markov mode…
The variational hierarchical EM algorithm for clustering hidden Markov models
In this paper, we derive a novel algorithm to cluster hidden Markov models (HMMs) according to their probability distributions. We propose a variational hierarchical EM algorithm that i) clusters a given collection of H…
ClusteringMusic TaggingA New Algorithm for Hidden Markov Models Learning Problem
This research focuses on the algorithms and approaches for learning Hidden Markov Models (HMMs) and compares HMM learning methods and algorithms. HMM is a statistical Markov model in which the system being modeled is ass…
Forward-Backward Activation Algorithm for Hierarchical Hidden Markov Models
Hierarchical Hidden Markov Models (HHMMs) are sophisticated stochastic models that enable us to capture a hierarchical context characterization of sequence data. However, existing HHMM parameter estimation methods requir…
parameter estimation