It’s weird how you can muck about with structures for so long and still forget what the hell you’re doing all the time. This post is supposed to try and clarify segment HMMs a bit for me, so that I can approach the learning problem with a clear mind. It’s all very specific; and it’s all below the fold.

I’m going to define the model again. Notation is important:

• : state transition probability
• : duration density
• : segment density
• : initial state distribution

Some things to note.

1. The state transition probability doesn’t really care how long the segment associated with q_i is. This means that the transition is invariant under changes to which kind of means the whole thing is still Markovian, though this enough for people to start using terms like ‘semi-Markovian’ which is kind of confusing.
2. The duration of the state at time is dependent on the state at time . This implies that:
3. The segment starts at time and lasts for time steps. This means that the last time index in the ‘current’ segment is .

What we’d like to do is write this out as a properly specified graphical model, but it turns out that this is pretty hard to do for the general case. As a first crack I tried introducing a counting variable . Unfortunately it doesn’t qutie make it, but was a useful learning experience. So, with a counting variable we can write the alternative model out as follows:

1. : counting variable transition distribution
2. : state transition probability conditioned on the counting variable at the previous time point
3. : segment density
4. : initial state distribution

The counting variable either decrements or resets, such that and . Here is simply the duration density, such that when the counter resets it starts off at a new duration.

Similarly, the state variable either stays the same or transitions depending on the counting variable. So and .

So we’ve swapped some awkardness in having two ideas of time’s passage – one for the underlying state and one for the observations – with some awkwardness of defining these conditional densities.

As it stands, though, we’re still stuck with a variable topology – the introduction of the counting variable hasn’t really changed the fact that the segment density changes dimension dependent on . If each observation was independent given the state then the counting variable would be all we need to get a nice regular graph.

The observations aren’t independent though! This is the big difference between Segment HMMs and what are known as explicit-duration HMMs. Hence to be able to draw a graph we must make some assumptions on the form of the output density. Murphy actually states this in one of his technical reports, but it seems to have taken a couple of months for it to actually sink in. Next step, then, is a graphical model for a th order explicit duration switching AR model! I think I’ll save that for the next post.