esp  
DeutschEnglishFrançaisEspañol

Algoritmo de avance-retroceso



Tabla de contenidos

Introducción

Uno de los problemas básicos de los Modelos Ocultos de Markov 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 observación O dada una secuencia de estado 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(ot | qt,μ) corresponde con el valor de b_{q_t}(o_t)

Probabilidad de una observación 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 1011 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 Markov 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 hasta el instante de tiempo t en el estado i.

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

Inicialización

α1(i) = πibi(o1),

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

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

El esquema muestra los estados y probabilidades necesarios para el cálculo de β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 N2T operaciones; muy inferior a 2TNT − 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 Markov:

  • ¿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

 
Este articulo se basa en el articulo Algoritmo_de_avance-retroceso publicado en la enciclopedia libre de Wikipedia. El contenido está disponible bajo los términos de la Licencia de GNU Free Documentation License. Véase también en Wikipedia para obtener una lista de autores.
Su navegador no está actualizado. Microsoft Internet Explorer 6.0 no es compatible con algunas de las funciones de Chemie.DE.