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},\ldots ,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 )=\displaystyle \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 )=\displaystyle \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},\ldots ,o_{t},q_{t}=i|\mu )$

Dado el modelo $\mu$, $\alpha _{t}(i)$ es la probabilidad de observar $o_{1},o_{2},\ldots ,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\leq i\leq N$

Recurrencia

$\alpha _{t+1}(j)={\biggl [}\displaystyle \sum _{i=1}^{N}{\alpha _{t}(i)a_{ij}}{\biggr ]}b_{j}(o_{t+1})$

$t=1,2,\ldots ,T-1$, $1\leq j\leq N$

Terminación

$P(O|\mu )=\displaystyle \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)={\biggl [}\displaystyle \sum _{i=1}^{5}{\alpha _{3}(i)a_{i3}}{\biggr ]}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},\ldots ,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\leq i\leq N$

Recurrencia

$\beta _{t}(i)=\displaystyle \sum _{j=1}^{N}{a_{ij}\beta _{t+1}(j)b_{j}(o_{t+1})}$,

$t=T-1,T-2,\ldots ,1$, $1\leq i\leq N$

Terminación

$P(O|\mu )=\displaystyle \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)=\displaystyle \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 $2TN^{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},\ldots ,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

Referencias

• Datos: Q4909