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 μ = (π,A,B). El objetivo es por tanto calcular eficientemente P(O | μ).

Probabilidad de una secuencia S de estados

Supongamos una secuencia de estado $S = (q_1,q_2, \dots, q_T)$. La probabildad 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,μ) corresponde con el valor de $b_{q_t}(o_t)$

Probabilidad de una secuencia de observables O dado un modelo μ

Por tanto, para obtener la probabilidad de una secuencia O de observables dado un modelo μ, 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 | μ) tal y como se muestra es impracticable; sólo para 10 estados y 10 observaciones sería necesario realizar del orden de 10¹¹ 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 α_t(i)

Consideramos la variable α_t(i) como:

$\alpha_{t}(i)=P(o_{1},o_{2},\ldots,o_{t},q_{t}=i|\mu)$

Dado el modelo μ, α_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

α₁(i) = π_ib_i(o₁),

$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 α₄(3)

El esquema muestra los estados y probabilidades necesarias para el cálculo de α₄(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 β_t(i)

Consideramos la variable β_t(i).

$\beta_{t}(i)=P(o_{t+1}o_{t+2},\ldots,o_{T}|q_{t}=i,\mu)$

Dado el modelo μ, β_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

β_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 β₂(3)

El esquema muestra los estados y probabilidades necesarios para el cálculo de β₂(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²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 | μ) para todas las posibles secuencias S del modelo.

El cálculo de los β_t(i) servirán - junto a los α_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 μ = (π,A,B) para maximizar P(O | μ). 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