El algoritmo de Viterbi es un algoritmo de programación dinámica para obtener la máxima estimación de probabilidad 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 en celulares digitales CDMA y GSM , módems de acceso telefónico , satélite, 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 la conversión de 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.
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 sobre enlaces de comunicación digital 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 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 usar 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]
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 todas o algunas de las variables latentes en un gran número 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 involucra el paso de mensajes y es sustancialmente similar a la propagación de creencias.algoritmo (que es la generalización del algoritmo adelante-atrás ).
Con el algoritmo llamado decodificación iterativa de Viterbi , uno puede encontrar la subsecuencia de una observación que se ajusta mejor (en promedio) a 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 mediante la invocación iterativa de un algoritmo de Viterbi modificado, reestimando la puntuación para un relleno hasta la convergencia.