I was bitten by this at work recently where I thought getting the top K paths would not require any modifications to the basic Viterbi algorithm. (Follow the link for one of the best explanations of the algorithm I could find.) The Viterbi algorithm, as advertised, works only to get the most probable path!
The easiest way to understand why the standard implementation does not work for this case, I came up with a simple example. Consider a two stage Viterbi algorithm where the first stage has only 2 hidden states and the second one just one. Now the algorithm will have a backpointer from the second stage to one and only one of the hidden states in the first stage corresponding to the most probable path. That gives us the highest probability path. But since we don't have a link from the second stage to the other hidden state in the first stage, we are unable to determine the second most probable path.
The easiest way to understand why the standard implementation does not work for this case, I came up with a simple example. Consider a two stage Viterbi algorithm where the first stage has only 2 hidden states and the second one just one. Now the algorithm will have a backpointer from the second stage to one and only one of the hidden states in the first stage corresponding to the most probable path. That gives us the highest probability path. But since we don't have a link from the second stage to the other hidden state in the first stage, we are unable to determine the second most probable path.
Comments
Post a Comment