7.3 Algoritmo hacia adelante-hacia atrás (forward-backward)

Utilizamos el algoritmo forward-backward para calcular ${\hat{\gamma }}_{ij}$ y ${\hat{\delta }}_j$. Recordemos que

$$\begin{array}{cc}{\hat{\delta }}_j& =P(S_t=j|x)=\frac{P(x,S_t=j)}{P\left(x\right)}\\ {\hat{\gamma }}_{ij}& =P(S_{t-1}=i,S_t=j|x)=\frac{P(x,S_{t-1}=i,S_t=j)}{P\left(x\right)}\end{array}$$

El cálculo de cada una de las probabilidades de arriba es computacionalmente intensivo, por ejemplo para calcular $P\left(x\right)$:

$$P\left(x\right)=\sum _S{p}_{s_1}\left(x_1\right)p_{s_1,s_2}{p}_{s_2}\left(x_2\right)\cdots p_{s_{T-1},s_T}{p}_{s_T}\left(x_T\right)$$

donde $S$ son las combinaciones de posibles estados ($M^T$ posibilidades) por tanto esta aproximación no es factible. Es por esto que surge la necesidad de un algoritmo más eficiente.

El algoritmo hacia adelante-hacia atrás usa el principio de programación dinámica(recursión inteligente) para calcular ${\hat{\gamma }}_{ij}$ y ${\hat{\delta }}_j$ en tiempo lineal ($M^{2}T$), consta de dos pasos y explota las independencias condicionales del modelo.

Probabilidad hacia adelante

Definimos la probabilidad hacia adelante ${\alpha }_i\left(t\right)$ como la probabilidad conjunta de observar las primeras $t$ observaciones $x^j$ ($j=1,...,t$) y siendo $i$ el estado al tiempo $t$:

$${\alpha }_i\left(t\right)=P(X_1=x_1,...,X_T=x_t,S_t=i)$$

La probabilidad se puede evaluar de manera recursiva siguiendo la fórmula:

1. ${\alpha }_i\left(1\right)={\pi }_k{p}_i\left(x_1\right)$ para $i=1,...,M$

2. ${\alpha }_i\left(t\right)=p_i\left(x_t\right){\sum }_{j=1}^M{\alpha }_j(t-1)p_{j,i}$ para $t=2,...,T$ e $i=1,...,M$.

Prueba:

La idea clave es usar $(S_t,X_t)\perp (X_1,...,X_{t-1})|S_{t-1}$ $$\begin{array}{cc}{\alpha }_i\left(t\right)& =P(x_1,...,x_t,S_t=i)\\ & =\sum _{j=1}^{M}P(x_1,...,x_t,S_t=i,S_{t-1}=j)\\ & =\sum _{j=1}^{M}P(x_1,...,x_{t-1},S_{t-1}=j)P(x_t|S_t=i)P(S_t=1|S_{t-1}=j)\\ & =\sum _{j=1}^M{\alpha }_j(t-1)p_i\left(x_t\right)p_{j,i}\end{array}$$

Probabilidad hacia atrás

Definimos la probabilidad hacia atrás ${\beta }_i\left(t\right)$ como la probabilidad condicional de las observaciones posteriores al tiempo $t$ ($x_{t+1},...,x_T$) dado que el estado al tiempo $t$ es $i$.

$${\beta }_i\left(t\right)=P(x_{t+1},...,x_T|S_t=i)$$ para $t=1,...T-1$.

La recursión de la probabilidad hacia atrás se evalúa como:

1. ${\beta }_i\left(T\right)=1$, para $i=1,...,M$.

2. ${\beta }_i\left(t\right)={\sum }_{i=1}^M{p}_{i,j}{p}_j\left(x_{t+1}\right){\beta }_i(t+1)$ para $t=1,...,T-1$.

Prueba:

La idea clave es usar $X_{t+1}\perp (X_{t+2},...,X_T)|S_{t+1}$

$$\begin{array}{cc}{\beta }_i\left(t\right)& =P(x_{t+1},...,x_T|S_t=i)\\ & =\sum _{j=1}^{M}P(x_{t+1},...,x_T,S_{t+1}=j|S_t=i)\\ & =\sum _{j=1}^{M}P(S_{t+1}=j|S_t=i)P(x_{t+1},...,x_T|S_{t+1}=j)\\ & =\sum _{j=1}^M{p}_{i,j}P(x_{t+1},...,x_T|S_{t+1}=j)\\ & =\sum _{j=1}^M{p}_{i,j}P(x_{t+1}|S_{t+1}=j)P(x_{t+2},...,x_T|s_{t+1}=j)\\ & =\sum _{j=1}^M{p}_{i,j}{p}_j\left(x_{t+1}\right){\beta }_j(t+1)\end{array}$$

Escribimos $\delta$ y $\gamma$

Ahora vemos como escrbir ${\delta }_j$ y ${\gamma }_{i,j}$ usando las probabilidades hacia adelante y hacia atrás:

$$\begin{array}{cc}{\hat{\delta }}_j\left(t\right)& =P(S_t=j|x)\\ & =\frac{P(x,S_t=j)}{P\left(x\right)}\\ & =\frac{{\alpha }_j\left(t\right){\beta }_j\left(t\right)}{{\sum }_{i=1}^M{\alpha }_i\left(T\right)}\end{array}$$

Prueba: $$\begin{array}{cc}P(x_1,...,x_T,S_t=j)& =P(x_1,...,x_t,S_t=j)P(x_{t+1},...,x_T|S_t=j)\\ & ={\alpha }_j\left(t\right){\beta }_j\left(t\right)\end{array}$$

Para el denominador notemos que:

$$\begin{array}{cc}P\left(x\right)& =\sum _i^{M}P(x,S_t=i)\\ & =\sum _{i=1}^M{\alpha }_i\left(t\right){\beta }_i\left(t\right)\end{array}$$ esto se cumple para cualquier $t$, así que si tomamos $t=T$:

$$P\left(x\right)=\sum _{i=1}^M{\alpha }_i\left(T\right)$$

En el caso de ${\gamma }_{i,j}$ tenemos:

$$\begin{array}{cc}{\hat{\gamma }}_{ij}& =P(S_{t-1}=i,S_t=j|x)\\ & =\frac{P(x,S_{t-1}=i,S_t=j)}{P\left(x\right)}\\ & =\frac{{\alpha }_i(t-1){\beta }_j\left(t\right)p_{i,j}{p}_j\left(x_t\right)}{P\left(x\right)}\end{array}$$

Prueba: $$\begin{array}{cc}P(x_1,...,x_T,S_{t-1}=i,S_t=j)& =P(x_1,...,x_{t-1},S_{t-1}=i)P(x_{t+1},...,X_T|S_t=j)P(S_t=j|S_{t-1}=i)P(x_t|S_t=j)\\ & ={\alpha }_i(t-1){\beta }_j\left(t\right)p_{i,j}{p}_j\left(x_t\right)\end{array}$$

7.3.1 Resumen de algoritmo de estimación

Entonces, el algoritmo de estimación itera de la siguiente manera:

1. Comenzamos con valores inciales ${\hat{\delta }}_j$ y ${\hat{\gamma }}_{ij}$.

2. Actualizamos los parámetros $${\hat{p}}_{ij}=\frac{{\hat{\gamma }}_{ij}}{{\sum }_l{\hat{\gamma }}_{il}}$$ y los correspondientes a las densidades $p_j\left(x\right)$.

3. Utilizando el conjunto de parámetros actuales (${\hat{p}}_{ij}$ y los correspondientes a $p_j\left(x\right)$) calculamos ${\hat{\delta }}_j$ y ${\hat{\gamma }}_{ij}$ a través del algoritmo hacia adelante-hacia atrás.

4. Iteramos entre 2 y 3.

7.3.2 Algoritmo de Viterbi

En muchas de las aplicaciones de HMM nos interesa hacer inferencia de la secuencia de estados $\{S_1,...,S_T\}$, en este caso el criterio de optimización es:

$$MAP\left(S|x\right)=argma{x}_{s}P\left(S|x\right)=argma{x}_{s}P(S,x)$$

Aqui estamos buscando el camino más probable. Si consideramos un algoritmo de fuerza bruta, esto es, realizamos búsqueda exahustiva sobre todas las posibles secuencias tendríamos que considerar $M^T$ casos. Es por ello que nuevamente recurrimos a un algoritmo de programación dinámica.