señales

CODIFICACION DE VITERBI

El algoritmo de Viterbi permite encontrar las secuencia de estados más probable en un Modelo oculto de Markov (MOM),

S=(q_{1},q_{2}, ldots, q_{T})
, a partir de unaobservación

O=(o_{1},o_{2},ldots, o_{T})
, es decir, obtiene la secuencia óptima que mejor explica la secuencia de observaciones.
Consideremos la variable δt(i) que se define como:delta_{t}{(i)} = max_{q_{1},q_{2},ldots,q_{t-1}}{P(q_{1},q_{2},ldots,q_{t}=i,o_{1},o_{2}, ldots, o_{t}|mu)}

δt(i) es la probabilidad del mejor camino hasta el estado i habiendo visto las t primerasobservaciones. Esta función se calcula para todos los estados e instantes de tiempo.

delta_{t+1}{(i)} = biggl[max_{1 leq i leq N}{delta_{t}(a_{ij})}biggr] b_{j}(o_{t+1})

Puesto que el objetivo es obtenerlas secuencia de estados más probable, será necesario almacenar el argumento que hace máxima la ecuación anterior en cada instante de tiempo t y para cada estado j y para ello utilizamos la variablevarphi_{t}{(j)}
.
A continuación se detalla el proceso completo utilizando las funciones δ y

varphi
.

Algoritmo
Inicialización
δ1(i) = πibi(o1)
donde

1 leq i leq N


Recursióndelta_{t+1}{(i)} = biggl[max_{1 leq i leq N}{delta_{i}(a_{ij})}biggr] b_{j}(o_{t+1})
,
donde:

t=1,2,ldots,T-1
,

1 leq j leq N



varphi_{t+1}{(j)}=argmax_{1 leq i leqN}{delta_{t}{(i)a_{ij}}}
,
donde:

t=1,2,ldots,T-1
,

1 leq j leq N


Terminación

q_{T}^{*} = argmax_{1 leq i leq N}{delta_{T}{(i)}}


Reconstrucción de la secuencia de estados más probableq_{t}^{*}=varphi_{t+1}{(q_{t+1}^{*})}
,
donde:

t=T-1,T-2,ldots,1

Algunos de los cálculos del algoritmo de Viterbi recuerdan a los del algoritmo forward necesario para calcular eficientemente la probabilidadde una secuencia de observables. Una de las diferencias es la incorporación de la función argmax (en lugar de sumar las probabilidades) para calcular la secuencia de estados más probable.
Ejemplo...