Algoritmo de avance-retroceso

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

Introducción[editar]

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 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,\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[editar]

Cálculo de \alpha_{t}(i)[editar]

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)[editar]

El esquema muestra los estados y probabilidades necesarias para el cálculo de \alpha_4(3):

Algoritmo forward


\alpha_{4}(3)=\biggl[\displaystyle\sum_{i=1}^{5}{\alpha_{3}(i)a_{i3}}\biggr]b_{3}(o_{4})

Cálculo hacia atrás[editar]

Cálculo de \beta_{t}(i)[editar]

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)[editar]

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.

Algoritmo backward


\beta_{2}(3)=\displaystyle\sum_{j=1}^{5}{a_{3j}\beta_{3}(j)b_{j}(o_{3})},

Complejidad computacional[editar]

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[editar]