stringtranslate.com

Cadena de Markov Monte Carlo

En estadística , el algoritmo Monte Carlo de cadena de Markov ( MCMC ) es una clase de algoritmos que se utilizan para extraer muestras de una distribución de probabilidad . Dada una distribución de probabilidad, se puede construir una cadena de Markov cuya distribución de elementos se aproxime a ella, es decir, la distribución de equilibrio de la cadena de Markov coincide con la distribución objetivo. Cuantos más pasos se incluyan, más se ajustará la distribución de la muestra a la distribución deseada real.

Los métodos de Monte Carlo de cadenas de Markov se utilizan para estudiar distribuciones de probabilidad que son demasiado complejas o demasiado dimensionales para estudiarlas únicamente con técnicas analíticas. Existen varios algoritmos para construir dichas cadenas de Markov, incluido el algoritmo Metropolis-Hastings .

Aplicaciones

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

En las estadísticas bayesianas, los métodos de Monte Carlo de cadenas de Markov se utilizan normalmente para calcular momentos e intervalos creíbles de distribuciones de probabilidad posteriores . El uso de métodos MCMC permite calcular grandes modelos jerárquicos que requieren integraciones sobre cientos o miles de parámetros desconocidos. [5]

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

Explicación general

Convergencia del algoritmo Metropolis-Hastings . El método Monte Carlo de cadena de Markov intenta aproximar la distribución azul con la distribución naranja.

Los métodos de Monte Carlo de cadena de Markov crean muestras de una variable aleatoria continua , con una 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, se suele desarrollar 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 desplazan aleatoriamente según un algoritmo que busca lugares con una contribución razonablemente alta a la integral para pasar a continuación, asignándoles mayores probabilidades.

Los métodos de Monte Carlo de paseo aleatorio 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 tales que tienen una distribución de equilibrio [ ancla rota ] 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 Monte Carlo, cuando el número de dimensiones aumenta, también tienden a sufrir la maldición de la dimensionalidad : 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 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 obtener un resultado preciso). 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, al tiempo que logran mantener el proceso en las regiones que dan una mayor contribución 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

Paseo aleatorio

Métodos de partículas interactuantes

Las metodologías MCMC interactuantes 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. [12] Estos modelos probabilísticos incluyen modelos de estados del espacio de trayectoria con horizonte temporal creciente, distribuciones posteriores con respecto a la secuencia de observaciones parciales, conjuntos de niveles de restricción crecientes para distribuciones condicionales, programas de temperatura decrecientes asociados con algunas distribuciones de Boltzmann-Gibbs y muchos otros. En principio, cualquier muestreador de Monte Carlo de cadena de Markov se puede convertir en un muestreador de Monte Carlo de cadena de Markov interactuante. Estos muestreadores de Monte Carlo de cadena de Markov interactuantes se pueden interpretar como una forma de ejecutar en paralelo una secuencia de muestreadores de Monte Carlo de cadena de Markov. Por ejemplo, los algoritmos de recocido simulado interactuantes se basan en movimientos Metropolis-Hastings independientes que interactúan secuencialmente con un mecanismo de tipo selección-remuestreo. A diferencia de los métodos tradicionales de Monte Carlo de cadena de Markov, el parámetro de precisión de esta clase de muestreadores de Monte Carlo de cadena de Markov interactuantes solo está relacionado con el número de muestreadores de Monte Carlo de cadena de Markov interactuantes. Estas metodologías de partículas avanzadas pertenecen a la clase de modelos de partículas de Feynman-Kac, [13] [14] también llamados métodos de Monte Carlo secuencial o de filtro de partículas en las comunidades de inferencia bayesiana y procesamiento de señales . [15] Los métodos de Monte Carlo de cadena de Markov interactuantes también se pueden interpretar como un algoritmo de partículas genéticas de selección de mutaciones con mutaciones de Monte Carlo de cadena de Markov.

Cuasi-Monte Carlo

El método cuasi-Monte Carlo es un análogo del método Monte Carlo normal que utiliza secuencias de baja discrepancia en lugar de números aleatorios. [16] [17] Produce un error de integración que decae más rápido que el del muestreo aleatorio verdadero, como se cuantifica mediante la desigualdad de Koksma-Hlawka . Empíricamente, permite la reducción tanto del error de estimación como del tiempo de convergencia en un orden de magnitud. [ cita requerida ] Los métodos cuasi-Monte Carlo de cadena de Markov [18] [19] como el método Array-RQMC combinan la simulación aleatoria cuasi-Monte Carlo y de cadena de Markov simulando cadenas simultáneamente de una manera que se aproxima mejor a la distribución real de la cadena que con el MCMC ordinario. [20] En experimentos empíricos, la varianza del promedio de una función del estado a veces converge a la tasa o incluso más rápido, en lugar de la tasa de Monte Carlo. [21]

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. [22] 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 entre las varianzas intercadena e intracadena para todos los parámetros muestreados sea cercana a 1. [22] [23]

Por lo general, el muestreo de Monte Carlo de 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 Monte Carlo de cadena de Markov, como el acoplamiento a partir del pasado, pueden producir muestras exactas, a costa de cálculos adicionales y un tiempo de ejecución ilimitado (aunque finito en expectativa) .

Muchos métodos de Monte Carlo de paseo aleatorio se mueven alrededor de la distribución de equilibrio en pasos relativamente pequeños, sin que los pasos tiendan a avanzar en la misma dirección. Estos métodos son fáciles de implementar y analizar, pero desafortunadamente puede llevar mucho tiempo para que el caminante explore todo el espacio. El caminante a menudo retrocederá y cubrirá el terreno ya cubierto.

Se puede encontrar una consideración más amplia de la convergencia en el teorema del límite central de la cadena de Markov . Véase [24] para 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:

Véase también

Referencias

Citas

  1. ^ Kasim, MF; Bott, AFA; Tzeferacos, P.; Lamb, DQ; Gregori, G.; Vinko, SM (septiembre de 2019). "Recuperación de campos de radiografía de protones sin perfiles de fuente". Physical Review E . 100 (3): 033208. arXiv : 1905.12934 . Bibcode :2019PhRvE.100c3208K. doi :10.1103/PhysRevE.100.033208. PMID  31639953. S2CID  170078861.
  2. ^ Gupta, Ankur; Rawlings, James B. (abril de 2014). "Comparación de métodos de estimación de parámetros en modelos cinéticos químicos estocásticos: ejemplos en biología de sistemas". AIChE Journal . 60 (4): 1253–1268. Bibcode :2014AIChE..60.1253G. doi :10.1002/aic.14409. PMC 4946376 . PMID  27429455. 
  3. ^ Véase Gill 2008.
  4. ^ Véase Robert y Casella 2004.
  5. ^ Banerjee, Sudipto; Carlin, Bradley P.; Gelfand, Alan P. (12 de septiembre de 2014). Modelado y análisis jerárquico de datos espaciales (segunda edición). CRC Press. pág. xix. ISBN 978-1-4398-1917-3.
  6. ^ Geman, Stuart; Geman, Donald (noviembre de 1984). "Relajación estocástica, distribuciones de Gibbs y restauración bayesiana de imágenes". IEEE Transactions on Pattern Analysis and Machine Intelligence . PAMI-6 (6): 721–741. doi :10.1109/TPAMI.1984.4767596. ISSN  0162-8828. PMID  22499653. S2CID  5837272.
  7. ^ Gilks, WR; Wild, P. (1 de enero de 1992). "Muestreo de rechazo adaptativo para el muestreo de Gibbs". Revista de la Royal Statistical Society. Serie C (Estadística aplicada) . 41 (2): 337–348. doi :10.2307/2347565. JSTOR  2347565.
  8. ^ Gilks, WR; Best, NG ; Tan, KKC (1 de enero de 1995). "Muestreo de metrópolis con rechazo adaptativo dentro del muestreo de Gibbs". Revista de la Royal Statistical Society. Serie C (Estadística aplicada) . 44 (4): 455–472. doi :10.2307/2986138. JSTOR  2986138.
  9. ^ Lee, Se Yoon (2021). "Inferencia variacional mediante el muestreador de Gibbs y el ascenso de coordenadas: una revisión de la teoría de conjuntos". Comunicaciones en estadística: teoría y métodos . 51 (6): 1–21. arXiv : 2008.01006 . doi :10.1080/03610926.2021.1921214. S2CID  220935477.
  10. ^ Véase Stramer 1999.
  11. ^ Véase Green 1995.
  12. ^ Del Moral, Pierre (2013). Simulación de campo medio para integración de Monte Carlo. Chapman & Hall/CRC Press. pág. 626.
  13. ^ Del Moral, Pierre (2004). Fórmulas de Feynman-Kac. Aproximaciones genealógicas y de partículas interactuantes. Springer. pág. 575.
  14. ^ Del Moral, Pierre; Micló, Laurent (2000). "Aproximaciones de sistemas de partículas ramificadas e interactivas de fórmulas de Feynman-Kac con aplicaciones al filtrado no lineal". En Jacques Azéma; Michel Ledoux; Michel Émery; Marc Yor (eds.). Seminario de Probabilités XXXIV (PDF) . Apuntes de conferencias de matemáticas. vol. 1729, págs. 1-145. doi :10.1007/bfb0103798. ISBN 978-3-540-67314-9.
  15. ^ Del Moral, Pierre (2006). "Muestreadores secuenciales de Monte Carlo". Revista de la Royal Statistical Society. Serie B (Metodología estadística) . 68 (3): 411–436. arXiv : cond-mat/0212648 . doi :10.1111/j.1467-9868.2006.00553.x. S2CID  12074789.
  16. ^ Papageorgiou, Anargyros; Traub, JF (1996). "Vencer a Montecarlo". Riesgo . 9 (6): 63–65.
  17. ^ Sobol, Ilya M (1998). "Sobre integraciones cuasi-monte carlo". Matemáticas y computadoras en simulación . 47 (2): 103–112. doi :10.1016/s0378-4754(98)00096-2.
  18. ^ Chen, S.; Dick, Josef; Owen, Art B. (2011). "Consistencia de cadenas de Markov cuasi-Monte Carlo en espacios de estados continuos". Anales de Estadística . 39 (2): 673–701. arXiv : 1105.1896 . doi : 10.1214/10-AOS831 .
  19. ^ Tribble, Seth D. (2007). Algoritmos de Monte Carlo con cadenas de Markov que utilizan secuencias de conducción completamente uniformemente distribuidas (Tesis doctoral). Universidad de Stanford. ProQuest  304808879.
  20. ^ L'Ecuyer, P.; Lécot, C.; Tuffin, B. (2008). "Un método de simulación cuasi-Monte Carlo aleatorio para cadenas de Markov" (PDF) . Investigación de operaciones . 56 (4): 958–975. doi :10.1287/opre.1080.0556.
  21. ^ L'Ecuyer, P.; Munger, D.; Lécot, C.; Tuffin, B. (2018). "Métodos de ordenamiento y tasas de convergencia para Array-RQMC: algunas comparaciones empíricas". Matemáticas y computadoras en simulación . 143 : 191–201. doi :10.1016/j.matcom.2016.07.010.
  22. ^ ab Gelman, A.; Rubin, DB (1992). "Inferencia a partir de simulación iterativa utilizando múltiples secuencias (con discusión)" (PDF) . Ciencia estadística . 7 (4): 457–511. Bibcode :1992StaSc...7..457G. doi : 10.1214/ss/1177011136 .
  23. ^ Cowles, MK; Carlin, BP (1996). "Diagnóstico de convergencia de Monte Carlo de cadena de Markov: una revisión comparativa". Revista de la Asociación Estadounidense de Estadística . 91 (434): 883–904. CiteSeerX 10.1.1.53.3445 . doi :10.1080/01621459.1996.10476956. 
  24. ^ Hill, SD; Spall, JC (2019). "Estacionariedad y convergencia del algoritmo Metropolis-Hastings: perspectivas sobre aspectos teóricos". Revista IEEE Control Systems . 39 (1): 56–67. doi :10.1109/MCS.2018.2876959. S2CID  58672766.
  25. ^ Foreman-Mackey, Daniel; Hogg, David W.; Lang, Dustin; Goodman, Jonathan (25 de noviembre de 2013). "emcee: The MCMC Hammer". Publicaciones de la Sociedad Astronómica del Pacífico . 125 (925): 306–312. arXiv : 1202.3665 . Código Bibliográfico :2013PASP..125..306F. doi :10.1086/670067. S2CID  88518555.
  26. ^ Phan, Du; Pradhan, Neeraj; Jankowiak, Martin (24 de diciembre de 2019). "Efectos componibles para programación probabilística flexible y acelerada en NumPyro". arXiv : 1912.11554 [stat.ML].

Fuentes

Lectura adicional