<p>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 <a href="http://bulletin.eatcs.org/index.php/beatcs/article/view/322" rel="nofollow">http://bulletin.eatcs.org/index.php/beatcs/article/view/322</a>.</p>

CC BY-SA 3.0
2015-09-10T23:22:44.860Z
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?
DaveTheScientist
CC BY-SA 3.0
2015-09-11T01:34:35.067Z
My algorithm depends on having positive edge weights but you can use the same idea as in Johnson's algorithm (https://en.wikipedia.org/wiki/Johnson%27s_algorithm) to convert the problem to an equivalent one with positive weights after running the Bellman-Ford algorithm.
David Eppstein
CC BY-SA 3.0
2015-09-10T19:15:53.777Z
2015-09-10T19:15:53.777Z
David Eppstein
<p>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. </p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2015-09-10T06:53:17.507Z
Crossposted to [datascience.stackexchange.com](http://datascience.stackexchange.com/q/8054)
Marzio De Biasi
<ds.algorithms><dynamic-programming><markov-chains>
How can I rank paths through an HMM?
DaveTheScientist
# How can I rank paths through an HMM?

(Asked by: username_0 on 2015-09-09)

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.

**Tags:** ds.algorithms, dynamic-programming, markov-chains

> **Comments:**
> **username_1**: Crossposted to [datascience.stackexchange.com](http://datascience.stackexchange.com/q/8054)  

---

## 1 answers

### Answer by username_2 on 2015-09-10. Score: 4 | Accepted answer

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>.

> **Comments:**
> **username_0**: 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?  
> **username_2**: My algorithm depends on having positive edge weights but you can use the same idea as in Johnson's algorithm (https://en.wikipedia.org/wiki/Johnson%27s_algorithm) to convert the problem to an equivalent one with positive weights after running the Bellman-Ford algorithm.  

---

