Algoritmo de Baum-Welch

En ingeniería eléctrica, informática estadística y bioinformática, el algoritmo de Baum-Welch es un caso especial del algoritmo de maximización de expectativas utilizado para encontrar los parámetros desconocidos de un modelo oculto de Markov (HMM). Utiliza el algoritmo de avance-retroceso para calcular las estadísticas del paso de expectativa.

Introducción

Uno de los problemas relacionados con los Modelos Ocultos de Márkov (MOM) es el de encontrar un modelo $\mu$ que maximice la probabilidad de una secuencia de observaciones $O=(o_{1},o_{2},\ldots ,o_{T})$, es decir, determinar el modelo que mejor explica tal secuencia. El problema es que no es posible encontrar tal modelo analíticamente y por ello es necesario un algoritmo iterativo como el de Baum y Welch, que permite estimar los parámetros de un modelo que hacen máxima la probabilidad de una secuencia de observables.

El algoritmo de Baum y Welch

Dada una secuencia de observaciones $O=(o_{1},o_{2},\ldots ,o_{T})$, el algoritmo de Baum y Welch permite estimar los parámetros $\mu$ de un Modelo oculto de Márkov (MOM) que maximizan la probabilidad de dicha secuencia, es decir, $P(O|\mu )$.

Valores esperados

Antes de describir el proceso de estimación, necesitamos conocer:

• el número esperado de transiciones desde el estado $i$ en $O$ y
• el número esperado de transiciones desde el estado $i$ al estado $j$ en $O$

Para ello definimos previamente $\xi _{t}{(i,j)}$ como la probabilidad de estar en el estado $i$ en el instante $t$ y en el estado $j$ en el instante $t+1$, dado una observación $O$ y el modelo $\mu$.

$\xi _{t}{(i,j)}=P(q_{t}=i,q_{t+1}=j|O,\mu )$

$\xi _{t}{(i,j)}={\frac {P(q_{t}=i,q_{t+1}=j,O|\mu )}{P(O|\mu )}}={\frac {\alpha _{t}{(i)}a_{ij}b_{j}(o_{t+1})\beta _{t+1}(j)}{P(O|\mu )}}$

$\xi _{t}{(i,j)}={\frac {\alpha _{t}{(i)}a_{ij}b_{j}(o_{t+1})\beta _{t+1}(j)}{\displaystyle \sum _{k=1}^{N}\displaystyle \sum _{l=1}^{N}{\alpha _{t}(k)a_{kl}b_{l}(o_{t+1})\beta _{t+1}(l)}}}$

donde los valores $\alpha _{t}(i)$ y $\beta _{t}(i)$ se pueden calcular eficientemente con el algoritmo de avance-retroceso.

$\alpha _{t}(i)=P(o_{1},o_{2},\ldots ,o_{t},q_{t}=i|\mu )$

$\beta _{t}(i)=P(o_{t+1},o_{t+2},\ldots ,o_{T}|q_{t}=i,\mu )$

La figura muestra un esquema parcial de los elementos necesarios para el cálculo de $\xi (i,j)$.

Definimos también $\gamma _{t}(i)$ como la probabilidad de estar en el estado $i$ en el instante $t$,

$\gamma _{t}(i)=\displaystyle \sum _{j=1}^{N}{\xi _{t}(i,j)}$

Sumando cada $\gamma _{t}(i)$ en cada instante de tiempo, obtenemos:

• el número esperado de transiciones desde el estado $i$ en la observación $O$

$\displaystyle \sum _{t=1}^{T-1}{\gamma _{t}(i)}$

y haciendo lo mismo con cada $\xi _{t}(i,j)$, obtenemos:

• el número esperado de transiciones desde el estado $i$ al estado $j$ en la observación $O$

$\displaystyle \sum _{t=1}^{T-1}{\xi _{t}(i,j)}$

Reestimación

El funcionamiento del procedimiento iterativo es básicamente el siguiente:

1. Se parte de un modelo inicial que se puede seleccionar aleatoriamente.
2. Se realiza el cálculo de las transiciones y símbolos de emisión que son más probables según el modelo inicial escogido.
3. Se construye un nuevo modelo en el que se incrementa la probabilidad de las transiciones y símbolos determinados en el paso anterior. Para la secuencia de observables en cuestión, el modelo tendrá ahora una probabilidad mayor que el modelo anterior.

Este proceso de entrenamiento se repite varias veces hasta que no exista mejora entre un modelo y el siguiente revisado.

Probabilidad de estar en el estado $i$ en el instante de tiempo $t=1$:

${\bar {\pi }}_{i}=\gamma _{1}(i)$

$1\leq i\leq N$

Reestimación de las probabilidades de transición. El numerador representa el número esperado de transiciones de $i$ a $j$, y el denominador representa el número esperado de transiciones desde $i$:

${\bar {a}}_{ij}={\frac {\displaystyle \sum _{t=1}^{T-1}{\xi _{t}(i,j)}}{\displaystyle \sum _{t=1}^{T-1}{\gamma _{t}(i)}}}$

$1\leq i\leq N$, $1\leq j\leq N$

Reestimación de las probabilidades de emisión. El numerador representa el número esperado de veces que se pasa por el estado $j$ y se observa $o_{k}$, y el denominador representa el número esperado de veces que se pasa por el estado $j$:

${\bar {b}}_{j}(o_{k})={\frac {\displaystyle \sum _{t=1:o_{t}=o_{k}}^{T}{\gamma _{t}(j)}}{\displaystyle \sum _{t=1}^{T}{\gamma _{t}(j)}}}$

$1\leq j\leq N$, $1\leq k\leq N$

Otras preguntas fundamentales

Otros dos problemas que es importante saber resolver para utilizar los MOM son:

1. ¿Cuál es la secuencia óptima $S$ de estados, dada una secuencia de observaciones $O$? (algoritmo de Viterbi)
2. ¿Cuál es la probabilidad de una secuencia de observaciones $O=(o_{1},o_{2},\ldots ,o_{T})$ dado un modelo $\mu =(\pi ,A,B)$? Es decir, ¿cómo podemos calcular de forma eficiente $P(O|\mu )$? (cálculo hacia adelante y hacia atrás).

Véase también

• Modelos Ocultos de Márkov
• Algoritmo de Viterbi
• Algoritmo de avance-retroceso

• Datos: Q811478