Algoritmo de Viterbi


Algoritmo de Viterbi

Contenido

Introducción

El algoritmo de Viterbi permite encontrar las secuencias de estados más probable en un Modelo oculto de Márkov (MOM), S=(q_{1},q_{2}, \ldots, q_{T}), a partir de una observació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 primeras observaciones. 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 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 t y para cada estado j y para ello utilizamos la variable φt(j).

A continuación se detalla el proceso completo utilizando las funciones δ y φ.

Algoritmo

Inicialización

δ1(i) = πibi(o1)

donde 1 \leq i \leq N

Recursión

\delta_{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)}=\arg\max_{1 \leq i \leq N}{\delta_{t}{(i)a_{ij}}},

donde:

t=1,2,\ldots,T-1, 1 \leq j \leq N

Terminación

q_{T}^{*} = \arg\max_{1 \leq i \leq N}{\delta_{T}{(i)}}

Reconstrucción de la secuencia de estados más probable

q_{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 probabilidad de una secuencia de observables. Una de las diferencias es la incorporación de la función 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 un secuencia de observaciones de longitud 5.

Ejemplo de secuencia de estados más probable en un MOM

Aplicación del algoritmo de Viterbi

Desambiguación léxica categorial

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:

  • El conjunto Q de estados sería el conjunto de posibles etiquetas (categorías gramaticales) para las palabras.
  • El conjunto V de observables en cada uno de los estados corresponde con el conjunto de palabras distintas.
  • El conjunto A de probabilidades de transiciones entre estados sería la probabilidad de que una determinada categoría categorial siga a otra. Por ejemplo, la probabilidad de que la categoría nombre vaya detrás de la categoría determinante.
  • El conjunto B de probabilidades de las observaciones correspondería con la probabilidad de pertenencia de una palabra (un observable) a una determinada categoría. Por ejemplo, la probabilidad de que la palabra casa sea verbo, que será menor que la probabilidad de que esta misma palabra tenga la categoría gramatical nombre.

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

Etiquetado gramatical de una oración

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.

Otras preguntas fundamentales

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

  1. ¿Cuál es la probabilidad de una secuencia de observaciones O=(o_{1},o_{2},\ldots,o_{T}) dado un modelo μ = (π,A,B)? Es decir, ¿cómo podemos calcular de forma eficiente P(O | μ)?. Para esto se puede usar el algoritmo de avance-retroceso.
  2. Dada una secuencia de observaciones O=(o_{1},o_{2},\ldots,o_{T}), ¿cómo podemos estimar los parámetros del modelo μ = (π,A,B) para maximizar P(O | μ). En este caso el objetivo es encontrar el modelo que mejor explica la secuencia observada. Para esto se puede usar el algoritmo de Baum-Welch.

Véase también

Enlaces externos


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • Viterbi — puede hacer referencia a: Algoritmo de Viterbi, un algoritmo en procesado de señales. Andrew Viterbi, ingeniero italiano, inventor del algoritmo mencionado. Esta página de desambiguación cataloga artículos relacionados con el mismo título. Si… …   Wikipedia Español

  • Algoritmo de Baum-Welch — Contenido 1 Introducción 2 El algoritmo de Baum y Welch 2.1 Valores esperados 2.2 Reestimación …   Wikipedia Español

  • Algoritmo de avance-retroceso — Contenido 1 Introducción 2 Procedimiento hacia adelante 2.1 Cálculo de αt(i) 2.2 Ejemplo de cálculo de α4(3) …   Wikipedia Español

  • Andrew Viterbi — Nombre Andrea James Viterbi Nacimiento 9 …   Wikipedia Español

  • Turbo código — Los turbo códigos son una nueva clase de códigos de corrección de errores (FEC), que se introdujeron, junto con un algoritmo de decodificación. La importancia de los turbo códigos es que permiten una comunicación fiable y su eficiencia energética …   Wikipedia Español

  • Modelo oculto de Márkov — Ejemplo de transición de estados en un modelo oculto de Márkov x estados ocultos y salidas observables a probabilidades de transición b probabilidades de salida Un modelo oculto de Márkov o HMM (por sus siglas del inglés, Hidden Markov Model) es… …   Wikipedia Español

  • Internet por satélite — Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Puedes añadirlas así o avisar …   Wikipedia Español

  • Anexo:Episodios de Numb3rs — La siguiente es una lista de episodios de la serie norteamericana NUMB3RS. Contenido 1 Estrenos y Lanzamientos en DVD 2 Primera temporada (2005) 3 Segunda temporada (2005 2006) …   Wikipedia Español

  • Alineamiento múltiple de secuencias — Un alineamiento múltiple de secuencias (MSA, por sus siglas en inglés) es un alineamiento de tres o más secuencias biológicas, generalmente proteínas, ADN o ARN. En general, se asume que el conjunto de secuencias de consulta que se ingresa como… …   Wikipedia Español

  • Episodios de Numb3rs — Anexo:Episodios de Numb3rs Saltar a navegación, búsqueda La siguiente es una lista de episodios de la serie norteamericana NUMB3RS. Contenido 1 Estrenos y Lanzamientos en DVD 2 Primera temporada (2005) 3 Segunda temporada ( …   Wikipedia Español