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 = o₁,… , o_t) 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 θ₁(i) = π_i × b_i (o₁), esta obtiene la primera variable directa (α) que se calcula multiplicando la probabilidad inicial del estado π_i por la probabilidad b de la observación o₁ (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) Probabilidad (PI) del estado (1) Laboral × Probabilidad Ir de Tiendas → 0,70 * 0,10 = 0,070
2.   α₁(2) Probabilidad (PI) del estado (2) Festivo × Probabilidad Ir de Tiendas → 0,30 * 0,55 = 0,165

 

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 o₂ (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 o₂ (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.

 

 

 

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.}

 

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