Algoritmo de Viterbi

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, denominada ruta de Viterbi, que da como resultado una secuencia de eventos observados, especialmente en el contexto de fuentes de información de Markov y modelos ocultos de Markov (HMM).

El algoritmo ha encontrado una aplicación universal para decodificar 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, 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.

Historia

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. Sin embargo, 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 de etiquetado de partes del discurso ya en 1987.

Camino de Viterbi y 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. Por ejemplo, en el análisis estadístico, se puede usar un algoritmo de programación dinámica para descubrir la derivación (análisis) libre de contexto más probable de una cadena, que comúnmente se denomina "análisis de Viterbi". Otra aplicación es el seguimiento de objetivos, donde se calcula el seguimiento que asigna una probabilidad máxima a una secuencia de observaciones.

Extensiones

Se puede usar 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 todos o algunos subconjunto de variables latentes en una gran cantidad de modelos gráficos, p. Redes bayesianas, campos aleatorios de Markov y campos aleatorios condicionales. Las variables latentes necesitan, en general, estar conectadas de una manera similar a un modelo oculto de Markov (HMM), con un número limitado de conexiones entre variables y algún tipo de estructura lineal entre las variables. El algoritmo general implica 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, uno puede encontrar la subsecuencia de una observación que se ajusta mejor (en promedio) a un modelo oculto de Markov dado. Este algoritmo es propuesto por Qi Wang et al. para lidiar con el código turbo. 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.

Se ha propuesto un algoritmo alternativo, el algoritmo Lazy Viterbi. Para muchas aplicaciones de interés práctico, en condiciones de ruido razonables, el decodificador perezoso (que usa el algoritmo Lazy Viterbi) es mucho más rápido que el decodificador Viterbi original (que usa el algoritmo Viterbi). Mientras que el algoritmo de Viterbi original calcula cada nodo en el enrejado de posibles resultados, el algoritmo Lazy Viterbi mantiene una lista priorizada de nodos para evaluar en orden, y la cantidad de cálculos necesarios suele ser menor (y nunca mayor) que el algoritmo de Viterbi ordinario para el mismo resultado Sin embargo, no es tan fácil paralelizar en hardware.

Pseudocódigo

Este algoritmo genera un camino X=()x1,x2,...... ,xT){displaystyle X=(x_{1},x_{2},ldotsx_{T}}, que es una secuencia de estados xn▪ ▪ S={}s1,s2,...... ,sK}{displaystyle x_{n}in S={1},s_{2},dotss_{K}} que generan las observaciones Y=()Sí.1,Sí.2,...... ,Sí.T){displaystyle Y=(y_{1},y_{2},ldotsy_{T} con Sí.n▪ ▪ O={}o1,o2,...... ,oN}{displaystyle y_{n}in O={o_{1},o_{2},dotso_{N}}, donde N{displaystyle N} es el número de posibles observaciones en el espacio de observación O{displaystyle O..

Dos tablas de dos dimensiones K× × T{displaystyle Ktimes T} se construyen:

• Cada elemento T1[i,j]{displaystyle T_{1}[i,j] de T1{displaystyle T_{1} almacena la probabilidad de la ruta más probable hasta ahora X^ ^ =()x^ ^ 1,x^ ^ 2,...... ,x^ ^ j){displaystyle {hat {x}=({hat {x}_{1},{hat {x}_{2},ldots{hat {x}_{j}}}} con x^ ^ j=si{displaystyle {hat {x}_{j}=s_{i} que genera Y=()Sí.1,Sí.2,...... ,Sí.j){displaystyle Y=(y_{1},y_{2},ldotsy_{j}}.
• Cada elemento T2[i,j]{displaystyle T_{2}[i,j] de T2{displaystyle T_{2} tiendas x^ ^ j− − 1{displaystyle {hat {x}_{j-1} del camino más probable hasta ahora X^ ^ =()x^ ^ 1,x^ ^ 2,...... ,x^ ^ j− − 1,x^ ^ j=si){displaystyle {hat {x}=({hat {x}_{1},{hat {x}_{2},ldots{hat {x}}_{j-1},{hat {hat}} {x}_{j}=s_{i}) } О О j,2≤ ≤ j≤ ≤ T{displaystyle forall j,2leq jleq T}

Las entradas de la tabla T1[i,j],T2[i,j]{displaystyle T_{1}[i,j],T_{2}[i,j] están llenos por orden creciente de K⋅ ⋅ j+i{displaystyle Kcdot J+i:

T1[i,j]=maxk()T1[k,j− − 1]⋅ ⋅ Aki⋅ ⋅ BiSí.j){displaystyle T_{1}[i,j]=max _{k}{0}[k,j-1]cdot A_{ki}cdot B_{iy_{j}}}},

T2[i,j]=argmaxk⁡ ⁡ ()T1[k,j− − 1]⋅ ⋅ Aki⋅ ⋅ BiSí.j){displaystyle T_{2}[i,j]=cdot A_{ki}cdot B_{iy_{j}}}},

con Aki{displaystyle A_{ki} y BiSí.j{displaystyle B_{iy_{j}} como se define a continuación. Note que BiSí.j{displaystyle B_{iy_{j}} no necesita aparecer en esta última expresión, ya que no es negativo e independiente de k{displaystyle k} y por lo tanto no afecta el argmax.

Input

• El espacio de observación O={}o1,o2,...... ,oN}{displaystyle O={o_{1},o_{2},dotso_{N}},
• el espacio estatal S={}s1,s2,...... ,sK}{displaystyle S={1},s_{2},dotss_{K}},
• una serie de probabilidades iniciales ▪ ▪ =()π π 1,π π 2,...... ,π π K){displaystyle Pi =(pi _{1},pi _{2},dotspi ¿Qué? tales que π π i{displaystyle pi _{i} almacena la probabilidad de que x1=si{displaystyle x_{1}=s_{i}},
• a secuencia de observaciones Y=()Sí.1,Sí.2,...... ,Sí.T){displaystyle Y=(y_{1},y_{2},ldotsy_{T} tales que Sí.t=oi{displaystyle Y... si la observación a tiempo t{displaystyle t} es oi{displaystyle O...,
• matriz de transición A{displaystyle A} de tamaño K× × K{displaystyle Ktimes K} tales que Aij{displaystyle A_{ij} almacena la probabilidad de transición de tránsito del estado si{displaystyle S_{i} al estado sj{displaystyle s_{j},
• matriz de emisiones B{displaystyle B} de tamaño K× × N{displaystyle Ktimes N} tales que Bij{displaystyle B_{ij} almacena la probabilidad de observar oj{displaystyle o_{j} del estado si{displaystyle S_{i}.

Producto

• La secuencia de estado oculta más probable X=()x1,x2,...... ,xT){displaystyle X=(x_{1},x_{2},ldotsx_{T}}

función VITERBI    () O , S , ▪ ▪  , Y , A , B ) : X   {displaystyle (O,S,PiY,A,B):X}  para cada estado     i = 1 , 2 , ......  , K   {displaystyle i=1,2,ldotsK}  do      T  1   [ i , 1 ] ← ←   π π   i   ⋅ ⋅   B  i  Sí.  1       {displaystyle T_{1}[i,1]leftarrow pi ¿Qué? B_{iy_{1}}       T  2   [ i , 1 ] ← ←  0   {displaystyle T_{2}[i,1]leftarrow 0}  final for para cada observación     j = 2 , 3 , ......  , T   {displaystyle j=2,3,ldotsT}  do para cada estado     i = 1 , 2 , ......  , K   {displaystyle i=1,2,ldotsK}  do      T  1   [ i , j ] ← ←   max  k    ()  T  1   [ k , j − −  1 ] ⋅ ⋅   A  k i   ⋅ ⋅   B  i  Sí.  j     )    {displaystyle T_{1}[i,j]gets max _{k}{(T_{1}[k,j-1]cdot A_{ki}cdot B_{iy_{j}}}}       T  2   [ i , j ] ← ←  arg ⁡ ⁡   max  k    ()  T  1   [ k , j − −  1 ] ⋅ ⋅   A  k i   ⋅ ⋅   B  i  Sí.  j     )    {displaystyle T_{2}[i,j]gets arg max _{k}{(T_{1}[k,j-1]cdot A_{ki}cdot B_{iy_{j}}}}  final for final for      z  T   ← ←  arg ⁡ ⁡   max  k    ()  T  1   [ k , T ] )    {displaystyle z_{T}gets arg max _{k}{(T_{1}[k,T]}}       x  T   ← ←   s   z  T       {displaystyle x_{T}leftarrow S_{z_{T}}  para     j = T , T − −  1 , ......  , 2   {displaystyle J=T,T-1,ldots2}  do      z  j − −  1   ← ←   T  2   [  z  j   , j ]   {displaystyle z_{j-1}leftarrow T_{2} [z_{j},j]       x  j − −  1   ← ←   s   z  j − −  1       {displaystyle x_{j-1}leftarrow S_{z_{j-1}}  final for retorno     X   {displaystyle X} función final

Reformulado en un sucinto casi-Python:

función viterbi    () O , S , ▪ ▪  , T m , E m ) : b e s t ¿Qué? ¿Qué?  p a t h   Mejor.  Tm: matriz de transición Em: matriz de emisiones
     t r e l l i s ← ←  m a t r i x () l e n g t h () S ) , l e n g t h () O ) )   {displaystyle trellisleftarrow matriz(length(S),length(O)}  Mantener la probabilidad de cada estado dada cada observación
     p o i n t e r s ← ←  m a t r i x () l e n g t h () S ) , l e n g t h () O ) )   {displaystyle pointersleftarrow matriz(length(S),length(O)}  Mantener el backpointer al mejor estado anterior
 para s dentro     r a n g e () l e n g t h () S ) )   {displaystyle range(length(S)} : Determinar la probabilidad de cada estado oculto a la vez 0...
     t r e l l i s [ s , 0 ] ← ←  ▪ ▪  [ s ] ⋅ ⋅  E m [ s , O [ 0 ] ]   {displaystyle trellis[s,0]leftarrow Pi [s]cdot Em[s,O[0]}  para o dentro     r a n g e () 1 , l e n g t h () O ) )   {displaystyle range(1,length(O)} :...y después, rastreando el estado previo más probable de cada estado, k
 para s dentro     r a n g e () l e n g t h () S ) )   {displaystyle range(length(S)} :
     k ← ←  arg ⁡ ⁡  max () t r e l l i s [ k , o − −  1 ] ⋅ ⋅  T m [ k , s ] ⋅ ⋅  E m [ s , o ]    f o r    k    i n    r a n g e () l e n g t h () S ) ) )   {displaystyle kleftarrow arg max(trellis[k,o-1]cdot Tm[k,s]cdot Em[s,o] {fnMitsf {f}\cH00} range(length(S))}}      t r e l l i s [ s , o ] ← ←  t r e l l i s [ k , o − −  1 ] ⋅ ⋅  T m [ k , s ] ⋅ ⋅  E m [ s , o ]   {displaystyle trellis[s,o]leftarrow trellis[k,o-1]cdot Tm[k,s]cdot Em[s,o]      p o i n t e r s [ s , o ] ← ←  k   {displaystyle pointers[s,o]leftarrow k}      b e s t ¿Qué? ¿Qué?  p a t h ← ←  l i s t () )   {displaystyle best_pathleftarrow list()}      k ← ←  arg ⁡ ⁡  max () t r e l l i s [ k , l e n g t h () O ) − −  1 ]    f o r    k    i n    r a n g e () l e n g t h () S ) ) )   {displaystyle kleftarrow arg max(trellis[k,length(O)-1] {fnMitsf {f}\cH00} range(length(S))}}  Encontrar k del mejor estado final
 para o dentro     r a n g e () l e n g t h () O ) − −  1 , − −  1 , − −  1 )   {displaystyle range(length(O)-1,-1,-1)} : Backtrack de última observación
     b e s t ¿Qué? ¿Qué?  p a t h . i n s e r t () 0 , S [ k ] )   {displaystyle best_path.insert(0,S[k]}  Insertar el estado anterior en la ruta más probable
     k ← ←  p o i n t e r s [ k , o ]   {displaystyle kleftarrow pointers[k,o]}  Use backpointer para encontrar el mejor estado anterior
 retorno     b e s t ¿Qué? ¿Qué?  p a t h   {displaystyle best_path} 

Explicación

Supongamos que nos dan un modelo oculto de Markov (HMM) con espacio estatal S{displaystyle S., probabilidades iniciales π π i{displaystyle pi _{i} de estar en estado i{displaystyle i} y probabilidades de transición ai,j{displaystyle a_{i,j} de transición del Estado i{displaystyle i} al estado j{displaystyle j}. Digamos que observamos productos Sí.1,...... ,Sí.T{displaystyle Y.... La secuencia de estado más probable x1,...... ,xT{displaystyle x_{1},dotsx_{T} que produce las observaciones se da por las relaciones de recurrencia

V1,k=P()Sí.1Silenciok)⋅ ⋅ π π k,Vt,k=maxx▪ ▪ S()P()Sí.tSilenciok)⋅ ⋅ ax,k⋅ ⋅ Vt− − 1,x).{displaystyle {begin{aligned}V_{1,k} {mathrm {} {big {big (}y_{1} ¦\ k{big)}cdot pi _{k},V_{t,k} {=max _{xin S}left(mathrm {P} {big (}y_{t} Н k{big)}cdot a_{x,k}cdot V_{t-1,x}right)end{aligned}}}

Aquí. Vt,k{displaystyle V_{t,k} es la probabilidad de la secuencia estatal más probable P()x1,...... ,xt,Sí.1,...... ,Sí.t){displaystyle mathrm {big (}x_{1},dotsx_{t},y_{1},dotsy_{t}{big)}} responsable de la primera t{displaystyle t} observaciones que tienen k{displaystyle k} como su estado final. El camino de Viterbi se puede recuperar salvando los punteros traseros que recuerdan qué estado x{displaystyle x} fue utilizado en la segunda ecuación. Vamos Ptr()k,t){displaystyle mathrm {Ptr} (k,t)} ser la función que devuelve el valor x{displaystyle x} us to compute Vt,k{displaystyle V_{t,k} si 1}" xmlns="http://www.w3.org/1998/Math/MathML">t■1{displaystyle t título1}1" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/730f3de856e6f8850f89a9b990cfc7f7ba7c28bf" style="vertical-align: -0.338ex; width:5.101ex; height:2.176ex;"/>, o k{displaystyle k} si t=1{displaystyle t=1}. Entonces...

xT=arg⁡ ⁡ maxx▪ ▪ S()VT,x),xt− − 1=Ptr()xt,t).{displaystyle {begin{aligned}x_{T} limit=arg max _{xin S}(V_{T,x}),x_{t-1} {=mathrm {Ptr} (x_{t},t).end{aligned}}}

Aquí estamos usando la definición estándar de arg max.

La complejidad de esta aplicación es O()T× × SilencioSSilencio2){displaystyle O(Ttimes left sometida{S}right sometida^{2}. Existe una mejor estimación si el máximo en el bucle interno se encuentra en cambio por la iteración sólo sobre estados que se vinculan directamente con el estado actual (es decir, hay un borde de k{displaystyle k} a j{displaystyle j}). Luego usando el análisis amortizado se puede demostrar que la complejidad es O()T× × ()SilencioSSilencio+SilencioESilencio)){displaystyle O(Ttimes (left WordPress{S}rightprehensión+left sometida{E}right sometida)}, donde E{displaystyle E} es el número de bordes en el 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 cada uno tiene 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 los pacientes opera como una cadena de Markov discreta. Hay dos estados, "Saludable" y "Fiebre", pero el médico no puede observarlos directamente; están ocultos del médico. Cada día, existe una cierta posibilidad de que un paciente le diga al médico 'Me siento normal', 'Tengo frío' o 'Me siento mareado', dependiendo del estado de salud del paciente.

Las observaciones (normal, frío, mareado) junto con un estado oculto (sano, fiebre) forman un modelo oculto de Markov (HMM), y se pueden representar como sigue en el lenguaje de programación Python:

obs = ()"normal", "frío", "dizzy")estados = ()"Healthy", "Nunca")start_p = {}"Healthy": 0.6, "Nunca": 0,4}trans_p = {} "Healthy": {}"Healthy": 0.7, "Nunca": 0.3} "Nunca": {}"Healthy": 0,4, "Nunca": 0.6}}emit_p = {} "Healthy": {}"normal": 0.5, "frío": 0,4, "dizzy": 0.1} "Nunca": {}"normal": 0.1, "frío": 0.3, "dizzy": 0.6}}

En este fragmento de código, start_p representa la creencia del médico acerca del estado en el que se encuentra el HMM cuando el paciente visita por primera vez (todo lo que el médico 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 {'Saludable': 0.57, 'Fiebre': 0.43}. La transition_p representa el cambio de la condición de salud en la cadena de Markov subyacente. En este ejemplo, un paciente que hoy está sano tiene solo un 30 % de posibilidades de tener fiebre mañana. El emit_p representa la probabilidad de que cada posible observación (normal, resfriado o mareado) sea dada la condición subyacente (sano o con fiebre). Un paciente sano tiene un 50% de posibilidades de sentirse normal; quien tiene fiebre tiene un 60% de posibilidades de sentirse mareado.

Representación gráfica del HMM dado

Un paciente visita tres días seguidos y el médico descubre que el paciente se siente normal el primer día, frío el segundo día y mareado el tercero. 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 dentro estados: V[0] [st] = {}"prob": start_p[st] * emit_p[st] [obs[0]] "prev": Ninguno} # Run Viterbi when t # 0 para t dentro rango()1, Len()obs) V.apéndice({}) para st dentro estados: max_tr_prob = V[t - 1] [estados[0]] ["prob"] * trans_p[estados[0]] [st] * emit_p[st] [obs[t]] prev_st_selected = estados[0] para prev_st dentro estados[1: tr_prob = V[t - 1] [prev_st] ["prob"] * trans_p[prev_st] [st] * emit_p[st] [obs[t]] si tr_prob ■ max_tr_prob: max_tr_prob = tr_prob prev_st_selected = prev_st max_prob = max_tr_prob V[t] [st] = {}"prob": max_prob, "prev": prev_st_selected} para línea dentro dptable()V): impresión()línea) opt = [] max_prob = 0,0 best_st = Ninguno # Obtenga el estado más probable y su retroceso para st, datos dentro V[-1].Temas(): si datos["prob"] ■ max_prob: max_prob = datos["prob"] best_st = st opt.apéndice()best_st) anterior = best_st # Siga la pista trasera hasta la primera observación para t dentro rango()Len()V) - 2, -1, -1): opt.insertar()0, V[t + 1] [anterior] ["prev"]) anterior = V[t + 1] [anterior] ["prev"] impresión ()"Los pasos de los estados son " + ".Únase()opt) + " con mayor probabilidad de %s" % max_prob)def dptable()V): # Imprimir una tabla de pasos del diccionario rendimiento " * 5 + ".Únase()"%3d" % i) para i dentro rango()Len()V)) para estado dentro V[0]: rendimiento "%.7: % estado + ".Únase()"%.7" % ()"%" % v[estado] ["prob"]) para v dentro V)

La función viterbi toma los siguientes argumentos: obs es la secuencia de observaciones, p. ['normal', 'resfriado', 'mareado']; 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á definido para todos los estados i,j.

En el ejemplo en ejecución, el algoritmo de avance/Viterbi se usa de la siguiente manera:

viterbi()obs, estados, start_p, trans_p, emit_p)

La salida del script es

$ Python viterbi_example.py
 0 1 2Salud: 0,30000 0,08400 0,00588fiebre: 0,04000 0,02700 0,01512Los pasos de los estados son Fiebre Saludable con mayor probabilidad de 0.01512

Esto revela que las observaciones ['normal', 'frío', 'mareado'] probablemente fueron generadas por estados ['Saludable', 'Saludable', 'Fiebre']. En otras palabras, dadas las actividades observadas, lo más probable es que el paciente haya estado sano el primer día y también el segundo (a pesar de sentir frío ese día), y que solo haya tenido fiebre el tercer día.

El funcionamiento del algoritmo de Viterbi se puede visualizar mediante un diagrama de enrejado El camino de Viterbi es esencialmente el más corto camino a través de este enrejado.

Algoritmo Viterbi de salida suave

El algoritmo Viterbi de salida suave (SOVA) es una variante del algoritmo Viterbi clásico.

SOVA se diferencia del clásico algoritmo 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 confiabilidad de la decisión.

El primer paso en el SOVA es la selección de la ruta del sobreviviente, pasando por un único nodo en cada instante de tiempo, t. Dado que cada nodo tiene 2 ramas que convergen en él (se elige una rama para formar la Ruta del superviviente y se descarta la otra), la diferencia en las métricas de la rama (o costo) entre las ramas elegidas y descartadas indicar la cantidad de error en la elección.

Este costo se acumula a lo largo de toda la ventana deslizante (normalmente equivale a al menos cinco longitudes de restricción), para indicar la medida de salida blanda de fiabilidad de la decisión de bit duro del algoritmo de Viterbi.

Referencias generales

• Viterbi AJ (abril de 1967). "Error se une a los códigos convolutivos y a un algoritmo de decodificación asintomáticamente óptimo". Transacciones de IEEE sobre información Teoría. 13 (2): 260–269. doi:10.1109/TIT.1967.1054010. (nota: el algoritmo de decodificación Viterbi se describe en la sección IV.) Suscripción requerida.
• Feldman J, Abou-Faycal I, Frigo M (2002). "Un rápido decodificador de máxima probabilidad para códigos conversos". Proceedings IEEE 56a Conferencia de Tecnología Vehicular. Vehicular Technology ConferenceVol. 1. págs. 371 a 375. CiteSeerX10.1.1.114.1314. doi:10.1109/VETECF.2002.1040367. ISBN 978-0-7803-7467-6. S2CID 9783963.
• Forney GD (marzo de 1973). "El algoritmo Viterbi". Proceedings of the IEEE. 61 (3): 268–278. doi:10.1109/PROC.1973.9030. Suscripción requerida.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 16.2. Decodificación Viterbi". Recetas numéricas: El arte de la computación científica (3a edición). 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 discursos". Proceedings of the IEEE. 77 (2): 257–286. CiteSeerX10.1.1.381.3454. doi:10.1109/5.18626. S2CID 13618539. (Describe el algoritmo delantero y el algoritmo Viterbi para HMMs).
• Shinghal, R. y Godfried T. Toussaint, "Experimentos en reconocimiento de texto con el algoritmo modificado de Viterbi," Transacciones IEEE en Análisis de Patrones e Inteligencia de Máquinas, Vol. PAMI-l, abril de 1979, págs. 184 a 193.
• Shinghal, R. y Godfried T. Toussaint, "La sensibilidad del algoritmo modificado de Viterbi a las estadísticas de origen," Transacciones IEEE en Análisis de Patrones e Inteligencia de Máquinas, vol. PAMI-2, marzo de 1980, pp. 181–185.