Algoritmo de Viterbi

Encuentra la secuencia probable de estados ocultos

El algoritmo de Viterbi es un algoritmo de programación dinámica que permite obtener la máxima estimación de probabilidad a posteriori de la secuencia más probable de estados ocultos (denominada camino de Viterbi ) que da como resultado una secuencia de eventos observados. Esto se hace especialmente en el contexto de las fuentes de información de Markov y los modelos ocultos de Markov (HMM).

El algoritmo ha encontrado una aplicación universal en la decodificación de los códigos convolucionales utilizados tanto en CDMA como en GSM , módems de acceso telefónico , satélite, comunicaciones de espacio profundo y redes LAN inalámbricas 802.11 . Ahora 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 se trata como la secuencia observada de eventos, y una cadena de texto se considera la "causa oculta" de la señal acústica. El algoritmo de Viterbi encuentra la cadena de texto más probable dada la señal acústica.

Historia

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 invención múltiple , 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.

La ruta 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 utilizar un algoritmo de programación dinámica para descubrir la única 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 pista que asigna una probabilidad máxima a una secuencia de observaciones. ^[7]

Algoritmo

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

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

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

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

Pseudocódigo

La función Viterbi(estados, init, trans, emit, obs) es  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 × O entrada obs: secuencia de T observaciones prob ← Matriz de ceros T × S prev ← 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 nuevo_prob ← prob[t - 1][r] * trans[r][s] * emitir[s][obs[t]] Si new_prob > prob[t][s] entonces prob[t][s] ← nuevo_prob anterior[t][s] ← r ruta ← matriz vacía de longitud T path[T - 1] ← el estado s con máxima probabilidad[T - 1][s] para t = T - 2 a 0 inclusive hacer ruta[t] ← anterior[t + 1][ruta[t + 1]] Fin de la ruta de retorno

La complejidad temporal del algoritmo es . Si se sabe qué transiciones de estado tienen una probabilidad distinta de cero, se puede encontrar un límite mejorado iterando solo sobre aquellas que se vinculan a en el bucle interno. Luego, utilizando el análisis amortizado, se puede demostrar que la complejidad es , donde es el número de aristas en el gráfico, es decir, el número de entradas distintas de cero en la matriz de transición. ${\displaystyle O(T\times \left|{S}\right|^{2})}$ ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle O(T\times (\left|{S}\right|+\left|{E}\right|))}$ ${\displaystyle E}$

Ejemplo

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 decir que se sienten normales, mareados o con frío.

Se cree que el estado de salud de los pacientes funciona como una cadena discreta de Markov . Existen dos estados, "saludable" 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 "tengo mareos" depende únicamente del estado de salud del paciente ese día.

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

init = {"Saludable": 0,6, "Fiebre": 0,4}trans = { "Saludable": {"Saludable": 0,7, "Fiebre": 0,3}, "Fiebre": {"Saludable": 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 sería {'Healthy': 0.57, 'Fever': 0.43}según las probabilidades de transición. Las probabilidades de transición transrepresentan el cambio de la condición de salud en la cadena de Markov subyacente. En este ejemplo, un paciente que está sano hoy tiene solo un 30% de posibilidades de tener fiebre mañana. Las probabilidades de emisión emitrepresentan la probabilidad de cada posible observación (normal, resfriado o mareado), dada la condición subyacente (sano o fiebre). Un paciente que está sano tiene un 50% de posibilidades de sentirse normal; uno que tiene fiebre tiene un 60% de posibilidades de sentirse mareado.

Representación gráfica del HMM dado

Un paciente en particular visita tres días seguidos y refiere sentirse normal el primer día, con frío el segundo día y mareado el tercer día.

En primer lugar, se calculan las probabilidades de estar sano o de tener fiebre el primer día. La probabilidad de que un paciente esté sano el primer día y diga que se siente normal es . Del mismo modo, la probabilidad de que un paciente tenga fiebre el primer día y diga que se siente normal es . ${\displaystyle 0.6\times 0.5=0.3}$ ${\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 probabilidad más alta de estar sano el segundo día y reportar tener un resfriado, después de reportar tener un resfriado normal el primer día, es el máximo de y . Esto sugiere que es más probable que el paciente haya estado sano durante ambos días, en lugar de tener fiebre y recuperarse. ${\displaystyle 0.3\times 0.7\times 0.4=0.084}$ ${\displaystyle 0.04\times 0.4\times 0.4=0.0064}$

El resto de probabilidades se resumen en la siguiente tabla:

De la tabla se desprende que lo más probable es que el paciente haya tenido 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), que se puede encontrar rastreando los estados que se utilizaron al calcular los máximos (que resulta ser la mejor estimación de cada día, pero no siempre lo será). En otras palabras, dadas las actividades observadas, lo más probable es que el paciente haya estado sano el primer día y también el segundo día (a pesar de sentir frío ese día), y que solo haya 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.

Extensiones

Una generalización del algoritmo de Viterbi, denominada algoritmo de suma máxima (o algoritmo de producto máximo ), se puede utilizar para encontrar la asignación más probable de todas o de algún subconjunto de 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 necesitan, en general, estar conectadas de una manera 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 las variables. 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 ).

Con un algoritmo llamado decodificación iterativa de Viterbi , se puede encontrar la subsecuencia de una observación que coincide mejor (en promedio) con un modelo oculto de Markov dado. Este algoritmo es propuesto por Qi Wang et al. para tratar con el código 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, en 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 resultados posibles, el algoritmo Lazy Viterbi mantiene una lista priorizada de nodos para evaluar en orden, y la cantidad de cálculos necesarios es típicamente menor (y nunca mayor) que el algoritmo Viterbi ordinario para el mismo resultado. Sin embargo, no es tan fácil ^{[ aclaración necesaria ]} para paralelizar en hardware.

Algoritmo de Viterbi de salida suave

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 confiabilidad de la decisión.

El primer paso en SOVA es la selección de la ruta 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 (se elige una rama para formar la ruta de supervivencia y se descarta la otra), la diferencia en las métricas de las ramas (o el costo ) entre las ramas elegidas y descartadas indica la cantidad de error en la elección.

Este costo se acumula a lo largo de toda la ventana deslizante (generalmente equivale al menos a cinco longitudes de restricción) para indicar la medida de salida suave de la confiabilidad de la decisión de bit dura del algoritmo de Viterbi.

Véase también

• Algoritmo de expectativa-maximización
• Algoritmo de Baum-Welch
• Algoritmo de avance y retroceso
• Algoritmo de avance
• Código de corrección de errores
• Descodificador Viterbi
• Modelo oculto de Markov
• Etiquetado de partes del discurso
• Algoritmo de búsqueda A*

Referencias

1. Xavier Anguera et al., "Diarización del hablante: una revisión de investigaciones recientes" Archivado el 12 de mayo de 2016 en Wayback Machine , consultado el 19 de agosto de 2010, IEEE TASLP
2. 29 de abril de 2005, G. David Forney Jr: El algoritmo de Viterbi: una historia personal
3. Daniel Jurafsky; James H. Martin. Procesamiento del habla y del lenguaje . Pearson Educación Internacional. pág. 246.
4. Schmid, Helmut (2004). Análisis eficiente de gramáticas independientes del contexto altamente ambiguas con vectores de bits (PDF) . Proc. 20th Int'l Conf. on Computational Linguistics (COLING). doi : 10.3115/1220355.1220379 .
5. Klein, Dan; Manning, Christopher D. (2003). Análisis sintáctico A*: selección rápida y exacta del análisis sintáctico de Viterbi (PDF) . Proc. 2003 Conf. del Capítulo norteamericano de la Asociación de Lingüística Computacional sobre Tecnología del Lenguaje Humano (NAACL). págs. 40–47. doi : 10.3115/1073445.1073461 .
6. Stanke, M.; Keller, O.; Gunduz, I.; Hayes, A.; Waack, S.; Morgenstern, B. (2006). "AUGUSTUS: predicción ab initio de transcripciones alternativas". Nucleic Acids Research . 34 (número del servidor web): W435–W439. doi :10.1093/nar/gkl200. PMC 1538822 . PMID  16845043. 
7. Quach, T.; Farooq, M. (1994). "Formación de pistas de máxima verosimilitud con el algoritmo de Viterbi". Actas de la 33.ª Conferencia IEEE sobre decisiones y control . Vol. 1. págs. 271–276. doi :10.1109/CDC.1994.410918.{{cite conference}}: CS1 maint: multiple names: authors list (link)
8. Xing E, diapositiva 11.
9. Qi Wang; Lei Wei; Rodney A. Kennedy (2002). "Decodificación iterativa de Viterbi, modelado de enrejado y estructura multinivel para TCM concatenado con paridad de alta tasa". IEEE Transactions on Communications . 50 : 48–55. doi :10.1109/26.975743.
10. Un decodificador rápido de máxima verosimilitud para códigos convolucionales (PDF) . Conferencia sobre tecnología vehicular. Diciembre de 2002. págs. 371–375. doi :10.1109/VETECF.2002.1040367.

Referencias generales

• 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. Descodificación de Viterbi". Recetas numéricas: el arte de la computación científica (3.ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8Archivado desde el original el 11-08-2011 . Consultado el 17-08-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 de avance 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-1, abril de 1979, págs. 184-193.
• Shinghal, R. y Godfried T. Toussaint , "La sensibilidad del algoritmo Viterbi modificado a las estadísticas de origen", IEEE Transactions on Pattern Analysis and Machine Intelligence , vol. PAMI-2, marzo de 1980, págs. 181–185.

Enlaces externos

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

Implementaciones

• Mathematica tiene una implementación como parte de su soporte para procesos estocásticos
• El marco de procesamiento de señales de Susa proporciona aquí la implementación de C++ para códigos de corrección de errores de avance y ecualización de canal.
• C++
• DO#
• Java Archivado el 4 de mayo de 2014 en Wayback Machine
• Java 8
• Julia (HMMBase.jl)
• Perl
• Prolog Archivado el 2 de mayo de 2012 en Wayback Machine.
• Haskell
• Ir
• SFIHMM incluye código para la decodificación de Viterbi.