Algoritmo de avance-retroceso

algoritmo de Estadística

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 probabilidad 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  :

 

 

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.

 

 

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

Referencias

editar