Algoritmo de Viterbi
Algoritmo que halla la secuencia de estados ocultos más probable que explica una serie de observaciones, muy usado en comunicaciones digitales y reconocimiento del habla.
- Año
- 1967
- Protagonistas
- Andrew Viterbi
- Sección
- Informática
Historia
El algoritmo de Viterbi es un procedimiento para encontrar la secuencia de estados ocultos más probable que explica una serie de observaciones. Se basa en la programación dinámica, una técnica que resuelve un problema grande descomponiéndolo en subproblemas cuyas soluciones se reutilizan. Su importancia radica en que aparece en comunicaciones, reconocimiento del habla y bioinformática, casi siempre dentro de modelos ocultos de Márkov, sistemas en los que lo que se observa depende de algo que no se ve directamente.
Antes de Viterbi, la decodificación de los códigos convolucionales, que añaden redundancia a los mensajes digitales para corregir errores en canales con ruido, se resolvía con métodos menos eficientes. Andrew Viterbi propuso su algoritmo en 1967 como forma de decodificar estos códigos en enlaces digitales ruidosos. La idea central es sencilla: para cada estado posible en cada instante se guarda la probabilidad del mejor camino que llega hasta él, junto con el estado anterior que lo maximiza. Al final basta con retroceder por esas anotaciones para reconstruir la ruta completa. Así, mientras el algoritmo forward suma todas las probabilidades posibles, Viterbi se queda solo con la mayor en cada paso.
Para verlo con un ejemplo, imaginemos un médico que no puede observar directamente si sus pacientes tienen fiebre, pero sí sabe si se encuentran normal, con frío o mareados. A partir de probabilidades estimadas por la experiencia, el algoritmo compara en cada día los caminos posibles y conserva el más verosímil. En el caso descrito en la fuente, la secuencia más probable es sano, sano, fiebre, con una probabilidad de 0,01512, aunque el mejor candidato en cada día por separado no siempre coincide con la ruta global, y por eso hace falta el retroceso.
El método se extendió más allá de la ingeniería de comunicaciones. En 1987 se introdujo en el procesamiento del lenguaje natural como técnica para el etiquetado gramatical, es decir, para asignar a cada palabra su categoría más probable. Con el tiempo, los términos «camino de Viterbi» y «algoritmo de Viterbi» se convirtieron en nombres habituales para cualquier aplicación de programación dinámica que maximice probabilidades. Así ocurre en el análisis sintáctico estadístico, donde se habla de la «análisis de Viterbi», o en el seguimiento de objetivos. Su coste de cálculo crece con el cuadrado del número de estados, aunque se reduce cuando solo algunas transiciones son posibles. Existen además variantes como el Lazy Viterbi, que resulta más rápido en muchos casos prácticos con ruido moderado.
Hoy el algoritmo forma parte de la decodificación de señales en redes de telefonía móvil GSM y CDMA, en módems, en comunicaciones por satélite y de espacio profundo, y en redes inalámbricas 802.11. También sostiene sistemas de conversión de voz en texto, en los que el sonido recibido es la observación y el texto es la causa oculta más probable. Su impacto cotidiano pasa casi inadvertido: cada vez que un teléfono móvil recupera un mensaje con errores o un asistente de voz entiende una frase, es probable que alguna versión de este procedimiento esté trabajando por debajo.
Cronología
- 1967Andrew Viterbi propone el algoritmo como método para decodificar códigos convolucionales en enlaces digitales con ruido.
- 1987Se introduce en el procesamiento del lenguaje natural como técnica de etiquetado gramatical.
- Fecha no precisada en las fuentes: adopción en la decodificación de GSM, CDMA, módems, satélites y redes 802.11.
Curiosidades y anécdotas
Un método descubierto varias veces
Se cuentan al menos siete descubrimientos independientes de técnicas parecidas, entre ellos los de Needleman y Wunsch y los de Wagner y Fischer. Por eso la autoría única es discutible.
Una ruta más corta
Si el cálculo se dibuja como una rejilla de estados y tiempos, el camino de Viterbi equivale al trayecto más corto a través de ella.
Andrew Viterbi1935 · Tecnología y comunicaciones