Viterbi algorithm
(45 minutes to learn)
Summary
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.
Context
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)
-Paid-
→ 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
See also
- 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 .