Tema

Algoritmo de Viterbi

IA clásica
Nivel avanzado
Con simulador interactivo

El algoritmo de Viterbi calcula por programación dinámica la secuencia completa de estados ocultos más probable dada una secuencia de observaciones, reemplazando la suma del algoritmo hacia adelante por un máximo y guardando punteros hacia atrás.

Nombre en inglés

Viterbi algorithm

Intuición

La tabla tiene una fila por estado y una columna por instante. En cada celda se guarda la probabilidad del mejor camino que termina ahí, no la suma de todos los caminos, y además de qué celda vino. Al llegar al final se elige la celda mayor de la última columna y se reconstruye el camino siguiendo los punteros hacia atrás. El coste es lineal en la longitud de la secuencia y cuadrático en el número de estados.

Fórmula

delta_t(j) = max_i [ delta_{t-1}(i) * P(s_j | s_i) ] * P(o_t | s_j)

Ejemplo resuelto

Con el modelo de lluvia y sol, transiciones P(lluvia | lluvia) = 0.7, P(sol | lluvia) = 0.3, P(lluvia | sol) = 0.4, P(sol | sol) = 0.6, emisiones P(paraguas | lluvia) = 0.9 y P(paraguas | sol) = 0.2 y prior P(lluvia) = 0.6, se observa paraguas dos días seguidos. En el primer instante delta vale 0.54 para lluvia y 0.08 para sol. Para lluvia en el segundo instante se compara 0.54 por 0.7 = 0.378 con 0.08 por 0.4 = 0.032, gana el primero y al multiplicar por 0.9 queda 0.3402. Para sol se compara 0.54 por 0.3 = 0.162 con 0.08 por 0.6 = 0.048, gana el primero y al multiplicar por 0.2 queda 0.0324. El máximo final es 0.3402 y la secuencia más probable es lluvia y lluvia.

Errores frecuentes

Sumar en lugar de maximizar, lo que convierte el algoritmo en el de hacia adelante y responde a otra pregunta, la verosimilitud total de la secuencia observada.
No guardar los punteros hacia atrás y tratar de reconstruir el camino eligiendo el máximo de cada columna por separado, que es justo el error que Viterbi existe para evitar.
Multiplicar probabilidades crudas en secuencias largas, donde conviene trabajar con logaritmos y sumar, porque el producto de cientos de factores menores que 1 se hace cero en coma flotante.

Ejercicio

Con el mismo modelo, supón que en el segundo día no hay paraguas, de modo que P(sin paraguas | lluvia) = 0.1 y P(sin paraguas | sol) = 0.8. Calcula delta para los dos estados en el segundo instante.

Ver la solución

Los valores del primer instante siguen siendo 0.54 para lluvia y 0.08 para sol. Para lluvia en el segundo instante el mejor predecesor da max(0.54 por 0.7, 0.08 por 0.4) = 0.378, y al multiplicar por 0.1 queda 0.0378. Para sol el mejor predecesor da max(0.54 por 0.3, 0.08 por 0.6) = 0.162, y al multiplicar por 0.8 queda 0.1296. Como 0.1296 supera a 0.0378, la secuencia más probable pasa a ser lluvia y sol.