Viterbi Algorithm
L'algorithme de Viterbi utilise la programmation dynamique pour trouver la séquence d'états cachés la plus probable d'un HMM, évitant l'énumération de tous les chemins.
Objectif
Décoder efficacement le chemin optimal d'états cachés d'un HMM ; utilisé en reconnaissance vocale et en TAL.
Mécanisme
Récursion avant δ_t(j)=max_i[δ_{t-1}(i)*a_{ij}]*b_j(o_t), en enregistrant le meilleur prédécesseur ψ_t(j). Le retour en arrière part du plus grand δ_T à l'instant T et suit ψ pour retrouver le chemin optimal. Complexité O(TN^2).
Cas d’usage
- Reconnaissance vocale
- Étiquetage morphosyntaxique
- Analyse de séquences biologiques