I have implemented a k-best Viterbi algorithm in order to extract k-best paths through an HMM as described here. However, I get an error in case k is greater than the number of hidden states.
Consider the following: At the first observation at time t, every k for each state j is the same (i.e. all paths to that state are the same, since it's the first observation). I then want to compute the k-best paths for a state i at time t+1. In order to do that, I extract the k-best predecessor paths at time t. However, since all paths for each state at t are the same, I end up with the same best predecessor state k times for my state i (the same applies for all states at time t+1). This effectively results in all paths being the same path (1st-best).
As suggested in the literature, I disregarded paths that have already been taken when looking for k-best predecessor states. However, that effectively leaves me with N different paths at time t, with N referring to the number of hidden states. So, choosing k to be bigger than N results in an error when looking for k-best predecessor paths at time t.
I hope the point I am trying to make got through. Obviously, I am missing something here, but I cannot figure out what.
