Algoritmo de avance-retroceso

Introducción

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 $O=(o_1,o_2,\dots ,o_T)$ dado un modelo $\mu =(\pi ,A,B)$. El objetivo es por tanto calcular eficientemente $P(O|\mu )$.

Probabilidad de una secuencia $S$ de estados

Supongamos una secuencia de estados $S=(q_1,q_2,\dots ,q_T)$. La probabilidad de esta secuencia es:

$P(S|\mu )={\pi }_{q_1}{a}_{q_1{q}_2}{a}_{q_2{q}_3}\dots a_{q_{T-1}{q}_T}$

Probabilidad de una secuencia de observables $O$ dada una secuencia de estados $S$

La probabilidad de observar $O=(o_1,o_2,\dots ,o_T)$ cuando se da precisamente esta secuencia de estados $S$ es:

$P(O|S,\mu )=\prod _{t=1}^{T}P(o_t|q_t,\mu )$

Cada $P(o_t|q_t,\mu )$ corresponde con el valor de $b_{q_t}(o_t)$

Probabilidad de una secuencia de observables $O$ dado un modelo $\mu$

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

$P(O|\mu )={\sum }^{S}P(S|\mu )P(O|S,\mu )$

El cálculo de $P(O|\mu )$ tal y como se muestra es impracticable; sólo para $10$ estados y $10$ observaciones sería necesario realizar del orden de $10^{11}$ 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

Cálculo de ${\alpha }_t(i)$

Consideramos la variable ${\alpha }_t(i)$ como:

${\alpha }_t(i)=P(o_1,o_2,\dots ,o_t,q_t=i|\mu )$

Dado el modelo $\mu$, ${\alpha }_t(i)$ es la probabilidad de observar $o_1,o_2,\dots ,o_t$ y estar en el instante de tiempo $t$ en el estado $i$.

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

Inicialización

${\alpha }_1(i)={\pi }_i{b}_i(o_1),$

$1\le i\le N$

Recurrencia

${\alpha }_{t+1}(j)=\left[\sum _{i=1}^N{\alpha }_t(i)a_{ij}\right]b_j(o_{t+1})$

$t=1,2,\dots ,T-1$, $1\le j\le N$

Terminación

$P(O|\mu )=\sum _{i=1}^N{\alpha }_T(i)$

Ejemplo de cálculo de ${\alpha }_4(3)$

El esquema muestra los estados y probabilidades necesarias para el cálculo de ${\alpha }_4(3)$:

${\alpha }_4(3)=\left[\sum _{i=1}^5{\alpha }_3(i)a_{i3}\right]b_3(o_4)$

Cálculo hacia atrás

Cálculo de ${\beta }_t(i)$

Consideramos la variable ${\beta }_t(i)$.

${\beta }_t(i)=P(o_{t+1}{o}_{t+2},\dots ,o_T|q_t=i,\mu )$

Dado el modelo $\mu$, ${\beta }_t(i)$ es la probabilidad de la secuencia de observación desde el instante de tiempo $t+1$ hasta el final, cuando el estado en el instante de tiempo $t$ es $i$.

Inicialización

${\beta }_T(i)=1$,

$1\le i\le N$

Recurrencia

${\beta }_t(i)=\sum _{j=1}^N{a}_{ij}{\beta }_{t+1}(j)b_j(o_{t+1})$,

$t=T-1,T-2,\dots ,1$, $1\le i\le N$

Terminación

$P(O|\mu )=\sum _{i=1}^N{\beta }_1(i){\pi }_i{b}_i(o_1)$

Ejemplo de cálculo de ${\beta }_2(3)$

El esquema muestra los estados y probabilidades necesarios para el cálculo de ${\beta }_2(3)$ para un modelo de 5 estados y una secuencia de observaciones de longitud 5.

${\beta }_2(3)=\sum _{j=1}^5{a}_{3j}{\beta }_3(j)b_j(o_3),$

Complejidad computacional

Tanto el procedimiento hacia adelante como el algoritmo backward, requieren del orden de $N^{2}T$ operaciones; muy inferior a $2T{N}^T-1$ operaciones ($N$ es el número de estados y $T$ es la longitud de la secuencia de observaciones) que son necesarias si se calcula $P(O,S|\mu )$ para todas las posibles secuencias $S$ del modelo.

El cálculo de los ${\beta }_t(i)$ servirán - junto a los ${\alpha }_t(i)$ - para contestar las otras dos preguntas fundamentales de los Modelos Ocultos de Márkov:

• ¿Cuál es la secuencia óptima $S$ de estados dado una secuencia de observaciones $O$? (algoritmo de Viterbi)
• Dada una secuencia de observaciones $O=(o_1,o_2,\dots ,o_T)$, ¿cómo podemos estimar los parámetros del modelo $\mu =(\pi ,A,B)$ para maximizar $P(O|\mu )$. En este caso el objetivo es encontrar el modelo que mejor explica la secuencia observada (algoritmo de Baum-Welch).

Véase también

• Modelos Ocultos de Márkov
• Algoritmo de Viterbi
• Algoritmo de Baum-Welch