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 ${\displaystyle O=(o_{1},o_{2},\ldots ,o_{T})}$ dado un modelo ${\displaystyle \mu =(\pi ,A,B)}$. El objetivo es por tanto calcular eficientemente ${\displaystyle P(O|\mu )}$.

Probabilidad de una secuencia ${\displaystyle S}$ de estados

Supongamos una secuencia de estados ${\displaystyle S=(q_{1},q_{2},\dots ,q_{T})}$. La probabilidad de esta secuencia es:

${\displaystyle 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 ${\displaystyle O}$ dada una secuencia de estados ${\displaystyle S}$

La probabilidad de observar ${\displaystyle O=(o_{1},o_{2},\dots ,o_{T})}$ cuando se da precisamente esta secuencia de estados ${\displaystyle S}$ es:

${\displaystyle P(O|S,\mu )=\displaystyle \prod _{t=1}^{T}{P(o_{t}|q_{t},\mu )}}$

Cada ${\displaystyle P(o_{t}|q_{t},\mu )}$ corresponde con el valor de ${\displaystyle b_{q_{t}}(o_{t})}$

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

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

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

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

Consideramos la variable ${\displaystyle \alpha _{t}(i)}$ como:

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

Dado el modelo ${\displaystyle \mu }$, ${\displaystyle \alpha _{t}(i)}$ es la probabilidad de observar ${\displaystyle o_{1},o_{2},\ldots ,o_{t}}$ y estar en el instante de tiempo ${\displaystyle t}$ en el estado ${\displaystyle i}$.

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

Inicialización

${\displaystyle \alpha _{1}(i)=\pi _{i}b_{i}(o_{1}),}$

${\displaystyle 1\leq i\leq N}$

Recurrencia

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

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

Terminación

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

Ejemplo de cálculo de ${\displaystyle \alpha _{4}(3)}$

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

${\displaystyle \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 ${\displaystyle \beta _{t}(i)}$

Consideramos la variable ${\displaystyle \beta _{t}(i)}$.

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

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

Inicialización

${\displaystyle \beta _{T}(i)=1}$,

${\displaystyle 1\leq i\leq N}$

Recurrencia

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

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

Terminación

${\displaystyle P(O|\mu )=\displaystyle \sum _{i=1}^{N}{\beta _{1}(i)\pi _{i}b_{i}(o_{1})}}$

Ejemplo de cálculo de ${\displaystyle \beta _{2}(3)}$

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

${\displaystyle \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 ${\displaystyle N^{2}T}$ operaciones; muy inferior a ${\displaystyle 2TN^{T}-1}$ operaciones (${\displaystyle N}$ es el número de estados y ${\displaystyle T}$ es la longitud de la secuencia de observaciones) que son necesarias si se calcula ${\displaystyle P(O,S|\mu )}$ para todas las posibles secuencias ${\displaystyle S}$ del modelo.

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

• ¿Cuál es la secuencia óptima ${\displaystyle S}$ de estados dado una secuencia de observaciones ${\displaystyle O}$? (algoritmo de Viterbi)
• Dada una secuencia de observaciones ${\displaystyle O=(o_{1},o_{2},\ldots ,o_{T})}$, ¿cómo podemos estimar los parámetros del modelo ${\displaystyle \mu =(\pi ,A,B)}$ para maximizar ${\displaystyle 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