4 ms·

https://en.wikipedia.org/wiki/Viterbi_algorithm https://en.wikipedia.org/wiki/Viterbi_algorithm

by jwilk 3y ago

magicalhippo 3y ago
That's one of those Wikipedia pages that I find very difficult to get anything out of. The math has little explanation, the pseudo-code lacks definitions (where did s_z_j come from?) and while actual code helps with implementation (except Talk page mentions it's not correct), it can be quite difficult to grasp what the essence of the algorithm. I found this[1] video to give me a much better overview of the algorithm, and this[2] follow-up video looks promising in terms of practical application. edit: [2] is actually the prequel, he made [1] to go into the details. [1]: https://www.youtube.com/watch?v=xxpBHCkypS4 https://www.youtube.com/watch?v=xxpBHCkypS4 Viterbi Algorithm Explained with an Example [2]: https://www.youtube.com/watch?v=IJE94FhyygM https://www.youtube.com/watch?v=IJE94FhyygM Decoding Convolutional Codes: The Viterbi Algorithm Explained
- offbynull 3y ago
  I took a crack at explaining the Viterbi algorithm after learning about HMMs from a bioinformatics book I was reading. You may find it helpful, but that's assuming my interpretation of it is correct. https://offbynull.com/data/learn/Bioinformatics/output/output.html#H_Most%20Probable%20Hidden%20Path https://offbynull.com/data/learn/Bioinformatics/output/outpu...
- shoo 3y ago
  see also: https://courses.grainger.illinois.edu/ece448/sp2021/slides/lec16.pdf https://courses.grainger.illinois.edu/ece448/sp2021/slides/l... There's some good baseline material on HMMs in Russell & Norvig [1] (the chapter on "Probabilistic Reasoning over Time") as well as Rabiner's HMM tutorial [1] https://aima.cs.berkeley.edu/ https://aima.cs.berkeley.edu/ [2] https://www.cs.ubc.ca/~murphyk/Bayes/rabiner.pdf https://www.cs.ubc.ca/~murphyk/Bayes/rabiner.pdf
- lqet 3y ago
  Essentially, the Viterbi algorithm computes the shortest path through a DAG. If you explicitly model each transition/emission event as a single node in a graph, and if you then convert all probabilities p to -log p, than any shortest path algorithm will find the same result as Viterbi, which is the path of maximum likelihood. This is easy to prove: for probabilities p_1, p_2, p_3 ..., the path which maximizes p_1 * p_2 * p_3 ... also maximizes log(p_1 * p_2 * p_3 ...) = log(p_1) + log(p_2) + log(p_3) + ... and thus minimizes -(log(p_1) + log(p_2) + log(p_3) + ...) = -log(p_1) - log(p_2) - log(p_3) .... Because the probs are all 0 <= p <= 1, their log is <= 0, and choosing -log(p) as an edge weight gives non-negative weights. So you can use any standard shortest path algorithm to minimize -log(p_1) - log(p_2) - log(p_3) - ... and thus maximize p_1 * p_2 * p_3 * ... The Viterbi algorithm uses the same "trick" as the common algorithm for finding the shortest path through a DAG with better complexity than Dijkstra's algorithm: you can just process them in their topological order (which can be found in linear time), instead of processing them based on their position in a priority queue (as in Dijkstra's algorithm). Even better, in a HMM, the topological ordering of the graph is already part of the input: it's just the sequence of observations.
  - tonyarkles 3y ago
    There was a pretty funny, to me and my buddy, moment in our Digital Communications course when we were learning this. We were both dual EE/CS students while the rest of the class was straight EE. The professor is drawing out the trellis diagrams and going through this elaborate description of things and most people (including me and my buddy) were completely lost. At some point, though, he and I both had the same lightbulb moment. We turned to each other and simultaneously just whispered “it’s a dynamic programming problem”. And then it was all easy from there.
  - tgv 3y ago
    Doesn't the algorithm work on directed graphs, rather than only DAGs, i.e., also on cyclic ones? That's a difference with Dijkstra, where cycles are excluded from the solution. Plus, it takes the graph and a sequence of transitions.
    - 3y ago
- abnry 3y ago
  Take a look at Slide 4: https://ocw.mit.edu/courses/6-02-introduction-to-eecs-ii-digital-communication-systems-fall-2012/f398fa4a366439301b3d17e45e028952_MIT6_02F12_lec07.pdf https://ocw.mit.edu/courses/6-02-introduction-to-eecs-ii-dig...

https://en.wikipedia.org/wiki/Viterbi_algorithm https://en.wikipedia.org/wiki/Viterbi_algorithm

by jwilk 3y ago

https://en.wikipedia.org/wiki/Viterbi_algorithm https://en.wikipedia.org/wiki/Viterbi_algorithm

That's one of those Wikipedia pages that I find very difficult to get anything out of. The math has little explanation, the pseudo-code lacks definitions (where did s_z_j come from?) and while actual code helps with implementation (except Talk page mentions it's not correct), it can be quite difficult to grasp what the essence of the algorithm. I found this[1] video to give me a much better overview of the algorithm, and this[2] follow-up video looks promising in terms of practical application. edit: [2] is actually the prequel, he made [1] to go into the details. [1]: https://www.youtube.com/watch?v=xxpBHCkypS4 https://www.youtube.com/watch?v=xxpBHCkypS4 Viterbi Algorithm Explained with an Example [2]: https://www.youtube.com/watch?v=IJE94FhyygM https://www.youtube.com/watch?v=IJE94FhyygM Decoding Convolutional Codes: The Viterbi Algorithm Explained

offbynull 3y ago
I took a crack at explaining the Viterbi algorithm after learning about HMMs from a bioinformatics book I was reading. You may find it helpful, but that's assuming my interpretation of it is correct. https://offbynull.com/data/learn/Bioinformatics/output/output.html#H_Most%20Probable%20Hidden%20Path https://offbynull.com/data/learn/Bioinformatics/output/outpu...
shoo 3y ago
see also: https://courses.grainger.illinois.edu/ece448/sp2021/slides/lec16.pdf https://courses.grainger.illinois.edu/ece448/sp2021/slides/l... There's some good baseline material on HMMs in Russell & Norvig [1] (the chapter on "Probabilistic Reasoning over Time") as well as Rabiner's HMM tutorial [1] https://aima.cs.berkeley.edu/ https://aima.cs.berkeley.edu/ [2] https://www.cs.ubc.ca/~murphyk/Bayes/rabiner.pdf https://www.cs.ubc.ca/~murphyk/Bayes/rabiner.pdf
lqet 3y ago
Essentially, the Viterbi algorithm computes the shortest path through a DAG. If you explicitly model each transition/emission event as a single node in a graph, and if you then convert all probabilities p to -log p, than any shortest path algorithm will find the same result as Viterbi, which is the path of maximum likelihood. This is easy to prove: for probabilities p_1, p_2, p_3 ..., the path which maximizes p_1 * p_2 * p_3 ... also maximizes log(p_1 * p_2 * p_3 ...) = log(p_1) + log(p_2) + log(p_3) + ... and thus minimizes -(log(p_1) + log(p_2) + log(p_3) + ...) = -log(p_1) - log(p_2) - log(p_3) .... Because the probs are all 0 <= p <= 1, their log is <= 0, and choosing -log(p) as an edge weight gives non-negative weights. So you can use any standard shortest path algorithm to minimize -log(p_1) - log(p_2) - log(p_3) - ... and thus maximize p_1 * p_2 * p_3 * ... The Viterbi algorithm uses the same "trick" as the common algorithm for finding the shortest path through a DAG with better complexity than Dijkstra's algorithm: you can just process them in their topological order (which can be found in linear time), instead of processing them based on their position in a priority queue (as in Dijkstra's algorithm). Even better, in a HMM, the topological ordering of the graph is already part of the input: it's just the sequence of observations.
- tonyarkles 3y ago
  There was a pretty funny, to me and my buddy, moment in our Digital Communications course when we were learning this. We were both dual EE/CS students while the rest of the class was straight EE. The professor is drawing out the trellis diagrams and going through this elaborate description of things and most people (including me and my buddy) were completely lost. At some point, though, he and I both had the same lightbulb moment. We turned to each other and simultaneously just whispered “it’s a dynamic programming problem”. And then it was all easy from there.
- tgv 3y ago
  Doesn't the algorithm work on directed graphs, rather than only DAGs, i.e., also on cyclic ones? That's a difference with Dijkstra, where cycles are excluded from the solution. Plus, it takes the graph and a sequence of transitions.
  - 3y ago
abnry 3y ago
Take a look at Slide 4: https://ocw.mit.edu/courses/6-02-introduction-to-eecs-ii-digital-communication-systems-fall-2012/f398fa4a366439301b3d17e45e028952_MIT6_02F12_lec07.pdf https://ocw.mit.edu/courses/6-02-introduction-to-eecs-ii-dig...