Algoritmo de Viterbi

El algoritmo Viterbi es un algoritmo que desarrolló Andrew James Viterbi en 1.967 como técnica de codificación convolucional diseñada para reducir la probabilidad de transmisión errónea a través de canales de telecomunicación ruidosos. Anteriormente, y dentro del ámbito de las comunicaciones, ya existían otros algoritmos similares o con mejor desarrollo:Andrew James Viterbi

 

  • J. M. Wozencraft en 1.957
  • R. M. Fano en 1.963
  • K. Sh. Zigangirov en 1.966

A partir del trabajo de Viterbi surgieron otros planteamientos de resolución similares que, de alguna forma, terminaron llamándose de Viterbi, estos fueron propuestos por:

 

  • T. K. Vintsyuk en 1.968 para el procesamiento de voz.
  • Saul B. Needleman y Christian D. Wunsch en 1.970 para bioinformática.
  • H. Sakoe y S. Chiba en 1.971 para el procesamiento de voz.
  • David Sankoff  en 1.972 para el tratamiento de secuencias coincidentes moleculares.
  • T. A. Reichert, D. N. Cohen y A. K. C. Wong en 1.973 para mutaciones genéticas.
  • R. A. Wagner y M. J. Fischer en 1.974 para problemas de la corrección ortográfica.

 

Respecto de su aplicación en HMM, el algoritmo pretende encontrar una secuencia de estados (Q = q1, q2, … qt), denominada ruta de Viterbi, que explique una secuencia determinada de observaciones (O = o1,… , ot) y su modelo Φ = (A, B, π). La mejor secuencia de estados, a través de la red de estados y observaciones, es la que tiene la menor distancia de Hamming.

 

El primer intento de solución es examinar todas las secuencias de la red y seleccionar la que proporcione la mayor probabilidad. Para el ejemplo propuesto en HMM es fácil, pero para situaciones reales es imposible abordar su obtención, ya que el número de secuencias, y por consiguiente el de operaciones, crece exponencialmente con el número de estados-observaciones. Basta con cambiar el número de observaciones de 3 a 6 y obtenemos, con los mismos estados, 720 secuencias que contrastadas con las seis iniciales (ejemplo) es algo desproporcionado.

 

Comparado con el anterior intento de solución, el algoritmo de Viterbi limita el número de secuencias a considerar para cada estado, de tal forma que cuando encuentra la mejor secuencia, el resto se descarta. Para cada tiempo y estado, se guarda la mejor secuencia obtenida y su valor.

 

En el ejemplo de abajo, en lenguaje Java con los datos del ejemplo propuesto en HMM, se puede observar la similitud de parte del código con el algoritmo de Avance.

 

El tiempo de complejidad computacional es igual a la del algoritmo de Avance, O(n2 × m) y la complejidad de espacio es O(n2 + n × m), donde:

n = número de estados posibles.

m = Longitud de la secuencia de observación.

 

🔴 Pulsar sobre el gráfico para ampliar.

 

Algoritmo de Viterbi en Java
Algoritmo de Viterbi en Java