State Sequence Analysis in Hidden Markov Models

Yuri Grinberg Ottawa Hospital Research Inst., Theodore Perkins Ottawa Hospital Research Institute
Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, PMLR R13:507-515, 2015.

Abstract

Given a discrete time finite state Hidden Markov Model (HMM) and a sequence of observations, different algorithms exist to answer different inference questions about the hidden states that the HMM traversed through. In this paper, the problem of finding the most probable state sequence is considered. The state sequence, as opposed to state trajectory, is a sequence of states that the HMM visited but without specifying the dwelling times in these states. This inference problem is relevant in a variety of domains, like text analysis, behavior recognition and etc. However, none of the existing algorithms addresses this inference question adequately. Previously, the problem of finding the most probable state sequence has been considered within the scope of continuous time Markov chains. Building on that work, we develop a provably correct algorithm, called \textit{state sequence analysis}, that addresses this inference question in HMMs. We discuss and illustrate empirically the differences between finding the most probable state sequence directly and doing so through running Viterbi algorithm and collapsing repetitive state visitations. Two synthetic experimental results demonstrate settings where Viterbi-based approach can be, at times significantly, suboptimal as compared to state sequence analysis. Further, we demonstrate the benefits of the proposed approach on a real activity recognition problem.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR13-inst-15a, title = {State Sequence Analysis in Hidden {M}arkov Models}, author = {Inst., Yuri Grinberg Ottawa Hospital Research and Institute, Theodore Perkins Ottawa Hospital Research}, booktitle = {Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence}, pages = {507--515}, year = {2015}, editor = {Meila, Marina and Heskes, Tom}, volume = {R13}, series = {Proceedings of Machine Learning Research}, month = {12--16 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r13/main/assets/inst-15a/inst-15a.pdf}, url = {https://proceedings.mlr.press/r13/inst-15a.html}, abstract = {Given a discrete time finite state Hidden Markov Model (HMM) and a sequence of observations, different algorithms exist to answer different inference questions about the hidden states that the HMM traversed through. In this paper, the problem of finding the most probable state sequence is considered. The state sequence, as opposed to state trajectory, is a sequence of states that the HMM visited but without specifying the dwelling times in these states. This inference problem is relevant in a variety of domains, like text analysis, behavior recognition and etc. However, none of the existing algorithms addresses this inference question adequately. Previously, the problem of finding the most probable state sequence has been considered within the scope of continuous time Markov chains. Building on that work, we develop a provably correct algorithm, called \textit{state sequence analysis}, that addresses this inference question in HMMs. We discuss and illustrate empirically the differences between finding the most probable state sequence directly and doing so through running Viterbi algorithm and collapsing repetitive state visitations. Two synthetic experimental results demonstrate settings where Viterbi-based approach can be, at times significantly, suboptimal as compared to state sequence analysis. Further, we demonstrate the benefits of the proposed approach on a real activity recognition problem.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T State Sequence Analysis in Hidden Markov Models %A Yuri Grinberg Ottawa Hospital Research Inst. %A Theodore Perkins Ottawa Hospital Research Institute %B Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2015 %E Marina Meila %E Tom Heskes %F pmlr-vR13-inst-15a %I PMLR %P 507--515 %U https://proceedings.mlr.press/r13/inst-15a.html %V R13 %X Given a discrete time finite state Hidden Markov Model (HMM) and a sequence of observations, different algorithms exist to answer different inference questions about the hidden states that the HMM traversed through. In this paper, the problem of finding the most probable state sequence is considered. The state sequence, as opposed to state trajectory, is a sequence of states that the HMM visited but without specifying the dwelling times in these states. This inference problem is relevant in a variety of domains, like text analysis, behavior recognition and etc. However, none of the existing algorithms addresses this inference question adequately. Previously, the problem of finding the most probable state sequence has been considered within the scope of continuous time Markov chains. Building on that work, we develop a provably correct algorithm, called \textit{state sequence analysis}, that addresses this inference question in HMMs. We discuss and illustrate empirically the differences between finding the most probable state sequence directly and doing so through running Viterbi algorithm and collapsing repetitive state visitations. Two synthetic experimental results demonstrate settings where Viterbi-based approach can be, at times significantly, suboptimal as compared to state sequence analysis. Further, we demonstrate the benefits of the proposed approach on a real activity recognition problem. %Z Reissued by PMLR on 04 October 2026.
APA
Inst., Y.G.O.H.R. & Institute, T.P.O.H.R.. (2015). State Sequence Analysis in Hidden Markov Models. Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R13:507-515 Available from https://proceedings.mlr.press/r13/inst-15a.html. Reissued by PMLR on 04 October 2026.

Related Material