Geometry and factorization of multivariate Markov chains with applications to MCMC acceleration and approximate inference

Aquí presento un resumen técnico detallado del artículo "Geometry and factorization of multivariate Markov chains with applications to MCMC acceleration and approximate inference" (Geometría y factorización de cadenas de Markov multivariadas con aplicaciones a la aceleración de MCMC y la inferencia aproximada), escrito por Michael C.H. Choi, Youjia Wang y Geoffrey Wolfer.

---

1. Problema y Motivación

El artículo aborda dos desafíos fundamentales en el análisis de cadenas de Markov multivariadas definidas sobre espacios de estado producto $X = X^{(1)} \times \dots \times X^{(d)}$:

1. Complejidad Computacional en MCMC: Los algoritmos de Monte Carlo mediante Cadenas de Markov (MCMC), como el algoritmo de intercambio (swapping algorithm) o los métodos de "lifted" (elevados), a menudo sufren de tiempos de mezcla lentos, especialmente en distribuciones objetivo multimodales o de alta dimensión. La dependencia entre coordenadas puede ralentizar la exploración del espacio de estados.
2. Inferencia Aproximada en Alta Dimensión: En problemas de filtrado (como en modelos ocultos de Markov o HMM), la distribución de filtrado exacta requiere mantener una distribución sobre todo el espacio de estados, lo que implica un costo computacional exponencial en la dimensión $d$.

El objetivo central es entender la geometría de la factorización de las matrices de transición. Específicamente, ¿cuál es la "cadenas de Markov independiente" (producto) más cercana a una cadena dada $P$? ¿Cómo se comportan las propiedades de mezcla y las distancias de información al proyectar $P$ sobre subespacios de cadenas factorizadas?

2. Metodología y Marco Teórico

Los autores desarrollan un marco teórico basado en la geometría de la información y las divergencias $f$ entre matrices de transición.

A. Divergencia $f$ y Proyecciones de Información

Definen la divergencia $f$ entre dos matrices de transición $M$ y $L$ con respecto a una distribución $\pi$:
$$D^\pi_f(M \| L) := \sum_{x \in X} \pi(x) \sum_{y \in X} L(x, y) f\left(\frac{M(x, y)}{L(x, y)}\right)$$
En particular, utilizan la divergencia de Kullback-Leibler (KL) ($f(t) = t \ln t$).

B. Distancia a la Independencia

Introducen el concepto de distancia a la independencia de una cadena $P$, definida como la mínima divergencia KL hacia cualquier cadena producto:
$$I^\pi(P) := \min_{L_i \in \mathcal{L}(X^{(i)})} D^\pi_{KL}\left(P \Big\| \bigotimes_{i=1}^d L_i\right)$$
Demuestran que el minimizador único (la cadena producto más cercana) bajo KL es la cadena tensorial de las márginales de Markov de $P$, denotadas como $\bigotimes_{i=1}^d P^{(i)}_\pi$.

C. Identidad Pitagórica y Desigualdades

Establecen una identidad pitagórica para la divergencia KL:
$$D^\pi_{KL}(P \| \bigotimes L_i) = D^\pi_{KL}(P \| \bigotimes P^{(i)}_\pi) + D^\pi_{KL}(\bigotimes P^{(i)}_\pi \| \bigotimes L_i)$$
Esto implica que la proyección de información $\bigotimes P^{(i)}_\pi$ es el punto óptimo. Además, generalizan el Lema de Shearer y la Desigualdad de Han al contexto de cadenas de Markov, demostrando que la entropía de la tasa de la cadena y la distancia a la independencia son funciones submodulares (o supermodulares en ciertos casos) respecto a los conjuntos de coordenadas.

D. Matrices de Transición "Leave-S-out" y "Keep-S-in"

Definen matrices de transición marginales:

• Keep-S-in ($P^{(S)}$): La cadena inducida en un subconjunto de coordenadas $S$, promediando sobre las demás.
• Leave-S-out ($P^{(-S)}$): La cadena en el complemento de $S$.
  Estas matrices se interpretan como esperanzas condicionales (análogo al teorema de Rao-Blackwell) de la cadena original, lo que sugiere que deberían tener mejores propiedades de mezcla.

3. Contribuciones Clave

1. Caracterización Geométrica: Se demuestra que las cadenas inducidas en factores de un espacio producto son proyecciones de información. Esto permite cuantificar la "no independencia" de un sistema interactuante.
2. Aceleración de MCMC mediante Muestreadores de Proyección:
   • Se propone un muestreador de proyección basado en el algoritmo de intercambio (swapping algorithm).
   • En lugar de ejecutar la cadena completa, el método resamplea la coordenada de mayor temperatura (o la primera) desde su distribución estacionaria en cada paso, manteniendo el resto de la dinámica.
   • Resultado Teórico: Se prueba que el tiempo de mezcla de este muestreador de proyección es más rápido que el original por un factor multiplicativo relacionado con la dimensión del espacio ($N$) y el número de temperaturas ($d$). Específicamente, para un espacio binario de dimensión $N$, la aceleración es del orden de $O(N)$ o $O(dN)$.
3. Filtrado Factorizado Aproximado:
   • Se propone un esquema de filtrado factorizado para HMMs (ej. modelo de Ising).
   • En el paso de predicción, la dinámica acoplada $P$ se reemplaza por su proyección KL sobre kernels producto ($\hat{P} = \bigotimes P^{(i)}$).
   • Resultado: Esto reduce el costo computacional de exponencial ($O(2^d)$) a lineal ($O(d)$) por paso, permitiendo inferencia en alta dimensión.
4. Medida de Error de Aproximación: Se demuestra que la distancia a la independencia $I^\pi(P)$ sirve como un proxy cuantitativo robusto para el error de aproximación introducido por la factorización.

4. Resultados Experimentales

Los autores validan sus teorías mediante experimentos numéricos:

• Distribución Bimodal (MCMC):

  • Se utiliza una distribución objetivo en forma de "V" (bimodal) en un espacio discreto.
  • Resultados: El algoritmo de intercambio original (swapping) y el MCMC "lifted" a menudo quedan atrapados en un modo. El muestreador de proyección logra saltar entre modos con mayor frecuencia, generando distribuciones empíricas y momentos (media, varianza) mucho más cercanos a la verdad fundamental.
  • Se observa una reducción significativa en la distancia de variación total (TV) y la divergencia KL.

• Filtrado en Modelo de Ising (HMM):

  • Se compara el filtro exacto (factible solo para dimensiones bajas, $d=16$) con el filtro factorizado propuesto.
  • Escalabilidad: El filtro exacto se vuelve intratable rápidamente al aumentar $L$ (donde $d=L^2$), mientras que el filtro factorizado escala linealmente con $d$.
  • Correlación: Existe una correlación estadísticamente significativa entre la distancia a la independencia calculada en cada paso y el error real de filtrado (tanto marginal como conjunto). Esto confirma que la métrica teórica predice el rendimiento práctico.

5. Significado e Impacto

Este trabajo es significativo por varias razones:

• Unificación Teórica: Conecta conceptos de teoría de la información (mutual information, desigualdades de Han-Shearer) con la teoría de cadenas de Markov y la geometría de la información, proporcionando nuevas herramientas analíticas para estudiar la mezcla.
• Mejora de Algoritmos Existentes: Ofrece una justificación teórica rigurosa y una mejora práctica para algoritmos populares como el Swapping Algorithm y los métodos de Lifted MCMC, demostrando que "olvidar" o resamplear ciertas coordenadas (proyección) puede acelerar la convergencia en lugar de degradarla.
• Inferencia Escalable: Proporciona una solución viable para problemas de inferencia en sistemas de alta dimensión (como redes de Ising o modelos espaciales) donde los métodos exactos son imposibles, ofreciendo un compromiso controlado entre costo computacional y precisión.
• Diagnóstico de Error: La capacidad de usar la distancia a la independencia como una métrica de diagnóstico en tiempo real para evaluar la calidad de una aproximación factorizada es una contribución práctica valiosa para la implementación de algoritmos de inferencia.

En resumen, el paper demuestra que la factorización y la proyección de información no son solo aproximaciones heurísticas, sino operaciones geométricas bien definidas que pueden explotar para acelerar la mezcla de cadenas de Markov y hacer viable la inferencia en alta dimensión.