El algoritmo de avance-retroceso es un algoritmo de inferencia para modelos de Markov ocultos que calcula los 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 generalmente se denomina 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 algoritmo hacia adelante-hacia atrás .
El término algoritmo hacia adelante-hacia atrás también se usa para referirse a cualquier algoritmo que pertenezca a la clase general de algoritmos que operan en modelos de secuencia de una manera hacia adelante-hacia atrás. En este sentido, las descripciones en el resto de este artículo se refieren a una instancia específica de esta clase.
Descripción general
En el primer paso, el algoritmo de avance-retroceso calcula un conjunto de probabilidades de avance que proporcionan, para todos , la probabilidad de terminar en cualquier estado en particular dada la primera observaciones en la secuencia, es decir . En el segundo paso, 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 la secuencia de observación completa:
El último paso se deriva de una aplicación de la regla de Bayes y la independencia condicional de y dado .
Como se describió anteriormente, el algoritmo consta de tres pasos:
- calcular probabilidades de avance
- calcular probabilidades hacia atrás
- 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 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 las observaciones anteriores 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 momento. Sin embargo, no se puede utilizar para encontrar la secuencia de estados más probable (consulte el algoritmo de Viterbi ).
Probabilidades futuras
La siguiente descripción utilizará matrices de valores de probabilidad en lugar de distribuciones de probabilidad, aunque en general el algoritmo hacia adelante y hacia atrás se puede aplicar a modelos de probabilidad continuos y discretos.
Transformamos las distribuciones de probabilidad relacionadas con un modelo de Markov oculto dado en notación matricial de la siguiente manera. Las probabilidades de transición de una variable aleatoria dada La representación de todos los estados posibles en el modelo de Markov oculto estará representada por la matriz donde el índice de la columna representará el estado de destino y el índice de fila representa el estado de inicio. Una transición del estado fila-vector al estado de vector de fila incremental está escrito como . El siguiente ejemplo representa un sistema en el que la probabilidad de permanecer en el mismo estado después de cada paso es del 70% y la probabilidad de pasar al otro estado es del 30%. La matriz de transición es entonces:
En un modelo de Markov típico, multiplicaríamos un vector de estado por esta matriz para obtener las probabilidades del estado subsiguiente. En un modelo de Markov oculto, el estado es desconocido y, en cambio, observamos eventos asociados con los posibles estados. Una matriz de eventos de la forma:
proporciona las probabilidades de observar eventos en 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 un 10% de probabilidad de ocurrir en este estado. Por el contrario, el evento 1 solo se observará el 20% del tiempo si estamos en el estado 2 y el evento 2 tiene un 80% de posibilidades de ocurrir. Dado un vector fila arbitrario que describe el estado del sistema (), la probabilidad de observar el evento j es entonces:
La probabilidad de que un estado dado conduzca al evento j observado se puede representar en forma de matriz multiplicando el vector fila de estado () con una matriz de observación () que contiene solo entradas diagonales. Continuando con el ejemplo anterior, la matriz de observación para el evento 1 sería:
Esto nos permite calcular el nuevo vector de estado de probabilidades no normalizadas a través de la regla de Bayes, ponderado por la probabilidad de que cada elemento de evento generado 1 como:
Ahora podemos hacer que este procedimiento general sea específico para nuestra serie de observaciones. Suponiendo un vector de estado inicial, (que se puede optimizar como parámetro a través de repeticiones del procedimiento de avance y retroceso), comenzamos con , luego actualizando la distribución del estado y la ponderación por la probabilidad de la primera observación:
Este proceso se puede llevar a cabo con observaciones adicionales utilizando:
Este valor es el vector de probabilidad no normalizado hacia adelante. La i-ésima entrada de este vector proporciona:
Por lo general, normalizaremos el vector de probabilidad en cada paso para que sus entradas sumen 1. Por lo tanto, se introduce un factor de escala en cada paso de manera que:
dónde 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:
Esto nos permite interpretar el vector de probabilidad escalado como:
Por tanto, encontramos que el producto de los factores de escala nos proporciona la probabilidad total de observar la secuencia dada hasta el momento t y que el vector de probabilidad escalado nos proporciona la probabilidad de estar en cada estado en ese momento.
Probabilidades hacia atrás
Se puede construir un procedimiento similar para encontrar probabilidades hacia atrás. Estos pretenden proporcionar las probabilidades:
Es decir, ahora queremos asumir que comenzamos en un estado particular (), y ahora estamos interesados en la probabilidad de observar todos los eventos futuros desde este estado. Dado que el estado inicial se asume como dado (es decir, la probabilidad previa de este estado = 100%), comenzamos con:
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:
Si bien también podríamos normalizar este vector para que sus entradas sumen uno, esto no se suele hacer. 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 (asumiendo valores previos uniformes para el vector de estado final ). Sin embargo, es más común escalar este vector usando el mismo constantes utilizadas en los cálculos de probabilidad directa. no está escalado, pero las operaciones posteriores usan:
dónde representa el vector escalado anterior. Este resultado es que el vector de probabilidad escalado está relacionado con las probabilidades hacia atrás por:
Esto es útil porque nos permite encontrar la probabilidad total de estar en cada estado en un momento dado, t, multiplicando estos valores:
Para entender esto, notamos que proporciona la probabilidad de observar los eventos dados de una manera que pasa por el estado en el momento t. Esta probabilidad incluye las probabilidades hacia adelante que cubren todos los eventos hasta el momento 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 lo 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.
Los valores por lo tanto, proporcione la probabilidad de estar en cada estado en el tiempo t. Como tales, son útiles para determinar el estado más probable en cualquier momento. El término "estado más probable" es algo ambiguo. Si bien el estado más probable es el que tiene más probabilidades de ser correcto en un punto dado, la secuencia de estados probables individualmente no es probable que sea la secuencia más probable. Esto se debe a que las probabilidades de cada punto se calculan independientemente unas de otras. No tienen en cuenta las probabilidades de transición entre estados, por lo que es posible obtener estados en dos momentos (t y t + 1) que son ambos más probables en esos puntos de tiempo pero que tienen muy poca probabilidad de ocurrir juntos, es decir. La secuencia de estados más probable que produjo una secuencia de observación se puede encontrar utilizando el algoritmo de Viterbi .
Ejemplo
Este ejemplo toma como base el mundo paraguas en Russell & Norvig 2010 Capítulo 15 págs. 567 en el que nos gustaría inferir el clima dada la observación de otra persona que lleva o no un paraguas. Suponemos dos estados posibles para el clima: estado 1 = lluvia, estado 2 = sin lluvia. Suponemos que el clima tiene un 70% de posibilidades de permanecer igual todos los días y un 30% de posibilidades de cambiar. Las probabilidades de transición son entonces:
También asumimos que cada estado genera uno de dos eventos posibles: evento 1 = paraguas, evento 2 = sin paraguas. Las probabilidades condicionales de que ocurran en cada estado vienen dadas por la matriz de probabilidad:
Luego observamos la siguiente secuencia de eventos: {paraguas, paraguas, sin paraguas, paraguas, paraguas} que representaremos en nuestros cálculos como:
Tenga en cuenta que difiere de los demás debido a la observación "sin paraguas".
Al calcular las probabilidades de avance, comenzamos con:
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, usaremos la transposición de la matriz para que los cálculos a continuación sean más fáciles de leer. Luego, nuestros cálculos se escriben en la forma:
en vez de:
Observe que la matriz de transformación también se transpone, pero en nuestro ejemplo la transposición es igual a la matriz original. Realizar estos cálculos y normalizar los resultados proporciona:
Para las probabilidades hacia atrás, comenzamos con:
Entonces podemos calcular (usando las observaciones en orden inverso y normalizando con diferentes constantes):
Finalmente, calcularemos los valores de probabilidad suavizados. Estos resultados también deben escalarse para que sus entradas sumen 1 porque no escalamos las probabilidades hacia atrás con lase ha encontrado antes. Por tanto, los vectores de probabilidad hacia atrás de arriba representan en realidad la probabilidad de cada estado en el tiempo t dadas las observaciones futuras. Debido a que estos vectores son proporcionales a las probabilidades reales hacia atrás, el resultado debe escalarse una vez más.
Observe que el valor de es igual a y eso es igual a . Esto se sigue naturalmente porque ambos y comience con priores uniformes sobre los vectores de estado inicial y final (respectivamente) y tenga en cuenta todas las observaciones. Sin emabargo, solo será igual a cuando nuestro vector de estado inicial representa un anterior uniforme (es decir, todas las entradas son iguales). Cuando este no es el casodebe combinarse con el vector de estado inicial para encontrar el estado inicial más probable. Por tanto, encontramos que las probabilidades de avance 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 de avance y retroceso solo necesitan combinarse para inferir los estados más probables entre los puntos inicial y final.
Los cálculos anteriores revelan que el estado meteorológico más probable todos los días, excepto el tercero, fue "lluvia". Sin embargo, nos dicen más que esto, ya que ahora proporcionan una forma de cuantificar las probabilidades de cada estado en diferentes momentos. Quizás lo más importante, nuestro valor encuantifica nuestro conocimiento del vector de estado al final de la secuencia de observación. Luego, podemos usar esto para predecir la probabilidad de los diversos estados climáticos mañana, así como la probabilidad de observar un paraguas.
Actuación
El algoritmo de avance-retroceso se ejecuta con complejidad de tiempo en el espacio , dónde es la longitud de la secuencia de tiempo y es el número de símbolos en el alfabeto estatal. [1] El algoritmo también puede ejecutarse en un espacio constante con complejidad temporal.volviendo a calcular los valores en cada paso. [2] A modo de comparación, un procedimiento de fuerza bruta generaría todas lassecuencias de estado y calcular la probabilidad conjunta de cada secuencia de estado con la serie de eventos observada, que tendría complejidad de tiempo . La fuerza bruta es intratable para problemas realistas, ya que el número de posibles secuencias de nodos ocultos suele ser extremadamente alto.
Una mejora del algoritmo general hacia adelante y hacia atrás, llamado algoritmo Island , intercambia un uso de memoria más pequeño por un tiempo de ejecución más largo, lo que requiere tiempo y memoria. Además, es posible invertir el modelo de proceso para obtener un espacio, algoritmo de tiempo, aunque el proceso invertido puede no existir o estar mal condicionado . [3]
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]
Pseudocódigo
algoritmo forward_backward es entrada: guessStatesalida int sequenceIndex : resultado si sequenceIndex está más allá del final de la secuencia , devuelve 1 si ( guessState , sequenceIndex ) se ha visto antes, luego 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, sequenceIndex + 1) guardar resultado para ( guessState , sequenceIndex ) devolver resultado
Ejemplo de Python
Dado HMM (como en el algoritmo de Viterbi ) representado en el lenguaje de programación Python :
estados = ( 'Saludable' , 'Fiebre' ) end_state = 'E' observaciones = ( 'normal' , 'frío' , 'mareado' ) start_probability = { 'Saludable' : 0.6 , 'Fiebre' : 0.4 } transición_probabilidad = { 'Saludable' : { 'Saludable' : 0.69 , 'Fiebre' : 0.3 , 'E' : 0.01 }, 'Fiebre' : { 'Saludable' : 0.4 , 'Fiebre' : 0.59 , 'E' : 0.01 } , } emisión_probabilidad = { '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 hacia adelante y hacia atrás de esta manera:
def fwd_bkw ( observaciones , estados , start_prob , trans_prob , emm_prob , end_st ): "" "Algoritmo hacia adelante-hacia atrás." "" # Parte delantera del algoritmo fwd = [] para i , observación_i en enumerate ( observaciones ): f_curr = { } para st en estados : 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 ] para k en estados ) f_curr [ st ] = emm_prob [ st ] [ observación_i ] * prev_f_sum fwd . añadir ( f_curr ) f_prev = f_curr p_fwd = sum ( f_curr [ k ] * trans_prob [ k ] [ end_st ] para k en estados ) # Parte hacia atrás del algoritmo bkw = [] para i , observación_i_plus en enumerate ( invertido ( observaciones [ 1 :] + ( None ,))): b_curr = {} para st en estados : if i == 0 : # caso base para la parte hacia atrás b_curr [ st ] = trans_prob [ st ] [ end_st ] else : b_curr [ st ] = sum ( trans_prob [ st ] [ l ] * emm_prob [ l ] [ observación_i_plus ] * b_prev [ l ] para l en estados ) bkw . insert ( 0 , b_curr ) b_prev = b_curr p_bkw = sum ( start_prob [ l ] * emm_prob [ l ] [ observaciones [ 0 ]] * b_curr [ l ] para l en estados ) # Fusionando las dos partes posterior = [] para i en rango ( len ( observaciones )): posterior . añadir ({ st : fwd [ i ] [ st ] * bkw [ i ] [ st ] / p_fwd para st en estados }) afirmar p_fwd == p_bkw return fwd , bkw , posterior
La función fwd_bkw
toma los siguientes argumentos: x
es la secuencia de observaciones, por ejemplo ['normal', 'cold', 'dizzy']
; states
es el conjunto de estados ocultos; a_0
es la probabilidad de inicio; a
son las probabilidades de transición; y e
son las probabilidades de emisión.
Para simplificar el código, asumimos que la secuencia de observación x
no está vacía y que a[i][j]
y e[i][j]
está definida para todos los estados i, j.
En el ejemplo de ejecución, el algoritmo de avance y retroceso se utiliza de la siguiente manera:
def ejemplo (): retorno fwd_bkw ( observaciones , estados , start_probability , transition_probability , emission_probability , end_state )
>>> 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.028120319999999997} {' 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}
Ver también
Referencias
- ^ Russell y Norvig 2010 págs. 579
- ^ Russell y Norvig 2010 págs. 575
- ^ Carpeta, John; Murphy, Kevin; Russell, Stuart (1997). "Inferencia espacial-eficiente en redes probabilísticas dinámicas" (PDF) . Int'l, Joint Conf. Sobre inteligencia artificial . Consultado el 8 de julio de 2020 .
- ^ Russell y Norvig 2010 Figura 15.6 págs. 580
- Lawrence R. Rabiner , Un tutorial sobre modelos ocultos de Markov y aplicaciones seleccionadas en el reconocimiento de voz. Actas del IEEE , 77 (2), p. 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 hacia adelante y hacia atrás (hoja de cálculo y artículo con un recorrido paso a paso)
- Tutorial de modelos ocultos de Markov, incluido el algoritmo hacia adelante y hacia atrás
- Colección de algoritmos de IA implementados en Java (incluido HMM y el algoritmo de avance-retroceso)