Algoritmo de Viterbi

El algoritmo de Viterbi es un algoritmo de programación dinámica que permite hallar la secuencia más probable de estados ocultos (el llamado camino de Viterbi) que produce una secuencia observada de sucesos, especialmente en el contexto de fuentes de información de Márkov y modelos ocultos de Márkov.

Se aplica de forma general en la descodificación de códigos convolucionales usados en redes de telefonía celular digital GSM y CDMA, módems de líneas conmutadas, satélites, comunicaciones espaciales y redes inalámbricas IEEE 802.11. También se usa en reconocimiento del habla, síntesis de habla, diarización, búsqueda de palabras clave, lingüística computacional y bioinformática.

El algoritmo de Viterbi permite encontrar las secuencias de estados más probable en un Modelo oculto de Márkov (MOM), ${displaystyle S=(q_{1},q_{2},ldots ,q_{T})}$, a partir de una observación ${displaystyle O=(o_{1},o_{2},ldots ,o_{T})}$, es decir, obtiene la secuencia óptima que mejor explica la secuencia de observaciones.

Consideremos la variable ${displaystyle delta _{t}{(i)}}$ que se define como:

${displaystyle 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 )}}$

${displaystyle delta _{t}{(i)}}$ es la probabilidad del mejor camino hasta el estado ${displaystyle i}$ habiendo visto las ${displaystyle t}$ primeras observaciones. Esta función se calcula para todos los estados e instantes de tiempo.

${displaystyle delta _{t+1}{(j)}={iggl [}max _{1leq ileq N}{delta _{t}{(i)(a_{ij})}}{iggr ]}b_{j}(o_{t+1})}$

Puesto que el objetivo es obtener las secuencia de estados más probable, será necesario almacenar el argumento que hace máxima la ecuación anterior en cada instante de tiempo ${displaystyle t}$ y para cada estado ${displaystyle j}$ y para ello utilizamos la variable ${displaystyle varphi _{t}{(j)}}$.

A continuación se detalla el proceso completo utilizando las funciones ${displaystyle delta }$ y ${displaystyle varphi }$.

${displaystyle delta _{1}(i)=pi _{i}b_{i}(o_{1})}$

donde ${displaystyle 1leq ileq N}$

${displaystyle delta _{t+1}{(j)}={iggl [}max _{1leq ileq N}{delta _{t}{(i)}a_{ij}}{iggr ]}b_{j}(o_{t+1})}$,

donde:

${displaystyle t=1,2,ldots ,T-1}$, ${displaystyle 1leq jleq N}$ ${displaystyle varphi _{t+1}{(j)}=arg max _{1leq ileq N}{delta _{t}{(i)a_{ij}}}}$,

donde:

${displaystyle t=1,2,ldots ,T-1}$, ${displaystyle 1leq jleq N}$

${displaystyle q_{T}^{*}=arg max _{1leq ileq N}{delta _{T}{(i)}}}$

${displaystyle q_{t}^{*}=varphi _{t+1}{(q_{t+1}^{*})}}$,

donde:

${displaystyle 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 probabilidad de una secuencia de observables. Una de las diferencias es la incorporación de la función ${displaystyle arg max }$ (en lugar de sumar las probabilidades) para calcular la secuencia de estados más probable.

Ejemplo de secuencia de estados más probable

La figura muestra un ejemplo de secuencia de estados más probable en un Modelo Oculto de Márkov de 5 estados dada una secuencia de observaciones de longitud 5.

Muy usado para reconocimiento de voz, biología molecular, fonemas, palabras, codificadores entre otros. A cada secuencia de estados le corresponde una secuencia de etiquetas (o labels) de clasificación, es decir, palabras, caracteres, fonemas, sufijos. Dada una secuencia observada, se deduce la más probable secuencia de estados.

Una de las aplicaciones del algoritmo de Viterbi es en el área de procesamiento del lenguaje natural, más concretamente en el proceso de desambiguación léxica categorial.

En este caso particular, los elementos de un Modelo Oculto de Márkov serían los siguientes:

La figura siguiente muestra un ejemplo de etiquetado gramatical para la oración "Coto privado de caza"

En él, los observables son la secuencia de palabras de la oración. Se puede observar como para cada palabra se contempla sólo un conjunto limitado de posibles categorías gramaticales (caza puede ser o nombre o verbo). Este es debido a que la probabilidad de pertenencia de determinadas palabras a una categoría gramatical es nula (como la probabilidad de que la palabra caza sea adverbio). Esto simplifica enormemente los cálculos en el modelo.

Otros dos problemas que es importante saber resolver para utilizar los MOM son: