Algoritmo de avance y retroceso

Algoritmo de inferencia para modelos ocultos de Markov

El algoritmo forward-backward es un algoritmo de inferencia para modelos ocultos de Markov que calcula las marginales posteriores de todas las variables de estado ocultas dada una secuencia de observaciones/emisiones , es decir, calcula, para todas las variables de estado ocultas , la distribución . Esta tarea de inferencia se suele llamar suavizado . El algoritmo hace uso del principio de programación dinámica para calcular de manera eficiente los valores que se requieren para obtener las distribuciones marginales posteriores en dos pasadas. La primera pasada avanza en el tiempo mientras que la segunda retrocede en el tiempo; de ahí el nombre de algoritmo forward-backward . ${\displaystyle o_{1:T}:=o_{1},\dots ,o_{T}}$ ${\displaystyle X_{t}\in \{X_{1},\dots ,X_{T}\}}$ ${\displaystyle P(X_{t}\ |\ o_{1:T})}$

El término algoritmo de avance-retroceso también se utiliza para referirse a cualquier algoritmo que pertenece a la clase general de algoritmos que operan sobre modelos de secuencia de manera de avance-retroceso. En este sentido, las descripciones en el resto de este artículo se refieren únicamente a una instancia específica de esta clase.

Descripción general

En la primera pasada, el algoritmo de avance-retroceso calcula un conjunto de probabilidades hacia adelante que proporcionan, para todos los , la probabilidad de terminar en cualquier estado particular dadas las primeras observaciones en la secuencia, es decir . En la segunda pasada, el algoritmo calcula un conjunto de probabilidades hacia atrás que proporcionan la probabilidad de observar las observaciones restantes dado cualquier punto de partida , es decir . Estos dos conjuntos de distribuciones de probabilidad se pueden combinar para obtener la distribución sobre los estados en cualquier punto específico en el tiempo dada toda la secuencia de observaciones: ${\displaystyle t\in \{1,\dots ,T\}}$ ${\displaystyle t}$ ${\displaystyle P(X_{t}\ |\ o_{1:t})}$ ${\displaystyle t}$ ${\displaystyle P(o_{t+1:T}\ |\ X_{t})}$

${\displaystyle P(X_{t}\ |\ o_{1:T})=P(X_{t}\ |\ o_{1:t},o_{t+1:T})\propto P(o_{t+1:T}\ |\ X_{t})P(X_{t}|o_{1:t})}$

El último paso se deriva de una aplicación de la regla de Bayes y de la independencia condicional de y dado . ${\displaystyle o_{t+1:T}}$ ${\displaystyle o_{1:t}}$ ${\displaystyle X_{t}}$

Como se ha descrito anteriormente, el algoritmo consta de tres pasos:

1. Calcular probabilidades a futuro
2. Calcular probabilidades inversas
3. Calcular valores suavizados.

Los pasos hacia adelante y hacia atrás también pueden denominarse "paso de mensaje hacia adelante" y "paso de mensaje hacia atrás"; estos términos se deben al paso de mensaje utilizado en los enfoques generales de propagación de creencias . En cada observación individual de la secuencia, se calculan las probabilidades que se utilizarán para los cálculos en la siguiente observación. El paso de suavizado se puede calcular simultáneamente durante el paso hacia atrás. Este paso permite que el algoritmo tenga en cuenta cualquier observación anterior de la salida para calcular resultados más precisos.

El algoritmo de avance-retroceso se puede utilizar para encontrar el estado más probable para cualquier punto en el tiempo. Sin embargo, no se puede utilizar para encontrar la secuencia de estados más probable (véase el algoritmo de Viterbi ).

Probabilidades a futuro

La siguiente descripción utilizará matrices de valores de probabilidad en lugar de distribuciones de probabilidad, aunque en general el algoritmo de avance-retroceso se puede aplicar a modelos de probabilidad continuos y discretos.

Transformamos las distribuciones de probabilidad relacionadas con un modelo oculto de Markov dado en notación matricial de la siguiente manera. Las probabilidades de transición de una variable aleatoria dada que representa todos los estados posibles en el modelo oculto de Markov estarán representadas por la matriz donde el índice de la columna representará el estado objetivo y el índice de la fila representará el estado inicial. Una transición del estado de vector de fila al estado de vector de fila incremental se escribe como . El ejemplo siguiente representa un sistema donde la probabilidad de permanecer en el mismo estado después de cada paso es del 70% y la probabilidad de transición al otro estado es del 30%. La matriz de transición es entonces: ${\displaystyle \mathbf {P} (X_{t}\mid X_{t-1})}$ ${\displaystyle X_{t}}$ ${\displaystyle \mathbf {T} }$ ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle \mathbf {\pi _{t}} }$ ${\displaystyle \mathbf {\pi _{t+1}} }$ ${\displaystyle \mathbf {\pi _{t+1}} =\mathbf {\pi _{t}} \mathbf {T} }$

${\displaystyle \mathbf {T} ={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}}$

En un modelo típico de Markov, multiplicaríamos un vector de estado por esta matriz para obtener las probabilidades del estado subsiguiente. En un modelo oculto de Markov, el estado es desconocido y, en su lugar, observamos los eventos asociados con los estados posibles. Una matriz de eventos de la forma:

${\displaystyle \mathbf {B} ={\begin{pmatrix}0.9&0.1\\0.2&0.8\end{pmatrix}}}$

proporciona las probabilidades de observar eventos dado un estado particular. En el ejemplo anterior, el evento 1 se observará el 90% del tiempo si estamos en el estado 1, mientras que el evento 2 tiene una probabilidad del 10% de ocurrir en este estado. En contraste, el evento 1 solo se observará el 20% del tiempo si estamos en el estado 2 y el evento 2 tiene una probabilidad del 80% de ocurrir. Dado un vector de fila arbitrario que describe el estado del sistema ( ), la probabilidad de observar el evento j es entonces: ${\displaystyle \mathbf {\pi } }$

${\displaystyle \mathbf {P} (O=j)=\sum _{i}\pi _{i}B_{i,j}}$

La probabilidad de que un estado dado conduzca al evento observado j se puede representar en forma matricial multiplicando el vector de fila de estado ( ) por una matriz de observación ( ) que contiene solo entradas diagonales. Siguiendo con el ejemplo anterior, la matriz de observación para el evento 1 sería: ${\displaystyle \mathbf {\pi } }$ ${\displaystyle \mathbf {O_{j}} =\mathrm {diag} (B_{*,o_{j}})}$

${\displaystyle \mathbf {O_{1}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}}$

Esto nos permite calcular el nuevo vector de estados de probabilidades no normalizadas a través de la regla de Bayes, ponderando por la probabilidad de que cada elemento del evento generado 1 sea: ${\displaystyle \mathbf {\pi '} }$ ${\displaystyle \mathbf {\pi } }$

${\displaystyle \mathbf {\pi '} =\mathbf {\pi } \mathbf {O_{1}} }$

Ahora podemos hacer que este procedimiento general sea específico para nuestra serie de observaciones. Suponiendo un vector de estado inicial , (que puede optimizarse como parámetro mediante repeticiones del procedimiento de avance-retroceso), comenzamos con , y luego actualizamos la distribución de estado y la ponderación por la probabilidad de la primera observación: ${\displaystyle \mathbf {\pi } _{0}}$ ${\displaystyle \mathbf {f_{0:0}} =\mathbf {\pi } _{0}}$

${\displaystyle \mathbf {f_{0:1}} =\mathbf {\pi } _{0}\mathbf {T} \mathbf {O_{o_{1}}} }$

Este proceso se puede llevar a cabo con observaciones adicionales utilizando:

${\displaystyle \mathbf {f_{0:t}} =\mathbf {f_{0:t-1}} \mathbf {T} \mathbf {O_{o_{t}}} }$

Este valor es el vector de probabilidad no normalizada hacia delante. La entrada i-ésima de este vector proporciona:

${\displaystyle \mathbf {f_{0:t}} (i)=\mathbf {P} (o_{1},o_{2},\dots ,o_{t},X_{t}=x_{i}|\mathbf {\pi } _{0})}$

Normalmente, normalizaremos el vector de probabilidad en cada paso para que sus entradas sumen 1. De este modo, se introduce un factor de escala en cada paso de modo que:

${\displaystyle \mathbf {{\hat {f}}_{0:t}} =c_{t}^{-1}\ \mathbf {{\hat {f}}_{0:t-1}} \mathbf {T} \mathbf {O_{o_{t}}} }$

donde representa el vector escalado del paso anterior y representa el factor de escala que hace que las entradas del vector resultante sumen 1. El producto de los factores de escala es la probabilidad total de observar los eventos dados independientemente de los estados finales: ${\displaystyle \mathbf {{\hat {f}}_{0:t-1}} }$ ${\displaystyle c_{t}}$

${\displaystyle \mathbf {P} (o_{1},o_{2},\dots ,o_{t}|\mathbf {\pi } _{0})=\prod _{s=1}^{t}c_{s}}$

Esto nos permite interpretar el vector de probabilidad escalado como:

${\displaystyle \mathbf {{\hat {f}}_{0:t}} (i)={\frac {\mathbf {f_{0:t}} (i)}{\prod _{s=1}^{t}c_{s}}}={\frac {\mathbf {P} (o_{1},o_{2},\dots ,o_{t},X_{t}=x_{i}|\mathbf {\pi } _{0})}{\mathbf {P} (o_{1},o_{2},\dots ,o_{t}|\mathbf {\pi } _{0})}}=\mathbf {P} (X_{t}=x_{i}|o_{1},o_{2},\dots ,o_{t},\mathbf {\pi } _{0})}$

De este modo, encontramos que el producto de los factores de escala nos proporciona la probabilidad total de observar la secuencia dada hasta el tiempo t y que el vector de probabilidad escalada nos proporciona la probabilidad de estar en cada estado en ese momento.

Probabilidades hacia atrás

Se puede construir un procedimiento similar para hallar probabilidades inversas. Estos pretenden proporcionar las probabilidades:

${\displaystyle \mathbf {b_{t:T}} (i)=\mathbf {P} (o_{t+1},o_{t+2},\dots ,o_{T}|X_{t}=x_{i})}$

Es decir, ahora queremos suponer que comenzamos en un estado particular ( ), y ahora nos interesa la probabilidad de observar todos los eventos futuros desde este estado. Dado que se supone que el estado inicial está dado (es decir, la probabilidad previa de este estado = 100 %), comenzamos con: ${\displaystyle X_{t}=x_{i}}$

${\displaystyle \mathbf {b_{T:T}} =[1\ 1\ 1\ \dots ]^{T}}$

Observe que ahora estamos usando un vector de columna mientras que las probabilidades hacia adelante usan vectores de fila. Luego podemos trabajar hacia atrás usando:

${\displaystyle \mathbf {b_{t-1:T}} =\mathbf {T} \mathbf {O_{t}} \mathbf {b_{t:T}} }$

Si bien también podríamos normalizar este vector para que sus entradas sumen uno, esto no se hace habitualmente. Teniendo en cuenta que cada entrada contiene la probabilidad de la secuencia de eventos futuros dado un estado inicial particular, normalizar este vector sería equivalente a aplicar el teorema de Bayes para encontrar la probabilidad de cada estado inicial dados los eventos futuros (suponiendo valores anteriores uniformes para el vector de estado final). Sin embargo, es más común escalar este vector utilizando las mismas constantes utilizadas en los cálculos de probabilidad a futuro. no se escala, pero las operaciones posteriores utilizan: ${\displaystyle c_{t}}$ ${\displaystyle \mathbf {b_{T:T}} }$

${\displaystyle \mathbf {{\hat {b}}_{t-1:T}} =c_{t}^{-1}\mathbf {T} \mathbf {O_{t}} \mathbf {{\hat {b}}_{t:T}} }$

donde representa el vector anterior, escalado. Este resultado es que el vector de probabilidad escalado está relacionado con las probabilidades anteriores por: ${\displaystyle \mathbf {{\hat {b}}_{t:T}} }$

${\displaystyle \mathbf {{\hat {b}}_{t:T}} (i)={\frac {\mathbf {b_{t:T}} (i)}{\prod _{s=t+1}^{T}c_{s}}}}$

Esto es útil porque nos permite encontrar la probabilidad total de estar en cada estado en un momento dado, t, multiplicando estos valores:

${\displaystyle \mathbf {\gamma _{t}} (i)=\mathbf {P} (X_{t}=x_{i}|o_{1},o_{2},\dots ,o_{T},\mathbf {\pi } _{0})={\frac {\mathbf {P} (o_{1},o_{2},\dots ,o_{T},X_{t}=x_{i}|\mathbf {\pi } _{0})}{\mathbf {P} (o_{1},o_{2},\dots ,o_{T}|\mathbf {\pi } _{0})}}={\frac {\mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)}{\prod _{s=1}^{T}c_{s}}}=\mathbf {{\hat {f}}_{0:t}} (i)\cdot \mathbf {{\hat {b}}_{t:T}} (i)}$

Para entender esto, observamos que proporciona la probabilidad de observar los eventos dados de una manera que pasa por el estado en el tiempo t. Esta probabilidad incluye las probabilidades hacia adelante que cubren todos los eventos hasta el tiempo t, así como las probabilidades hacia atrás que incluyen todos los eventos futuros. Este es el numerador que estamos buscando en nuestra ecuación, y dividimos por la probabilidad total de la secuencia de observación para normalizar este valor y extraer solo la probabilidad de que . Estos valores a veces se denominan "valores suavizados", ya que combinan las probabilidades hacia adelante y hacia atrás para calcular una probabilidad final. ${\displaystyle \mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)}$ ${\displaystyle x_{i}}$ ${\displaystyle X_{t}=x_{i}}$

Los valores proporcionan así la probabilidad de estar en cada estado en el tiempo t. Como tal, son útiles para determinar el estado más probable en cualquier momento. El término "estado más probable" es algo ambiguo. Mientras que el estado más probable es el que tiene más probabilidades de ser correcto en un punto dado, la secuencia de estados individualmente probables no es probable que sea la secuencia más probable. Esto se debe a que las probabilidades para cada punto se calculan independientemente unas de otras. No tienen en cuenta las probabilidades de transición entre estados, y por lo tanto es posible obtener estados en dos momentos (t y t+1) que sean ambos más probables en esos puntos de tiempo pero que tengan muy poca probabilidad de ocurrir juntos, es decir . La secuencia más probable de estados que produjo una secuencia de observación se puede encontrar utilizando el algoritmo de Viterbi . ${\displaystyle \mathbf {\gamma _{t}} (i)}$ ${\displaystyle \mathbf {P} (X_{t}=x_{i},X_{t+1}=x_{j})\neq \mathbf {P} (X_{t}=x_{i})\mathbf {P} (X_{t+1}=x_{j})}$

Ejemplo

Este ejemplo toma como base el mundo de los paraguas de Russell & Norvig 2010, capítulo 15, pág. 567, en el que nos gustaría inferir el tiempo que hace a partir de la observación de otra persona que lleva o no un paraguas. Suponemos dos estados posibles para el tiempo: estado 1 = lluvia, estado 2 = sin lluvia. Suponemos que el tiempo tiene un 70 % de probabilidades de permanecer igual cada día y un 30 % de probabilidades de cambiar. Las probabilidades de transición son entonces:

${\displaystyle \mathbf {T} ={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}}$

También asumimos que cada estado genera uno de dos eventos posibles: evento 1 = paraguas, evento 2 = sin paraguas. Las probabilidades condicionales de que estos ocurran en cada estado están dadas por la matriz de probabilidad:

${\displaystyle \mathbf {B} ={\begin{pmatrix}0.9&0.1\\0.2&0.8\end{pmatrix}}}$

Observamos entonces la siguiente secuencia de eventos: {paraguas, paraguas, sin paraguas, paraguas, paraguas} que representaremos en nuestros cálculos como:

${\displaystyle \mathbf {O_{1}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{2}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{3}} ={\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}~~\mathbf {O_{4}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{5}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}}$

Tenga en cuenta que se diferencia de los demás por la observación de "sin paraguas". ${\displaystyle \mathbf {O_{3}} }$

Para calcular las probabilidades a futuro comenzamos con:

${\displaystyle \mathbf {f_{0:0}} ={\begin{pmatrix}0.5&0.5\end{pmatrix}}}$

que es nuestro vector de estado anterior que indica que no sabemos en qué estado se encuentra el clima antes de nuestras observaciones. Si bien un vector de estado debe darse como un vector de fila, utilizaremos la transposición de la matriz para que los cálculos a continuación sean más fáciles de leer. Nuestros cálculos se escriben en la forma:

${\displaystyle (\mathbf {{\hat {f}}_{0:t}} )^{T}=c_{t}^{-1}\mathbf {O_{t}} (\mathbf {T} )^{T}(\mathbf {{\hat {f}}_{0:t-1}} )^{T}}$

en lugar de:

${\displaystyle \mathbf {{\hat {f}}_{0:t}} =c_{t}^{-1}\mathbf {{\hat {f}}_{0:t-1}} \mathbf {T} \mathbf {O_{t}} }$

Observe que la matriz de transformación también está transpuesta, pero en nuestro ejemplo la transpuesta es igual a la matriz original. Al realizar estos cálculos y normalizar los resultados, se obtiene lo siguiente:

${\displaystyle (\mathbf {{\hat {f}}_{0:1}} )^{T}=c_{1}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.5000\\0.5000\end{pmatrix}}=c_{1}^{-1}{\begin{pmatrix}0.4500\\0.1000\end{pmatrix}}={\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}}$

${\displaystyle (\mathbf {{\hat {f}}_{0:2}} )^{T}=c_{2}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}=c_{2}^{-1}{\begin{pmatrix}0.5645\\0.0745\end{pmatrix}}={\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}}$

${\displaystyle (\mathbf {{\hat {f}}_{0:3}} )^{T}=c_{3}^{-1}{\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}=c_{3}^{-1}{\begin{pmatrix}0.0653\\0.2772\end{pmatrix}}={\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}}$

${\displaystyle (\mathbf {{\hat {f}}_{0:4}} )^{T}=c_{4}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}=c_{4}^{-1}{\begin{pmatrix}0.3386\\0.1247\end{pmatrix}}={\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}}$

${\displaystyle (\mathbf {{\hat {f}}_{0:5}} )^{T}=c_{5}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}=c_{5}^{-1}{\begin{pmatrix}0.5331\\0.0815\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}}$

Para las probabilidades hacia atrás, comenzamos con:

${\displaystyle \mathbf {b_{5:5}} ={\begin{pmatrix}1.0\\1.0\end{pmatrix}}}$

Luego podemos calcular (utilizando las observaciones en orden inverso y normalizando con diferentes constantes):

${\displaystyle \mathbf {{\hat {b}}_{4:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}1.0000\\1.0000\end{pmatrix}}=\alpha {\begin{pmatrix}0.6900\\0.4100\end{pmatrix}}={\begin{pmatrix}0.6273\\0.3727\end{pmatrix}}}$

${\displaystyle \mathbf {{\hat {b}}_{3:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.6273\\0.3727\end{pmatrix}}=\alpha {\begin{pmatrix}0.4175\\0.2215\end{pmatrix}}={\begin{pmatrix}0.6533\\0.3467\end{pmatrix}}}$

${\displaystyle \mathbf {{\hat {b}}_{2:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}{\begin{pmatrix}0.6533\\0.3467\end{pmatrix}}=\alpha {\begin{pmatrix}0.1289\\0.2138\end{pmatrix}}={\begin{pmatrix}0.3763\\0.6237\end{pmatrix}}}$

${\displaystyle \mathbf {{\hat {b}}_{1:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.3763\\0.6237\end{pmatrix}}=\alpha {\begin{pmatrix}0.2745\\0.1889\end{pmatrix}}={\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}}$

${\displaystyle \mathbf {{\hat {b}}_{0:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}=\alpha {\begin{pmatrix}0.3976\\0.2170\end{pmatrix}}={\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}}$

Por último, calcularemos los valores de probabilidad suavizados. Estos resultados también deben escalarse de modo que sus entradas sumen 1, ya que no escalamos las probabilidades inversas con los valores encontrados anteriormente. Por lo tanto, los vectores de probabilidad inversa anteriores representan en realidad la probabilidad de cada estado en el momento t dadas las observaciones futuras. Debido a que estos vectores son proporcionales a las probabilidades inversas reales, el resultado debe escalarse una vez más. ${\displaystyle c_{t}}$

${\displaystyle (\mathbf {\gamma _{0}} )^{T}=\alpha {\begin{pmatrix}0.5000\\0.5000\end{pmatrix}}\circ {\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}=\alpha {\begin{pmatrix}0.3235\\0.1765\end{pmatrix}}={\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}}$

${\displaystyle (\mathbf {\gamma _{1}} )^{T}=\alpha {\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}\circ {\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}=\alpha {\begin{pmatrix}0.4846\\0.0741\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}}$

${\displaystyle (\mathbf {\gamma _{2}} )^{T}=\alpha {\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}\circ {\begin{pmatrix}0.3763\\0.6237\end{pmatrix}}=\alpha {\begin{pmatrix}0.3324\\0.0728\end{pmatrix}}={\begin{pmatrix}0.8204\\0.1796\end{pmatrix}}}$

${\displaystyle (\mathbf {\gamma _{3}} )^{T}=\alpha {\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}\circ {\begin{pmatrix}0.6533\\0.3467\end{pmatrix}}=\alpha {\begin{pmatrix}0.1246\\0.2806\end{pmatrix}}={\begin{pmatrix}0.3075\\0.6925\end{pmatrix}}}$

${\displaystyle (\mathbf {\gamma _{4}} )^{T}=\alpha {\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}\circ {\begin{pmatrix}0.6273\\0.3727\end{pmatrix}}=\alpha {\begin{pmatrix}0.4584\\0.1003\end{pmatrix}}={\begin{pmatrix}0.8204\\0.1796\end{pmatrix}}}$

${\displaystyle (\mathbf {\gamma _{5}} )^{T}=\alpha {\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}\circ {\begin{pmatrix}1.0000\\1.0000\end{pmatrix}}=\alpha {\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}}$

Nótese que el valor de es igual a y que es igual a . Esto se sigue naturalmente porque tanto y comienzan con valores anteriores uniformes sobre los vectores de estado inicial y final (respectivamente) y tienen en cuenta todas las observaciones. Sin embargo, solo será igual a cuando nuestro vector de estado inicial represente un valor anterior uniforme (es decir, todas las entradas son iguales). Cuando este no es el caso, debe combinarse con el vector de estado inicial para encontrar el estado inicial más probable. Por lo tanto, encontramos que las probabilidades hacia adelante por sí mismas son suficientes para calcular el estado final más probable. De manera similar, las probabilidades hacia atrás se pueden combinar con el vector de estado inicial para proporcionar el estado inicial más probable dadas las observaciones. Las probabilidades hacia adelante y hacia atrás solo necesitan combinarse para inferir los estados más probables entre los puntos inicial y final. ${\displaystyle \mathbf {\gamma _{0}} }$ ${\displaystyle \mathbf {{\hat {b}}_{0:5}} }$ ${\displaystyle \mathbf {\gamma _{5}} }$ ${\displaystyle \mathbf {{\hat {f}}_{0:5}} }$ ${\displaystyle \mathbf {{\hat {f}}_{0:5}} }$ ${\displaystyle \mathbf {{\hat {b}}_{0:5}} }$ ${\displaystyle \mathbf {\gamma _{0}} }$ ${\displaystyle \mathbf {{\hat {b}}_{0:5}} }$ ${\displaystyle \mathbf {{\hat {b}}_{0:5}} }$

Los cálculos anteriores revelan que el estado meteorológico más probable para cada día, excepto el tercero, era "lluvia". Sin embargo, nos dicen más que eso, ya que ahora proporcionan una forma de cuantificar las probabilidades de cada estado en diferentes momentos. Quizás lo más importante es que nuestro valor en cuantifica nuestro conocimiento del vector de estado al final de la secuencia de observación. Luego podemos utilizar esto para predecir la probabilidad de los diversos estados meteorológicos mañana, así como la probabilidad de observar un paraguas. ${\displaystyle \mathbf {\gamma _{5}} }$

Actuación

El algoritmo de avance-retroceso se ejecuta con complejidad temporal en el espacio , donde es la longitud de la secuencia temporal y es el número de símbolos en el alfabeto de estados. ^[1] El algoritmo también puede ejecutarse en un espacio constante con complejidad temporal al recalcular los valores en cada paso. ^[2] A modo de comparación, un procedimiento de fuerza bruta generaría todas las posibles secuencias de estados y calcularía la probabilidad conjunta de cada secuencia de estados con la serie observada de eventos, que tendría una complejidad temporal . La fuerza bruta es intratable para problemas realistas, ya que la cantidad de posibles secuencias de nodos ocultos suele ser extremadamente alta. ${\displaystyle O(S^{2}T)}$ ${\displaystyle O(ST)}$ ${\displaystyle T}$ ${\displaystyle S}$ ${\displaystyle O(S^{2}T^{2})}$ ${\displaystyle S^{T}}$ ${\displaystyle O(T\cdot S^{T})}$

Una mejora del algoritmo general de avance-retroceso, llamado algoritmo de la Isla , sacrifica un menor uso de memoria por un mayor tiempo de ejecución, lo que requiere tiempo y memoria. Además, es posible invertir el modelo de proceso para obtener un algoritmo de espacio- tiempo, aunque el proceso invertido puede no existir o estar mal condicionado . ^[3] ${\displaystyle O(S^{2}T\log T)}$ ${\displaystyle O(S\log T)}$ ${\displaystyle O(S)}$ ${\displaystyle O(S^{2}T)}$

Además, se han desarrollado algoritmos para calcular de manera eficiente a través del suavizado en línea, como el algoritmo de suavizado de retardo fijo (FLS). ^[4] ${\displaystyle \mathbf {f_{0:t+1}} }$

Pseudocódigo

El algoritmo forward_backward se  ingresa como guessState int sequenceIndex  salida:  resultado Si  sequenceIndex está más allá del final de la secuencia , entonces  devuelve 1. Si ( guessState , sequenceIndex ) se ha visto antes, entonces  devuelve el resultado guardado. resultado  := 0 para cada estado vecino n: resultado  := resultado + (probabilidad de transición de guessState a n elemento de observación dado en sequenceIndex ) × Hacia atrás(n, índiceDeSecuencia + 1) guardar resultado para ( guessState , sequenceIndex ) devolver  resultado

Ejemplo de Python

Dado HMM (al igual que en el algoritmo de Viterbi ) representado en el lenguaje de programación Python :

estados  =  ( 'Saludable' ,  'Fiebre' ) estado_final  =  'E' observaciones  =  ( 'normal' ,  'frío' ,  'mareado' ) probabilidad_inicial  =  { 'Saludable' :  0,6 ,  'Fiebre' :  0,4 } probabilidad_de_transición  =  {  'Saludable'  :  { 'Saludable' :  0,69 ,  'Fiebre' :  0,3 ,  'E' :  0,01 },  'Fiebre'  :  { 'Saludable' :  0,4 ,  'Fiebre' :  0,59 ,  'E' :  0,01 },  } probabilidad_de_emisión  =  {  'Saludable'  :  { 'normal' :  0,5 ,  'frío' :  0,4 ,  'mareado' :  0,1 },  'Fiebre'  :  { 'normal' :  0,1 ,  'frío' :  0,3 ,  'mareado' :  0,6 },  }

Podemos escribir la implementación del algoritmo adelante-atrás de la siguiente manera:

def  fwd_bkw ( observaciones ,  estados ,  start_prob ,  trans_prob ,  emm_prob ,  end_st ): """Algoritmo de avance-retroceso.""" # Parte de avance del algoritmo fwd = [] for i , observation_i in enumerate ( observaciones ): f_curr = {} for st in states : if i == 0 : # caso base para la parte de avance prev_f_sum = start_prob [ st ] else : prev_f_sum = sum ( f_prev [ k ] * trans_prob [ k ][ st ] for k in states )                                    f_curr [ st ]  =  emm_prob [ st ][ observación_i ]  *  prev_f_sum fwd .append ( f_curr ) f_prev = f_curr​    p_fwd  =  suma ( f_curr [ k ]  *  trans_prob [ k ][ end_st ]  para  k  en  estados ) # Parte inversa del algoritmo  bkw  =  []  para  i ,  observación_i_más  en  enumerar ( reversed ( observaciones [ 1 :]  +  ( Ninguna ,))):  b_curr  =  {}  para  st  en  estados :  si  i  ==  0 :  # caso base para la parte inversa  b_curr [ st ]  =  trans_prob [ st ][ end_st ]  de lo contrario :  b_curr [ st ]  =  suma ( trans_prob [ st ][ l ]  *  emm_prob [ l ][ observación_i_más ]  *  b_prev [ l ]  para  l  en  estados ) bkw . insert ( 0 , b_curr )  b_prev  =  b_curr p_bkw  =  suma ( start_prob [ l ]  *  emm_prob [ l ][ observaciones [ 0 ]]  *  b_curr [ l ]  para  l  en  estados ) # Fusionando las dos partes  posterior  =  []  for  i  in  range ( len ( observations )):  posterior . append ({ st :  fwd [ i ][ st ]  *  bkw [ i ][ st ]  /  p_fwd  for  st  in  states }) afirmar  p_fwd  ==  p_bkw  devolver  fwd ,  bkw ,  posterior

La función fwd_bkwtoma los siguientes argumentos: xes la secuencia de observaciones, por ejemplo ['normal', 'cold', 'dizzy']; stateses el conjunto de estados ocultos; a_0es la probabilidad de inicio; ason las probabilidades de transición; y eson las probabilidades de emisión.

Para simplificar el código, suponemos que la secuencia de observación xno está vacía y que a[i][j]y e[i][j]está definida para todos los estados i, j.

En el ejemplo en ejecución, se utiliza el algoritmo de avance-retroceso de la siguiente manera:

def  ejemplo ():  return  fwd_bkw ( observaciones ,  estados ,  probabilidad_de_inicio ,  probabilidad_de_transición ,  probabilidad_de_emisión ,  estado_final )

>>> para  la línea  en  el ejemplo (): ...  print ( * línea ) ... {'Saludable': 0.3, 'Fiebre': 0.04000000000000001} {'Saludable': 0.0892, 'Fiebre': 0.03408} {'Saludable': 0.007518, 'Fiebre': 0.02812031999999997} {'Saludable': 0.0010418399999999998, 'Fiebre': 0.00109578} {'Saludable': 0.00249, 'Fiebre': 0.00394} {'Saludable': 0.01, 'Fiebre': 0.01} {'Saludable': 0,8770110375573259, 'Fiebre': 0,1229889624426741} {'Saludable': 0,623228030950954, 'Fiebre': 0,3767719690490461} {'Saludable': 0,2109527048413057, 'Fiebre': 0,7890472951586943}

Véase también

• Algoritmo de Baum-Welch
• Algoritmo de Viterbi
• Algoritmo BCJR

Referencias

1. Russell y Norvig 2010 págs. 579
2. Russell y Norvig 2010 págs. 575
3. Binder, John; Murphy, Kevin; Russell, Stuart (1997). "Inferencia eficiente en el espacio en redes probabilísticas dinámicas" (PDF) . Int'l, Joint Conf. On Artificial Intelligence . Consultado el 8 de julio de 2020 .
4. Russell y Norvig 2010 Figura 15.6 págs. 580

• Lawrence R. Rabiner , Un tutorial sobre modelos ocultos de Markov y aplicaciones seleccionadas en reconocimiento de voz. Actas del IEEE , 77 (2), pág. 257–286, febrero de 1989. 10.1109/5.18626
• Lawrence R. Rabiner, BH Juang (enero de 1986). "Una introducción a los modelos ocultos de Markov". Revista IEEE ASSP : 4–15.
• Eugene Charniak (1993). Aprendizaje estadístico de idiomas . Cambridge, Massachusetts: MIT Press. ISBN 978-0-262-53141-2.
• Stuart Russell y Peter Norvig (2010). Inteligencia artificial: un enfoque moderno, 3.ª edición . Upper Saddle River, Nueva Jersey: Pearson Education/Prentice-Hall. ISBN 978-0-13-604259-4.

Enlaces externos

• Una hoja de cálculo interactiva para enseñar el algoritmo de avance-retroceso (hoja de cálculo y artículo con explicación paso a paso)
• Tutorial de modelos ocultos de Markov, incluido el algoritmo de avance-retroceso
• Colección de algoritmos de IA implementados en Java (incluido HMM y el algoritmo de avance-retroceso)