Cadena de Markov-Monte Carlo

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

En estadística, los métodos de cadena de Markov Monte Carlo (MCMC) comprenden una clase de algoritmos para el muestreo de una distribución de probabilidad. Al construir una cadena de Markov que tenga la distribución deseada como su distribución de equilibrio, se puede obtener una muestra de la distribución deseada registrando los 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 Metropolis-Hastings.

Dominios de aplicación

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

En las estadísticas bayesianas, el reciente desarrollo de los métodos MCMC ha hecho posible calcular grandes modelos jerárquicos que requieren integraciones de cientos a 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 falla rara.

Explicación general

Los métodos de cadena de Markov Monte Carlo crean muestras a partir de una variable aleatoria continua, con densidad de probabilidad proporcional a una función conocida. Estas muestras se pueden utilizar para evaluar una integral sobre esa variable, como su valor esperado o varianza.

En la práctica, generalmente se desarrolla un conjunto de cadenas a partir de un conjunto de puntos elegidos arbitrariamente y suficientemente distantes entre sí. Estas cadenas son procesos estocásticos de "caminantes" que se mueven aleatoriamente de acuerdo con un algoritmo que busca lugares con una contribución razonablemente alta a la integral para moverse a continuación, asignándoles mayores probabilidades.

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

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

Reducir la correlación

Si bien los métodos MCMC se crearon para abordar problemas multidimensionales mejor que los algoritmos genéricos de Monte Carlo, cuando aumenta el número de dimensiones, también tienden a sufrir la maldición de la dimensionalidad: las regiones de mayor probabilidad tienden a estirarse y perderse en un volumen de espacio cada vez mayor. que contribuye poco a la integral. Una forma de abordar este problema podría ser acortar los pasos del caminante, de modo que no intente continuamente salir de la región de mayor probabilidad, aunque de esta manera el proceso estaría altamente autocorrelacionado y sería costoso (es decir, se requerirían muchos pasos para un resultado exacto). Métodos más sofisticados, como el hamiltoniano Monte Carlo y el algoritmo de Wang y Landau, utilizan varias formas de reducir esta autocorrelación. logrando mantener el proceso en las regiones que dan un mayor aporte a la integral. Estos algoritmos generalmente se basan en una teoría más complicada y son más difíciles de implementar, pero generalmente convergen más rápido.

Ejemplos

Caminata aleatoria

Algoritmo Metropolis-Hastings: este método genera una cadena de Markov utilizando una densidad 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 simple MCMC (algoritmo Metropolis) 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 se muestreen exactamente. Cuando dibujar a partir de las distribuciones condicionales completas no es sencillo, se utilizan otros muestreadores dentro de Gibbs (p. ej., consulte). El muestreo de Gibbs es popular en parte porque no requiere ningún "ajuste". La estructura del algoritmo del muestreo de Gibbs se parece mucho a la de la inferencia variacional de ascenso coordinado en que ambos algoritmos utilizan las distribuciones condicionales completas en el procedimiento de actualización.
- El algoritmo de Langevin ajustado por Metropolis y otros métodos que se basan en el gradiente (y posiblemente en la segunda derivada) de la densidad del objetivo logarítmico para proponer pasos que tienen más probabilidades de estar en la dirección de una mayor densidad de probabilidad.
- Metropolis-Hastings pseudomarginal: este método reemplaza la evaluación de la densidad de la distribución objetivo con una estimación imparcial y es útil cuando la densidad objetivo no está disponible analíticamente, por ejemplo, modelos de variables latentes.
Muestreo por sectores: este método se basa en el principio de que se puede muestrear una distribución muestreando uniformemente 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 del 'rebanado' horizontal definido por la posición vertical actual.
Metropolis de múltiples intentos: este método es una variación del algoritmo Metropolis-Hastings que permite múltiples intentos en cada punto. Al hacer posible dar pasos más grandes en cada iteración, ayuda a abordar 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 cadena de Markov Monte Carlo 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 un gran conjunto canónico (p. ej., cuando el número de moléculas en una caja es variable). Pero la variante de salto reversible es útil cuando se realizan muestreos de cadena de Markov Monte Carlo o Gibbs sobre modelos bayesianos no paramétricos, como los que involucran el proceso de Dirichlet o el proceso de restaurante chino, donde el número de componentes de mezcla/grupos/etc. se deduce automáticamente de los datos.
Montecarlo hamiltoniano (o híbrido) (HMC): trata de evitar el comportamiento de caminata aleatoria mediante la introducción de un vector de impulso auxiliar y la implementación de la dinámica hamiltoniana, por lo que la función de energía potencial es la densidad objetivo. Las muestras de impulso se descartan después del muestreo. El resultado final de Hybrid Monte Carlo es que las propuestas se mueven a través del espacio de muestra en pasos más grandes; por lo tanto, están menos correlacionados y convergen a la distribución objetivo más rápidamente.

Métodos de partículas que interactúan

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 ruta con horizonte de tiempo creciente, distribuciones posteriores con secuencia de observaciones parciales, conjuntos de niveles de restricción crecientes para distribuciones condicionales, programas de temperatura decreciente asociados con algunas distribuciones de Boltzmann-Gibbs y muchos otros. En principio, cualquier muestreador Monte Carlo de cadena de Markov se puede convertir en un muestreador Monte Carlo de cadena de Markov interactivo. Estos muestreadores Monte Carlo de cadena de Markov que interactúan pueden interpretarse como una forma de ejecutar en paralelo una secuencia de muestreadores Monte Carlo de cadena de Markov. Por ejemplo, los algoritmos de recocido simulado que interactúan se basan en movimientos independientes de Metropolis-Hastings que interactúan secuencialmente con un mecanismo de tipo selección-remuestreo. A diferencia de los métodos tradicionales de cadena de Markov Monte Carlo,solo relacionado con el número de muestreadores Monte Carlo de la cadena de Markov que interactúan. Estas metodologías de partículas avanzadas pertenecen a la clase de modelos de partículas de Feynman-Kac, también llamados Monte Carlo secuencial o métodos de filtro de partículas en comunidades de procesamiento de señales e inferencia bayesiana. Los métodos de Monte Carlo de la cadena de Markov interactivos también se pueden interpretar como un algoritmo de partículas genéticas de selección de mutación con mutaciones de Monte Carlo de la cadena de Markov.

Cadena de Markov cuasi-Monte Carlo (MCQMC).

Es bien conocida la ventaja de las secuencias de baja discrepancia en lugar de los números aleatorios para el muestreo Monte Carlo independiente simple. Este procedimiento, conocido como método Quasi-Monte Carlo (QMC), arroja un error de integración que decae a una tasa superior a la obtenida por 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. El método Array-RQMC combina la simulación aleatoria de cadenas cuasi-Monte Carlo y Markov al simular $norte$ cadenas simultáneamente de manera que la distribución empírica de los $norte$ estados en cualquier paso dado es una mejor aproximación de la verdadera distribución de la cadena que con el MCMC ordinario.En experimentos empíricos, la varianza del promedio de una función del estado a veces converge a la tasa ${ estilo de visualización O (n ^ {-2})}$ o incluso más rápido, en lugar de la $O(n^{-1})$ tasa de Monte Carlo.

Convergencia

Por lo general, no es difícil construir una cadena de Markov con las propiedades deseadas. El problema más difícil es determinar cuántos pasos se necesitan 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 a partir de una posición arbitraria. Un método empírico estándar para evaluar la convergencia es ejecutar varias cadenas de Markov simuladas independientes y verificar que la relación de varianzas entre cadenas e intracadenas para todos los parámetros muestreados sea cercana a 1.

Por lo general, el muestreo Monte Carlo de la cadena de Markov solo 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 la cadena de Markov Monte Carlo, como el acoplamiento del 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 Monte Carlo de caminata aleatoria se mueven alrededor de la distribución de equilibrio en pasos relativamente pequeños, sin tendencia a que los pasos avancen en la misma dirección. Estos métodos son fáciles de implementar y analizar, pero desafortunadamente puede tomar mucho tiempo para que el caminante explore todo el espacio. El andador a menudo retrocederá y cubrirá el terreno ya cubierto.

Una consideración adicional de la convergencia se encuentra en el teorema del límite central de la cadena de Markov. Consulte una discusión de la teoría relacionada con la convergencia y la estacionariedad del algoritmo Metropolis-Hastings.

Software

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

Software ParaMonte paralelo Monte Carlo disponible en varios lenguajes de programación, incluidos C, C++, Fortran, MATLAB y Python.
Software Vandal para creación de simulación Monte Carlo disponible en Python.
Paquetes que usan dialectos del lenguaje modelo BUGS:
- WinBUGS/OpenBUGS/MultiBUGS
- JAGAS
MCSim
Lenguaje Julia con paquetes como Turing.jl, DynamicHMC.jl, AffineInvariantMCMC.jl y los del repositorio StanJulia.
Python (lenguaje de programación) con los paquetes emcee, ParaMonte, PyMC3 y vandal.
R (lenguaje de programación) con los paquetes adaptMCMC, atmcmc, BRugs, mcmc, MCMCpack, ramcmc, rjags, rstan, etc.
Stan
TensorFlow Probability (biblioteca de programación probabilística basada en TensorFlow)
Marco de alto rendimiento de Korali para UQ bayesiano, optimización y aprendizaje por refuerzo.

Contenido relacionado

Más resultados...