Compositionality in algorithms for smoothing

1. Planteamiento del Problema

El artículo aborda el problema de la inferencia bayesiana en sistemas parcialmente observados, específicamente en modelos de espacio de estado (también conocidos como modelos de Markov ocultos o HMM) definidos sobre grafos dirigidos (árboles o líneas de tiempo).

• El Desafío: El objetivo es el "suavizado" (smoothing), es decir, inferir la distribución de probabilidad de las variables latentes en todos los nodos internos de un proceso estocástico, condicionadas a las observaciones realizadas en los nodos hoja (finales).
• Limitaciones Actuales: Los métodos clásicos, como la recursión hacia adelante-hacia atrás normalizada o el filtro de Kalman, a menudo requieren formas cerradas que solo existen en casos específicos (ej. espacios de estado finitos o sistemas lineales gaussianos).
• El Algoritmo BFFG: Se centra en el algoritmo de Filtrado Hacia Atrás y Guía Hacia Adelante (Backward Filtering Forward Guiding - BFFG), introducido previamente por Mider et al. [2021]. Este algoritmo es un marco general que maneja el suavizado mediante un flujo de datos bidireccional:
  1. Paso de Filtrado Hacia Atrás: Calcula funciones de guía (o "funciones h") utilizando dinámicas simplificadas o aproximadas.
  2. Paso de Guía Hacia Adelante: Muestrea trayectorias utilizando la transformación h (h-transform) basada en las funciones calculadas.
• La Brecha Teórica: Aunque BFFG es potente, carecía de una comprensión estructural profunda sobre cómo se componen sus operaciones cuando se dividen o combinan procesos estocásticos. El artículo busca llenar esta brecha utilizando la teoría de categorías.

2. Metodología

Los autores emplean herramientas de la teoría de categorías para descomponer y analizar el algoritmo BFFG. La metodología se basa en tres pilares conceptuales:

1. Categoría de Núcleos de Markov ($\mathbf{Stoch}$): Se utiliza la categoría donde los objetos son espacios medibles y los morfismos son núcleos de Markov (probabilidades de transición). La composición se define mediante las ecuaciones de Chapman-Kolmogorov.
2. Ópticas (Optics): Se adoptan las "ópticas" (introducidas por Riley [2018]) como modelos abstractos para flujos de datos bidireccionales. Una óptica consiste en un par de morfismos:
   • Un primer mapa (paso hacia atrás/filtrado) que genera un estado interno (mensaje).
   • Un segundo mapa (paso hacia adelante/guía) que consume ese estado interno para producir una salida.
3. Funtores y Estructura Monoidal: El objetivo es demostrar que el algoritmo BFFG no es solo una secuencia de pasos, sino un functor que preserva la estructura composicional. Específicamente, se investiga si el algoritmo es un functor monoidal laxo (preserva composiciones paralelas).

3. Contribuciones Clave

El trabajo establece una conexión formal entre el algoritmo BFFG y la teoría de categorías, logrando las siguientes contribuciones:

• Definición de Ópticas para BFFG: Se definen formalmente los mapas de filtrado y guía como componentes de una óptica en la categoría $\mathbf{Optic}(\mathbf{Set})$.
  • El Filtrado Hacia Atrás corresponde al primer mapa ($f_m$) de la óptica.
  • La Guía Hacia Adelante corresponde al segundo mapa ($s_m$).
• Functorialidad (Teorema 8): Se demuestra que BFFG define un functor contravariante desde una categoría de pares de núcleos de Markov ($\mathbf{Stoch}^2$) hacia la categoría de ópticas. Esto implica que la composición secuencial de núcleos de Markov se mapea consistentemente a la composición secuencial de ópticas.
• Propiedad Monoidal Laxa (Teorema 11): Se demuestra que, en el caso especial donde las dinámicas de guía coinciden con las dinámicas generativas (es decir, cuando no se usa una aproximación, conocido como BFFS o Backward Filtering Forward Sampling), el functor es monoidal laxo. Esto significa que el algoritmo preserva la composición paralela (producto tensorial) de sistemas independientes, hasta un isomorfismo natural.
• Análisis de la Falta de Monoidalidad en BFFG General: Se explica por qué BFFG general (con dinámicas aproximadas distintas) falla en ser monoidal laxo: la necesidad de rastrear pesos globales (factores de corrección) introduce dependencias que rompen la independencia estricta al componer sistemas en paralelo. Sin embargo, se argumenta que esto no afecta la validez estadística en métodos de Monte Carlo.

4. Resultados Principales

Los resultados teóricos se resumen en dos teoremas fundamentales:

1. Teorema 8 (Composición Secuencial):
   El algoritmo BFFG es composicional. Si se tiene un proceso estocástico definido por la composición de núcleos $\kappa_1$ y $\kappa_2$, aplicar BFFG al núcleo compuesto $\kappa_1 \circ \kappa_2$ es equivalente (en el sentido de las ópticas) a componer las ópticas individuales generadas por BFFG para $\kappa_1$ y $\kappa_2$.

   • Implicación: Permite dividir un problema complejo en subproblemas más pequeños (ej. dividir una transición de tiempo larga en pasos discretos) sin alterar el resultado final del algoritmo.

2. Teorema 11 (Composición Paralela y BFFS):
   En el caso de BFFS (donde la guía es exacta, $\tilde{\kappa} = \kappa$), el functor es monoidal laxo.

   • Implicación: El suavizado de dos procesos independientes observados conjuntamente puede descomponerse en el suavizado de cada proceso por separado, combinando luego los resultados mediante un producto tensorial de ópticas. Esto valida la modularidad del algoritmo en sistemas de alta dimensión.

3. Interpretación Estadística de la Falta de Monoidalidad (Nota 17):
   Aunque BFFG general no es estrictamente monoidal laxo debido a los factores de peso (likelihood ratios) que dependen de la estructura conjunta, en la práctica de inferencia Monte Carlo (SMC), estos factores constantes se cancelan en los estimadores normalizados. Por lo tanto, la falta de monoidalidad estricta no es un obstáculo para la aplicación práctica.

5. Significado e Impacto

Este trabajo tiene un impacto significativo tanto en la teoría de la probabilidad computacional como en la ciencia de datos:

• Descomposición Modular: Proporciona una justificación teórica rigurosa para descomponer algoritmos de suavizado complejos en bloques más pequeños. Esto facilita la implementación en grafos complejos (árboles dirigidos) y permite optimizar el cálculo dividiendo transiciones inmanejables en pasos más pequeños (ej. discretización de EDEs).
• Abstracción de Implementación: Al elevar el algoritmo al nivel de ópticas, se abstraen los detalles de implementación específicos (como la elección de medidas dominantes o la discretización), permitiendo un razonamiento más limpio sobre la estructura del algoritmo.
• Puente entre Áreas: Conecta la inferencia estadística avanzada con la teoría de categorías moderna (ópticas, lenses), abriendo la puerta a la aplicación de herramientas de teoría de categorías (como diagramas de cuerda) para diseñar nuevos algoritmos de inferencia.
• Generalización: Muestra que resultados conocidos para algoritmos específicos (como FFBS en HMMs) son casos particulares de una estructura composicional más general (BFFG), unificando así diversas técnicas de suavizado bajo un mismo marco matemático.

En resumen, el paper demuestra que el algoritmo BFFG posee una estructura de orden superior preservadora de la composición, lo que permite tratarlo como un bloque constructivo fundamental en la arquitectura de algoritmos de inferencia bayesiana complejos.