Algoritmo de Viterbi

El algoritmo de Viterbi es un algoritmo de programación dinámica que encuentra la secuencia más probable de eventos ocultos que explicarían una secuencia de eventos observados. El resultado del algoritmo se conoce como trayectoria de Viterbi . Se utiliza con mayor frecuencia con modelos ocultos de Markov (HMM). Por ejemplo, si un médico observa los síntomas de un paciente durante varios días (los eventos observados), el algoritmo de Viterbi podría determinar la secuencia más probable de afecciones subyacentes (los eventos ocultos) que causaron dichos síntomas.

El algoritmo ha encontrado aplicación universal en la decodificación de códigos convolucionales utilizados en comunicaciones celulares digitales CDMA y GSM , módems de acceso telefónico , satélites, comunicaciones de espacio profundo y redes LAN inalámbricas 802.11 . También se utiliza comúnmente en reconocimiento de voz , síntesis de voz , diarización , ^{[ 1 ]} detección de palabras clave , lingüística computacional y bioinformática . Por ejemplo, en la conversión de voz a texto (reconocimiento de voz), la señal acústica es la secuencia observada, y una cadena de texto es la "causa oculta" de esa señal. El algoritmo de Viterbi encuentra la cadena de texto más probable dada la señal acústica .

El algoritmo de Viterbi recibe su nombre de Andrew Viterbi , quien lo propuso en 1967 como un algoritmo de decodificación para códigos convolucionales sobre enlaces de comunicación digital ruidosos. ^{[ 2 ]} Sin embargo, tiene una historia de múltiples invenciones , con al menos siete descubrimientos independientes, incluidos los de Viterbi, Needleman y Wunsch , y Wagner y Fischer . ^{[ 3 ]} Se introdujo en el procesamiento del lenguaje natural como un método de etiquetado de partes del discurso ya en 1987.

El camino de Viterbi y el algoritmo de Viterbi se han convertido en términos estándar para la aplicación de algoritmos de programación dinámica a problemas de maximización que involucran probabilidades. ^{[ 3 ]} Por ejemplo, en el análisis estadístico, se puede usar un algoritmo de programación dinámica para descubrir la derivación (análisis) libre de contexto más probable de una cadena, que comúnmente se denomina "análisis de Viterbi". ^{[ 4 ] [ 5 ] [ 6 ]} Otra aplicación es en el seguimiento de objetivos , donde se calcula la trayectoria que asigna una máxima probabilidad a una secuencia de observaciones. ^{[ 7 ]}

Dado un modelo oculto de Markov con un conjunto de estados ocultos${\displaystyle S}$, un conjunto de posibles emisiones (observaciones) M, y una secuencia de${\displaystyle T}$observaciones${\displaystyle o_{0},o_{1},\dots ,o_{T-1}}$El algoritmo de Viterbi encuentra la secuencia más probable de estados ocultos que podrían haber producido esas observaciones. En cada paso de tiempo${\displaystyle t}$, el algoritmo resuelve el subproblema donde solo las observaciones hasta${\displaystyle o_{t}}$se consideran.

Dos matrices de tamaño${\displaystyle T\times \left|{S}\right|}$se construyen:

• ${\displaystyle P_{t,s}}$contiene la probabilidad máxima de terminar en el estado${\displaystyle s}$en observación${\displaystyle t}$, de entre todas las posibles secuencias de estados que conducen a ella.
• ${\displaystyle Q_{t,s}}$rastrea el estado anterior que se utilizó antes${\displaystyle s}$en esta secuencia de estados de máxima probabilidad.

Dejar${\displaystyle \pi _{s}}$y${\displaystyle a_{r,s}}$sean las probabilidades inicial y de transición respectivamente, y sea${\displaystyle b_{s,o}}$sea ​​la probabilidad de observar${\displaystyle o}$en el estado${\displaystyle s}$. Entonces los valores de${\displaystyle P}$están dadas por la relación de recurrencia ^{[ 8 ]}$${\displaystyle P_{t,s}={\begin{cases}\pi _{s}\cdot b_{s,o_{t}}&{\text{si }}t=0,\\\max _{r\in S}\left(P_{t-1,r}\cdot a_{r,s}\cdot b_{s,o_{t}}\right)&{\text{si }}t>0.\end{cases}}}$$ La fórmula para${\displaystyle Q_{t,s}}$es idéntico para${\displaystyle t>0}$, excepto que${\displaystyle \max }$es reemplazado por${\displaystyle \arg \max }$, y${\displaystyle Q_{0,s}=0}$. El camino de Viterbi se puede encontrar seleccionando el máximo de${\displaystyle P}$en el paso de tiempo final y a continuación${\displaystyle Q}$marcha atrás.

La función Viterbi(estados, init, trans, emit, obs) tiene como entrada estados: S estados ocultos entrada init: probabilidades iniciales de cada estado entrada trans: matriz de transición S × S entrada emit: matriz de emisión S × M entrada obs: secuencia de T observaciones prob ← Matriz de ceros T × S anterior ← matriz T × S vacía para cada estado s en estados hacer prob[0][s] = init[s] * emit[s][obs[0]] para t = 1 a T - 1 inclusive hacer // t = 0 ya se ha tratado para cada estado s en estados hacer para cada estado r en estados hacer nueva_probabilidad ← prob[t - 1][r] * trans[r][s] * emit[s][obs[t]] Si new_prob > prob[t][s] entonces prob[t][s] ← nueva_prob prev[t][s] ← r ruta ← matriz vacía de longitud T ruta[T - 1] ← el estado s con máxima probabilidad[T - 1][s] para t = T - 2 hasta 0 inclusive hacer ruta[t] ← prev[t + 1][ruta[t + 1]] fin de la ruta de retorno

La complejidad temporal del algoritmo es${\displaystyle O(T\times \left|{S}\right|^{2})}$. Si se sabe qué transiciones de estado tienen una probabilidad distinta de cero, se puede encontrar una cota mejorada iterando solo sobre esas${\displaystyle r}$que enlazan con${\displaystyle s}$en el bucle interno. Luego, utilizando el análisis amortizado, se puede demostrar que la complejidad es${\displaystyle O(T\times (\left|{S}\right|+\left|{E}\right|))}$, dónde${\displaystyle E}$es el número de aristas en el grafo, es decir, el número de entradas no nulas en la matriz de transición.

Un médico desea determinar si los pacientes están sanos o tienen fiebre. La única información que puede obtener es preguntándoles cómo se sienten. Los pacientes pueden indicar que se sienten bien, mareados o con frío.

Se cree que el estado de salud de los pacientes funciona como una cadena de Markov discreta . Existen dos estados: "sano" y "fiebre", pero el médico no puede observarlos directamente; están ocultos para él. Cada día, la probabilidad de que un paciente le diga al médico "Me siento normal", "Tengo frío" o "Me siento mareado" depende únicamente de su estado de salud ese día.

Las observaciones (normal, frío, mareo) junto con los estados ocultos (sano, fiebre) forman un modelo oculto de Markov (HMM). A partir de la experiencia previa, las probabilidades de este modelo se han estimado como:

init = {"Sano": 0.6, "Fiebre": 0.4} trans = { "Saludable": {"Saludable": 0.7, "Fiebre": 0.3}, "Fiebre": {"Sano": 0.4, "Fiebre": 0.6}, } emitir = { "Saludable": {"normal": 0.5, "frío": 0.4, "mareado": 0.1}, "Fiebre": {"normal": 0.1, "resfriado": 0.3, "mareado": 0.6}, } 

En este código, initrepresenta la creencia del médico sobre la probabilidad de que el paciente esté sano inicialmente. Nótese que la distribución de probabilidad particular utilizada aquí no es la de equilibrio, que se correspondería {'Healthy': 0.57, 'Fever': 0.43}con las probabilidades de transición. Las probabilidades de transición transrepresentan el cambio en el estado de salud en la cadena de Markov subyacente. En este ejemplo, un paciente que está sano hoy tiene solo un 30 % de probabilidad de tener fiebre mañana. Las probabilidades de emisión emitrepresentan la probabilidad de cada observación posible (normal, resfriado o mareo), dada la condición subyacente (sano o con fiebre). Un paciente que está sano tiene un 50 % de probabilidad de sentirse normal; uno que tiene fiebre tiene un 60 % de probabilidad de sentirse mareado.

Un paciente en particular acude a la consulta tres días seguidos y refiere sentirse normal el primer día, con frío el segundo y mareado el tercero.

En primer lugar, se calculan las probabilidades de estar sano o tener fiebre el primer día. La probabilidad de que un paciente esté sano el primer día y reporte sentirse normal es${\displaystyle 0.6\times 0.5=0.3}$. De manera similar, la probabilidad de que un paciente tenga fiebre el primer día y reporte sentirse normal es${\displaystyle 0.4\times 0.1=0.04}$.

Las probabilidades para cada uno de los días siguientes se pueden calcular directamente a partir del día anterior. Por ejemplo, la mayor probabilidad de estar sano el segundo día y reportar tener frío, después de reportar estar normal el primer día, es el máximo de${\displaystyle 0.3\times 0.7\times 0.4=0.084}$y${\displaystyle 0.04\times 0.4\times 0.4=0.0064}$Esto sugiere que es más probable que el paciente estuviera sano durante esos dos días, en lugar de tener fiebre y recuperarse.

El resto de las probabilidades se resumen en la siguiente tabla:

En la tabla se observa que lo más probable es que el paciente tuviera fiebre el tercer día. Además, existe una secuencia de estados que termina en "fiebre", cuya probabilidad de producir las observaciones dadas es de 0,01512. Esta secuencia es precisamente (sano, sano, fiebre), la cual se puede encontrar al rastrear qué estados se utilizaron al calcular los máximos (que resultan ser la mejor estimación de cada día, pero no siempre lo serán). En otras palabras, dadas las actividades observadas, lo más probable es que el paciente hubiera estado sano el primer día y también el segundo (a pesar de sentir frío ese día), y que solo hubiera contraído fiebre el tercer día.

El funcionamiento del algoritmo de Viterbi se puede visualizar mediante un diagrama de enrejado . El camino de Viterbi es, esencialmente, el camino más corto a través de este enrejado.

Una generalización del algoritmo de Viterbi, denominada algoritmo de suma máxima (o algoritmo de producto máximo ), puede utilizarse para encontrar la asignación más probable de todas o algunas variables latentes en un gran número de modelos gráficos , por ejemplo, redes bayesianas , campos aleatorios de Markov y campos aleatorios condicionales . Las variables latentes deben, en general, estar conectadas de forma similar a un modelo oculto de Markov (HMM), con un número limitado de conexiones entre variables y algún tipo de estructura lineal entre ellas. El algoritmo general implica el paso de mensajes y es sustancialmente similar al algoritmo de propagación de creencias (que es la generalización del algoritmo de avance-retroceso ).

Mediante un algoritmo denominado decodificación iterativa de Viterbi , se puede encontrar la subsecuencia de una observación que mejor se ajusta (en promedio) a un modelo oculto de Markov dado. Este algoritmo fue propuesto por Qi Wang et al. para trabajar con códigos turbo . ^{[ 9 ]} La decodificación iterativa de Viterbi funciona invocando iterativamente un algoritmo de Viterbi modificado, reestimando la puntuación de un relleno hasta la convergencia.

Se ha propuesto un algoritmo alternativo, el algoritmo Lazy Viterbi . ^{[ 10 ]} Para muchas aplicaciones de interés práctico, bajo condiciones de ruido razonables, el decodificador Lazy (que utiliza el algoritmo Lazy Viterbi) es mucho más rápido que el decodificador Viterbi original (que utiliza el algoritmo Viterbi). Mientras que el algoritmo Viterbi original calcula cada nodo en el enrejado de posibles resultados, el algoritmo Lazy Viterbi mantiene una lista priorizada de nodos para evaluar en orden, y el número de cálculos requeridos suele ser menor (y nunca mayor) que el del algoritmo Viterbi ordinario para el mismo resultado. Sin embargo, no es tan fácil paralelizarlo en hardware.

El algoritmo de Viterbi de salida suave ( SOVA ) es una variante del algoritmo de Viterbi clásico.

SOVA se diferencia del algoritmo clásico de Viterbi en que utiliza una métrica de ruta modificada que tiene en cuenta las probabilidades a priori de los símbolos de entrada y produce una salida suave que indica la fiabilidad de la decisión.

El primer paso en el SOVA es la selección del camino de supervivencia, que pasa por un nodo único en cada instante de tiempo, t . Dado que cada nodo tiene 2 ramas que convergen en él (una rama se elige para formar el camino de supervivencia y la otra se descarta), la diferencia en las métricas de las ramas (o costo ) entre las ramas elegidas y descartadas indica la cantidad de error en la elección.

Este coste se acumula a lo largo de toda la ventana deslizante (que suele ser igual a al menos cinco longitudes de restricción), para indicar la medida de salida suave de la fiabilidad de la decisión de bit duro del algoritmo de Viterbi.

• Algoritmo de maximización de expectativas
• Algoritmo de Baum-Welch
• Algoritmo de avance-retroceso
• Algoritmo de avance
• Código corrector de errores
• decodificador Viterbi
• Etiquetado de partes de la oración
• Algoritmo de búsqueda A*

• Viterbi AJ (abril de 1967). "Límites de error para códigos convolucionales y un algoritmo de decodificación asintóticamente óptimo". IEEE Transactions on Information Theory . 13 (2): 260– 269. doi : 10.1109/TIT.1967.1054010 .(Nota: el algoritmo de decodificación de Viterbi se describe en la sección IV). Se requiere suscripción.
• Feldman J, Abou-Faycal I, Frigo M (2002). "Un decodificador rápido de máxima verosimilitud para códigos convolucionales". Actas de la 56.ª Conferencia de Tecnología Vehicular del IEEE . Vol.  1. págs. 371–375 . CiteSeerX 10.1.1.114.1314 . doi : 10.1109/VETECF.2002.1040367 . ISBN   978-0-7803-7467-6. S2CID 9783963 . 
• Forney GD (marzo de 1973). "El algoritmo de Viterbi". Actas del IEEE . 61 (3): 268– 278. doi : 10.1109/PROC.1973.9030 .Se requiere suscripción.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). «Sección 16.2. Decodificación de Viterbi» . Numerical Recipes: The Art of Scientific Computing (3.ª  ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8Archivado del original el 11 de agosto de 2011. Consultado el 17 de agosto de 2011 .
• Rabiner LR (febrero de 1989). "Un tutorial sobre modelos ocultos de Markov y aplicaciones seleccionadas en el reconocimiento de voz". Actas del IEEE . 77 (2): 257– 286. CiteSeerX 10.1.1.381.3454 . doi : 10.1109/5.18626 . S2CID 13618539 .  (Describe el algoritmo directo y el algoritmo de Viterbi para HMM).
• Shinghal, R. y Godfried T. Toussaint , "Experimentos en reconocimiento de texto con el algoritmo Viterbi modificado", IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. PAMI-l, abril de 1979, págs.  184-193.
• Shinghal, R. y Godfried T. Toussaint , "La sensibilidad del algoritmo Viterbi modificado a las estadísticas de la fuente", IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. PAMI-2, marzo de 1980, págs.  181-185.

• Implementaciones en Java, F#, Clojure, C# en Wikilibros
• Tutorial sobre codificación convolucional con decodificación de Viterbi, por Chip Fleming.
• Tutorial para un conjunto de herramientas de modelos ocultos de Markov (implementado en C) que contiene una descripción del algoritmo de Viterbi.
• Algoritmo de Viterbi del Dr. Andrew J. Viterbi (scholarpedia.org).