(45 minutes to learn)
The Viterbi algorithm is an algorithm for finding the most likely state sequence in the posterior for an HMM. It is based on dynamic programming and has linear time complexity in the length of the sequence.
This concept has the prerequisites:
- hidden Markov models (The Viterbi algorithm is an algorithm for HMM inference.)
- forward-backward algorithm (The Viterbi algorithm is closely based on the forward-backward algorithm.)
Core resources (read/watch one of the following)
→ Pattern Recognition and Machine Learning
A textbook for a graduate machine learning course, with a focus on Bayesian methods.
Location: Section 13.2.5, pages 629-631
→ Machine Learning: a Probabilistic Perspective
A very comprehensive graudate-level machine learning textbook.
Location: Section 17.4.4, pages 612-616
- The Viterbi algorithm can be interpreted as a special case of [belief propagation](max_product_on_trees) .
- The Viterbi algorithm is an example of dynamic programming .
- create concept: shift + click on graph
- change concept title: shift + click on existing concept
- link together concepts: shift + click drag from one concept to another
- remove concept from graph: click on concept then press delete/backspace
- add associated content to concept: click the small circle that appears on the node when hovering over it
- other actions: use the icons in the upper right corner to optimize the graph placement, preview the graph, or download a json representation