Algoritmo de Avance

El algoritmo Forward o de Avance, aplicado en un modelo oculto de Markov (HMM), se utiliza para obtener la probabilidad P (O | Φ) de cierta secuencia de observación (O = o1,… , ot) derivada del modelo Φ = (A, B, π). El algoritmo fue propueso por Leonard E. Baum y J. Alonzo Egon en 1.967 y mejorado por Baum y G. Roger Sell en 1.968. A este respecto, existe una publicación de 1.966, donde R.W. Chang y  J.C. Hancock adelantan el algoritmo, también en versión retroceso (Forward-Backward).

 

Continúo con el ejemplo de HMM tomando la secuencia de observación (123) – (Tiendas, Dormir, Familia).

 

Comenzamos con la ecuación θ1(i) = πi × bi (o1), esta obtiene la primera variable directa (α) que se calcula multiplicando la probabilidad inicial del estado πi por la probabilidad b de la observación o1 (Ir de Tiendas) de ese estado en el tiempo 1. Todo ello se realiza por cada uno de los (E) estados posibles (N).

 

En el ejemplo (Paso 1):

 

  1.   α1(1) Probabilidad (PI) del estado (1) Laboral × Probabilidad Ir de Tiendas → 0,70 * 0,10 = 0,070
  2.   α1(2) Probabilidad (PI) del estado (2) Festivo × Probabilidad Ir de Tiendas → 0,30 * 0,55 = 0,165
Ejemplo calculo algoritmo HMM Forward - Avance. Paso 1
Paso 1 algoritmo Forward – Avance.

 

Con estos valores comienza verdaderamente el algoritmo de Avance.

Tomamos el valor de la probabilidad del estado Laboral en el tiempo 1 calculada anteriormente 0,070, esta es multiplicada por la probabilidad a del estado Laboral (1) = 0,85 y por la probabilidad b de la observación o2 (Dormir) = 0,70.

0,070 * 0,85 *  0,7 = 0,04165

 

Cambiamos y tomamos el valor de la probabilidad del estado Festivo en el tiempo 1 calculada anteriormente (0,165) y se multiplica por probabilidad a del estado Festivo (1) = 0,15 y por la probabilidad b de la observación o2 (Dormir) = 0,70.

0,165 * 0,75 *  0,7 = 0,0866

 

Ahora sumamos los dos resultados

0,4165 + 0,0866 = 0,128275

 

Ya tenemos la probabilidad que se corresponde al estado laboral en la observación Dormir.

 

Los cálculos anteriores se repetirían según el gráfico del ejemplo hasta llegar a la última observación, donde sumaríamos las probabilidades correspondientes a los estados en esa observación, obteniendo la probabilidad de la secuencia.

 

Explicación Algoritmo Forward - Avance para HMM Hide Markov Model
Gráfico Algoritmo Avance para HMM Hide Markov Model

 

 

Aquí el algoritmo en lenguaje Java con todas las secuencias de observación posibles del ejemplo (permutaciones ordinarias).

🔴 Pulsar sobre el gráfico para ampliar.

 

HMM Modelo oculto de Markov algoritmo-Forward
HMM Modelo oculto de Markov algoritmo-Forward en Java

Existen distintas versiones de este algoritmo, una de ellas es el algoritmo directo híbrido HFA (Hybrid Forward Algorithm), utilizado en la construcción de redes neuronales de función de base radial, RBF (Radial Basis Function).

 

El seudocódigo del algoritmo por: scholar.harvard.edu