An efficient exact algorithm for state sequence estimation in imprecise hidden Markov models

by gertekoo

Jasper De Bock is one of the master’s students whose work I supervise at Ghent University. With a little help from us as his friends, he has devised a truly ingenious and very efficient exact algorithm for estimating state sequences from outputs (or observations) in imprecise hidden Markov models (iHMM), where both the uncertainty linking one state to the next, and that linking a state to its output, are represented using coherent lower previsions.

Two important things to note:

First of all, the notion of independence we associate with the credal network representing the iHMM is that of epistemic irrelevance. We strongly suspect that using this weaker version, rather than the more commonly used strong independence, is what allows us to make the algorithm so efficient. Could it be that the extra dilation that doing this brings along, helps us keep the complexity at bay?

Second, we consider as ‘best estimates’ for state sequences the (Walley-Sen-)maximal sequences for the posterior joint state model (conditioned on the observed output sequence), associated with a loss function that is the indicator of the state sequence. This corresponds to (and generalises) finding the state sequence with the highest posterior probability in HMMs with precise transition and output probabilities (pHMM).

We are currently testing the algorithm on specific examples, and taking a closer look at its complexity, which we suspect to be similar to that of Viterbi’s for pHMMs. We are also trying to get this into publishable form before the ISIPTA 2011 paper submission deadline.

I will update this post with more information as soon as this work bears more fruit.