En estadística , los métodos de cadena de Markov Monte Carlo ( MCMC ) comprenden una clase de algoritmos para muestrear a partir de una distribución de probabilidad . Al construir una cadena de Markov que tiene la distribución deseada como 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 .
En estadística bayesiana, el reciente desarrollo de métodos MCMC ha hecho posible calcular grandes modelos jerárquicos que requieren integraciones de cientos a miles de parámetros desconocidos. [5]
"Convergencia del algoritmo Metropolis-Hastings" . La cadena de Markov Monte Carlo intenta aproximar la distribución azul con la distribución naranja.
Los métodos Monte Carlo de la cadena de Markov crean muestras a partir 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, 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 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.
Si bien 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 de espacio cada vez mayor. que poco aporta 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 necesitarían muchos pasos para una localización precisa). resultado). 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 al mismo tiempo 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 implementar, pero suelen converger más rápido.
Ejemplos
Caminata aleatoria
Algoritmo de Metropolis-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 simple MCMC (algoritmo de Metropolis) y muchas alternativas más recientes que se enumeran a continuación.
Muestreo de Gibbs : cuando la distribución objetivo es multidimensional, el algoritmo de muestreo de Gibbs [6] actualiza cada coordenada a partir de su distribución condicional completa dadas otras coordenadas. El muestreo de Gibbs puede verse como un caso especial del algoritmo de Metropolis-Hastings con una tasa de aceptación uniformemente igual a 1. Cuando no es sencillo extraer de las distribuciones condicionales completas, se utilizan otros muestreadores dentro de Gibbs (por ejemplo, consulte [ 7] [8] ). 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 de coordenadas en el sentido de que ambos algoritmos utilizan distribuciones totalmente condicionales en el procedimiento de actualización. [9]
Algoritmo de Langevin ajustado por Metropolis y otros métodos que se basan en el gradiente (y posiblemente la segunda derivada) de la densidad objetivo logarítmica para proponer pasos que es más probable que estén en la dirección de una densidad de probabilidad más alta. [10]
Metrópolis pseudomarginal-Hastings: este método reemplaza la evaluación de la densidad de la distribución objetivo con una estimación insesgada y es útil cuando la densidad objetivo no está disponible analíticamente, por ejemplo, modelos de variables latentes .
Muestreo de cortes : este método depende del principio de que se puede tomar muestras de una distribución muestreando uniformemente de la región bajo la gráfica de su función de densidad. Alterna el muestreo uniforme en la dirección vertical con el muestreo uniforme del 'corte' horizontal definido por la posición vertical actual.
Metropolis de intentos múltiples : este método es una variación del algoritmo Metropolis-Hastings que permite múltiples intentos en cada punto. Al permitir dar pasos más grandes en cada iteración, se 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. [11] Los métodos Monte Carlo de 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 un gran conjunto canónico (por ejemplo, cuando el número de moléculas en una caja es variable). Pero la variante de salto reversible es útil cuando se realiza un muestreo de Monte Carlo o Gibbs en cadena de Markov sobre modelos bayesianos no paramétricos , como los que involucran el proceso de Dirichlet o el proceso del restaurante chino , donde el número de componentes/grupos/etc. se infiere automáticamente a partir de los datos.
Monte Carlo hamiltoniano (o híbrido) (HMC): intenta evitar el comportamiento de caminata aleatoria introduciendo un vector de impulso auxiliar e implementando la dinámica hamiltoniana , de modo que la función de energía potencial sea la densidad objetivo. Las muestras de impulso se descartan después del muestreo. El resultado final del Monte Carlo 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 correlacionados 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. [12] Estos modelos probabilísticos incluyen modelos de estado del espacio de trayectoria con horizonte temporal creciente, distribuciones posteriores con 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 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 se pueden interpretar como una forma de ejecutar en paralelo una secuencia de muestreadores Monte Carlo de cadena de Markov. Por ejemplo, los algoritmos de recocido simulados 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 Monte Carlo de cadena de Markov, el parámetro de precisión de esta clase de muestreadores Monte Carlo de cadena de Markov que interactúan solo está relacionado con el número de muestreadores Monte Carlo de cadena de Markov que interactúan. Estas metodologías avanzadas de partículas pertenecen a la clase de modelos de partículas de Feynman-Kac, [13] [14] también llamados Monte Carlo secuencial o métodos de filtro de partículas en las comunidades de procesamiento de señales y inferencia bayesiana . [15] Los métodos de Monte Carlo de cadena de Markov que interactúan 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.
Cadena de Markov cuasi-Monte Carlo (MCQMC) [16] [17]
Es bien conocida la ventaja de secuencias de baja discrepancia en lugar de números aleatorios para el muestreo Monte Carlo independiente simple. [18] Este procedimiento, conocido como método Quasi-Monte Carlo (QMC), [19] produce un error de integración que decae a un ritmo superior al obtenido mediante 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 necesaria ] El método Array-RQMC combina la simulación aleatoria de cadenas cuasi-Monte Carlo y Markov simulando cadenas simultáneamente de manera que la distribución empírica de los estados en cualquier paso dado sea una mejor aproximación de la verdadera distribución de la cadena que con MCMC ordinario. [20] En experimentos empíricos, la varianza del promedio de una función del estado a veces converge a una tasa o incluso más rápido, en lugar de la tasa de Monte Carlo. [21]
Convergencia
Normalmente no resulta 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 entre cadenas e intracadenas para todos los parámetros muestreados sea cercana a 1. [22] [23]
Normalmente, 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 cálculos adicionales y un tiempo de ejecución ilimitado (aunque finito en expectativas) .
Muchos métodos de Monte Carlo de paseo aleatorio 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 el caminante puede tardar mucho tiempo en explorar todo el espacio. El caminante a menudo retrocederá y cubrirá el terreno ya recorrido.
Una consideración más detallada de la convergencia se encuentra 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 de Metropolis-Hastings.
Software
Varios programas de software proporcionan capacidades de muestreo MCMC, por ejemplo:
El software ParaMonte Monte Carlo paralelo está disponible en múltiples lenguajes de programación, incluidos C , C++ , Fortran , MATLAB y Python .
Software vandálico para la creación de simulación Monte Carlo disponible en Python .
Paquetes que utilizan dialectos del lenguaje modelo BUGS :
^ Kasim, MF; Bott, AFA; Tzeferacos, P.; Cordero, DQ; Gregorio, G.; Vinko, SM (septiembre de 2019). "Recuperación de campos de radiografía de protones sin perfiles de origen". Revisión física E. 100 (3): 033208. arXiv : 1905.12934 . Código bibliográfico : 2019PhRvE.100c3208K. doi : 10.1103/PhysRevE.100.033208. PMID 31639953. S2CID 170078861.
^ 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". Revista AIChE . 60 (4): 1253–1268. doi :10.1002/aic.14409. PMC 4946376 . PMID 27429455.
^ Ver Gill 2008.
^ Véase Robert y Casella 2004.
^ Banerjee, Sudipto; Carlin, Bradley P.; Gelfand, Alan P. (12 de septiembre de 2014). Modelado y análisis jerárquico de datos espaciales (Segunda ed.). Prensa CRC. pag. xix. ISBN978-1-4398-1917-3.
^ Alemán, Stuart; Geman, Donald (noviembre de 1984). "Relajación estocástica, distribuciones de Gibbs y restauración bayesiana de imágenes". Transacciones IEEE sobre análisis de patrones e inteligencia artificial . PAMI-6 (6): 721–741. doi :10.1109/TPAMI.1984.4767596. ISSN 0162-8828. PMID 22499653. S2CID 5837272.
^ Gilks, WR; Salvaje, P. (1 de enero de 1992). "Muestreo de rechazo adaptativo para muestreo de Gibbs". Revista de la Real Sociedad de Estadística. Serie C (Estadística Aplicada) . 41 (2): 337–348. doi :10.2307/2347565. JSTOR 2347565.
^ Gilks, WR; Mejor, NG ; Bronceado, KKC (1 de enero de 1995). "Muestreo de metrópolis de rechazo adaptativo dentro del muestreo de Gibbs". Revista de la Real Sociedad de Estadística. Serie C (Estadística Aplicada) . 44 (4): 455–472. doi :10.2307/2986138. JSTOR 2986138.
^ Lee, Se Yoon (2021). "Muestreador de Gibbs e inferencia variacional de 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.
^ Véase Stramer 1999.
^ Ver Verde 1995.
^ Del Moral, Pierre (2013). Simulación de campo medio para la integración de Monte Carlo. Chapman y Hall/CRC Press. pag. 626.
^ Del Moral, Pierre (2004). Fórmulas de Feynman-Kac. Aproximaciones genealógicas y de partículas interactuantes. Saltador. pag. 575.
^ 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. ISBN978-3-540-67314-9.
^ Del Moral, Pierre (2006). "Muestreadores secuenciales de Monte Carlo". Revista de la Real Sociedad de Estadística. 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.
^ Chen, S.; Dick, José; Owen, arte B. (2011). "Consistencia de la cadena de Markov cuasi-Montecarlo en espacios de estados continuos". Anales de Estadística . 39 (2): 673–701. arXiv : 1105.1896 . doi : 10.1214/10-AOS831 .
^ Tribble, Seth D. (2007). Algoritmos Monte Carlo de cadena de Markov que utilizan secuencias de conducción distribuidas de manera completamente uniforme (Diss.). Universidad Stanford. ProQuest 304808879.
^ Sobol, Ilya M (1998). "Sobre las integraciones cuasi-montecarlo". Matemáticas y Computación en Simulación . 47 (2): 103–112. doi :10.1016/s0378-4754(98)00096-2.
^ L'Ecuyer, P.; Lécot, C.; Tuffin, B. (2008). "Un método de simulación aleatorio cuasi-Monte Carlo para cadenas de Markov" (PDF) . La investigación de operaciones . 56 (4): 958–975. doi :10.1287/opre.1080.0556.
^ L'Ecuyer, P.; Munger, D.; Lécot, C.; Tuffin, B. (2018). "Métodos de clasificación y tasas de convergencia para Array-RQMC: algunas comparaciones empíricas". Matemáticas y Computación en Simulación . 143 : 191-201. doi : 10.1016/j.matcom.2016.07.010.
^ 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. Código bibliográfico : 1992StaSc...7..457G. doi : 10.1214/ss/1177011136 .
^ Cowles, MK; Carlin, BP (1996). "Diagnóstico de convergencia de Monte Carlo de la 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.
^ Hill, Dakota del Sur; Spall, JC (2019). "Estacionariedad y convergencia del algoritmo Metropolis-Hastings: conocimientos sobre aspectos teóricos". Revista de sistemas de control IEEE . 39 (1): 56–67. doi :10.1109/MCS.2018.2876959. S2CID 58672766.
^ Capataz-Mackey, Daniel; Hogg, David W.; Lang, Dustin; Goodman, Jonathan (25 de noviembre de 2013). "maestro de ceremonias: el martillo MCMC". Publicaciones de la Sociedad Astronómica del Pacífico . 125 (925): 306–312. arXiv : 1202.3665 . Código Bib : 2013PASP..125..306F. doi :10.1086/670067. S2CID 88518555.
Fuentes
Christophe Andrieu, Nando De Freitas, Arnaud Doucet y Michael I. Jordan Introducción a MCMC para el aprendizaje automático, 2003
Asmussen, Søren; Glynn, Peter W. (2007). Simulación estocástica: algoritmos y análisis . Modelización estocástica y probabilidad aplicada. vol. 57. Saltador.
Atzberger, P. "Introducción a los métodos de Montecarlo" (PDF) .
Bolstad, William M. (2010). Comprensión de la estadística bayesiana computacional . Wiley. ISBN 978-0-470-04609-8.
Casella, George; George, Eduardo I. (1992). "Explicando la muestra de Gibbs". El estadístico estadounidense . 46 (3): 167-174. CiteSeerX 10.1.1.554.3993 . doi :10.2307/2685208. JSTOR 2685208.
Gill, Jeff (2008). Métodos bayesianos: un enfoque de las ciencias sociales y del comportamiento (2ª ed.). Chapman y Hall /CRC. ISBN 978-1-58488-562-7.
Verde, PJ (1995). "Cálculo de Monte Carlo de la cadena de Markov de salto reversible y determinación del modelo bayesiano". Biometrika . 82 (4): 711–732. CiteSeerX 10.1.1.407.8942 . doi :10.1093/biomet/82.4.711.
Neal, Radford M. (2003). "Muestreo de cortes". Anales de Estadística . 31 (3): 705–767. doi : 10.1214/aos/1056562461 . JSTOR 3448413.
Neal, Radford M. (1993). "Inferencia probabilística utilizando métodos de Monte Carlo de cadena de Markov".
Robert, Christian P.; Casella, G. (2004). Métodos estadísticos de Monte Carlo (2ª ed.). Saltador. ISBN 978-0-387-21239-5.
Smith, RL (1984). "Procedimientos eficientes de Monte Carlo para generar puntos distribuidos uniformemente en regiones delimitadas". La investigación de operaciones . 32 (6): 1296-1308. doi :10.1287/opre.32.6.1296. hdl : 2027.42/7681 .
Spall, JC (abril de 2003). "Estimación mediante la cadena de Markov Monte Carlo". Revista de sistemas de control IEEE . 23 (2): 34–45. doi :10.1109/mcs.2003.1188770.
Stramer, O.; Tweedie, R. (1999). "Modelos tipo Langevin II: candidatos de autofocalización para algoritmos MCMC". Metodología y Computación en Probabilidad Aplicada . 1 (3): 307–328. doi :10.1023/A:1010090512027. S2CID 1512689.
Otras lecturas
Diaconis, Persi (abril de 2009). «La revolución de Montecarlo de la cadena de Markov» (PDF) . Toro. América. Matemáticas. Soc. 46 (2): 179–205. doi : 10.1090/s0273-0979-08-01238-x . S 0273-0979(08)01238-X.
Richey, Matthew (mayo de 2010). "La evolución de los métodos Monte Carlo de la cadena de Markov" (PDF) . El Mensual Matemático Estadounidense . 117 (5): 383–413. CiteSeerX 10.1.1.295.4478 . doi :10.4169/000298910x485923. S2CID 13630404.