# How to find next to optimal path in hidden Markov model or what should be LIST-Viterbi algorithm ?

The Viterbi algorithm is an algorithm for finding the most likely sequence of hidden states – called the Viterbi path.

Question If I am interested in list of several paths - optimal, sub-optimal, sub-sub-optimal etc... what should I do ? Are there some algorithms to solve it or to prove that this is hard (NP ?) problem ?

There is naive way - actually Viterbi algorithm on each step keeps S paths (S-number of states), so at the final step we can choose list of candidates from these S paths. But it will not give actually sub-optimal paths. The problem is rather clear - these paths will be different only for time moments near to the end and same at the begining - so if actual sub-extremum is different at first positions, then we will never find it.

Motivation Consider the error-correcting code (used e.g. in GSM) which is two-step coding: 1) Add CRC 2) make convolutional coding.

The decoding for this code can be like this 1) List Viterbi for convolutional part 2) Check if any result satisy CRC constraint.

-
It seems there are rather simple modification of Viterbi algorithm to get the desired answer. One idea is to keep "L" suboptimal "paths" arriving to each "state" on each step of the algorithm - called parallel List Viterbi see e.g. google.ru/… There is another way called "serial" which first finds optimal path, next run finds subop... – Alexander Chervov Aug 4 '12 at 7:52

The Viterbi algorithm works by maintaining, at all times between $[t,T]$, for all states $S^k_t$, the likelihood of the maximum likelihood path between this state and any state $S_T$. You can run it a second time, but this time, maintain the likelihood of reaching any state $S_T$ following a path that maximizes likelihood while being less likely than the one previously calculated. To avoid dealing with exact duplicates, you can add a very small noise to every edge.

In maybe-compiling C++,

// do something for the case t = T
for(int t = T-1; t > 0; --t) {
ll2[k][t] = NEGATIVE_INFINITY;
for(int i = 0; i < K; ++i) {
// we could make this transition then follow the 2nd best path
double a = ll_transition[t][k][i] + ll2[i][t+1];
if (a < ll[k][t]) // we don't want a maximum likelihood path
ll2[k][t] = max( ll2[k][t], a );
// or we could make a transition then follow the best path
a =  ll_transition[t][k][i] + ll[i][t+1]
if (a < ll[k][t]) // we don't want a maximum likelihood path
ll2[k][t] = max( ll2[k][t], a )
}
}
// do something for the case t = 0

-
Thank you for the answer ! I am not sure that I understand it, but what seems unreasonable for me (if I understand correctly) that you suggest to keep suboptimal paths for every time moment - I do not think it will work, I think suboptimal path may be same as true path at number of positions and then diverge from it then may be converge back to optimal - but in you proposal you will loose such situation. (If I understand correctly what you propose). – Alexander Chervov Jul 31 '12 at 14:10
I edited my pseudo-code, there was a mistake. Does that answer your objection? – Arthur B Jul 31 '12 at 17:14