2
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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... $\endgroup$
    – Alexander Chervov
    Commented Aug 4, 2012 at 7:52

1 Answer 1

Reset to default
1
$\begingroup$

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
Improve this answer
$\endgroup$
8
  • $\begingroup$ 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). $\endgroup$
    – Alexander Chervov
    Commented Jul 31, 2012 at 14:10
  • $\begingroup$ I edited my pseudo-code, there was a mistake. Does that answer your objection? $\endgroup$
    – Arthur B
    Commented Jul 31, 2012 at 17:14
  • $\begingroup$ Code is unclear for me. Can you add comments to code? $\endgroup$
    – Alexander Chervov
    Commented Jul 31, 2012 at 17:25
  • $\begingroup$ Thanks for comments. Still not clear: I am not familiar with Python, but seems something missing: you write "IF condition" where is "THEN" part ? $\endgroup$
    – Alexander Chervov
    Commented Jul 31, 2012 at 19:31
  • $\begingroup$ Also: I get used to think that paths go from initial states S(t=0) to S_{k}(t=T), but you seems to go in opposite direction ? From T to 0 ? $\endgroup$
    – Alexander Chervov
    Commented Jul 31, 2012 at 19:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .