Algoritmo de avance

El algoritmo de avance , en el contexto de un modelo oculto de Markov (HMM), se utiliza para calcular un "estado de creencia": la probabilidad de un estado en un momento determinado, dada la historia de la evidencia. Este proceso también se conoce como filtrado . El algoritmo de avance está estrechamente relacionado con el algoritmo de Viterbi , pero es distinto de este .

Los algoritmos de avance y retroceso deben considerarse dentro del contexto de la probabilidad, ya que parecen ser simplemente nombres dados a un conjunto de procedimientos matemáticos estándar dentro de algunos campos. Por ejemplo, ni el "algoritmo de avance" ni el "Viterbi" aparecen en la Enciclopedia de Matemáticas de Cambridge . La principal conclusión que se puede extraer de estos algoritmos es cómo organizar las actualizaciones e inferencias bayesianas para que sean computacionalmente eficientes en el contexto de grafos dirigidos de variables (véase redes suma-producto ).

Para un HMM como este:

Esta probabilidad se escribe como${\displaystyle p(x_{t}|y_{1:t})}$. Aquí${\displaystyle x(t)}$es el estado oculto que se abrevia como${\displaystyle x_{t}}$y${\displaystyle y_{1:t}}$son las observaciones${\displaystyle 1}$a${\displaystyle t}$.

El algoritmo hacia atrás complementa al algoritmo hacia adelante al tener en cuenta el historial futuro si se quisiera mejorar la estimación para tiempos pasados. Esto se conoce como suavizado y el algoritmo hacia adelante/hacia atrás calcula${\displaystyle p(x_{t}|y_{1:T})}$para${\displaystyle 1<t<T}$Por lo tanto, el algoritmo completo hacia adelante/atrás tiene en cuenta toda la evidencia. Nótese que se puede calcular un estado de creencia en cada paso de tiempo, pero hacerlo no produce, en sentido estricto, la secuencia de estados más probable , sino más bien el estado más probable en cada paso de tiempo, dado el historial anterior. Para lograr la secuencia más probable, se requiere el algoritmo de Viterbi . Este calcula la secuencia de estados más probable dada la historia de observaciones, es decir, la secuencia de estados que maximiza${\displaystyle p(x_{0:t}|y_{0:t})}$.

El objetivo del algoritmo hacia adelante es calcular la probabilidad conjunta.${\displaystyle p(x_{t},y_{1:t})}$donde, por conveniencia notacional, hemos abreviado${\displaystyle x(t)}$como${\displaystyle x_{t}}$y${\displaystyle (y(1),y(2),...,y(t))}$como${\displaystyle y_{1:t}}$. Una vez que la probabilidad conjunta${\displaystyle p(x_{t},y_{1:t})}$se calcula, las otras probabilidades${\displaystyle p(x_{t}|y_{1:t})}$y${\displaystyle p(y_{1:t})}$son fáciles de obtener.

Tanto el estado como el estado${\displaystyle x_{t}}$y observación${\displaystyle y_{t}}$Se supone que son variables aleatorias discretas y finitas. Las probabilidades de transición de estado del modelo oculto de Markov${\displaystyle p(x_{t}|x_{t-1})}$probabilidades de observación/emisión${\displaystyle p(y_{t}|x_{t})}$y probabilidad previa inicial${\displaystyle p(x_{0})}$se supone que son conocidas. Además, la secuencia de observaciones${\displaystyle y_{1:t}}$se supone que están dados.

Computación${\displaystyle p(x_{t},y_{1:t})}$Ingenuamente requeriría marginalizar sobre todas las posibles secuencias de estados.${\displaystyle \{x_{1:t-1}\}}$, cuyo número crece exponencialmente con${\displaystyle t}$En cambio, el algoritmo directo aprovecha las reglas de independencia condicional del modelo oculto de Markov (HMM) para realizar el cálculo de forma recursiva.

Para demostrar la recursión, dejemos

${\displaystyle \alpha (x_{t})=p(x_{t},y_{1:t})=\sum _{x_{t-1}}p(x_{t},x_{t-1},y_{1:t})}$.

Utilizando la regla de la cadena para expandir${\displaystyle p(x_{t},x_{t-1},y_{1:t})}$, entonces podemos escribir

${\displaystyle \alpha (x_{t})=\sum _{x_{t-1}}p(y_{t}|x_{t},x_{t-1},y_{1:t-1})p(x_{t}|x_{t-1},y_{1:t-1})p(x_{t-1},y_{1:t-1})}$.

Porque${\displaystyle y_{t}}$es condicionalmente independiente de todo excepto${\displaystyle x_{t}}$, y${\displaystyle x_{t}}$es condicionalmente independiente de todo excepto${\displaystyle x_{t-1}}$, esto se simplifica a

${\displaystyle \alpha (x_{t})=p(y_{t}|x_{t})\sum _{x_{t-1}}p(x_{t}|x_{t-1})\alpha (x_{t-1})}$.

Por lo tanto, dado que${\displaystyle p(y_{t}|x_{t})}$y${\displaystyle p(x_{t}|x_{t-1})}$están dadas por las distribuciones de emisión y probabilidades de transición del modelo , que se suponen conocidas, se puede calcular rápidamente${\displaystyle \alpha (x_{t})}$de${\displaystyle \alpha (x_{t-1})}$y evitar incurrir en un tiempo de cálculo exponencial.

La fórmula de recursión dada anteriormente se puede escribir de forma más compacta. Sea${\displaystyle a_{ij}=p(x_{t}=i|x_{t-1}=j)}$sean las probabilidades de transición y${\displaystyle b_{ij}=p(y_{t}=i|x_{t}=j)}$sean las probabilidades de emisión, entonces

${\displaystyle \mathbf {\alpha } _{t}=\mathbf {b} _{t}^{T}\odot \mathbf {A} \mathbf {\alpha } _{t-1}}$

dónde${\displaystyle \mathbf {A} =[a_{ij}]}$es la matriz de probabilidad de transición,${\displaystyle \mathbf {b} _{t}}$es la i-ésima fila de la matriz de probabilidad de emisión${\displaystyle \mathbf {B} =[b_ {ij}]}$lo cual corresponde a la observación real${\displaystyle y_{t}=i}$en ese momento${\displaystyle t}$, y${\displaystyle \mathbf {\alpha } _{t}=[\alpha (x_{t}=1),\ldots ,\alpha (x_{t}=n)]^{T}}$es el vector alfa. El${\displaystyle \odot }$es el producto de Hadamard entre la transpuesta de${\displaystyle \mathbf {b} _{t}}$y${\displaystyle \mathbf {A} \mathbf {\alpha } _{t-1}}$.

La condición inicial se establece de acuerdo con la probabilidad previa sobre${\displaystyle x_{0}}$como

${\displaystyle \alpha (x_{0})=p(y_{0}|x_{0})p(x_{0})}$.

Una vez que la probabilidad conjunta${\displaystyle \alpha (x_{t})=p(x_{t},y_{1:t})}$Se ha calculado utilizando el algoritmo hacia adelante, podemos obtener fácilmente la probabilidad conjunta relacionada.${\displaystyle p(y_{1:t})}$como

${\displaystyle p(y_{1:t})=\sum _{x_{t}}p(x_{t},y_{1:t})=\sum _{x_{t}}\alpha (x_{t})}$

y la probabilidad condicional requerida${\displaystyle p(x_{t}|y_{1:t})}$como

${\displaystyle p(x_{t}|y_{1:t})={\frac {p(x_{t},y_{1:t})}{p(y_{1:t})}}={\frac {\alpha (x_{t})}{\sum _{x_{t}}\alpha (x_{t})}}.}$

Una vez calculada la probabilidad condicional , también podemos hallar la estimación puntual de${\displaystyle x_{t}}$. Por ejemplo, la estimación MAP de${\displaystyle x_{t}}$es dado por

${\displaystyle {\widehat {x}}_{t}^{MAP}=\arg \max _{x_{t}}\;p(x_{t}|y_{1:t})=\arg \max _{x_{t}}\;\alpha (x_{t}),}$

mientras que la estimación MMSE de${\displaystyle x_{t}}$es dado por

${\displaystyle {\widehat {x}}_{t}^{MMSE}=\mathbb {E} [x_{t}|y_{1:t}]=\sum _{x_{t}}x_{t}p(x_{t}|y_{1:t})={\frac {\sum _{x_{t}}x_{t}\alpha (x_{t})}{\sum _{x_{t}}\alpha (x_{t})}}.}$

El algoritmo directo se puede modificar fácilmente para tener en cuenta también las observaciones de variantes del modelo oculto de Markov, como el sistema lineal de salto de Markov .

Este ejemplo muestra la observación de posibles estados climáticos a partir de la condición observada de las algas marinas. Tenemos observaciones de algas marinas durante tres días consecutivos, secas, húmedas y empapadas en ese orden. Los posibles estados climáticos pueden ser soleado, nublado o lluvioso. En total, puede haber${\displaystyle 3^{3}=27}$tales secuencias climáticas. Explorar todas esas posibles secuencias de estados es computacionalmente muy costoso. Para reducir esta complejidad, el algoritmo Forward resulta útil, donde el truco radica en utilizar la independencia condicional de los pasos de la secuencia para calcular probabilidades parciales,${\displaystyle \alpha (x_{t})=p(x_{t},y_{1:t})=p(y_{t}|x_{t})\sum _{x_{t-1}}p(x_{t}|x_{t-1})\alpha (x_{t-1})}$como se muestra en la derivación anterior. Por lo tanto, podemos calcular las probabilidades como el producto de la probabilidad de observación/emisión apropiada,${\displaystyle p(y_{t}|x_{t})}$(probabilidad de estado${\displaystyle y_{t}}$visto en el tiempo t a partir de la observación anterior) con la suma de las probabilidades de alcanzar ese estado en el tiempo t, calculadas utilizando probabilidades de transición. Esto reduce la complejidad del problema de buscar en todo el espacio de búsqueda a solo usar previamente calculado${\displaystyle \alpha }$y probabilidades de transición.

La complejidad del algoritmo de avance es${\displaystyle \Theta (nm^{2})}$, dónde${\displaystyle m}$es el número de estados posibles para una variable latente (como el número de condiciones climáticas en el ejemplo anterior), y${\displaystyle n}$ es la longitud de la secuencia observada. Esto representa una clara reducción con respecto al método ad hoc de explorar todos los estados posibles, que tiene una complejidad de${\displaystyle \Theta (nm^{n})}$.

• Algoritmo de avance híbrido : ^{[ 1 ]} Una variante del algoritmo de avance, denominada algoritmo de avance híbrido (HFA), puede utilizarse para la construcción de redes neuronales de función de base radial (RBF) con nodos ajustables. La red neuronal RBF se construye mediante algoritmos convencionales de selección de subconjuntos. La estructura de la red se determina combinando la configuración de la red de avance por pasos y la optimización continua de parámetros RBF. Se utiliza para producir de forma eficiente y eficaz una red neuronal RBF parsimoniosa que generaliza bien. Esto se logra mediante la determinación simultánea de la estructura de la red y la optimización de parámetros en el espacio de parámetros continuo . El HFA aborda el problema difícil de enteros mixtos utilizando un marco analítico integrado, lo que conduce a un mejor rendimiento de la red y a un menor uso de memoria para su construcción.

• Algoritmo de avance para el control óptimo en sistemas híbridos : ^{[ 2 ]} Esta variante del algoritmo de avance se inspira en la estructura de los entornos de fabricación que integran el control de procesos y operaciones. Derivamos una nueva propiedad de la estructura de la trayectoria de estado óptima que se cumple bajo una condición modificada en la función de coste. Esto nos permite desarrollar un algoritmo escalable y de baja complejidad para determinar explícitamente los controles óptimos, que puede ser más eficiente que el algoritmo de avance.

• Algoritmo de avance continuo : ^{[ 3 ]} Un algoritmo de avance continuo (CFA) puede utilizarse para el modelado e identificación no lineal mediante redes neuronales de función de base radial (RBF). El algoritmo propuesto realiza las dos tareas de construcción de red y optimización de parámetros dentro de un marco analítico integrado, y ofrece dos ventajas importantes. En primer lugar, el rendimiento del modelo puede mejorarse significativamente mediante la optimización continua de parámetros. En segundo lugar, la representación neuronal puede construirse sin generar ni almacenar todos los regresores candidatos, lo que reduce significativamente el uso de memoria y la complejidad computacional.

El algoritmo de avance es uno de los algoritmos utilizados para resolver el problema de decodificación. Desde el desarrollo del reconocimiento de voz ^{[ 4 ]} y el reconocimiento de patrones, y campos relacionados como la biología computacional que utilizan HMM, el algoritmo de avance ha ganado popularidad.

El algoritmo Forward se utiliza principalmente en aplicaciones que requieren determinar la probabilidad de estar en un estado específico a partir de una secuencia de observaciones. Este algoritmo puede aplicarse en cualquier contexto donde se pueda entrenar un modelo a medida que se reciben datos, utilizando Baum-Welch ^{[ 5 ]} o cualquier algoritmo EM general . El algoritmo Forward nos indicará la probabilidad de los datos con respecto a lo esperado según nuestro modelo. Una de sus aplicaciones se encuentra en el ámbito financiero , donde puede ayudar a decidir cuándo comprar o vender activos tangibles.

Puede tener aplicaciones en todos los campos donde aplicamos modelos ocultos de Markov (HMM). Los más populares incluyen dominios de procesamiento del lenguaje natural como el etiquetado de partes del habla y el reconocimiento de voz . ^{[ 4 ]} Recientemente también se está utilizando en el dominio de la bioinformática .

El algoritmo de avance también puede aplicarse para realizar predicciones meteorológicas . Podemos tener un modelo oculto de Markov (HMM) que describa el clima y su relación con el estado de las observaciones durante varios días consecutivos (por ejemplo, seco, húmedo, lluvioso, soleado, nublado, etc.). Podemos calcular recursivamente la probabilidad de observar cualquier secuencia de observaciones a partir del HMM. A continuación, podemos calcular la probabilidad de alcanzar un estado intermedio como la suma de todas las posibles rutas hacia ese estado. De este modo, las probabilidades parciales para la observación final contendrán la probabilidad de alcanzar esos estados siguiendo todas las rutas posibles.

• Algoritmo de Viterbi
• Algoritmo de avance-retroceso
• Algoritmo de Baum-Welch

• El libro de Russell y Norvig , *Inteligencia Artificial: Un Enfoque Moderno* , que comienza en la página 570 de la edición de 2010, ofrece una exposición concisa de este y otros temas relacionados.
• Smyth, Padhraic, David Heckerman y Michael I. Jordan. "Redes de independencia probabilística para modelos de probabilidad de Markov ocultos". Neural Computation 9.2 (1997): 227-269.
• Read, Jonathon. "Modelos ocultos de Markov y programación dinámica". Universidad de Oslo (2011).
• Kohlschein, Christian, Introducción a los modelos ocultos de Markov
• Manganiello, Fabio, Mirco Marchetti y Michele Colajanni. Detección de ataques en múltiples etapas y correlación de alertas en sistemas de detección de intrusiones. Seguridad y garantía de la información. Springer Berlin Heidelberg, 2011. 101-110.
• Zhang, Ping y Christos G. Cassandras. "Un algoritmo directo mejorado para el control óptimo de una clase de sistemas híbridos." Automatic Control, IEEE Transactions on 47.10 (2002): 1735-1739.
• Stratonovich, RL "Procesos de Markov condicionales". Teoría de la probabilidad y sus aplicaciones 5, n.º 2 (1960): 156-178.

• El paquete R Hidden Markov Model contiene funcionalidades para calcular y recuperar el procedimiento hacia adelante.
• El paquete R momentuHMM proporciona herramientas para usar e inferir modelos ocultos de Markov (HMM).
• Biblioteca GHMM para Python
• La biblioteca Haskell del paquete hmm para HMMS implementa el algoritmo Forward.
• La biblioteca para Java contiene implementaciones de algoritmos de aprendizaje automático e inteligencia artificial.