Algoritmo de avance-retroceso

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

Introducción[editar]

Uno de los problemas básicos de los Modelos Ocultos de Márkov es el cálculo de la probabilidad de una secuencia de observables dado un modelo . El objetivo es por tanto calcular eficientemente .

Probabilidad de una secuencia de estados

Supongamos una secuencia de estados . La probabildad de esta secuencia es:

Probabilidad de una secuencia de observables dada una secuencia de estados

La probabilidad de observar cuando se da precisamente esta secuencia de estados es:

Cada corresponde con el valor de

Probabilidad de una secuencia de observables dado un modelo

Por tanto, para obtener la probabilidad de una secuencia de observables dado un modelo , deberíamos calcular la probabilidad de para cada una de las secuencias posibles .

El cálculo de tal y como se muestra es impracticable; sólo para estados y observaciones sería necesario realizar del orden de operaciones. Para reducir esta complejidad se emplean estrategias de programación dinámica como los algoritmos forward y backward.

Se recomienda revisar la formalización habitual de un Modelo Oculto de Márkov para comprender cada uno de los elementos en la formulación de estos dos procedimientos.

Procedimiento hacia adelante[editar]

Cálculo de [editar]

Consideramos la variable como:

Dado el modelo , es la probabilidad de observar y estar en el instante de tiempo en el estado .

Cálculo hacia adelante de la probabilidad de una secuencia de observaciones.

Inicialización

Recurrencia

,

Terminación

Ejemplo de cálculo de [editar]

El esquema muestra los estados y probabilidades necesarias para el cálculo de :

Algoritmo forward

Cálculo hacia atrás[editar]

Cálculo de [editar]

Consideramos la variable .

Dado el modelo , es la probabilidad de la secuencia de observación desde el instante de tiempo hasta el final, cuando el estado en el instante de tiempo es .

Inicialización

,

Recurrencia

,

,

Terminación

Ejemplo de cálculo de [editar]

El esquema muestra los estados y probabilidades necesarios para el cálculo de para un modelo de 5 estados y una secuencia de observaciones de longitud 5.

Algoritmo backward

Complejidad computacional[editar]

Tanto el procedimiento hacia adelante como el algoritmo backward, requieren del orden de operaciones; muy inferior a operaciones ( es el número de estados y es la longitud de la secuencia de observaciones) que son necesarias si se calcula para todas las posibles secuencias del modelo.

El cálculo de los servirán - junto a los - para contestar las otras dos preguntas fundamentales de los Modelos Ocultos de Márkov:

  • ¿Cuál es la secuencia óptima de estados dado una secuencia de observaciones ? (algoritmo de Viterbi)
  • Dada una secuencia de observaciones , ¿cómo podemos estimar los parámetros del modelo para maximizar . En este caso el objetivo es encontrar el modelo que mejor explica la secuencia observada (algoritmo de Baum-Welch).

Véase también[editar]