I have a profile hidden Markov model that I use to identify all instances of a user-defined pattern of symbols in a long sequence of symbols. I use the Viterbi algorithm to find the most probable path that generates that long sequence of symbols, and it all works very well to identify the user's pattern. But I'm now interested in extending this, and identifying the k-most probable paths through my model that would generate some long sequence. Is there an existing algorithm to do this? I've come across something called the "1-best" or "k-best" algorithm, but I can't find much of anything describing it.

I've also considered what I'm sure would be a heuristic, by finding the most probable path and then returning the neighbourhood around it. This would be found by iterating over each move between states in the most probable path, setting that particular step to 0, and resolving using Viterbi. This would obviously increase the run-time by a factor of (length of the path ~= length of pattern), which I suspect will be reasonable for my purposes.

Has anybody come across something like this, or can anybody see anything obviously wrong in my neighbourhood idea? I'd appreciate any feedback. As a note, this has been cross-posted to the Data Science forum.


Why not expand the HMM to a state graph and apply a k-shortest-paths algorithm to the graph? I have a recent survey on k-best enumeration that includes the k-shortest paths problem at http://bulletin.eatcs.org/index.php/beatcs/article/view/322.

| cite | improve this answer | |
  • $\begingroup$ Thank you very much for that survey (it's been immensely helpful) and for bringing your expertise. If I may I have a follow-up question about those k-shortest path algorithms; forgive my ignorance but I'm still working through your '97 paper. My situation is akin to allowing negative lengths in a shortest path problem with no cycles. Assuming I use Bellman-Ford (or an equivalent), I am still able to use your or Yen's algorithm to find my k-best paths? $\endgroup$ – DaveTheScientist Sep 10 '15 at 23:22
  • 1
    $\begingroup$ My algorithm depends on having positive edge weights but you can use the same idea as in Johnson's algorithm (en.wikipedia.org/wiki/Johnson%27s_algorithm) to convert the problem to an equivalent one with positive weights after running the Bellman-Ford algorithm. $\endgroup$ – David Eppstein Sep 11 '15 at 1:34

Not the answer you're looking for? Browse other questions tagged or ask your own question.