I have some data I need to analyze, and some prior knowledge I'd like to apply. I have discrete time points, and noisy, continuous outputs $x(t)$ that I observe at those time points, and would like to infer the discrete state $y(t)$ that is most likely to correspond to $x(t)$. If it matters, I know the distributions $x(y_1),\cdots,x(y_n)$, and that there are only six possible hidden states, and have lots of annotated data to train the model on.

Were it that simple, I think a hidden Markov model and the Viterbi algorithm would do the trick. But I know that the output at time $t_i$ is affected not only by the hidden state at time $t_i$, but by the three previous hidden states, like so:

link to picture of model

I left the diagram undirected, since the correlations between successive hidden states are not causal, but I could live with rightward arrows all around if I have to.

Anyway, does anyone know what such a model might be called, and/or if it's even plausible to try to learn the parameters for it? It seems simple enough that I feel like someone has got to have done it before, but I haven't been able to locate anything. I think it's basically a linear-chain conditional random field, but those extra edges make me feel lost and confused.


If it's any easier to parse/think about, here's an example where the current observed state depends on the past two, rather than four, hidden states:

Simplified model

This is sort of the minimal extension of a linear chain CRF, but I still can't find an example of something like it. Any help?

  • $\begingroup$ How about first using a log-linear model with generalized feature vector, followed by a Viterbi algorithm on it? Something similar was demonstrated on weeks 7 & 8 on Coursera's NLP course by Michael Collins. $\endgroup$
    – GuSuku
    Commented Nov 13, 2014 at 21:08

1 Answer 1


I think you need to recast your graphs into a different form. There is probably more than one way you could do this.

A really important thing to notice about your model is that at any given time, you can make a best guess about the hidden state. What is special is at the next time step you can make an even better guess as to what the previous hidden state was. At each time step up to 4 your estimate of past hidden state significantly improves.

Since you have 6 hidden states, you can in the bottom case replace that with 36 states representing all possible pairs. You then have a Markov process where most elements in the transition matrix are zero, since the tuple state $(A,D)$ must be followed by $(D,?)$. Now you have 36 output probability distributions to consider, which is too many vs your original diagram. The reason for the inflation is that we are now allowing interactions between $y(t_i)$ and $y(t_{i+1})$. If you ensure that your output probability model does not include interaction terms (i.e. it factorises completely) then you are back to the model you requested.

The same for the case where you have 4 histories that are important. Change this to a single 4-tuple and you have $6^4$ states. Then ensure that your output probability model factorises on each element of the state and you are back to the model above.

Notice that the Viterbi algorithm run on the vector hidden state is going to give you estimates, at each time point, of what the current set of 4 states are. If you "flatten" this back to a single series $...y(t_i), y(t_{i+1}),...$ then you have multiple estimates for each y, and they won't agree. This is correct and goes back to the point in the intro, that because each step depends on past values, we learn more on the past and can revise our estimate of what happened.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.