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