El algoritmo de Viterbi es un algoritmo de programación dinámica que identifica la secuencia más probable de estados ocultos que podría haber producido una secuencia dada de eventos observados. La secuencia resultante a menudo se denomina ruta de Viterbi. Se aplica con mayor frecuencia a modelos ocultos de Markov (HMM), donde los estados subyacentes no son directamente observables pero influyen en las observaciones. Por ejemplo, un médico que observa los síntomas de un paciente durante varios días podría usar el algoritmo para inferir la secuencia más probable de condiciones de salud subyacentes que causaron esos síntomas.
El algoritmo ha encontrado aplicación universal en la decodificación de códigos convolucionales utilizados en redes celulares digitales CDMA y GSM, módems de acceso telefónico, comunicaciones satelitales y de espacio profundo, y LAN inalámbricas 802.11. También se utiliza ampliamente en reconocimiento de voz, síntesis de voz, diarización de hablantes, detección de palabras clave, lingüística computacional y bioinformática. En sistemas de conversión de voz a texto, la señal acústica sirve como secuencia observada, y la cadena de texto es la causa oculta; el algoritmo de Viterbi encuentra el 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 con ruido. 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. Se introdujo en el procesamiento del lenguaje natural como un método para el etiquetado de partes del discurso ya en 1987.
Los términos "ruta de Viterbi" y "algoritmo de Viterbi" se han convertido en estándar para enfoques de programación dinámica a problemas de maximización que involucran probabilidades. En el análisis estadístico, un algoritmo de programación dinámica puede descubrir la derivación libre de contexto más probable (análisis sintáctico) de una cadena, comúnmente llamada "análisis de Viterbi". Otra aplicación es el seguimiento de objetivos, donde el algoritmo calcula la pista que asigna la máxima probabilidad a una secuencia de observaciones.
Resumen del Algoritmo
Dado un modelo oculto de Markov con un conjunto de estados ocultos S, un conjunto de posibles emisiones (observaciones) M, y una secuencia de T observaciones o0, o1, ..., oT-1, el algoritmo de Viterbi encuentra la secuencia más probable de estados ocultos que podría haber producido esas observaciones. En cada paso de tiempo t, el algoritmo resuelve el subproblema donde solo se consideran las observaciones hasta ot.
Se construyen dos matrices de tamaño T × |S|. La matriz Pt,s contiene la probabilidad máxima de terminar en el estado s en la observación t, entre todas las secuencias posibles de estados que conducen a ella. La matriz Qt,s rastrea el estado anterior que se usó antes de s en esta secuencia de estados de probabilidad máxima.
Sean πs y ar,s las probabilidades iniciales y de transición respectivamente, y sea bs,o la probabilidad de observar o en el estado s. Entonces los valores de P están dados por una relación de recurrencia. En el tiempo t = 0, Pt,s es igual a πs multiplicado por bs,o0. Para t > 0, Pt,s es igual al máximo sobre todos los estados anteriores r de (Pt-1,r × ar,s × bs,ot). Después de llenar las matrices, el algoritmo retrocede desde el estado con la probabilidad más alta en el paso de tiempo final usando la matriz Q para reconstruir la secuencia de estados más probable.
Aplicaciones en Comunicaciones
El algoritmo es una piedra angular de las comunicaciones digitales modernas. Decodifica códigos convolucionales, que son códigos de corrección de errores utilizados en muchos sistemas inalámbricos y cableados. En redes celulares CDMA y GSM, el algoritmo de Viterbi ayuda a recuperar datos transmitidos a pesar del ruido y la interferencia. Los módems de acceso telefónico, los enlaces satelitales y los sistemas de comunicación de espacio profundo también dependen de él. El estándar de LAN inalámbrica 802.11 incorpora la decodificación de Viterbi para una transmisión de datos confiable.
La eficiencia del algoritmo proviene de su naturaleza de programación dinámica: evita la enumeración exhaustiva de todas las secuencias de estados posibles al almacenar probabilidades intermedias y usar el principio de optimalidad. Esto hace factible decodificar secuencias largas en tiempo real, incluso en dispositivos con recursos limitados.
Aplicaciones en Habla y Lenguaje
En el reconocimiento de voz, el algoritmo de Viterbi alinea características acústicas con modelos fonéticos o de palabras. La señal acústica es la secuencia observada, y la cadena de texto es la causa oculta. El algoritmo encuentra la cadena de texto más probable dada la señal acústica, lo que permite una transcripción precisa. También se utiliza en la síntesis de voz para seleccionar la secuencia más natural de unidades de habla, y en la diarización de hablantes para determinar quién habló y cuándo.
En la lingüística computacional, el algoritmo se aplica al etiquetado de partes del discurso, donde los estados ocultos son categorías gramaticales y las observaciones son palabras. También respalda el análisis estadístico, donde encuentra el árbol de análisis más probable para una oración. En bioinformática, ayuda a alinear secuencias biológicas y predecir estructuras genéticas, tratando secuencias de ADN o proteínas como observaciones y elementos funcionales como estados ocultos.
Técnicas Relacionadas
El algoritmo de Viterbi está estrechamente relacionado con otros métodos de programación dinámica, como el algoritmo hacia adelante-hacia atrás, que calcula probabilidades sobre todas las secuencias de estados posibles en lugar de solo la más probable. También comparte fundamentos conceptuales con búsqueda de haz, una técnica de búsqueda heurística utilizada en la generación de secuencias. En sistemas modernos de aprendizaje automático y inteligencia artificial, especialmente aquellos que involucran modelos secuencia a secuencia y modelos de lenguaje grandes, la búsqueda de haz a menudo se prefiere sobre la decodificación exacta de Viterbi debido a los grandes espacios de estados involucrados.
A pesar del auge de los enfoques de redes neuronales, el algoritmo de Viterbi sigue siendo relevante en sistemas híbridos. Por ejemplo, puede usarse para decodificar salidas de modelos acústicos de redes neuronales en el reconocimiento de voz, o para imponer restricciones estructurales en tareas de procesamiento del lenguaje natural. Su claridad matemática y eficiencia aseguran su uso continuo en aplicaciones tanto clásicas como contemporáneas.