MCMC using $\textit{bouncy}$ Hamiltonian dynamics: A unifying framework for Hamiltonian Monte Carlo and piecewise deterministic Markov process samplers

Este trabajo presenta un marco unificador que conecta los métodos de Monte Carlo Hamiltoniano (HMC) con los procesos de Markov deterministas por partes (PDMP) mediante dinámicas hamiltonianas "reboteantes", permitiendo la creación de muestreadores sin rechazo que combinan las ventajas de ambos enfoques y logran un rendimiento competitivo en problemas de inferencia bayesiana a gran escala.

Lo esencial

Imagina que eres un explorador perdido en un vasto territorio montañoso (el mundo de los datos estadísticos) y tu misión es encontrar el punto más alto de un valle misterioso (la respuesta correcta a un problema complejo). Este territorio es tan grande y complicado que si caminas al azar, dando pasos pequeños y sin dirección, tardarías una eternidad en encontrar el camino.

Este artículo presenta una nueva forma de explorar ese territorio, combinando dos de las mejores técnicas existentes para no perderse. Aquí te lo explico con analogías sencillas:

1. Los dos exploradores anteriores

Antes de esta nueva invención, existían dos métodos principales para explorar este terreno:

• El Método del "Patinador de Hielo" (Hamiltonian Monte Carlo - HMC):
  Imagina a un patinador sobre hielo. Una vez que empuja, se desliza muy rápido y en línea recta gracias a la inercia. Usa el mapa (los gradientes de la montaña) para saber hacia dónde empujar. Es muy rápido y eficiente, pero tiene un problema: si el terreno es muy irregular o tiene bordes extraños, el patinador puede chocar y tener que "rebotar" o, peor aún, tener que decidir si acepta o rechaza un movimiento (como si alguien le gritara "¡No vayas por ahí!"). A veces, esos rechazos hacen que pierda tiempo.

• El Método del "Rebote de Pelota" (Piecewise Deterministic Markov Processes - PDMP, como el Bouncy Particle Sampler):
  Imagina una pelota de ping-pong que rebotan en una mesa. Se mueve en línea recta hasta que choca contra una pared invisible (un cambio en el terreno) y rebota instantáneamente. Nunca se detiene, nunca rechaza un movimiento; simplemente cambia de dirección al instante. Es muy ágil y nunca se queda atascado, pero a veces su movimiento parece un poco caótico o "aleatorio" en comparación con el patinador.

2. El problema: Dos mundos separados

Durante años, los científicos pensaron que estos dos métodos eran muy diferentes y que no podían mezclarse. El patinador usaba reglas estrictas de física, y la pelota usaba reglas de rebotes aleatorios.

3. La gran idea: El "Patinador con Inercia Mágica"

Los autores de este paper, Andrew Chin y Akihiko Nishimura, han creado un híbrido genial. Han inventado un nuevo tipo de explorador que combina lo mejor de ambos mundos. Lo llaman "Dinámica Hamiltoniana con Rebote" (Bouncy Hamiltonian Dynamics).

¿Cómo funciona? La analogía del "Combustible de Inercia":

Imagina que nuestro nuevo explorador es un patinador, pero lleva un tanque de combustible especial llamado "Inercia".

1. El viaje: El patinador se desliza por el terreno (como el HMC) usando un mapa de referencia (una "energía potencial de sustituto").
2. El combustible: A medida que viaja, su tanque de "Inercia" se va vaciando. La velocidad a la que se gasta depende de lo difícil que sea el terreno.
3. El rebote: Cuando el tanque de inercia se queda exactamente en cero, ¡PUM! El explorador rebota instantáneamente contra una pared invisible y cambia de dirección.
4. La magia: A diferencia de la pelota de ping-pong que rebota por azar, este patinador rebota de una manera determinista y calculada. El rebote está diseñado para que el explorador nunca tenga que decir "no, ese camino no sirve" (rechazar el movimiento). Siempre avanza hacia la solución correcta.

4. ¿Por qué es tan importante?

• Sin rechazos: En el mundo de los datos, "rechazar" un movimiento es como perder tiempo valioso. Este nuevo método es "sin rechazos"; siempre avanza.
• Conexión perfecta: Han demostrado matemáticamente que si haces que el explorador recargue su tanque de inercia muy, muy rápido (casi infinitamente), su comportamiento se vuelve idéntico al de la pelota de ping-pong (el método PDMP). Pero si lo dejas con inercia por más tiempo, se comporta como el patinador (HMC). ¡Es un puente entre dos mundos!
• Resultados reales: Probaron este método en problemas reales muy difíciles, como analizar datos médicos con miles de variables (por ejemplo, comparar medicamentos para la sangre o estudiar la evolución del virus del VIH). En estos casos, su nuevo método fue mucho más rápido y eficiente que los métodos anteriores, y fue más fácil de configurar (menos "ajustes manuales" necesarios).

En resumen

Piensa en esto como si hubieras descubierto que el patinador de hielo y la pelota de ping-pong en realidad son el mismo animal, solo que con diferentes niveles de energía.

Al crear un sistema donde el patinador lleva un tanque de combustible que se agota y le obliga a rebotar de forma inteligente, los autores han creado una herramienta más potente para resolver los problemas matemáticos más difíciles de la estadística moderna. Es como darle a un explorador un mapa perfecto y un motor que nunca se detiene, asegurando que llegue a la meta más rápido y sin perderse en el camino.

Resumen técnico

1. Planteamiento del Problema

El muestreo de Monte Carlo mediante Cadenas de Markov (MCMC) es fundamental para la inferencia bayesiana. Existen dos paradigmas principales que han evolucionado de forma paralela con poca interacción:

1. Hamiltonian Monte Carlo (HMC): Utiliza dinámica hamiltoniana determinista para proponer estados, aprovechando el gradiente de la distribución objetivo para evitar el comportamiento de "caminata aleatoria" típico de los algoritmos Metropolis-Hastings tradicionales. Sin embargo, HMC requiere una aceptación/rechazo (aunque es libre de rechazos si la simulación es exacta) y es sensible a la elección de la energía cinética y la escala de la cola de la distribución objetivo.
2. Procesos de Markov Deterministas a Trozos (PDMP): Incluyen muestreadores como el Bouncy Particle Sampler (BPS) y el Zig-Zag. Estos procesos utilizan variables auxiliares de velocidad y eventos de "rebote" estocásticos (gobernados por procesos de Poisson) para cambiar la dirección. Son eficientes y no requieren pasos de aceptación/rechazo, pero su implementación puede ser costosa computacionalmente y su conexión teórica con HMC ha sido limitada.

El problema central: Aunque se han observado conexiones aisladas (por ejemplo, el muestreador Zig-Zag como límite de HMC con momentum Laplaciano), no existía un marco unificado que explicara cómo la dinámica determinista de HMC y los rebotes estocásticos de los PDMP son dos caras de la misma moneda. Además, los métodos existentes a menudo carecen de la flexibilidad para combinar la eficiencia de HMC con la robustez de los PDMP en problemas de alta dimensión.

2. Metodología: Dinámica Hamiltoniana "Rebotante" (Bouncy Hamiltonian Dynamics)

Los autores proponen un nuevo marco teórico y algorítmico basado en la Dinámica Hamiltoniana Rebotante (Bouncy Hamiltonian Dynamics). La metodología se construye sobre dos ideas clave:

A. Dinámica de Sustitución (Surrogate Dynamics)

En lugar de simular la dinámica hamiltoniana exacta basada en la energía potencial objetivo $U_{tar} = -\log \pi(x)$, se utiliza una dinámica de sustitución basada en una energía potencial auxiliar $U_{sur}$.

• La dinámica sigue las ecuaciones de Hamilton para $U_{sur}$, lo que genera trayectorias deterministas.
• La discrepancia entre la distribución objetivo y la propuesta se maneja mediante una diferencia de energía potencial: $U_{dif} = U_{tar} - U_{sur}$.

B. El Mecanismo de Rebote Determinista

Para corregir la discrepancia sin usar un paso de aceptación/rechazo (que reduciría la eficiencia), los autores introducen una variable de inercia ($\iota \geq 0$), distribuida exponencialmente.

• Evolución de la inercia: A medida que la partícula se mueve, la inercia se consume según la integral del producto punto entre la velocidad y el gradiente de la discrepancia:
  $$\iota_t = \iota_0 - \int_0^t v_s^\top \nabla U_{dif}(x_s) \, ds$$
• Evento de Rebote: Cuando la inercia se agota ($\iota_t = 0$), ocurre un rebote instantáneo. La velocidad $v$ se refleja determinísticamente sobre el hiperplano ortogonal a $\nabla U_{dif}(x)$, utilizando la misma fórmula de reflexión elástica que en los PDMP:
  $$v_{new} = v - 2 \frac{v^\top \nabla U_{dif}}{\|\nabla U_{dif}\|^2} \nabla U_{dif}$$
• Propiedad Clave: Este mecanismo asegura que la trayectoria se mantenga en regiones de alta probabilidad de la distribución objetivo, haciendo que la propuesta sea libre de rechazos (rejection-free) y conserve la densidad conjunta $\pi(x, v, \iota)$.

C. El Muestreador HBP (Hamiltonian Bouncy Particle Sampler)

Un caso particular importante es cuando $U_{sur} = 0$ (potencial constante). Esto genera trayectorias lineales a trozos, análogas al BPS, pero con tiempos de evento deterministas en lugar de estocásticos. Los autores lo denominan HBP.

D. Conexión Teórica y Límite

El marco demuestra que:

1. La dinámica propuesta es reversible en el tiempo, preserva el volumen y conserva la energía aumentada ($U_{tar} + K(v) + \iota$).
2. Si se introduce una renovación periódica de la inercia (resampling de $\iota$) con un intervalo $\Delta t$, y se toma el límite $\Delta t \to 0$, la dinámica determinista converge fuertemente a su contraparte PDMP estocástica. Esto unifica teóricamente HMC y PDMP.

3. Contribuciones Clave

1. Unificación Paradigmática: Se establece que HMC y los muestreadores PDMP (como BPS y Zig-Zag) son casos límite o variantes de una misma estructura subyacente de dinámica hamiltoniana con rebotes.
2. Nuevo Mecanismo de Propuesta: Se introduce un mecanismo de propuesta libre de rechazos que combina la eficiencia de la dinámica hamiltoniana con la estructura de eventos de los PDMP, pero de forma puramente determinista hasta la renovación de inercia.
3. Generalización de HMC: Se demuestra que la dinámica hamiltoniana no necesita conservar la energía total del sistema objetivo para ser válida; puede usar una energía de sustitución y corregir la desviación mediante rebotes deterministas.
4. Algoritmos Prácticos:
   • HBP con No-U-Turn (NUTS): Se adapta el algoritmo NUTS de HMC para trabajar con la dinámica HBP, permitiendo una configuración automática del tiempo de viaje sin intervención manual.
   • Aproximación Numérica: Se propone un esquema de integración (basado en el método del punto medio y splitting) para casos donde las soluciones exactas de los tiempos de rebote no son factibles.
   • Estrategias Locales y Coordenada a Coordenada: Extensiones para manejar factores de la distribución objetivo y actualizaciones por bloques de coordenadas.

4. Resultados Empíricos

Los autores evaluaron el muestreador HBP en dos aplicaciones de datos reales de alta dimensión, comparándolo con el BPS estándar y variantes de Gibbs:

1. Regresión Logística Bayesiana Escasa (Sparse Logistic Regression):

   • Contexto: Estudio observacional con 72,489 pacientes y 22,174 covariables.
   • Desafío: La distribución condicional de los coeficientes es log-cóncava pero mal condicionada.
   • Resultados:
     • El HBP con ajuste manual superó al BPS en un factor de 4 en términos de tamaño de muestra efectivo (ESS) por unidad de tiempo.
     • La versión con NUTS (sin ajuste manual) fue superior al BPS en todas las configuraciones probadas, aunque ligeramente menos eficiente que la versión ajustada manualmente debido al costo computacional de la búsqueda de NUTS.
     • El muestreador BPS mostró alta sensibilidad a sus parámetros de ajuste (tiempo de viaje y tasa de renovación), mientras que HBP fue más robusto.

2. Modelo Probit Filogenético (Phylogenetic Probit Model):

   • Contexto: Datos de virus de VIH con 11,235 dimensiones (535 virus $\times$ 21 rasgos).
   • Desafío: Actualización conjunta de parámetros latentes y matriz de covarianza en un espacio truncado.
   • Resultados:
     • El HBP permitió una actualización conjunta de parámetros mediante un esquema de splitting (operador splitting), algo difícil de lograr con HMC estándar debido al costo de invertir matrices grandes en cada iteración.
     • En los parámetros de correlación parcial (los más difíciles de muestrear), el HBP con splitting logró una aceleración de 2.8 veces respecto al BPS condicional.

5. Significado e Impacto

• Puente entre Teorías: El trabajo disuelve la barrera teórica entre HMC y PDMP, sugiriendo que las diferencias de rendimiento observadas en la práctica a menudo se deben a detalles de implementación (como la sensibilidad de HMC a las colas de la distribución) más que a diferencias inherentes de eficiencia teórica.
• Escalabilidad: Al ofrecer un muestreador libre de rechazos que es más eficiente que los paseos aleatorios y más fácil de ajustar que el BPS, el HBP es una herramienta prometedora para la inferencia bayesiana a gran escala en lenguajes de programación probabilística modernos (como Stan o PyMC).
• Innovación Futura: El marco abierto permite la "polinización cruzada" de ideas. Por ejemplo, se pueden aplicar técnicas de optimización de HMC a PDMP y viceversa, y se pueden diseñar nuevos muestreadores híbridos que aprovechen lo mejor de ambos mundos (determinismo, conservación de energía y manejo de restricciones).

En resumen, el artículo presenta un avance teórico y práctico significativo al demostrar que la dinámica hamiltoniana puede generalizarse para incluir rebotes deterministas, creando un muestreador unificado que supera a los competidores actuales en problemas de alta dimensión y complejidad.