Home
Enciclopedia
Algoritmo_de_Baum-Welch

Algoritmo de Baum-Welch

Conocimientos adicionales recomendados

Cómo comprobar rápidamente el rendimiento de las pipetas

¿Cómo garantizar resultados de pesaje exactos cada día?

Guía de técnicas básicas de medición en el laboratorio

Tabla de contenidos

1 Introducción
2 El algoritmo de Baum y Welch
- 2.1 Valores esperados
- 2.2 Reestimación
3 Otras preguntas fundamentales
4 Véase también

Introducción

Uno de los problemas relacionado con los Modelos Ocultos de Markov (MOM) es el de encontrar un modelo $μ$ 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 de un Modelo oculto de Markov (MOM) $μ$ que maximizan la probabilidad de dicha secuencia, es decir, $P (O | μ)$ .

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 $ξ 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 $μ$ .

$ξ t (i, j) = P (q t = i, q t + 1 = j | O,μ)$

$\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 $α t (i)$ y $β 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 $ξ(i, j)$ .

Definimos también $γ 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 $γ 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 $ξ 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:

Se parte de un modelo inicial que se puede seleccionar aleatoriamente.
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.
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$

Número esperado de transiciones de $i$ a $j$ / 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$

Número esperado de veces que se pasa por el estado $j$ y se observa $o k$ / 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 MOO son:

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

Véase también

Categoría: Bioinformática

Este articulo se basa en el articulo Algoritmo_de_Baum-Welch 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.