HMM with random process that determines how long you stay in a state

I have a situation that is reasonably well-modelled by a discrete Hidden Markov Model (HMM), but with one twist: when you enter a state, the amount of time that you spend there is given by some distribution/random process that isn't necessarily stateless.

Assume that for each state $q_i$, we have a discrete probability distribution $p_i(t)$, where $p_i(t)$ is the probability that you spend the next $t$ time steps at $q_i$ and then leave $q_i$ in the $t+1$th time step. When you leave $q_i$, you pick one of the transitions out of $q_i$, according to the probabilities on the transitions, just as is standard for a Markov process. As always in a HMM, the distribution on the output depends on what state you're currently in.

This is a slight generalization of a standard HMM. If each probability distribution $p_i(\cdot)$ is memoryless (i.e., a geometric distribution), then it's equivalent to a standard HMM. So, let's call it a G-HMM.

Has this kind of model been studied? Given a set of output sequences, is there a way to learn a G-HMM that best explains those sequences, i.e., maximum-likelihood estimation of the parameters (akin to Baum-Welch)? (You can assume the shape of the $p_i(\cdot)$ distributions are known and only their parameters are unknown.)

• I believe you might be describing something covered under the topic of hidden semi-markov processes. Not sure, though. Jul 13 '16 at 19:47
• @Wayne, ahh, yes, that's perfect! I'll do a little research then update the question to clarify that this is what I'm asking about. Thank you. Or, if you'd like to write an answer (so I can upvote it), feel free.
– D.W.
Jul 13 '16 at 21:27

This is a Hidden Semi-Markov Process (HSMM), the "hidden" version of a semi-Markov process. The time/duration spent at a single state is called the sojourn time, and the HSMM specifies the distribution on the sojourn time for each possible state.

They have been studied in the literature. For instance, such a model has been used for speech detection, where it was found that the Weibull distribution is a better fit for sojourn times than the geometric distribution assumed by ordinary HMM's.

There are algorithms in the literature for inferring model parameters of a HSMM. For instance, one can use the EM algorithm to build an analog/variant of the Baum-Welch procedure for inferring model parameters. It looks like the calculations get a bit messy, though. Fortunately, there's also a R package, hsmm, as described in the hsmm documentation and an accompanying research paper. It implements analogs of the Viterbi and Baum-Welch algorithms. However, it is a bit limited on what distributions it supports: for instance, it doesn't support Weibull-distributed sojourn times.

Another pragmatic approach that might or might not work in any particular setting is to use standard HMM algorithms and tweak their output. In particular, given a set of output sequences:

1. Use Baum-Welch or similar algorithms to learn a HMM model (i.e., via maximum-likelihood estimation), treating sojourn times as geometric for the moment (even though may not actually be in real life).

2. For each output sequence, use the Viterbi algorithm to find the most likely sequence of states. Based on this, calculate the sojourn time spent in each state.

3. For each state $q_i$, fit a distribution to the sojourn times (i.e., choose parameters for the sojourn time distribution that best fit the observed durations from step 2 above).

4. Construct a HSMM, using the sojourn time distributions calculated in step 3 and the between-state transition probabilities calculated in step 1.

You can even iterate steps 2-4 until convergence, using re-estimated parameters (computed from inferred state sequences) to adjust the model parameters.

Here's a survey/overview paper on the subject that seems useful:

Shuh-Zheng Yu. Hidden semi-Markov models. Artificial Intelligence, vol 174, pp.215-243, 2010. [pdf]