Hidden Markov models assume that observations in time series data stem from some hidden process that can be compactly represented as a Markov chain. We generalize this model by assuming that the observed data stems from multiple hidden processes, whose outputs interleave to form the sequence of observations. Exact inference in this model is NP-hard. However, a tractable and effective inference algorithm is obtained by extending structured approximate inference methods used in factorial hidden Markov models. The proposed model is evaluated in an activity recognition domain, where multiple activities interleave and together generate a stream of sensor observations. It is shown to be more accurate than a standard hidden Markov model in this domain.
Discussion
A novel extension to the HMM model where we have multiple HMMs that are interleaved using a higher level HMM. Kinda related to factorial HMMs, except that at each point in time there is only one “active” HMM, and other “dormant” HMMs stay in their current state until they become active.
It is interesting that exact inference is NP-hard, kinda a little surprising.
I brought up the following point during the question period: instead of doing naive Gibbs sampling where one state variable is sampled at each time, we should be able to do blocked Gibbs sampling, where whole sequences of states are resampled together using forward-filtering-backward-sampling. Given that dynamic programming can be used to do structured VB efficiently, one should be able to do this blocked Gibbs efficiently as well. Perhaps I'm not understanding something in the dynamic programming. Comments?
Isn't this a restricted type of factored HMM (with restrictions on when states make non-self-transitions?) It's not too surprising that inference is hard - it's hard for general factored HMMs, right?
Yes, it is basically a factorial HMM with an additional “switching” chain plus the restriction on non-self transitions. Viterbi-style inference in factorial HMMs is also exponential, and basically for the same reasons (coupling of chains through the observation variables).
For those who are interested, I would like to note that a similar approach has recently been presented at UbiComp. The title of the paper is “Improving the Recognition of Interleaved Activities” by Modayil et al., and the proposed model is called an “interleaved HMM”.