Modelos de Markov y modelos ocultos de Markov

Un sistema cambiante necesita un estado para cada momento y una regla para pasar al momento siguiente. Una cadena de Markov de tiempo discreto registra estos estados en pasos separados por intervalos iguales. Elige conjuntamente el estado y el paso de tiempo: el tiempo meteorológico diario y la ubicación de un robot cada segundo describen procesos diferentes.

Qué debe contener el estado actual

La propiedad de Markov de primer orden es

Una vez conocido el estado actual, los estados anteriores no aportan información sobre el siguiente. Esto es independencia condicional, no independencia entre estados consecutivos. Conocer el tiempo de ayer puede ayudar a predecir el de mañana cuando se desconoce el de hoy.

Una cadena necesita una distribución inicial, $P(X_1)$, y un modelo de transición. Usamos transiciones homogéneas en el tiempo: en cada paso se aplican las mismas probabilidades. Algunos textos de IA llaman a esto supuesto de estacionariedad. En teoría de la probabilidad, un proceso estacionario tiene distribuciones conjuntas que no cambian al desplazar el tiempo; unas transiciones fijas por sí solas no garantizan esto. Sí lo garantiza iniciar una cadena homogénea en el tiempo en una distribución estacionaria.

Interpreta una matriz de transición

Para el tiempo meteorológico, sean los estados Soleado (S) y Nublado (C). Las filas indican el estado actual y las columnas, el estado siguiente:

Desde Soleado, el día siguiente es soleado con probabilidad 0,8 y nublado con probabilidad 0,2. Desde Nublado, esas probabilidades son 0,4 y 0,6. Cada fila suma 1 porque enumera todos los destinos desde un estado inicial. Las columnas no tienen por qué sumar 1. Un diagrama de estados representa la misma tabla con flechas, incluidas las que vuelven al mismo estado.

Algunos libros usan la transpuesta de esta convención. Antes de calcular, lee la definición de una entrada: aquí $T_{ij}=P(X_{t+1}=j\mid X_t=i)$. Un conjunto correcto de números usado con la orientación equivocada da una predicción incorrecta.

Multiplica a lo largo de un camino

Un camino concreto usa su probabilidad inicial y una transición por cada movimiento:

Si es seguro que el día 1 es soleado, el camino Soleado, Soleado, Nublado, Nublado tiene probabilidad

El primer movimiento aporta 0,8, el cambio aporta 0,2 y permanecer en Nublado aporta 0,6. Multiplicar las frecuencias diarias por separado descartaría los vínculos entre días. En una red bayesiana, esos vínculos son las flechas en $X_1\to X_2\to X_3\to \cdots$.

Conserva suficiente historia en el estado

Un modelo de segundo orden depende de los dos últimos valores. Conviértelo en un modelo de primer orden definiendo el estado como (ayer, hoy). Dos valores meteorológicos dan entonces cuatro pares posibles. Una transición desde (Soleado, Nublado) solo puede conducir a un par que comience por Nublado, porque los pares adyacentes deben solaparse. Para un proceso de orden $k$, almacena juntos los últimos $k$ valores; los algoritmos siguen siendo de primer orden, mientras que el número de estados combinados crece.

Una cadena ocupa un estado en cada instante, pero puede que no sepas cuál. Una distribución de estados almacena esa incertidumbre como un vector fila. Sus entradas indican las probabilidades de los estados posibles, no fracciones de tiempo dentro de un solo paso.

Suma todas las rutas hacia un destino

Para predecir Soleado mañana, considera las dos formas de llegar allí: hoy puede ser Soleado o Nublado. Pondera cada transición por la probabilidad de su estado inicial:

Para el vector completo, esto es $p_{t+1}=p_{t}T$. Después de $k$ movimientos, $p_{t+k}=p_t{T}^k$. Esta actualización se denomina a veces algoritmo de avance simplificado, la versión del filtrado de HMM sin evidencia.

Resuelve la cadena meteorológica

Usa las filas (0,8; 0,2) desde Soleado y (0,4; 0,6) desde Nublado. Comienza con un día ciertamente soleado: $p_1=(1,0)$. Un movimiento da $p_2=(\mathrm{0,8};\mathrm{0,2})$. Para el día 3, la contribución a Soleado es $\mathrm{0,8}\times \mathrm{0,8}=\mathrm{0,64}$ desde Soleado y $\mathrm{0,2}\times \mathrm{0,4}=\mathrm{0,08}$ desde Nublado. Súmalas para obtener 0,72. Las contribuciones a Nublado son $\mathrm{0,8}\times \mathrm{0,2}=\mathrm{0,16}$ y $\mathrm{0,2}\times \mathrm{0,6}=\mathrm{0,12}$, lo que da 0,28.

Así, $p_3=(\mathrm{0,72};\mathrm{0,28})$. Una actualización más da $P(X_4=S)=\mathrm{0,72}\times \mathrm{0,8}+\mathrm{0,28}\times \mathrm{0,4}=\mathrm{0,688}$ y $P(X_4=C)=\mathrm{0,312}$. Conserva los valores sin redondear entre pasos y redondea los resultados mostrados al final.

Comprueba el significado y la orientación

Cada resultado debe ser no negativo y sumar 1. Según la convención de filas, coloca la distribución a la izquierda. Usar $T{p}_1^{𝖳}$ da en cambio la columna (0,8; 0,4), cuyo total es 1,2. Ese cálculo selecciona las probabilidades de llegar a Soleado desde dos estados iniciales distintos; no distribuye una creencia inicial entre los destinos.

El valor 0,72 en el día 3 significa que aproximadamente el 72 % de muchas ejecuciones independientes con un día 1 soleado tendrán un día 3 soleado. No describe ni un patrón meteorológico fijo y repetitivo ni un día que sea soleado durante el 72 % del tiempo.

Por qué la predicción sigue siendo manejable

Una actualización densa sobre $S$ estados cuesta $O(S^2)$ operaciones. Resume todos los caminos anteriores en el vector actual, por lo que el costo por movimiento permanece igual a medida que avanza el tiempo. Enumerar cada camino desde un inicio conocido requeriría, en cambio, $S^{t-1}$ caminos en el instante $t$.

Para esta cadena meteorológica, las probabilidades sucesivas de Soleado se aproximan a $2\mathrm{/}3$. Si $s_t=P(X_t=S)$, entonces $s_{t+1}=\mathrm{0,4}+\mathrm{0,4}{s}_t$. Al restar $2\mathrm{/}3$ se observa que la distancia se reduce por un factor de 0,4 en cada paso. Otras cadenas pueden comportarse de otra manera; la convergencia requiere las condiciones estudiadas con las distribuciones estacionarias.

También puedes simular una ejecución. Extrae el estado inicial y después extrae de la fila de transición correspondiente al estado ocupado en ese momento. Desde Soleado, una extracción aleatoria uniforme inferior a 0,8 selecciona Soleado; una extracción de al menos 0,8 selecciona Nublado. Repetir muchas ejecuciones estima la misma distribución predicha e introduce la idea de muestreo utilizada por los filtros de partículas.

Una distribución puede permanecer inalterada aunque las ejecuciones individuales sigan cambiando de estado. Una distribución estacionaria describe este equilibrio. Es útil para las predicciones a largo plazo, pero su existencia por sí sola no indica si una cadena se aproxima a ella desde un punto de partida concreto.

Resuelve las ecuaciones de balance

Un vector fila estacionario satisface $\pi =\pi T$ junto con ${\sum }_j{\pi }_j=1$ y tiene entradas no negativas. Para la cadena meteorológica, la probabilidad que fluye de Soleado a Nublado debe equilibrar la que fluye de vuelta:

La primera ecuación da ${\pi }_S=2{\pi }_C$. Al sustituir se obtiene $3{\pi }_C=1$, por lo que $\pi =(2\mathrm{/}3,1\mathrm{/}3)$. Para una cadena de dos estados con probabilidades de cambio $a$ del estado 1 al 2 y $b$ del 2 al 1, ${\pi }_1=b\mathrm{/}(a+b)$ cuando $a+b>0$.

Para más estados, escribe una ecuación de flujo entrante por estado. Sustituye una por la ecuación que establece que la suma es 1 y resuelve el sistema lineal. Las ecuaciones de balance por sí solas dejan la escala indeterminada. Por último, multiplica el vector propuesto por la matriz para comprobarlo.

Para las estaciones de bicicletas compartidas A, B, C, toma las filas (0,6; 0,2; 0,2), (0,1; 0,8; 0,1) y (0,2; 0,2; 0,6). La solución es (0,25; 0,5; 0,25). Por ejemplo, la probabilidad entrante en B es $\mathrm{0,25}(\mathrm{0,2})+\mathrm{0,5}(\mathrm{0,8})+\mathrm{0,25}(\mathrm{0,2})=\mathrm{0,5}$. Una probabilidad uniforme no superaría esta comprobación.

Separa tres preguntas

Irreducible significa que desde cada estado se puede llegar a cualquier otro, posiblemente mediante varios movimientos. Aperiódica significa que los retornos no están restringidos a un ciclo fijo de más de un paso. La matriz meteorológica tiene todas sus entradas positivas, por lo que se cumplen ambas condiciones. En una cadena finita irreducible, las probabilidades estacionarias también dan las fracciones de pasos a largo plazo que se pasan en cada estado, incluso cuando la periodicidad impide la convergencia de la distribución en un instante dado.

Dos contraejemplos reveladores

Si dos estados siempre se intercambian, la distribución desde un primer estado cierto alterna entre (1, 0) y (0, 1). El único vector estacionario es (0,5; 0,5), pero estas predicciones nunca se aproximan a él. En una ejecución larga, cada estado sigue ocupando la mitad de los pasos.

Si ambos estados son absorbentes, cada uno permanece donde está para siempre. Todo vector (q, 1 − q) es estacionario, por lo que no hay un equilibrio único compartido por todos los inicios. Estos ejemplos muestran por qué la unicidad, la convergencia y los promedios temporales requieren comprobaciones separadas.

La distribución inicial describe el comienzo; solo es igual a una distribución estacionaria cuando se comienza en equilibrio. Las probabilidades de transición fijas describen la ley del modelo, no su distribución actual. PageRank usa probabilidades estacionarias para ordenar páginas en un modelo de navegación aleatoria. Los métodos de Monte Carlo mediante cadenas de Markov construyen una cadena con una distribución estacionaria deseada para que su ejecución a largo plazo proporcione muestras.

Una lectura de sensor aporta evidencia sobre un estado sin revelarlo perfectamente. En un modelo oculto de Markov, o HMM, el estado cambia con el tiempo y cada estado produce una observación. Un robot puede saber qué indicó su sensor de distancia mientras sigue sin tener certeza sobre su posición.

Especifica tres modelos de probabilidad

Un HMM necesita una distribución inicial de estados, un modelo de transición y un modelo de sensores:

El estado oculto es una variable discreta. El modelo de sensores, también llamado modelo de emisión o de observación, indica la verosimilitud de cada observación en cada estado. Asignamos una distribución a priori directamente a $X_1$ y observamos allí $E_1$. Los textos que comienzan con un $X_0$ no observado realizan, en cambio, una transición antes de la primera observación.

El estado cumple la propiedad de Markov de primer orden. La observación en un instante depende solo del estado en ese instante: $P(E_t\mid X_{1:t},E_{1:t-1})=P(E_t\mid X_t)$. En una red bayesiana, dibuja una cadena de estados ocultos y añade una flecha desde cada estado hasta su observación.

Construye el modelo del panel solar

El tiempo oculto es Soleado o Nublado, con filas de transición (0,8; 0,2) y (0,4; 0,6). Ambos estados iniciales tienen probabilidad 0,5. La producción diaria del panel es Alta o Baja:

Cada fila de sensores suma 1. Un día nublado también puede producir una producción Alta, por lo que Alta no identifica Soleado con certeza. Asimismo, $P(L\mid C)=\mathrm{0,7}$ es una afirmación sobre la producción en días nublados. Para encontrar $P(C\mid L)$ también se necesitan la distribución a priori y la regla de Bayes.

Calcula la probabilidad conjunta de estados y evidencia

Para un camino de estados y una secuencia de observaciones concretos,

Para Nublado, Nublado, Soleado con Baja, Baja, Alta, comienza con $\mathrm{0,5}\times \mathrm{0,7}=\mathrm{0,35}$. Permanecer en Nublado y observar Baja da $\mathrm{0,35}\times \mathrm{0,6}\times \mathrm{0,7}=\mathrm{0,147}$. Cambiar a Soleado y observar Alta da $\mathrm{0,147}\times \mathrm{0,4}\times \mathrm{0,8}=\mathrm{0,04704}$.

Las observaciones pueden ser dependientes aunque no haya flechas directas entre ellas. La persistencia del tiempo nublado hace que las lecturas sucesivas de Baja tiendan a darse juntas. Condicionar respecto de los estados ocultos elimina esa dependencia. La evidencia actualiza la creencia de quien observa; observar Baja no hace que el tiempo cambie por sí mismo.

Elige la pregunta de inferencia

Los mismos tres modelos sirven para las cinco tareas. Lo que cambia es qué variables conservas, cuáles eliminas por suma y si sumas los caminos o seleccionas la mayor puntuación de un camino.

La definición del estado determina qué puede recordar el modelo. Un modelo temporal útil conserva la información necesaria para predecir el siguiente estado y, al mismo tiempo, mantiene la inferencia a un costo asumible. Sus probabilidades también deben reflejar los datos y los fallos de los sensores que encontrará.

Elige suficiente información de estado

La posición por sí sola puede ser insuficiente para un objeto con inercia: las posiciones anteriores revelan su dirección. Añadir la velocidad permite que el estado actual explique esa dirección. Añade la estación del año si la dinámica depende de ella. Estas elecciones hacen más razonable la aproximación de Markov; son decisiones sobre qué información se transmite hacia delante.

Una magnitud continua puede situarse en una malla. Las temperaturas de 10 °C a 20 °C en incrementos de 0,1 °C dan 101 valores, incluidos ambos extremos. Una separación más fina aumenta el número de estados. Combinar varias magnitudes en mallas multiplica sus números de valores, y la inferencia exacta densa cuesta $O(S^2)$ por paso.

Cuenta los parámetros independientes

Una fila categórica con $r$ entradas tiene $r-1$ parámetros libres porque la última entrada queda fijada por su suma. Con $S$ estados y $O$ valores de observación, un HMM sin restricciones necesita, por tanto,

parámetros libres: para la distribución a priori, las transiciones y las emisiones. El modelo solar de dos estados y dos valores de producción necesita $1+2+2=5$. Contar todas las entradas de las tablas equivaldría a contar las restricciones de suma de las filas como opciones adicionales.

Factoriza el estado con una red bayesiana dinámica

Una red bayesiana dinámica (DBN) mantiene varias variables de estado y da a cada una sus propios nodos padre. Puede expresar dependencias locales sin construir una enorme tabla de transición plana. Veinte variables booleanas tienen $2^{20}=1048576$ estados conjuntos; una tabla de transición plana tiene $2^{40}$ entradas. Si cada variable booleana del siguiente paso tiene tres nodos padre booleanos, su tabla necesita ocho probabilidades, por lo que las 20 necesitan $20\times 8=160$.

Una DBN discreta puede convertirse en un HMM plano tratando una asignación completa como un estado. El almacenamiento factorizado es compacto, pero la inferencia exacta puede seguir siendo costosa cuando las dependencias acoplan muchas variables. Los métodos de partículas pueden muestrear estas asignaciones directamente.

Estima las filas a partir de datos

Cuando los estados están etiquetados, usa conteos condicionales. Cuarenta sucesores Soleado de 50 transiciones registradas desde Soleado dan $P(S\to S)=40\mathrm{/}50=\mathrm{0,8}$. El denominador cuenta las transiciones que salen de Soleado, no todos los días del registro. Un estado al final de un registro no tiene sucesor observado.

Los conteos de cero producen probabilidades de máxima verosimilitud iguales a cero. La corrección de sumar uno da a cada destino un pseudoconteo y aumenta el total de la fila en consecuencia. Esto evita descartar una transición solo porque un registro de entrenamiento pequeño no la incluyó. Cuando los estados están ocultos, Baum–Welch alterna conteos esperados suavizados con la reestimación de parámetros.

Da cabida a los fallos en el modelo de sensores

Si todos los estados posibles asignan verosimilitud cero a una lectura, una actualización tiene un total de cero y no puede normalizarse. Un pequeño componente de valores atípicos puede dar cierta probabilidad a lecturas inusuales. Una mezcla normalizada tiene la forma $P(e\mid x)=\mathrm{0,99}{P}_{\mathrm{r}\mathrm{e}\mathrm{g}\mathrm{u}\mathrm{l}\mathrm{a}\mathrm{r}}(e\mid x)+\mathrm{0,01}{P}_{\mathrm{o}\mathrm{u}\mathrm{t}\mathrm{l}\mathrm{i}\mathrm{e}\mathrm{r}}(e)$. Ambas distribuciones componentes deben estar normalizadas.

El efecto de una lectura depende de las razones de verosimilitudes entre estados. Las verosimilitudes iguales dejan la creencia predicha sin cambios después de la normalización. Una verosimilitud pequeña en todos los estados aún puede ser informativa si las verosimilitudes difieren mucho en términos relativos.

El filtrado estima el estado oculto actual usando todas las observaciones disponibles hasta el momento. Su resultado es una distribución de creencia, $f_t(x)=P(X_t=x\mid e_{1:t})$. Actualizas esta distribución compacta cuando llega una nueva lectura, sin conservar todos los caminos anteriores posibles.

Predice, pondera y normaliza

Para un paso posterior, primero desplaza la creencia por el modelo de transición:

Después pondera cada destino por la verosimilitud de la nueva observación y normaliza:

La predicción describe a dónde puede haberse desplazado el estado. La actualización con la evidencia es la regla de Bayes en el nuevo instante. Con una distribución a priori sobre $X_1$, comienza por ponderarla con la primera observación; no hay movimiento antes de ella.

Día 1: observa Baja

Usa el modelo del panel solar: distribución a priori (0,5; 0,5), filas de transición (0,8; 0,2) y (0,4; 0,6), y verosimilitudes de Baja (0,2; 0,7). La ponderación da $\mathrm{0,5}(\mathrm{0,2})=\mathrm{0,10}$ para Soleado y $\mathrm{0,5}(\mathrm{0,7})=\mathrm{0,35}$ para Nublado. El total es 0,45. Divide cada peso entre ese total para obtener $f_1=(2\mathrm{/}9,7\mathrm{/}9)\approx (\mathrm{0,2222};\mathrm{0,7778})$.

Día 2: observa Baja de nuevo

La predicción da ${\bar{f}}_2(S)=(2\mathrm{/}9)(\mathrm{0,8})+(7\mathrm{/}9)(\mathrm{0,4})=22\mathrm{/}45\approx \mathrm{0,4889}$. Nublado tiene probabilidad $23\mathrm{/}45\approx \mathrm{0,5111}$. Los nuevos pesos son $22\mathrm{/}225\approx \mathrm{0,0978}$ y $161\mathrm{/}450\approx \mathrm{0,3578}$. Su total es $41\mathrm{/}90\approx \mathrm{0,4556}$, lo que produce $f_2=(44\mathrm{/}205,161\mathrm{/}205)\approx (\mathrm{0,2146};\mathrm{0,7854})$.

La segunda producción Baja solo aumenta ligeramente la creencia en Nublado. El movimiento hacia el equilibrio de la cadena, que favorece Soleado, compite con la nueva evidencia favorable a Nublado. Aplicar Baja directamente a la creencia de ayer pasaría por alto ese movimiento.

Día 3: observa Alta

Predice ${\bar{f}}_3=(498\mathrm{/}1025,527\mathrm{/}1025)\approx (\mathrm{0,4859};\mathrm{0,5141})$. Alta tiene verosimilitudes (0,8; 0,3), por lo que los pesos son aproximadamente (0,3887; 0,1542). Divide entre su total, aproximadamente 0,5429, para obtener $f_3\approx (\mathrm{0,7159};\mathrm{0,2841})$.

Alta es $\mathrm{0,8}\mathrm{/}\mathrm{0,3}\approx \mathrm{2,67}$ veces más probable en Soleado que en Nublado. Esa razón de verosimilitudes desplaza las probabilidades relativas hacia Soleado. Una verosimilitud alta por sí sola es menos informativa que su tamaño en relación con la verosimilitud del estado competidor.

Mantén fiable un filtro en línea

Un paso denso cuesta $O(S^2)$ en tiempo y almacena $O(S)$ entradas de creencia, independientemente de la longitud de la historia. Esto es eliminación exacta de variables: cada estado pasado se elimina por suma a medida que avanzas.

Normaliza en cada observación. Sin ajustar la escala, el vector almacena probabilidades conjuntas de estado y evidencia, que pueden disminuir por debajo del rango de representación en coma flotante. Conserva por separado los totales descartados si necesitas la verosimilitud de la evidencia. Un total de cero requiere recuperar el modelo o la cobertura de las partículas; la división no puede solucionarlo.

Nuestra fórmula con vectores fila es $f_{t+1}\propto (f_{t}T)O_{t+1}$, donde la matriz diagonal contiene las nuevas verosimilitudes. Para creencias expresadas como columnas, la equivalente es $f_{t+1}\propto O_{t+1}{T}^{𝖳}{f}_t$. Mezclar estas convenciones es una fuente frecuente de errores.

Una creencia filtrada permite responder dos preguntas útiles: qué podría suceder después y hasta qué punto explicó el modelo las lecturas ya observadas. Ambas usan los mismos modelos de transición y de sensores, pero las respuestas describen magnitudes aleatorias distintas.

Predice sin lecturas futuras

Para una predicción a $k$ pasos, aplica la matriz de transición $k$ veces a la última creencia filtrada:

En un paso futuro no observado no corresponde hacer una actualización con una observación. Después de que el modelo solar observe Baja, Baja, Alta, la creencia del día 3 es aproximadamente (0,7159; 0,2841). Una predicción da $P(X_4=S)\approx \mathrm{0,7159}(\mathrm{0,8})+\mathrm{0,2841}(\mathrm{0,4})=\mathrm{0,6864}$. Al continuar con valores sin redondear se obtienen las probabilidades de Soleado 0,6745; 0,6698; 0,6679 y 0,6672.

Estas se aproximan a $2\mathrm{/}3$. La cadena pierde gradualmente su dependencia de la última creencia. El tiempo de mezcla indica cuántos pasos se necesitan para quedar dentro de una distancia elegida respecto del equilibrio desde cualquier estado inicial. Una predicción cercana al equilibrio aún conserva una pequeña influencia de la evidencia actual; no es un reinicio exacto.

La predicción no tiene por qué aumentar la incertidumbre en cada paso. Desde (0,5; 0,5), esta cadena meteorológica predice (0,6; 0,4), una distribución más concentrada. La convergencia se refiere a la pérdida de dependencia de la creencia inicial, no a una regla que obligue a las predicciones a volverse uniformes.

Predice una observación

Una predicción de la producción promedia la verosimilitud del sensor sobre los estados predichos:

Para Alta en el día 4, usa la predicción del estado del día 4, no el filtrado del día 3: $\mathrm{0,6864}(\mathrm{0,8})+\mathrm{0,3136}(\mathrm{0,3})\approx \mathrm{0,6432}$. La probabilidad de Soleado y la de producción Alta son diferentes porque ambos estados meteorológicos pueden producir una producción Alta.

Conserva los totales del filtrado

Antes de normalizar cada actualización, su total es la probabilidad de esa observación dadas las anteriores. Llámala $c_t=P(e_t\mid e_{1:t-1})$. La regla de la cadena da

Para Baja, Baja, Alta, los totales son aproximadamente 0,45; 0,4556 y 0,5429. Su producto, calculado antes de redondear, es 0,1113. Es una suma sobre todos los caminos ocultos compatibles con la evidencia. El mejor camino por sí solo aporta 0,04704, solo una parte del total.

Un recorrido hacia delante sin normalizar da la misma verosimilitud al sumar sus entradas finales. Un recorrido normalizado es más estable, siempre que se conserven los totales. En secuencias largas, almacena $\log P(e_{1:t})={\sum }_i\log c_i$ en lugar de multiplicar valores diminutos. Aquí el logaritmo natural es aproximadamente −2,196.

Compara modelos con la misma evidencia

Una verosimilitud mide hasta qué punto un modelo explica una secuencia concreta de observaciones. Para comparar HMM candidatos de palabras con la misma grabación, calcula la puntuación de esa grabación con cada modelo y combínala con las probabilidades a priori de las palabras al obtener sus probabilidades a posteriori. Las secuencias más largas suelen tener verosimilitudes sin ajustar menores, por lo que un número menor procedente de una grabación más larga no demuestra por sí solo que el modelo sea peor.

Una observación posterior puede cambiar lo que crees sobre un estado anterior. El suavizado estima $P(X_k\mid e_{1:t})$ para $k<t$. Es útil al reconstruir una trayectoria registrada o cuando una aplicación puede esperar brevemente antes de comunicar una estimación pasada.

Divide la evidencia en el instante de interés

El filtrado ya ha resumido la evidencia hasta el instante $k$ como $f_k(x)=P(X_k=x\mid e_{1:k})$. Un mensaje hacia atrás resume las observaciones restantes como una verosimilitud, $b_k(x)=P(e_{k+1:t}\mid X_k=x)$. Combínalos estado por estado:

Normaliza los productos entre estados. La evidencia posterior se pondera según lo plausible que sería desde cada estado candidato en el instante $k$.

Propaga la verosimilitud futura hacia atrás

En el último instante no hay observaciones posteriores, por lo que $b_t(x)=1$ para cada estado. Retroceder un paso da

Para cada sucesor posible, multiplica la probabilidad de llegar a él, la verosimilitud de su observación y la verosimilitud futura restante. Después suma sobre los sucesores. Un mensaje hacia atrás es una función de verosimilitud sobre los posibles estados iniciales, no una distribución de estados; sus entradas no tienen que sumar 1.

Suaviza el día 2 en el ejemplo solar

Las observaciones son Baja, Baja, Alta. Después de las dos lecturas de Baja, la creencia filtrada del día 2 es aproximadamente (0,2146; 0,7854). Para la última lectura de Alta, la verosimilitud hacia atrás desde un día 2 soleado es $\mathrm{0,8}(\mathrm{0,8})+\mathrm{0,2}(\mathrm{0,3})=\mathrm{0,70}$. Desde un día 2 nublado es $\mathrm{0,4}(\mathrm{0,8})+\mathrm{0,6}(\mathrm{0,3})=\mathrm{0,50}$.

Multiplica: los productos son aproximadamente $\mathrm{0,2146}(\mathrm{0,70})=\mathrm{0,1502}$ y $\mathrm{0,7854}(\mathrm{0,50})=\mathrm{0,3927}$. Normaliza sus valores sin redondear para obtener una probabilidad de Soleado de 0,2767 para el día 2. Alta en el día 3 hace que un día 2 soleado sea más plausible de lo que indicaba la probabilidad filtrada original de 0,2146.

Continúa hasta el día 1

La verosimilitud hacia atrás desde Soleado en el día 1 es $\mathrm{0,8}(\mathrm{0,2})(\mathrm{0,70})+\mathrm{0,2}(\mathrm{0,7})(\mathrm{0,50})=\mathrm{0,182}$. Desde Nublado es $\mathrm{0,4}(\mathrm{0,2})(\mathrm{0,70})+\mathrm{0,6}(\mathrm{0,7})(\mathrm{0,50})=\mathrm{0,266}$. Combínalas con $f_1=(2\mathrm{/}9,7\mathrm{/}9)$ y normaliza. La probabilidad suavizada de Soleado es aproximadamente 0,1635, frente a 0,2222: el futuro completo incluye otra producción Baja además de la Alta final.

La evidencia posterior no tiene por qué desplazar todas las estimaciones pasadas en la misma dirección. En el último instante, el suavizado coincide con el filtrado porque no existe evidencia posterior.

Organiza el cálculo

El algoritmo hacia delante y hacia atrás primero almacena todas las creencias hacia delante, después calcula los mensajes hacia atrás y los productos normalizados. Para $t$ pasos y $S$ estados, el cálculo denso cuesta $O(S^{2}t)$ y almacena $O(St)$ valores. El suavizado con retardo fijo proporciona el estado un número fijo de pasos antes del presente, intercambiando demora por más evidencia.

Invertir la lista de observaciones y ejecutar un filtro ordinario es un cálculo diferente. La recursión hacia atrás usa las transiciones originales hacia delante y las verosimilitudes futuras; no introduce una nueva distribución inicial a priori al final del registro. Las probabilidades suavizadas de los estados también proporcionan conteos esperados para el aprendizaje de Baum–Welch.

A veces la respuesta buscada es una explicación completa de las observaciones. La decodificación de Viterbi encuentra la secuencia de estados ocultos más probable. Tiene en cuenta las transiciones entre estados, que las elecciones independientes de los más probables en cada instante pueden ignorar.

Cambia el objetivo

El objetivo es $\arg {\max }_{x_{1:t}}P(x_{1:t}\mid e_{1:t})$. Todos los candidatos tienen el mismo denominador de evidencia, por lo que maximizar la puntuación conjunta $P(x_{1:t},e_{1:t})$ selecciona el mismo camino. Esta puntuación difiere de una probabilidad a posteriori del estado final, que suma todos los caminos que terminan en ese estado.

Con las observaciones solares Alta, Baja, los estados individuales más probables después del suavizado son Soleado en el día 1 y Nublado en el día 2. Sin embargo, Soleado, Soleado es el camino completo más probable: su probabilidad a posteriori es aproximadamente 0,3282, frente a 0,2872 para Soleado, Nublado. Si hay transiciones prohibidas, estados plausibles por separado pueden incluso formar un camino imposible.

Conserva el mejor prefijo para cada estado final

Sea $m_t(j)$ la mejor puntuación conjunta de camino y evidencia que termina en el estado $j$. Inicializa $m_1(j)=P(X_1=j)P(e_1\mid j)$. Después usa

Guarda el predecesor que maximiza la expresión como un puntero al predecesor. Los caminos que terminan en el mismo estado tienen las mismas continuaciones futuras posibles, por lo que puede descartarse un prefijo de menor puntuación. El algoritmo hacia delante suma los prefijos competidores; Viterbi selecciona su máximo.

Completa el diagrama de rejilla para Baja, Baja, Alta

Las puntuaciones iniciales son (0,10; 0,35). En el día 2, los candidatos para Soleado antes de la emisión son $\mathrm{0,10}(\mathrm{0,8})=\mathrm{0,08}$ y $\mathrm{0,35}(\mathrm{0,4})=\mathrm{0,14}$. Conserva el segundo y multiplícalo por 0,2 para obtener 0,028, con un puntero a Nublado. Para Nublado, compara 0,02 con 0,21; multiplicar el mayor por 0,7 da 0,147, también con un puntero a Nublado.

En el día 3, Soleado compara $\mathrm{0,028}(\mathrm{0,8})=\mathrm{0,0224}$ con $\mathrm{0,147}(\mathrm{0,4})=\mathrm{0,0588}$. Multiplicar el mayor por la verosimilitud de Alta, 0,8, da 0,04704. Nublado compara 0,0056 con 0,0882; multiplicar el mayor por 0,3 da 0,02646. Ambos punteros finales conducen a Nublado en el día 2.

Retrocede desde el final

La mayor puntuación final es 0,04704 en Soleado. Sigue su puntero hasta Nublado en el día 2 y después ese puntero hasta Nublado en el día 1. Invierte este recorrido hacia atrás para obtener Nublado, Nublado, Soleado. Al dividir por la verosimilitud de la evidencia 0,1113 se obtiene su probabilidad a posteriori, aproximadamente 0,4226.

Elegir por separado la mayor puntuación de cada columna descartaría las relaciones con los predecesores almacenadas. El vector de puntuaciones finales tampoco puede normalizarse para obtener una creencia filtrada: conserva solo un camino por estado, no las sumas de sus caminos.

Usa logaritmos para secuencias largas

Los productos pueden sufrir un desbordamiento por defecto. Almacena en su lugar puntuaciones logarítmicas:

Los logaritmos conservan el orden, por lo que el camino y los punteros no cambian. Las probabilidades cero se convierten en infinito negativo. De forma equivalente, las puntuaciones logarítmicas negativas convierten la decodificación en un camino de costo mínimo por un grafo organizado en capas temporales, o diagrama de rejilla. Viterbi denso cuesta $O(S^{2}t)$ en tiempo y almacena $O(St)$ punteros. Si varios caminos empatan en la mayor puntuación, cada uno es una explicación más probable válida.

Una tabla de probabilidad se vuelve difícil de almacenar cuando el espacio de estados es enorme. En general, las creencias continuas tampoco tienen una tabla finita. Un filtro de partículas representa una creencia mediante estados muestreados, lo que permite centrar el cálculo en una población manejable de posibilidades.

Representa la probabilidad con partículas

Cada partícula es un estado completo, no un objeto físico distinto. Después del remuestreo, todas las partículas tienen el mismo peso y la probabilidad estimada de un estado es la fracción que lo ocupa. Diez partículas repartidas en siete Soleado y tres Nublado representan la creencia (0,7; 0,3).

Extrae las partículas iniciales de $P(X_1)$. Una distribución a priori de (0,5; 0,5) da conteos esperados iguales, pero no obliga a que cada muestra aleatoria se reparta por igual. Según nuestra convención temporal, pondera estas partículas iniciales con la primera observación y remuestrea antes de cualquier transición.

Avanza el tiempo muestreando transiciones

En cada paso posterior, mueve cada partícula de forma independiente usando la fila de transición correspondiente a su estado actual. Con las filas meteorológicas (0,8; 0,2) y (0,4; 0,6), siete partículas Soleado y tres Nublado tienen un conteo esperado de Soleado de $7(\mathrm{0,8})+3(\mathrm{0,4})=\mathrm{6,8}$ después de moverse.

Una muestra concreta podría contener seis partículas Soleado y cuatro Nublado. Un conteo esperado puede ser fraccionario; un conteo de partículas obtenido debe ser un número entero. Conservar exactamente 6,8 partículas no sería un algoritmo de muestreo.

Pondera según la lectura

Supón que la nueva producción solar es Baja. Cada partícula Soleado recibe una verosimilitud de 0,2; cada partícula Nublado recibe 0,7. Las seis partículas Soleado tienen un peso total de $6(\mathrm{0,2})=\mathrm{1,2}$, y las cuatro partículas Nublado tienen $4(\mathrm{0,7})=\mathrm{2,8}$. De un peso total de 4,0, Soleado tiene una probabilidad ponderada de 0,3 y Nublado de 0,7.

Importan tanto los conteos como los pesos por partícula. Normalizar solo 0,2 y 0,7 ignoraría cuánta probabilidad predicha representaba cada grupo. La ponderación reutiliza la misma actualización de Bayes que el filtrado exacto sobre esta predicción muestreada.

Remuestrea una nueva población

Extrae diez partículas con reemplazo, seleccionando cada partícula anterior en proporción a su peso. Cada nueva extracción es Soleado con probabilidad 0,3 y Nublado con probabilidad 0,7. El conteo esperado de Soleado es tres, aunque una ejecución puede dar dos, cuatro u otro conteo. Se permiten varias copias; representan masa de probabilidad.

Restablece las partículas resultantes a pesos iguales. La evidencia ya ha influido en qué partículas se copiaron, por lo que conservar los pesos de verosimilitud anteriores la contaría de nuevo. La siguiente iteración mueve esta nueva población antes de procesar la siguiente observación.

Compara con la actualización exacta

El filtrado exacto desde (0,7; 0,3) predice (0,68; 0,32). Baja da entonces los pesos (0,136; 0,224), por lo que la probabilidad exacta a posteriori de Soleado es $\mathrm{0,136}\mathrm{/}\mathrm{0,36}\approx \mathrm{0,3778}$. El resultado ponderado de la ejecución con partículas fue 0,3 porque su movimiento aleatorio produjo solo seis partículas Soleado. El remuestreo introduce otra fuente de variación.

El ciclo es, por tanto, inicialización, ponderación con la primera observación y remuestreo, seguidos de movimiento, ponderación y remuestreo repetidos. Antes del remuestreo, interpreta las fracciones ponderadas; después, los conteos. Un paso cuesta aproximadamente $O(N)$ para $N$ partículas cuando el muestreo y la ponderación de estados tienen un costo fijo. Para dos estados meteorológicos, el filtrado exacto es más sencillo. Los métodos de partículas resultan útiles cuando un estado grande o continuo carece de un filtro exacto compacto de costo asumible.

Una estimación con partículas es aleatoria, por lo que su calidad depende tanto del tamaño de la población como de dónde sobrevivan las partículas. Más partículas mejoran la aproximación, pero una población grande puede seguir siendo ineficaz cuando casi toda su información útil se concentra en unas pocas muestras.

Comprende la escala de la exactitud

Para una estimación de una probabilidad $p$ a partir de muestras independientes, el error estándar es aproximadamente $\sqrt{p(1-p)\mathrm{/}N}$. Con $p=\mathrm{0,3}$, es aproximadamente 0,046 para 100 muestras y 0,0046 para 10 000. El error del filtro de partículas suele tener la misma escala aproximada $1\mathrm{/}\sqrt{N}$, aunque las partículas remuestreadas son dependientes y la dificultad del modelo influye.

Cuadruplicar la población reduce el error aproximadamente a la mitad; duplicarla no. Para una historia fija de observaciones, aumentar el número de partículas hace que un filtro de partículas consistente se aproxime a la creencia exacta. Esto no hace exacta una ejecución finita ni elimina los errores del modelo subyacente. Fija una semilla aleatoria para obtener comparaciones reproducibles o compara los resultados de varias ejecuciones.

Distingue dos fallos

Sin remuestreo, multiplicar verosimilitudes durante muchos pasos puede dejar a casi todas las partículas con un peso insignificante. El remuestreo sustituye ese desperdicio por copias de estados útiles. Pero también puede eliminar una ubicación alternativa que temporalmente se ajusta peor.

El remuestreo por sí solo no puede recrear una región ausente. La recuperación depende de que las muestras de movimiento lleguen a ella o de que otro mecanismo introduzca partículas allí. Si las transiciones hacen que esa región sea casi inaccesible, la recuperación puede ser lenta. Añadir pequeñas perturbaciones aleatorias o sustituir una pequeña fracción por partículas nuevas puede ayudar, pero estas decisiones deben respetar la representación del estado y la aproximación deseada.

Maneja un peso total de cero

Si todas las partículas reciben peso cero, las probabilidades de remuestreo no están definidas. La observación puede ser posible en otra parte del modelo aunque la población muestreada no haya cubierto esos estados. Reinicializa a partir de una distribución adecuada, como la distribución a priori o una distribución uniforme sobre los estados válidos, y comprueba el modelo de sensores. Un componente de valores atípicos distinto de cero puede reducir estos fallos. Si el propio modelo descarta la observación en todas partes, más partículas por sí solas no pueden solucionarlo.

Elige una representación adecuada para el modelo

El filtrado exacto hacia delante es apropiado para espacios de estados discretos pequeños. Un filtro de Kalman es exacto cuando la distribución a priori es gaussiana y los modelos de transición y de sensores son lineales con ruido gaussiano; entonces una media y una covarianza describen la creencia. Un filtro de partículas admite modelos no lineales y creencias con picos separados.

Una sola distribución gaussiana no puede representar fielmente un robot que probablemente esté en cualquiera de dos pasillos distantes, pero sea improbable que esté entre ellos. Los grupos de partículas pueden conservar ambas alternativas. Para un modelo de seguimiento gaussiano lineal, la representación de Kalman suele evitar ruido de muestreo innecesario.

En una DBN, cada partícula contiene una asignación completa a todas las variables de estado. Muestrea las variables del siguiente paso en orden topológico a partir de sus modelos condicionados por los nodos padre. La factorización reduce el trabajo por muestra frente a enumerar cada estado conjunto, aunque las creencias de muchas dimensiones pueden necesitar muchas partículas para cubrir sus regiones importantes.

El seguimiento combina movimiento incierto con mediciones que contienen ruido. El estado oculto puede incluir posición y velocidad; las observaciones pueden proceder de GPS, radar o una cámara. El filtrado mantiene una distribución de ubicaciones plausibles de una lectura a la siguiente.

Localiza en un pasillo de cinco casillas

Un robot ocupa una de cinco casillas, con puertas en las casillas 1 y 4. Su sensor informa de una puerta con probabilidad 0,9 junto a una puerta y 0,2 en los demás lugares. Comienza de manera uniforme, con probabilidad 0,2 por casilla. Un aviso de puerta da los pesos (0,18; 0,04; 0,04; 0,18; 0,04), que suman 0,48.

La creencia actualizada es $(\mathrm{0,375};1\mathrm{/}12;1\mathrm{/}12;\mathrm{0,375};1\mathrm{/}12)\mathrm{.}$ Ambas casillas con puerta siguen siendo plausibles. Seleccionar un solo pico descartaría la simetría que el sensor no ha resuelto.

Desplaza toda la creencia

El robot intenta moverse una casilla a la derecha. Lo consigue con probabilidad 0,8 y permanece en su lugar con probabilidad 0,2; desde la casilla 5 permanece con certeza junto a la pared. Cada casilla recibe contribuciones de todas las casillas iniciales desde las que puede alcanzarse.

La casilla 1 recibe $\mathrm{0,375}(\mathrm{0,2})=\mathrm{0,075}$. La casilla 2 recibe $\mathrm{0,375}(\mathrm{0,8})+(1\mathrm{/}12)(\mathrm{0,2})\approx \mathrm{0,3167}$. Las casillas 3 y 4 reciben aproximadamente 0,0833 y 0,1417. La casilla 5 recibe $(\mathrm{0,375})(\mathrm{0,8})+1\mathrm{/}12\approx \mathrm{0,3833}$: tanto las llegadas desde la casilla 4 como toda la masa ya existente en la casilla 5 permanecen allí.

La predicción es aproximadamente (0,0750; 0,3167; 0,0833; 0,1417; 0,3833). Tratar el límite como otro movimiento ordinario de probabilidad 0,8 haría perder probabilidad más allá del pasillo modelado.

Observa que no hay puerta

La verosimilitud de no detectar puerta es 0,1 en las casillas 1 y 4 y 0,8 en los demás lugares. Multiplicar la predicción sin redondear da un peso total de aproximadamente 0,6483. Al normalizar se obtiene (0,0116; 0,3907; 0,1028; 0,0219; 0,4730).

Las ubicaciones probables son ahora las casillas 2 y 5, justo después de las dos puertas. La creencia sigue siendo multimodal, con picos separados. Una lectura de sensor es evidencia, no una medición de la posición real; conservar alternativas da a los movimientos y lecturas posteriores la oportunidad de distinguirlas.

Extiende el método a robots reales

En la localización de Monte Carlo, una partícula representa una posición y orientación: posición en metros y orientación. Mueve cada una usando el movimiento ordenado más ruido y después pondérala según la concordancia entre las distancias observadas y las predichas a partir de un mapa conocido. Una población inicial concentrada sigue una ubicación inicial conocida; una población amplia permite la localización global.

Si el mapa también es desconocido, inclúyelo en el estado oculto. La localización y construcción simultáneas de mapas, o SLAM, estima conjuntamente el mapa y la posición y orientación. Con varios objetos, otro problema es la asociación de datos: decidir a qué objeto pertenece cada detección. Las distintas asignaciones producen distintas hipótesis de trayectoria.

El seguimiento de vehículos puede combinar una predicción de movimiento con lecturas de GPS. A 15 m/s con pasos de un segundo, el movimiento esperado es de unos 15 m entre lecturas. Un modelo de Kalman adecuado combina el movimiento y la medición inciertos para reducir el efecto de las lecturas con ruido. Un modelo de transición que no permita variaciones reales del movimiento puede descartar la trayectoria verdadera, aunque su cálculo sea correcto.

Los modelos de secuencias pueden inferir etiquetas además de estados físicos. Un reconocedor del habla conecta una señal sonora cambiante con palabras posibles. Un etiquetador de categorías gramaticales conecta palabras observadas con etiquetas gramaticales ocultas. Ambos deben puntuar las elecciones en contexto a lo largo del tiempo.

Combina el ajuste al sonido y la probabilidad del lenguaje

El reconocimiento del habla busca la secuencia de palabras con mayor probabilidad a posteriori:

El modelo acústico $P(s\mid w)$ puntúa hasta qué punto las palabras explican el sonido; el modelo de lenguaje $P(w)$ puntúa su plausibilidad a priori. El denominador compartido $P(s)$ no afecta al orden. Una verosimilitud acústica no es por sí misma una probabilidad a posteriori de las palabras.

Para obtener puntuaciones ilustrativas, compara «haber» con «a ver». Las verosimilitudes acústicas son 0,0004 y 0,0005; las probabilidades del lenguaje son 0,00002 y 0,000001. El primer producto es $8\times {10}^{-9}$ y el segundo $5\times {10}^{-10}$. El contexto lingüístico hace que gane la primera expresión pese a su verosimilitud acústica ligeramente menor.

Convierte el audio en una secuencia temporal

Una configuración habitual usa fotogramas solapados de 25 ms que comienzan cada 10 ms, lo que produce unos 100 vectores de características por segundo. Los vectores son observaciones. Los estados ocultos representan partes de sonidos del habla, o fonos, a menudo con estados de comienzo, parte central y final. Un diccionario de pronunciación conecta las palabras con los fonos.

Los bucles al mismo estado permiten que un estado de sonido ocupe varios fotogramas. Sin flexibilidad de duración, cambiar la velocidad del habla exigiría una alineación fija y a menudo inadecuada entre fotogramas y estados de sonido. Los distintos caminos de estados expresan distintas alineaciones de la misma grabación observada.

Representa un contexto lingüístico corto

Un modelo de bigramas aproxima una secuencia de palabras mediante $P(w_1){\prod }_{i=2}^{n}P(w_i\mid w_{i-1})$. Uno de trigramas usa las dos palabras anteriores. Estima estas probabilidades condicionadas a partir de conteos en textos. El supuesto de Markov es aquí una aproximación práctica: las relaciones gramaticales y semánticas de largo alcance pueden extenderse más allá de una o dos palabras anteriores.

Viterbi puede encontrar el mejor camino de estados a través de modelos enlazados de fonos y palabras. Para un vocabulario grande, la búsqueda en haz descarta caminos parciales menos prometedores para reducir el trabajo. Una vez descartado, un camino no puede ganar más adelante, por lo que un haz estrecho puede perder el mejor camino completo. Además, el mejor camino individual de estados para una secuencia de palabras tiene un objetivo diferente al de sumar todas sus posibles alineaciones.

Usa la misma estructura para las etiquetas

En el etiquetado de categorías gramaticales, los estados son etiquetas y las observaciones son palabras. Las transiciones puntúan $P({\mathrm{t}\mathrm{a}\mathrm{g}}_i\mid {\mathrm{t}\mathrm{a}\mathrm{g}}_{i-1})$; las emisiones puntúan $P({\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{d}}_i\mid {\mathrm{t}\mathrm{a}\mathrm{g}}_i)$. En «El cura cura», «cura» puede referirse a un sacerdote o a la acción de sanar. El camino de etiquetas debe tener en cuenta tanto las verosimilitudes de las palabras como las transiciones entre etiquetas.

Sitúa los HMM en la práctica del reconocimiento del habla

Los sistemas de vocabulario amplio desde la década de 1980 hasta principios de la de 2010 solían combinar HMM con modelos acústicos de mezcla de gaussianas. Alrededor de 2010–2012, los modelos acústicos neuronales adquirieron protagonismo en sistemas híbridos DNN–HMM. Los sistemas neuronales modernos de extremo a extremo pueden convertir audio en texto sin un HMM explícito. Las ideas compartidas de alineación incierta, puntuación de secuencias y programación dinámica siguen siendo útiles, y los HMM también aparecen en aplicaciones como la búsqueda de genes en el ADN.