State Sequence Analysis in Hidden Markov Models

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.