Viterbi Algorithm
El algoritmo de Viterbi usa programación dinámica para hallar la secuencia más probable de estados ocultos de un HMM, evitando enumerar todos los caminos.
Propósito
Decodificar eficientemente el camino óptimo de estados ocultos de un HMM; usado en reconocimiento del habla y PLN.
Mecanismo
Recursión hacia adelante δ_t(j)=max_i[δ_{t-1}(i)*a_{ij}]*b_j(o_t), registrando el mejor predecesor ψ_t(j). El retroceso parte del mayor δ_T en el instante T y sigue ψ para recuperar el camino óptimo. Complejidad O(TN^2).
Casos de uso
- Reconocimiento del habla
- Etiquetado gramatical
- Análisis de secuencias biológicas