title: Algoritmo de avance-retroceso
text: # 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 $\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 probabilidad 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.
  
  # Algoritmo de avance-retroceso
  ## Procedimiento hacia adelante
  ### Cálculo de $\alpha _{t}(i)$
  
  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)}$
  
  # Algoritmo de avance-retroceso
  ## Procedimiento hacia adelante
  ### Ejemplo de cálculo de $\alpha _{4}(3)$
  
  El esquema muestra los estados y probabilidades necesarias para el cálculo de $\alpha _{4}(3)$:
  $\alpha _{4}(3)={\biggl\displaystyle \sum _{i=1}^{5}{\alpha _{3}(i)a_{i3}}{\biggr ]}b_{3}(o_{4})$
  
  # Algoritmo de avance-retroceso
  ## Cálculo hacia atrás
  ### Cálculo de $\beta _{t}(i)$
  
  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})}$
  
  # Algoritmo de avance-retroceso
  ## Cálculo hacia atrás
  ### Ejemplo de cálculo de $\beta _{2}(3)$
  
  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.
  $\beta _{2}(3)=\displaystyle \sum _{j=1}^{5}{a_{3j}\beta _{3}(j)b_{j}(o_{3})},$
  
  # Algoritmo de avance-retroceso
  ## Complejidad computacional
  
  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).