Algoritmo de Viterbi

Encuentra una secuencia probable de estados ocultos

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

El algoritmo ha encontrado una aplicación universal en la decodificación de códigos convolucionales utilizados en celulares digitales CDMA y GSM , módems de acceso telefónico , satélites, comunicaciones de espacio profundo y LAN inalámbricas 802.11 . Ahora también se usa comúnmente en reconocimiento de voz , síntesis de voz , diarioizació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 lleva el nombre de Andrew Viterbi , quien lo propuso en 1967 como un algoritmo de decodificación de códigos convolucionales a través de enlaces de comunicación digitales ruidosos. ^[2] Tiene, sin embargo, 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 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 el seguimiento de objetivos , donde se calcula el seguimiento 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 donde 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 de 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 usó antes en esta secuencia de estados 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] ${\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 \max }$ ${\displaystyle \arg \max }$ ${\displaystyle P}$ ${\displaystyle Q}$

Pseudocódigo

la función Viterbi(states, init, trans, emit, obs) es estados  de entrada : S estados ocultos entrada init: probabilidades iniciales de cada estado entrada trans: S × S matriz de transición entrada emitir: S × O matriz de emisión entrada obs: secuencia de T observaciones prob ← T × S matriz de ceros anterior ← matriz T × S vacía para  cada estado s en estados hacer prob[0][s] = inicio[s] * emitir[s][obs[0]] final  para t = 1 a T - 1 hacer  para  cada estado s en estados hacer  para  cada estado r en estados hacer new_prob ← prob[t - 1][r] * trans[r][s] * emit[s][obs[t]] si new_prob > prob[t][s] entonces problema[t][s] ← nuevo_prob anterior[t][s] ← r fin  fin  fin  fin ruta ← matriz vacía de longitud T ruta[T - 1] ← el estado s con probabilidad máxima[T - 1][s] para t = T - 1 a 1 hacer ruta[t - 1] ← anterior[t][ruta[t]] final camino de retorno final

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 aquellas que se vinculan en el bucle interno. Luego, utilizando el análisis amortizado se puede demostrar que la complejidad es , donde está 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 el médico puede obtener es preguntando a los pacientes cómo se sienten. Los pacientes pueden informar que se sienten normales, mareados o fríos.

Se cree que el estado de salud de los pacientes opera como una cadena de Markov discreta . Hay dos estados, "sano" y "fiebre", pero el médico no puede observarlos directamente; están ocultos del médico. Cada día, la posibilidad de que un paciente le diga al médico "me siento normal", "tengo frío" o "me siento mareado" depende únicamente del estado de salud del paciente ese día.

Las observaciones (normal, frío, mareado) junto con los estados ocultos (salud, fiebre) forman un modelo oculto de Markov (HMM). Según la experiencia pasada, 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, "frío": 0,3, "mareo": 0,6},}

En este código, initrepresenta la creencia del médico sobre la probabilidad de que el paciente esté sano inicialmente. Tenga en cuenta 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 condición de salud en la cadena de Markov subyacente. En este ejemplo, un paciente que hoy está sano tiene sólo un 30% de posibilidades de tener fiebre mañana. Las probabilidades de emisión emitrepresentan la probabilidad de cada observación posible (normal, fría o mareada), dada la condición subyacente (salud o fiebre). Un paciente sano tiene un 50% de posibilidades de sentirse normal; Quien 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 e informa que se siente normal el primer día, frío el segundo día y mareado el tercer día.

En primer lugar se calculan las probabilidades de estar sano o tener fiebre el primer día. Dado que el paciente dice sentirse normal, la probabilidad de que realmente estuviera sano es . De manera similar, la probabilidad de que tuvieran fiebre 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 desde el día anterior. Por ejemplo, la probabilidad de estar sano el segundo día es máxima de y . Esto sugiere que es más probable que el paciente estuviera sano durante esos dos 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 tuviera fiebre al tercer día. Además, existe una secuencia de estados que terminan en "fiebre", cuya probabilidad de producir las observaciones dadas es 0,1512. Esta secuencia es precisamente (sano, sano, fiebre), que se puede encontrar rastreando qué estados se utilizaron al calcular los máximos. 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 día (a pesar de sentir frío ese día), y sólo hubiera contraído fiebre el tercer día.

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

Extensiones

Se puede utilizar una generalización del algoritmo de Viterbi, denominada algoritmo de suma máxima (o algoritmo de producto máximo ), para encontrar la asignación más probable de todos o algunos subconjuntos de variables latentes en una gran cantidad de modelos gráficos , por ejemplo , redes bayesianas , Markov. campos aleatorios y campos aleatorios condicionales . Las variables latentes necesitan, en general, estar conectadas de una manera algo 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 hacia adelante y hacia atrás ).

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 determinado. Este algoritmo es propuesto por Qi Wang et al. para lidiar 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 diferido (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 de Viterbi original calcula cada nodo en el entramado 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 algoritmo de Viterbi ordinario para el mismo resultado. Sin embargo, no es tan fácil ^{[ se necesita aclaración ]} 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, pasando 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 Survivor Path y la otra se descarta), la diferencia en las métricas de la rama (o costo ) entre las ramas elegidas y descartadas indican la cantidad de error en la elección.

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

Ver también

• Algoritmo de expectativa-maximización
• Algoritmo de Baum-Welch
• Algoritmo hacia adelante y hacia atrás
• Algoritmo directo
• Código de corrección de errores
• decodificador viterbi
• Modelo de Markov oculto
• Etiquetado de parte del discurso
• Un* algoritmo de búsqueda

Referencias

1. Xavier Anguera et al., "Diarización de los oradores: una revisión de investigaciones recientes", 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. Martín. Procesamiento del habla y el lenguaje . Internacional de la Educación Pearson. pag. 246.
4. Schmid, Helmut (2004). Análisis eficiente de gramáticas libres de contexto altamente ambiguas con vectores de bits (PDF) . Proc. 20ª Conferencia Internacional. en Lingüística Computacional (COLING). doi : 10.3115/1220355.1220379 .
5. Klein, Dan; Manning, Christopher D. (2003). "Análisis A *: selección rápida y exacta del análisis de Viterbi (PDF)" . Proc. Conferencia de 2003. 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). "AGOSTO: Predicción ab initio de transcripciones alternativas". Investigación de ácidos nucleicos . 34 (problema 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 Decisión 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, configuración de enrejado y estructura multinivel para TCM concatenada por paridad de alta tasa". Transacciones IEEE sobre Comunicaciones . 50 : 48–55. doi : 10.1109/26.975743.
10. Un decodificador rápido de máxima verosimilitud para códigos convolucionales (PDF) . Jornada de 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". Transacciones IEEE sobre teoría de la información . 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.
• Prensa, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 16.2. Decodificación de Viterbi". Recetas numéricas: el arte de la informática científica (3ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.
• Rabiner LR (febrero de 1989). "Un tutorial sobre modelos ocultos de Markov y aplicaciones seleccionadas en 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 de 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 de Viterbi modificado a las estadísticas fuente", 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 viterbi, por Chip Fleming
• Un tutorial para un kit 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 reenvío y ecualización de canales.
• C++
• C#
• Java
• Java 8
• Julia (HMMBase.jl)
• perla
• Prólogo
• Haskell
• Ir
• SFIHMM incluye código para decodificación de Viterbi.