Markov Chain Monte Carlo/es

Article
Topic area	Bayesian Methods
Prerequisites	Bayesian Inference, Markov Chain

Resumen

El método de Monte Carlo basado en cadenas de Markov (MCMC) es una familia de algoritmos para extraer muestras de una distribucion de probabilidad que solo se conoce hasta una constante de normalizacion. En lugar de muestrear directamente, MCMC construye una cadena de Markov cuya distribucion estacionaria es la distribucion objetivo, ejecuta la cadena el tiempo suficiente para que olvide su estado inicial y trata los estados subsiguientes como muestras aproximadas. Las esperanzas bajo la distribucion objetivo se estiman entonces promediando funciones de esos estados. La tecnica es la base de la inferencia bayesiana moderna: las distribuciones posteriores de la forma $ p(\theta \mid \mathbf{y}) \propto p(\mathbf{y} \mid \theta) p(\theta) $ son tipicamente intratables, pero su densidad no normalizada es barata de evaluar, que es exactamente lo que MCMC necesita.

MCMC se situa entre el muestreo exacto, que requiere una constante de normalizacion tratable, y la inferencia variacional, que optimiza un sustituto tratable a costa de una brecha de aproximacion fija. Con suficiente computo, un estimador MCMC es asintoticamente insesgado; sus principales preocupaciones practicas son el tiempo de mezcla, la autocorrelacion y la calibracion. El marco fue popularizado en estadistica por el algoritmo de Metropolis en 1953 y extendido por Hastings en 1970, y luego transformo la computacion bayesiana en los anos noventa una vez que muestreadores de proposito general como Gibbs y BUGS made hicieron rutinaria la inferencia posterior.

Intuicion

Imagine que se quiere calcular el valor promedio de una funcion sobre una distribucion posterior de alta dimension cuya densidad se puede evaluar pero no invertir. El muestreo directo falla porque no se conoce la constante de normalizacion; el muestreo por importancia falla porque no existe una buena propuesta en altas dimensiones. MCMC sortea ambos problemas con un paseo aleatorio sesgado hacia regiones de alta densidad: en cada paso, propone un cambio pequeno al estado actual y luego acepta o rechaza la propuesta de modo que, a la larga, la cadena pase tiempo en cada region en proporcion a la densidad objetivo.

El hecho clave es que solo se necesita evaluar cocientes de la densidad objetivo. Como $ p(\theta) = \tilde{p}(\theta) / Z $, donde $ Z $ es la constante de normalizacion desconocida, el cociente $ \tilde{p}(\theta')/\tilde{p}(\theta) $ es igual a $ p(\theta')/p(\theta) $. La constante desconocida se cancela, asi que la cadena puede simularse usando unicamente la densidad no normalizada.

Fundamentos

Una cadena de Markov es una sucesion de variables aleatorias $ \theta_0, \theta_1, \ldots $ donde $ \theta_{t+1} $ depende unicamente de $ \theta_t $, gobernada por un nucleo de transicion $ T(\theta' \mid \theta) $. Una distribucion $ \pi $ es estacionaria para $ T $ si

$ {\displaystyle \pi(\theta') = \int T(\theta' \mid \theta) \pi(\theta)\, d\theta.} $

Una condicion suficiente (pero no necesaria) para la estacionariedad es el balance detallado,

$ {\displaystyle \pi(\theta) T(\theta' \mid \theta) = \pi(\theta') T(\theta \mid \theta'),} $

que afirma que el flujo de probabilidad entre cualquier par de estados es simetrico. Si la cadena es ademas irreducible (cualquier estado es alcanzable desde cualquier otro) y aperiodica, el teorema ergodico garantiza que los promedios temporales a lo largo de la cadena convergen a esperanzas bajo $ \pi $. Los algoritmos MCMC son recetas para disenar nucleos de transicion cuya distribucion estacionaria sea el objetivo elegido.

Metropolis-Hastings

El algoritmo de Metropolis-Hastings (MH) es el metodo MCMC canonico. Dado el estado actual $ \theta $, se extrae un candidato $ \theta' $ de una distribucion de propuesta $ q(\theta' \mid \theta) $ y se acepta con probabilidad

$ {\displaystyle \alpha(\theta, \theta') = \min\!\left(1,\; \frac{\tilde{p}(\theta')\, q(\theta \mid \theta')}{\tilde{p}(\theta)\, q(\theta' \mid \theta)}\right).} $

Si la propuesta es simetrica (el caso original de Metropolis), el cociente $ q $ desaparece y la aceptacion se reduce a $ \min(1, \tilde{p}(\theta')/\tilde{p}(\theta)) $. Por construccion, el nucleo de transicion resultante satisface el balance detallado respecto a $ p $, asi que $ p $ es estacionaria. La propuesta es la unica palanca de diseno: una propuesta demasiado estrecha produce alta aceptacion pero exploracion lenta; una demasiado amplia se rechaza a menudo. La adaptacion del tamano de paso apuntando a una tasa de aceptacion cercana a 0,234 es asintoticamente optima para propuestas de paseo aleatorio en alta dimension.

Muestreo de Gibbs

El muestreo de Gibbs aprovecha la estructura de los objetivos multivariantes actualizando una coordenada (o bloque de coordenadas) a la vez, condicionada a las demas. Para $ \theta = (\theta_1, \ldots, \theta_d) $, un barrido del muestreador de Gibbs extrae

$ {\displaystyle \theta_i^{(t+1)} \sim p\!\left(\theta_i \,\big|\, \theta_{-i}^{(t+1, t)}\right),} $

donde $ \theta_{-i} $ denota las demas coordenadas con sus valores mas recientes. Cada actualizacion condicional es ella misma un paso MH con probabilidad de aceptacion uno, asi que no se requiere calibracion cuando las condicionales se pueden muestrear en forma cerrada. Los modelos jerarquicos conjugados, los modelos de mezcla y los modelos graficos con mantos de Markov tratables son aplicaciones naturales. Cuando una condicional no es directamente muestreable, se puede sustituir por un paso MH dentro de Gibbs o por un movimiento de muestreo por cortes, dando lugar a un esquema Metropolis-dentro-de-Gibbs.

Monte Carlo Hamiltoniano

El paseo aleatorio MH mezcla mal en altas dimensiones y en objetivos correlacionados. El Monte Carlo Hamiltoniano (HMC) aumenta el estado con una variable auxiliar de momento $ r $ y propone trayectorias largas guiadas por el gradiente simulando dinamica hamiltoniana con potencial $ U(\theta) = -\log \tilde{p}(\theta) $ y energia cinetica $ K(r) = \tfrac{1}{2} r^\top M^{-1} r $. El integrador leapfrog conserva el volumen y es reversible; el error de discretizacion remanente se corrige con un unico paso MH de aceptacion-rechazo sobre la energia conjunta $ (\theta, r) $. Como las trayectorias siguen el gradiente, HMC suprime el comportamiento de paseo aleatorio y escala mucho mejor con la dimension. El No-U-Turn Sampler (NUTS) automatiza la eleccion de la longitud de la trayectoria extendiendo la trayectoria hasta que comienza a regresar, eliminando uno de los dolores de cabeza de calibracion de HMC y convirtiendolo en el muestreador por defecto en Stan y PyMC.

Diagnosticos y convergencia

Las estimaciones MCMC son sesgadas para cadenas finitas; el sesgo decae a medida que la cadena olvida su inicializacion. Se descarta un periodo de calentamiento, y las muestras restantes se resumen mediante su autocorrelacion, el tamano efectivo de muestra (ESS) y el factor potencial de reduccion de escala $ \hat{R} $ calculado a partir de multiples cadenas inicializadas en puntos sobredispersos. Una regla empirica habitual es ejecutar al menos cuatro cadenas y tratar $ \hat{R} > 1{,}01 $ como evidencia de no convergencia. Las graficas de traza, las graficas de rangos y los diagnosticos de divergencia de HMC detectan patologias que los diagnosticos escalares pasan por alto, como embudos y multimodalidad. Ninguna de estas herramientas puede demostrar la convergencia; solo pueden senalar el fracaso.

Variantes y conexiones

Mas alla de los muestreadores canonicos, varias variantes abordan retos especificos. El MCMC de salto reversible maneja modelos de dimension variable. El temperado paralelo y el intercambio de replicas ejecutan multiples cadenas a distintas temperaturas e intercambian estados para escapar de modos. El Monte Carlo secuencial combina muestreo por importancia con movimientos MCMC y es muy adecuado para objetivos en flujo y temperados. Los metodos MCMC de gradiente estocastico como SGLD y SGHMC escalan a grandes conjuntos de datos reemplazando el gradiente sobre todos los datos por estimaciones de minilotes, sacrificando la estacionariedad exacta a cambio de tratabilidad. MCMC tambien interactua con otras herramientas de inferencia: proporciona posteriores de referencia asintoticamente insesgadas para evaluar la Variational Inference, suministra estimaciones de hiperparametros totalmente bayesianas para Gaussian Processes y ofrece una alternativa estocastica al Expectation-Maximization Algorithm cuando el paso E es intratable.

Limitaciones

La debilidad principal de MCMC es la eficiencia muestral: cada extraccion requiere una evaluacion completa de la densidad no normalizada (y, para HMC, de su gradiente), y las extracciones consecutivas estan correlacionadas, por lo que el tamano efectivo de muestra puede ser ordenes de magnitud menor que la longitud de la cadena. La mezcla se degrada en posteriores multimodales, donde las cadenas pueden quedar atrapadas en una sola moda durante un tiempo arbitrariamente largo, y en geometrias con fuerte variacion de curvatura, donde tamanos de paso que funcionan en una region fallan en otra. Los diagnosticos de convergencia son necesarios pero no suficientes. Las variantes de gradiente estocastico introducen un sesgo que rara vez se cuantifica con rigor. Para modelos de muy alta dimension o con variables latentes, los metodos variacionales y amortizados suelen preferirse cuando la incertidumbre calibrada no es la prioridad, reservando MCMC como inferencia de referencia de gold-standard.