Algoritmo de Baum-Welsh

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 17 de octubre de 2019; las comprobaciones requieren 2 ediciones .

El algoritmo de Baum-Welsh se utiliza en informática y estadística para encontrar parámetros desconocidos de un modelo oculto de Markov (HMM). Utiliza el algoritmo adelante-atrás y es un caso especial del algoritmo EM generalizado .

El algoritmo de Baum-Welsh para estimar un modelo oculto de Markov

Un modelo oculto de Markov es un modelo probabilístico de un conjunto de variables aleatorias . Las variables son observaciones discretas conocidas y son cantidades discretas "ocultas". En el marco del modelo oculto de Markov, hay dos declaraciones independientes que aseguran la convergencia de este algoritmo: ${\displaystyle \{Y_{1},\;\ldots,\;Y_{t},\;Q_{1},\;\ldots,\;Q_{t}\))$ ${\ Displaystyle Y_ {t}}$ $Q_{t}$

$t$ -ésima variable oculta con una conocida -ésima variable es independiente de todas las variables anteriores, es decir ; ${\ estilo de visualización (t-1)}$ ${\ estilo de visualización (t-1)}$ $P(Q_{t}\mid Q_{t-1},\;Y_{t-1},\;\ldots,\;Q_{1},\;Y_{1})=P(Q_ {t}\mid Q_{t-1})$
$t$ La observación conocida depende sólo del estado th, es decir, no depende del tiempo, . $t$ $P(Y_{t}\mid Q_{t},\;Q_{t-1},\;Y_{t-1},\;\ldots,\;Q_{1},\;Y_{ 1})=P(Y_{t}\mid Q_{t})$

A continuación, se propondrá un algoritmo de "supuestos y maximizaciones" para encontrar la estimación probabilística máxima de los parámetros del modelo oculto de Markov para un conjunto dado de observaciones. Este algoritmo también se conoce como el algoritmo de Baum-Welsh.

$Q_{t}$ es una variable aleatoria discreta que toma uno de los valores . Supondremos que este modelo de Markov, definido como , es homogéneo en el tiempo, es decir, independiente de . Entonces se puede especificar como una matriz de desplazamiento estocástico independiente del tiempo . Las probabilidades de los estados en un punto en el tiempo están determinadas por la distribución inicial . $norte$ ${\ estilo de visualización (1 \ puntos N)}$ $P(Q_{t}\mid Q_{t-1})$ $t$ $P(Q_{t}\mid Q_{t-1})$ $A=\{a_{ij}\}=p(Q_{t}=j\mid Q_{t-1}=i)$ $t=1$ ${\ estilo de visualización \ pi _ {i} = P (Q_ {1} = i)}$

Asumiremos que estamos en un estado en el momento del tiempo si . La secuencia de estados se expresa como , donde es el estado en el momento . $j$ $t$ $Q_{t}=j$ $q=(q_{1},\;\ldots,\;q_{T})$ $q_{t}\in \{1\ldots N\}$ $t$

Una observación en un punto en el tiempo puede tener uno de los valores posibles, . La probabilidad de un vector dado de observaciones en un punto en el tiempo para un estado se define como ( es una matriz en ). La secuencia de observaciones se expresa como . ${\ Displaystyle Y_ {t}}$ $t$ $L$ $y_{t}\in \{o_{1},\;\ldots,\;o_{L}\}$ $t$ $j$ $b_{j}(o_{i})=P(Y_{t}=o_{i}\mid Q_{t}=j)$ $B=\{b_{ij}\}$ $L$ $norte$ $y$ $y=(y_{1},\;\ldots,\;y_{T})$

Por lo tanto, podemos describir el modelo oculto de Markov con . Para un vector de observación dado, el algoritmo de Baum-Welsh encuentra . maximiza la probabilidad de las observaciones . ${\ estilo de visualización \ lambda = (A \;, B, \; \ pi)}$ $y$ $\lambda ^{*}=arg\max _{\lambda }P(y\mid \lambda )$ ${\ estilo de visualización \ lambda ^ {*}}$ $y$

Algoritmo

Datos iniciales: con condiciones iniciales aleatorias. ${\ estilo de visualización \ lambda = (A, \; B, \; \ pi)}$

El algoritmo actualiza iterativamente el parámetro hasta que converge en un punto. $\lambda$

Procedimiento directo

Indicar por la probabilidad de ocurrencia de una secuencia dada para el estado en el tiempo . $\alpha _{i}(t)=p(Y_{1}=y_{1},\;\ldots,\;Y_{t}=y_{t},\;Q_{t}=i \mid\lambda)$ ${\displaystyle y_{1},\;\ldots,\;y_{t))$ $i$ $t$

${\ estilo de visualización \ alfa _ {i} (t)}$ se puede calcular recursivamente:

$\alpha _{i}(1)=\pi _{i}\cdot b_{i}(y_{1});$
$\alpha _{j}(t+1)=b_{j}(y_{t+1})\sum _{i=1}^{N}{\alpha _{i}(t)\ cdot a_{ij}}.$

Procedimiento inverso

Este procedimiento nos permite calcular la probabilidad de una sucesión finita dada , siempre que partamos del estado inicial , en el tiempo . $\beta _{i}(t)=p(Y_{t+1}=y_{t+1},\ldots,Y_{T}=y_{T}\mid Q_{t}=i, \lambda)$ ${\displaystyle y_{t+1},\;\ldots,\;y_{T))$ $i$ $t$

Se puede calcular : ${\ estilo de visualización \ beta _ {i} (t)}$

$\beta _{i}(T)=p(Y_{T}=y_{T}\mid Q_{t}=i,\lambda )=1;$
$\beta _{i}(t)=\sum _{j=1}^{N}{\beta _{j}(t+1)a_{ij}b_{j}(y_{t+ uno })}.$

Usando y puedes calcular los siguientes valores: $\alfa$ $\beta$

$\gamma _{i}(t)\equiv p(Q_{t}=i\mid y,\;\lambda )={\frac {\alpha _{i}(t)\beta _{i }(t)}{\displaystyle \sum _{j=1}^{N}\alpha _{j}(t)\beta _{j}(t)))),$
$\xi _{ij}(t)\equiv p(Q_{t}=i,\;Q_{t+1}=j\mid y,\;\lambda )={\frac {\alpha _ {i}(t)a_{ij}\beta _{j}(t+1)b_{j}(y_{t+1})}{\displaystyle \sum _{i=1}^{N}\ estilo de visualización \sum _{j=1}^{N}\alpha _{i}(t)a_{ij}\beta _{j}(t+1)b_{j}(y_{t+1})} }.$

Teniendo y , podemos calcular nuevos valores de los parámetros del modelo: $\gama$ $\xi$

${\bar {\pi }}_{i}=\gamma _{i}(1),$
${\bar {a}}_{ij}={\frac {\displaystyle \sum _{t=1}^{T-1}\xi _{ij}(t)}{\displaystyle \sum _{t=1}^{T-1}\gamma_{i}(t)}},$
${\bar {b}}_{i}(o_{k})={\frac {\displaystyle \sum _{t=1}^{T}\delta _{y_{t},\; o_{k}}\gamma _{i}(t)}{\displaystyle \sum _{t=1}^{T}\gamma _{i}(t))).$ ,

dónde

\delta _{y_{t},\;o_{k}}={\begin{casos}1&{\text{si}}y_{t}=o_{k},\\0&{\text {de lo contrario}}\end{casos}}

función indicativa, y el número esperado de valores del observable igual en estado al número total de estados . $b_{i}^{*}(o_{k})$ ${\ Displaystyle o_ {k}}$ $i$ $i$

Usando nuevos valores de , y , las iteraciones continúan hasta la convergencia. $A$ $B$ $\Pi$

Véase también

Algoritmo de Viterbi