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, especialmente en el contexto de fuentes de información de Markov y Markov oculto. modelos (HMM).
El algoritmo ha encontrado una aplicación universal en la decodificación de los códigos convolucionales utilizados tanto en CDMA como en celulares digitales 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 , diarización , [1] detección de palabras clave , lingüística computacional y bioinformática . Por ejemplo, en voz a texto(reconocimiento de voz), la señal acústica se trata como la secuencia de eventos observada 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 para códigos convolucionales sobre enlaces de comunicación digital ruidosos. [2] Sin embargo, tiene una historia de múltiples inventos , 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 de voz 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 derivación libre de contexto más probable (análisis sintáctico) de una cadena, que comúnmente se denomina "análisis sintáctico 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]
Extensiones
Se puede utilizar una generalización del algoritmo de Viterbi, denominado algoritmo de suma máxima (o algoritmo de producto máximo ) para encontrar la asignación más probable de todas 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 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 el algoritmo llamado decodificación iterativa de Viterbi, se puede encontrar la subsecuencia de una observación que se corresponda mejor (en promedio) con un modelo de Markov oculto dado . Este algoritmo es propuesto por Qi Wang et al. para lidiar con el código turbo . [8] 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 . [9] Para muchas aplicaciones de interés práctico, en condiciones de ruido razonables, el decodificador perezoso (usando el algoritmo Lazy Viterbi) es mucho más rápido que el decodificador Viterbi original (usando el algoritmo Viterbi). Mientras que el algoritmo de Viterbi original calcula cada nodo en el trellis de posibles resultados, el algoritmo de Lazy Viterbi mantiene una lista priorizada de nodos para evaluar en orden, y el número de cálculos requeridos es típicamente menor (y nunca más) que el algoritmo de Viterbi ordinario para el mismo resultado. Sin embargo, no es tan fácil [ aclaración necesaria ] paralelizar en hardware.
Pseudocódigo
Este algoritmo genera una ruta , que es una secuencia de estados que generan las observaciones con , dónde es el número de posibles observaciones en el espacio de observación .
Dos tablas bidimensionales de tamaño están construidos:
- Cada elemento de almacena la probabilidad de la ruta más probable hasta ahora con que genera .
- Cada elemento de historias del camino más probable hasta ahora
Las entradas de la tabla se llenan por orden creciente de :
- ,
- ,
con y Como es definido debajo. Tenga en cuenta que no necesita aparecer en la última expresión, ya que no es negativo e independiente de y por lo tanto no afecta al argmax.
- Aporte
- El espacio de observación ,
- el espacio de estado ,
- una matriz de probabilidades iniciales tal que almacena la probabilidad de que ,
- una secuencia de observaciones tal que si la observación en el momento es ,
- matriz de transición de tamaño tal que almacena la probabilidad de transición de transitar desde el estado a estado ,
- matriz de emisión de tamaño tal que almacena la probabilidad de observar del estado .
- Producción
- La secuencia de estado oculta más probable
función VITERBI para cada estado hacer final para cada observación hacer para cada estado hacer fin por fin para por hacer final para el regreso función final
Reformulado en un sucinto casi Python :
# probabilidad == p. Tm: la matriz de transición. Em: la matriz de emisión.función viterbi (O, S, Π, Tm, Em): best_path trellis ← matriz (longitud (S), longitud (O)) # Para sujetar p. de cada estado dada cada observación. # Determine la p de cada estado oculto. en el tiempo 0… para s en rango (longitud (S)): enrejado [s, 0] ← Π [s] * Em [s, O [0]] #… Y luego, asumiendo el estado anterior más probable de cada estado, k. para o en rango (1, longitud (O)): para s en rango (longitud (S)): k ← argmax ( k en enrejado [ k , o-1] * Tm [ k , s] * Em [s, o]) enrejado [s, o] ← enrejado [ k , o-1] * Tm [ k , s] * Em [s, o] mejor_ruta ← lista () para o en rango (-1, - (longitud (O) +1), -1): # Retroceso de la última observación. k ← argmax ( k en trellis [ k , o]) # Estado más probable en o best_path.insert (0, S [ k ]) # se indica para retorno. devolver best_path
- Explicación
Supongamos que se nos da un modelo de Markov oculto (HMM) con espacio de estados, probabilidades iniciales de estar en estado y probabilidades de transición de hacer la transición del estado a estado . Digamos, observamos salidas. La secuencia de estados más probableque produce las observaciones viene dada por las relaciones de recurrencia [10]
Aquí es la probabilidad de la secuencia de estados más probable responsable de la primera observaciones que tienen como su estado final. La ruta de Viterbi se puede recuperar guardando los punteros hacia atrás que recuerdan qué estadose utilizó en la segunda ecuación. Dejar ser la función que devuelve el valor de utilizado para calcular Si , o Si . Luego
Aquí estamos usando la definición estándar de arg max .
La complejidad de esta implementación es . Existe una mejor estimación si el máximo en el bucle interno se encuentra en cambio iterando solo sobre estados que se vinculan directamente con el estado actual (es decir, hay un borde de a ). Luego, utilizando el análisis amortizado, se puede demostrar que la complejidad es, dónde es el número de aristas del gráfico.
Ejemplo
Considere una aldea donde todos los aldeanos están sanos o tienen fiebre y solo el médico de la aldea puede determinar si todos tienen fiebre. El médico diagnostica la fiebre preguntando a los pacientes cómo se sienten. Los aldeanos solo pueden responder que se sienten normales, mareados o con frío.
El médico cree que el estado de salud de sus pacientes opera como una cadena de Markov discreta . Hay dos estados, "Saludable" y "Fiebre", pero el médico no puede observarlos directamente; se le ocultan . Cada día, existe una cierta probabilidad de que el paciente le diga al médico que está "normal", "frío" o "mareado", según su estado de salud.
Las observaciones (normal, frío, mareado) junto con un estado oculto (saludable, fiebre) forman un modelo de Markov oculto (HMM) y se pueden representar de la siguiente manera en el lenguaje de programación Python :
obs = ( "normal" , "frío" , "mareado" ) estados = ( "Saludable" , "Fiebre" ) start_p = { "Saludable" : 0.6 , "Fiebre" : 0.4 } trans_p = { "Saludable" : { " Saludable " : 0,7 , " Fiebre " : 0,3 }, " Fiebre " : { " Saludable " : 0,4 , " Fiebre " : 0,6 }, } emit_p = { " Saludable " : { " normal " : 0,5 , " resfriado " : 0,4 , "mareado" : 0.1 }, "Fiebre" : { "normal" : 0.1 , "frío" : 0.3 , "mareado" : 0.6 }, }
En este código, start_p
representa la creencia del médico sobre en qué estado se encuentra el HMM cuando el paciente visita por primera vez (todo lo que sabe es que el paciente tiende a estar sano). La distribución de probabilidad particular utilizada aquí no es la de equilibrio, que es (dadas las probabilidades de transición) aproximadamente {'Healthy': 0.57, 'Fever': 0.43}
. El transition_p
representa el cambio del estado de salud en la cadena de Markov subyacente. En este ejemplo, hay solo un 30% de probabilidad de que mañana el paciente tenga fiebre si está sano hoy. El emit_p
representa la probabilidad de que cada posible observación, normal, fría o mareada, tenga su condición subyacente, saludable o fiebre. Si el paciente está sano, hay un 50% de posibilidades de que se sienta normal; si tiene fiebre, existe un 60% de probabilidad de que se sienta mareado.
El paciente visita tres días seguidos y el médico descubre que el primer día se siente normal, el segundo día siente frío, el tercer día se siente mareado. El médico tiene una pregunta: ¿cuál es la secuencia más probable de condiciones de salud del paciente que explicaría estas observaciones? Esto es respondido por el algoritmo de Viterbi.
def viterbi ( obs , estados , start_p , trans_p , emit_p ): V = [{}] para st en estados : V [ 0 ] [ st ] = { "prob" : start_p [ st ] * emit_p [ st ] [ obs [ 0 ]], "prev" : None } # Ejecute Viterbi cuando t> 0 para t en el rango ( 1 , len ( obs )): V . añadir ({}) para st en estados : max_tr_prob = V [ t - 1 ] [ estados [ 0 ]] [ "prob" ] * trans_p [ estados [ 0 ]] [ st ] prev_st_selected = estados [ 0 ] para prev_st en los estados [ 1 :]: tr_prob = V [ t - 1 ] [ prev_st ] [ "prob" ] * trans_p [ prev_st ] [ st ] si tr_prob > max_tr_prob : max_tr_prob = tr_prob prev_st_selected = prev_st max_prob = max_tr_prob * emit_p [ st ] [ obs [ t ]] V [ t ] [ st ] = { "prob" : max_prob , "prev" : prev_st_selected } para línea en dptable ( V ): imprimir ( línea ) opt = [] max_prob = 0.0 best_st = Ninguno # Obtenga el estado más probable y su retroceso para st , datos en V [ - 1 ] . elementos (): si datos [ "prob" ] > max_prob : max_prob = data [ "prob" ] best_st = st optar . añadir ( best_st ) anterior = best_st # Siga la pista hasta la primera observación para t en el rango ( len ( V ) - 2 , - 1 , - 1 ): optar . insertar ( 0 , V [ t + 1 ] [ anterior ] [ "anterior" ]) anterior = V [ t + 1 ] [ anterior ] [ "anterior" ] print ( "Los pasos de los estados son" + "" . join ( opt ) + "con la probabilidad más alta de % s " % max_prob )def dptable ( V ): # Imprime una tabla de pasos del diccionario rendimiento "" * 5 + "" . join (( " % 3d " % i ) para i en el rango ( len ( V ))) para el estado en V [ 0 ]: rendimiento " % .7s :" % estado + "" . join ( " % .7s " % ( " % lf " % v [ estado ] [ "prob" ]) para v en V )
La función viterbi
toma los siguientes argumentos: obs
es la secuencia de observaciones, por ejemplo ['normal', 'cold', 'dizzy']
; states
es el conjunto de estados ocultos; start_p
es la probabilidad de inicio; trans_p
son las probabilidades de transición; y emit_p
son las probabilidades de emisión. Para simplificar el código, asumimos que la secuencia de observación obs
no está vacía y que trans_p[i][j]
y emit_p[i][j]
está definida para todos los estados i, j.
En el ejemplo de ejecución, el algoritmo de avance / Viterbi se utiliza de la siguiente manera:
viterbi ( obs , estados , start_p , trans_p , emit_p )
La salida del script es
$ python viterbi_example.py 0 1 2 Saludable: 0.30000 0.08400 0.00588 Fiebre: 0.04000 0.02700 0.01512 Los pasos de los estados son Saludable Fiebre saludable con mayor probabilidad de 0.01512
Esto revela que las observaciones ['normal', 'cold', 'dizzy']
probablemente fueron generadas por estados ['Healthy', 'Healthy', 'Fever']
. En otras palabras, dadas las actividades observadas, era más probable que el paciente hubiera estado sano tanto el primer día cuando se sintió normal como el segundo día cuando sintió frío, y luego contrajo 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.
Algoritmo de Viterbi de salida suave
El algoritmo de Viterbi de salida suave ( SOVA ) es una variante del algoritmo clásico de Viterbi.
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 de la ruta del superviviente, pasando por un nodo único en cada instante de tiempo, t . Dado que cada nodo tiene 2 ramas que convergen en él (con una rama que se elige para formar la Ruta de Superviviente y la otra se descarta), la diferencia en las métricas de rama (o costo ) entre las ramas elegidas y descartadas indica la cantidad de error en la elección.
Este costo se acumula en toda la ventana deslizante (generalmente es igual a al menos cinco longitudes de restricción), 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 maximización de expectativas
- Algoritmo de Baum-Welch
- Algoritmo hacia adelante y hacia atrás
- Algoritmo de avance
- Código de corrección de errores
- Decodificador de Viterbi
- Modelo de Markov oculto
- Etiquetado de parte de la voz
- Algoritmo de búsqueda A *
Referencias
- ^ Xavier Anguera et al., "Speaker Diarization: A Review of Recent Research" , consultado el 19 de agosto de 2010, IEEE TASLP
- ^ 29 de abril de 2005, G. David Forney Jr: El algoritmo de Viterbi: una historia personal
- ^ a b Daniel Jurafsky; James H. Martin. Procesamiento del habla y el lenguaje . Pearson Education International. pag. 246.
- ^ Schmid, Helmut (2004). Análisis eficiente de gramáticas libres de contexto altamente ambiguas con vectores de bits (PDF) . Proc. 20ª Conf. Internacional de Lingüística Computacional (COLING). doi : 10.3115 / 1220355.1220379 .
- ^ 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 .
- ^ Stanke, M .; Keller, O .; Gunduz, I .; Hayes, A .; Waack, S .; Morgenstern, B. (2006). "AUGUSTUS: 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 .
- ^ 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 . 1 . págs. 271–276. doi : 10.1109 / CDC.1994.410918 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Qi Wang; Lei Wei; Rodney A. Kennedy (2002). "Decodificación iterativa de Viterbi, modelado enrejado y estructura multinivel para TCM concatenado por paridad de alta velocidad". Transacciones IEEE sobre comunicaciones . 50 : 48–55. doi : 10.1109 / 26.975743 .
- ^ 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 .
- ^ Xing E, diapositiva 11.
Referencias generales
- Viterbi AJ (abril de 1967). "Límites de error para códigos convolucionales y un algoritmo de decodificación óptimo asintóticamente". 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 . Jornada de Tecnología Vehicular . 1 . págs. 371–375. CiteSeerX 10.1.1.114.1314 . doi : 10.1109 / VETECF.2002.1040367 . ISBN 978-0-7803-7467-6.
- 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.
- Presione, 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 . (Describe el algoritmo de reenvío y el algoritmo de Viterbi para HMM).
- Shinghal, R. y Godfried T. Toussaint , "Experimentos en el reconocimiento de texto con el algoritmo de 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 de 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.
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 la implementación de C ++ para códigos de corrección de errores directos y ecualización de canales aquí .
- C ++
- C#
- Java
- Java 8
- Perl
- Prólogo
- Haskell
- Ir
- SFIHMM incluye código para la decodificación de Viterbi.
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 de Markov oculto (implementado en C) que contiene una descripción del algoritmo de Viterbi
- Algoritmo de Viterbi por el Dr. Andrew J. Viterbi (scholarpedia.org).