Métodos de Montecarlo basados en cadenas de Markov

En estadística, los métodos de Montecarlo basados en cadenas de Markov (MCMC por sus siglas en inglés, Markov chain Montecarlo) comprenden una clase de algoritmos para el muestreo de una distribución de probabilidad. Construyendo una cadena de Markov que tiene la distribución deseada como su distribución de equilibrio, se puede obtener una muestra de la distribución deseada registrando estados de la cadena. Cuantos más pasos se incluyan, más se acercará la distribución de la muestra a la distribución real deseada. Existen varios algoritmos para construir cadenas, incluido el algoritmo de Metrópolis-Hastings.

Ámbitos de aplicación

Los métodos MCMC se utilizan principalmente para calcular aproximaciones numéricas de integrales múltiples, por ejemplo en estadística bayesiana, física computacional,​ biología computaciona​ l y lingüística computacional.​​

En la estadística bayesiana, el reciente desarrollo de los métodos MCMC ha permitido calcular grandes modelos jerárquicos que requieren integraciones sobre cientos o miles de parámetros desconocidos.​

En el muestreo de eventos raros, también se utilizan para generar muestras que pueblan gradualmente la región de fallos raros.^{[cita requerida]}

Explicación general

Convergencia del algoritmo Metrópolis-Hastings. El método MCMC intenta aproximar la distribución azul a la distribución naranja.

Los métodos de Montecarlo basados en cadenas de Markov crean muestras de una variable aleatoria continua, con una densidad de probabilidad proporcional a una función conocida. Estas muestras pueden utilizarse para evaluar una integral sobre esa variable, como su valor esperado o su varianza.

En la práctica, se suele desarrollar una colectividad de cadenas que parten de un conjunto de puntos elegidos arbitrariamente y suficientemente distantes entre sí. Estas cadenas son procesos estocásticos de "caminantes" que se desplazan aleatoriamente según un algoritmo que busca lugares con una contribución razonablemente alta a la integral para desplazarse a continuación, asignándoles mayores probabilidades.

Los métodos de Montecarlo de paseo aleatorio son un tipo de simulación aleatoria o método de Montecarlo. Sin embargo, mientras que las muestras aleatorias del integrando utilizadas en una integración de Montecarlo convencional son estadísticamente independientes, las utilizadas en MCMC están autocorrelacionadas. La correlación de las muestras introduce la necesidad de utilizar el teorema del límite central al estimar el error de los valores medios.

Estos algoritmos crean cadenas de Markov tales que tienen una distribución de equilibrio que es proporcional a la función dada.

Reducción de la correlación

Aunque los métodos MCMC se crearon para abordar problemas multidimensionales mejor que los algoritmos genéricos de Montecarlo, cuando el número de dimensiones aumenta también tienden a sufrir la maldición de la dimensión: las regiones de mayor probabilidad tienden a estirarse y perderse en un volumen creciente de espacio que contribuye poco a la integral. Una forma de abordar este problema podría ser acortar los pasos del caminante, de forma que no intente continuamente salir de la región de mayor probabilidad, aunque de esta forma el proceso sería altamente autocorrelacionado y costoso (es decir, se necesitarían muchos pasos para obtener un resultado preciso). Métodos más sofisticados, como los métodos hamiltonianos de Montecarlo y el algoritmo de Wang-Landau, utilizan diversas formas de reducir esta autocorrelación, al tiempo que consiguen mantener el proceso en las regiones que dan una mayor contribución a la integral. Estos algoritmos suelen basarse en una teoría más complicada y son más difíciles de aplicar, pero suelen converger más rápidamente.

Ejemplos

Paseo aleatorio

• Algoritmo de Metrópolis-Hastings: Este método genera una cadena de Markov utilizando una densidad de propuesta para nuevos pasos y un método para rechazar algunos de los movimientos propuestos. En realidad es un marco general que incluye como casos especiales el primer y más sencillo MCMC (algoritmo de Metrópolis) y muchas alternativas más recientes que se enumeran a continuación.
  • Muestreo de Gibbs: Este método requiere que todas las distribuciones condicionales de la distribución objetivo sean muestreadas exactamente. Cuando la extracción de las distribuciones condicionales completas no es sencilla, se utilizan otros muestreadores dentro de Gibbs (por ejemplo, véase​​). El muestreo de Gibbs es popular en parte porque no requiere ningún "ajuste". La estructura del algoritmo del muestreo de Gibbs se asemeja mucho a la de la inferencia variacional por ascenso de coordenadas, ya que ambos algoritmos utilizan las distribuciones condicionales completas en el procedimiento de actualización.​
  • Algoritmo de Langevin ajustado por Metrópolis y otros métodos que se basan en el gradiente (y posiblemente en la segunda derivada) de la densidad logarítmica del objetivo para proponer pasos que tengan más probabilidades de ir en la dirección de una mayor densidad de probabilidad.​
  • Método de Metrópolis-Hastings pseudo-marginal: Este método sustituye la evaluación de la densidad de la distribución objetivo por una estimación insesgada y es útil cuando la densidad objetivo no está disponible analíticamente, por ejemplo, en los modelos de variables latentes.
• Muestreo por cortes: Este método se basa en el principio de que se puede realizar un muestreo de una distribución tomando muestras uniformes de la región bajo el gráfico de su función de densidad. Alterna el muestreo uniforme en la dirección vertical con el muestreo uniforme de la "rebanada" horizontal definida por la posición vertical actual.
• Método de Metrópolis de múltiples intentos: Este método es una variación del algoritmo Metrópolis-Hastings que permite realizar múltiples ensayos en cada punto. Al permitir dar pasos más grandes en cada iteración, ayuda a resolver la maldición de la dimensionalidad.
• Salto reversible: Este método es una variante del algoritmo Metropolis-Hastings que permite propuestas que cambian la dimensionalidad del espacio.​ Los métodos de Montecarlo con cadena de Markov que cambian la dimensionalidad se han utilizado durante mucho tiempo en aplicaciones de física estadística, donde para algunos problemas se utiliza una distribución que es una colectividad macrocanónica (por ejemplo, cuando el número de moléculas en una caja es variable). Pero la variante de salto reversible es útil cuando se hace un Montecarlo de cadena de Markov o un muestreo de Gibbs sobre modelos bayesianos no paramétricos, como los que implican el proceso de Dirichlet o el proceso de restaurante chino, en los que el número de componentes de mezcla/clústeres/etc. se infiere automáticamente de los datos.
• Métodos hamiltonianos (o híbridos) de Montecarlo (HMC): Intenta evitar el comportamiento de paseo aleatorio introduciendo un vector de momento auxiliar e implementando la dinámica hamiltoniana, de modo que la función de energía potencial es la densidad objetivo. Las muestras de momento se descartan después del muestreo. El resultado final del Montecarlo Híbrido es que las propuestas se mueven a través del espacio muestral en pasos más grandes; por lo tanto, están menos correlacionadas y convergen a la distribución objetivo más rápidamente.

Métodos de partículas interactivas

Las metodologías MCMC interactivas son una clase de métodos de partículas de campo medio para obtener muestras aleatorias de una secuencia de distribuciones de probabilidad con un nivel creciente de complejidad de muestreo.​ Estos modelos probabilísticos incluyen modelos de estado de espacio de trayectoria con un horizonte temporal creciente, distribuciones posteriores en función de la secuencia de observaciones parciales, conjuntos de niveles de restricción crecientes para distribuciones condicionales, programas de temperatura decrecientes asociados a algunas distribuciones de Boltzmann-Gibbs, y muchos otros. En principio, cualquier muestreador de Montecarlo con cadena de Markov puede convertirse en un muestreador de Montecarlo con cadena de Markov interactiva. Estos muestreadores de Montecarlo de cadenas de Markov interactivas pueden interpretarse como una forma de ejecutar en paralelo una secuencia de muestreadores de Montecarlo de cadenas de Markov. Por ejemplo, los algoritmos de recocido simulado interactivo se basan en movimientos independientes de Metropolis-Hastings que interactúan secuencialmente con un mecanismo de tipo selección-muestreo. A diferencia de los métodos tradicionales de Montecarlo en cadena de Markov, el parámetro de precisión de esta clase de muestreadores de Montecarlo en cadena de Markov interactivos sólo está relacionado con el número de muestreadores de Montecarlo en cadena de Markov interactivos. Estas metodologías avanzadas de partículas pertenecen a la clase de modelos de partículas de Feynman-Kac,​​ también llamados métodos de Montecarlo secuencial o de filtro de partículas en las comunidades de inferencia bayesiana y de procesamiento de señales.​ Los métodos de Montecarlo de cadenas de Markov interactivas también pueden interpretarse como un algoritmo genético de partículas de selección de mutaciones con mutaciones de Montecarlo de cadenas de Markov.

Cadenas de Markov cuasi-Montecarlo (MCQMC)​

La ventaja de las secuencias de baja discrepancia en lugar de los números aleatorios para el muestreo Montecarlo independiente simple es bien conocida.​ Este procedimiento, conocido como método cuasi-Montecarlo (QMC),​ produce un error de integración que decae a un ritmo superior al obtenido por el muestreo IID, por la desigualdad de Koksma-Hlawka. Empíricamente permite reducir tanto el error de estimación como el tiempo de convergencia en un orden de magnitud.^{[cita requerida]} El método Array-RQMC combina el cuasi-Montecarlo aleatorio y la simulación en cadena de Markov, simulando $n$ cadenas simultáneamente de forma que la distribución empírica de los $n$estados en cualquier paso dado es una mejor aproximación a la verdadera distribución de la cadena que con el MCMC ordinario.​ En los experimentos empíricos, la varianza de la media de una función de estado converge a veces a una velocidad $O(n^{-2})$ o incluso más rápido, en lugar del $O(n^{-1})$ de Montecarlo.​

Convergencia

Normalmente no es difícil construir una cadena de Markov con las propiedades deseadas. El problema más difícil es determinar cuántos pasos son necesarios para converger a la distribución estacionaria dentro de un error aceptable.​ Una buena cadena tendrá una mezcla rápida: la distribución estacionaria se alcanza rápidamente partiendo de una posición arbitraria. Un método empírico estándar para evaluar la convergencia consiste en ejecutar varias cadenas de Markov simuladas independientes y comprobar que la relación entre las varianzas entre cadenas y dentro de ellas para todos los parámetros muestreados es cercana a 1.​​

Normalmente, el muestreo de Montecarlo con cadena de Markov sólo puede aproximarse a la distribución objetivo, ya que siempre hay algún efecto residual de la posición inicial. Los algoritmos más sofisticados basados en cadenas de Markov de Montecarlo, como el acoplamiento desde el pasado, pueden producir muestras exactas, a costa de un cálculo adicional y un tiempo de ejecución ilimitado (aunque finito en la expectativa).

Muchos métodos de Montecarlo de paseo aleatorio se mueven alrededor de la distribución de equilibrio en pasos relativamente pequeños, sin tendencia a que los pasos procedan en la misma dirección. Estos métodos son fáciles de implementar y analizar, pero desgraciadamente el caminante puede tardar mucho tiempo en explorar todo el espacio. A menudo, el caminante vuelve atrás y cubre el terreno ya cubierto.

Una consideración más detallada de la convergencia se encuentra en el teorema del límite central de la cadena de Markov. En​ encontramos una discusión de la teoría relacionada con la convergencia y la estacionariedad del algoritmo Metropolis-Hastings.

Software

Varios programas de software proporcionan capacidades de muestreo MCMC, por ejemplo:

• El software de Montecarlo paralelo ParaMonte está disponible en múltiples lenguajes de programación, como C, C++, Fortran, MATLAB y Python.
• Paquetes que utilizan dialectos del lenguaje del modelo BUGS:
  • WinBUGS / OpenBUGS/ MultiBUGS
  • JAGS
• MCSim
• El lenguaje Julia con paquetes como Turing.jl, DynamicHMC.jl, AffineInvariantMCMC.jl, y los del repositorio StanJulia.
• Python con los paquetes emcee, ParaMonte, PyMC3 y vandal.​
• R con los paquetes adaptMCMC, atmcmc, BRugs, mcmc, MCMCpack, ramcmc, rjags, rstan, etc.
• Stan
• TensorFlow Probability (biblioteca de programación probabilística construida sobre TensorFlow)

Referencias

Fuentes

 

• Christophe Andrieu, Nando De Freitas, Arnaud Doucet and Michael I. Jordan An Introduction to MCMC for Machine Learning, 2003
• Asmussen, Søren; Glynn, Peter W. (2007). Stochastic Simulation: Algorithms and Analysis. Stochastic Modelling and Applied Probability 57. Springer. 
• Atzberger, P. «An Introduction to Monte-Carlo Methods». 
• Berg, Bernd A. (2004). Markov Chain Monte Carlo Simulations and Their Statistical Analysis. World Scientific. 
• Bolstad, William M. (2010). Understanding Computational Bayesian Statistics. Wiley. ISBN 978-0-470-04609-8. 
• Casella, George; George, Edward I. (1992). «Explaining the Gibbs sampler». The American Statistician 46 (3): 167-174. JSTOR 2685208. doi:10.2307/2685208. 
• Gelfand, A.E.; Smith, A.F.M. (1990). «Sampling-Based Approaches to Calculating Marginal Densities». Journal of the American Statistical Association 85 (410): 398-409. doi:10.1080/01621459.1990.10476213. 
• Gelman, Andrew; Carlin, John B.; Stern, Hal S.; Rubin, Donald B. (1995). Bayesian Data Analysis (1st edición). Chapman and Hall.  (See Chapter 11.)
• Geman, S.; Geman, D. (1984). «Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images». IEEE Transactions on Pattern Analysis and Machine Intelligence 6 (6): 721-741. PMID 22499653. S2CID 5837272. doi:10.1109/TPAMI.1984.4767596. 
• Gilks, W.R.; Richardson, S.; Spiegelhalter, D.J. (1996). Markov Chain Monte Carlo in Practice. Chapman and Hall/CRC. 
• Gill, Jeff (2008). Bayesian methods: a social and behavioral sciences approach (2nd edición). Chapman and Hall/CRC. ISBN 978-1-58488-562-7. 
• Green, P.J. (1995). «Reversible-jump Markov chain Monte Carlo computation and Bayesian model determination». Biometrika 82 (4): 711-732. doi:10.1093/biomet/82.4.711. 
• Neal, Radford M. (2003). «Slice Sampling». Annals of Statistics 31 (3): 705-767. JSTOR 3448413. doi:10.1214/aos/1056562461. 
• Neal, Radford M. (1993). «Probabilistic Inference Using Markov Chain Monte Carlo Methods». 
• Robert, Christian P.; Casella, G. (2004). Monte Carlo Statistical Methods (2nd edición). Springer. ISBN 978-0-387-21239-5. 
• Rubinstein, R.Y.; Kroese, D.P. (2007). Simulation and the Monte Carlo Method (2nd edición). Wiley. ISBN 978-0-470-17794-5. 
• Smith, R.L. (1984). «Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed Over Bounded Regions». Operations Research 32 (6): 1296-1308. doi:10.1287/opre.32.6.1296. hdl:2027.42/7681. 
• Spall, J.C. (April 2003). «Estimation via Markov Chain Monte Carlo». IEEE Control Systems Magazine 23 (2): 34-45. doi:10.1109/mcs.2003.1188770. 
• Stramer, O.; Tweedie, R. (1999). «Langevin-Type Models II: Self-Targeting Candidates for MCMC Algorithms». Methodology and Computing in Applied Probability 1 (3): 307-328. S2CID 1512689. doi:10.1023/A:1010090512027. 

• Datos: Q1191869