Viterbi Algorithm
The Viterbi algorithm uses dynamic programming to find the most likely hidden-state sequence of an HMM, avoiding enumeration of all paths.
Purpose
To decode the optimal hidden-state path of an HMM efficiently, used in speech recognition and NLP.
Mechanism
Forward recursion δ_t(j)=max_i[δ_{t-1}(i)*a_{ij}]*b_j(o_t), recording the best predecessor ψ_t(j). Backtracking starts from the largest δ_T at time T and follows ψ back to recover the optimal path. Complexity O(TN^2).
Use cases
- Speech recognition
- Part-of-speech tagging
- Biological sequence analysis