4

I am trying to find some (preferably MATLAB) code for the Viterbi algorithm in a 2nd order HMM. I know how to apply it for a first order model, and understand the concept for 2nd order. However I am having trouble implementing it for a 2nd order model. Can anyone give me any good references? I have searched Google and, surprisingly, could not find anything that's reasonably clear.

Also, is there a MATLAB library that already implements this? I know there is one for a first order HMM. Thanks

alguru
  • 404
  • 6
  • 16
  • If you have the statistics toolbox, you have the function [hmmtrain](http://www.mathworks.com/help/stats/hmmtrain.html) where you can use viterbi algorithm. I didn't get into the function that much, just refer it. – Vuwox Dec 11 '13 at 03:35
  • @AlexandreBizeau It is my understanding that `hmmtrain` only provides a first order HMM, whereas I require a second order model. – alguru Dec 11 '13 at 03:48
  • Okay, like I said. I didn't read that much the documentation. I just send it as information. But have you look in the file exchange ? – Vuwox Dec 11 '13 at 13:20
  • Will [this blogpost](http://prashanth-kamle.blogspot.co.uk/2009/03/viterbi-algorithm-for-second-order.html), by Prashanth Kamle help? If not - someone in the comments questions his implementation - [here's a short 1988 paper on it](http://www.scribd.com/doc/190946060/Extended-Viterbi-Algorithm-for-Second-Order-Hidden-Markov-Processes). – Andy Jones Dec 11 '13 at 18:17

2 Answers2

2

I know this is old, but I had this question, and had to figure out the answer myself.

You just need to represent the transition probabilities as P((State_t-2, State_t-1) => (State_t-1, State_t))

You can keep emission probabilities in terms of State_t though (you need a lot of data for 2nd-order emission probabilities to be reasonable).

That should give you reasonable results.

Jared Forsyth
  • 12,808
  • 7
  • 45
  • 54
0

see this paper https://journals.sagepub.com/doi/pdf/10.1177/1550147718772541

You need to modify viterbi path finding by considering prev and prev-to-prev-state

Sitaram Ramachandrula
  • 1