Algoritmo de muestreo anidado

El algoritmo de muestreo anidado es un enfoque computacional para los problemas estadísticos bayesianos de comparar modelos y generar muestras a partir de distribuciones posteriores. Fue desarrollado en 2004 por el físico John Skilling. ^[1]

Fondo

El teorema de Bayes se puede aplicar a un par de modelos en competencia y a datos , uno de los cuales puede ser verdadero (aunque se desconoce cuál) pero ambos no pueden ser verdaderos simultáneamente. La probabilidad posterior de puede calcularse como: ${\displaystyle M_{1}}$ ${\displaystyle M_{2}}$ ${\displaystyle D}$ ${\displaystyle M_{1}}$

${\displaystyle {\begin{aligned}P(M_{1}\mid D)&={\frac {P(D\mid M_{1})P(M_{1})}{P(D)}}\\&={\frac {P(D\mid M_{1})P(M_{1})}{P(D\mid M_{1})P(M_{1})+P(D\mid M_{2})P(M_{2})}}\\&={\frac {1}{1+{\frac {P(D\mid M_{2})}{P(D\mid M_{1})}}{\frac {P(M_{2})}{P(M_{1})}}}}\end{aligned}}}$

Las probabilidades a priori y ya son conocidas, ya que el investigador las elige de antemano. Sin embargo, el factor de Bayes restante no es tan fácil de evaluar, ya que en general requiere marginar parámetros molestos. Generalmente, tiene un conjunto de parámetros que se pueden agrupar y llamar , y tiene su propio vector de parámetros que pueden ser de diferente dimensionalidad, pero aún así se denomina . La marginación es ${\displaystyle M_{1}}$ ${\displaystyle M_{2}}$ ${\displaystyle P(D\mid M_{2})/P(D\mid M_{1})}$ ${\displaystyle M_{1}}$ ${\displaystyle \theta }$ ${\displaystyle M_{2}}$ ${\displaystyle \theta }$ ${\displaystyle M_{1}}$

${\displaystyle P(D\mid M_{1})=\int d\theta \,P(D\mid \theta ,M_{1})P(\theta \mid M_{1})}$

y lo mismo para . Esta integral suele ser analíticamente intratable y en estos casos es necesario emplear un algoritmo numérico para encontrar una aproximación. El algoritmo de muestreo anidado fue desarrollado por John Skilling específicamente para aproximar estas integrales de marginación y tiene el beneficio adicional de generar muestras a partir de la distribución posterior . ^[2] Es una alternativa a los métodos de la literatura bayesiana ^[3], como el muestreo de puentes y el muestreo de importancia defensiva. ${\displaystyle M_{2}}$ ${\displaystyle P(\theta \mid D,M_{1})}$

Aquí hay una versión simple del algoritmo de muestreo anidado, seguida de una descripción de cómo calcula la densidad de probabilidad marginal donde es o : ${\displaystyle Z=P(D\mid M)}$ ${\displaystyle M}$ ${\displaystyle M_{1}}$ ${\displaystyle M_{2}}$

Comience con puntos tomados de muestras anteriores. for to do  % El número de iteraciones j se elige mediante conjeturas. valores de probabilidad actuales de los puntos ; Guarde el punto con menor probabilidad como punto de muestra con peso . ${\displaystyle N}$ ${\displaystyle \theta _{1},\ldots ,\theta _{N}}$  ${\displaystyle i=1}$ ${\displaystyle j}$  ${\displaystyle L_{i}:=\min(}$ ${\displaystyle )}$ ${\displaystyle X_{i}:=\exp(-i/N);}$  ${\displaystyle w_{i}:=X_{i-1}-X_{i}}$  ${\displaystyle Z:=Z+L_{i}\cdot w_{i};}$ ${\displaystyle w_{i}}$ Actualice el punto con menor probabilidad con algunos pasos de Monte Carlo de la cadena de Markov de acuerdo con lo anterior, aceptando solo los pasos que Mantenga la probabilidad arriba . fin de retorno ; ${\displaystyle L_{i}}$  ${\displaystyle Z}$

En cada iteración, hay una estimación de la cantidad de masa anterior cubierta por el hipervolumen en el espacio de parámetros de todos los puntos con probabilidad mayor que . El factor de peso es una estimación de la cantidad de masa anterior que se encuentra entre dos hipersuperficies anidadas y . El paso de actualización calcula la suma de para aproximar numéricamente la integral ${\displaystyle X_{i}}$ ${\displaystyle \theta _{i}}$ ${\displaystyle w_{i}}$ ${\displaystyle \{\theta \mid P(D\mid \theta ,M)=P(D\mid \theta _{i-1},M)\}}$ ${\displaystyle \{\theta \mid P(D\mid \theta ,M)=P(D\mid \theta _{i},M)\}}$ ${\displaystyle Z:=Z+L_{i}w_{i}}$ ${\displaystyle i}$ ${\displaystyle L_{i}w_{i}}$

${\displaystyle {\begin{aligned}P(D\mid M)&=\int P(D\mid \theta ,M)P(\theta \mid M)\,d\theta \\&=\int P(D\mid \theta ,M)\,dP(\theta \mid M)\end{aligned}}}$

En el límite , este estimador tiene un sesgo positivo de orden ^[4] que puede eliminarse utilizando en lugar del algoritmo anterior. ${\displaystyle j\to \infty }$ ${\displaystyle 1/N}$ ${\displaystyle (1-1/N)}$ ${\displaystyle \exp(-1/N)}$

La idea es subdividir el rango de y estimar, para cada intervalo , qué probabilidad hay a priori de que un objeto elegido al azar se corresponda con este intervalo. Esto puede considerarse como una forma bayesiana de implementar numéricamente la integración de Lebesgue . ^[5] ${\displaystyle f(\theta )=P(D\mid \theta ,M)}$ ${\displaystyle [f(\theta _{i-1}),f(\theta _{i})]}$ ${\displaystyle \theta }$

Implementaciones

Implementaciones de ejemplo que demuestran el algoritmo de muestreo anidado están disponibles públicamente para su descarga, escritas en varios lenguajes de programación .

• En el sitio web de John Skilling se encuentran ejemplos sencillos en C , R o Python . ^[6]
• Una adaptación de Haskell de los códigos simples anteriores se encuentra en Hackage. ^[7]
• Un ejemplo en R diseñado originalmente para ajustar espectros se describe en ^[8] y está en GitHub. ^[9]
• Un NestedSampler es parte de la caja de herramientas de Python BayesicFitting ^[10] para el ajuste de modelos genéricos y el cálculo de evidencia. Está en Github ^[11]
• Un ejemplo en C++ , llamado Diamonds, está en GitHub. ^[12]
• Un ejemplo paralelo de Python altamente modular para usos de la física estadística y la física de la materia condensada se encuentra en GitHub. ^[13]
• pymatnest es un paquete de Python diseñado para explorar el panorama energético de diferentes materiales, calcular variables termodinámicas a temperaturas arbitrarias y localizar transiciones de fase en GitHub. ^[14]
• El paquete de software MultiNest es capaz de realizar muestreos anidados en distribuciones posteriores multimodales. ^[15] Tiene interfaces para entradas de C++, Fortran y Python, y está disponible en GitHub. ^[dieciséis]
• PolyChord es otro paquete de software de muestreo anidado disponible en GitHub. ^[17] La ​​eficiencia computacional de PolyChord aumenta mejor con un aumento en el número de parámetros que MultiNest, lo que significa que PolyChord puede ser más eficiente para problemas de alta dimensión. ^[18]
• NestedSamplers.jl, un paquete de Julia para implementar algoritmos de muestreo anidados elipsoidales simples y múltiples, está en GitHub. ^[19]
• Korali es un marco de alto rendimiento para la cuantificación de la incertidumbre, la optimización y el aprendizaje por refuerzo profundo, que también implementa muestreo anidado.

Aplicaciones

Desde que se propuso el muestreo anidado en 2004, se ha utilizado en muchos aspectos del campo de la astronomía . Un artículo sugirió utilizar muestreo anidado para la selección de modelos cosmológicos y la detección de objetos, ya que "combina de manera única precisión, aplicabilidad general y viabilidad computacional". ^[20] Se ha sugerido un refinamiento del algoritmo para manejar posteriores multimodales como un medio para detectar objetos astronómicos en conjuntos de datos existentes. ^[15] Otras aplicaciones del muestreo anidado se encuentran en el campo de la actualización de elementos finitos, donde el algoritmo se utiliza para elegir un modelo de elementos finitos óptimo , y esto se aplicó a la dinámica estructural . ^[21] Este método de muestreo también se ha utilizado en el campo del modelado de materiales. Se puede utilizar para aprender la función de partición de la mecánica estadística y derivar propiedades termodinámicas . ^[22]

Muestreo anidado dinámico

El muestreo anidado dinámico es una generalización del algoritmo de muestreo anidado en el que el número de muestras tomadas en diferentes regiones del espacio de parámetros se ajusta dinámicamente para maximizar la precisión del cálculo. ^[23] Esto puede conducir a grandes mejoras en la precisión y la eficiencia computacional en comparación con el algoritmo de muestreo anidado original, en el que la asignación de muestras no se puede cambiar y, a menudo, muchas muestras se toman en regiones que tienen poco efecto en la precisión del cálculo.

Los paquetes de software de muestreo anidado dinámico disponibles públicamente incluyen:

• dynesty: una implementación de Python de muestreo dinámico anidado que se puede descargar desde GitHub. ^{[24] [25]}
• dyPolyChord: un paquete de software que se puede utilizar con Python, C++ y Fortran probable y distribuciones anteriores. ^[26] dyPolyChord está disponible en GitHub. ^[27]

El muestreo dinámico anidado se ha aplicado a una variedad de problemas científicos, incluido el análisis de ondas gravitacionales, ^[28] el mapeo de distancias en el espacio ^[29] y la detección de exoplanetas. ^[30]

Ver también

• Comparación de modelos bayesianos
• Lista de algoritmos

Referencias

1. Habilidad, John (2004). "Muestreo anidado". Actas de la conferencia AIP . 735 : 395–405. Código Bib : 2004AIPC..735..395S. doi : 10.1063/1.1835238.
2. Habilidad, John (2006). "Muestreo anidado para computación bayesiana general". Análisis bayesiano . 1 (4): 833–860. doi : 10.1214/06-BA127 .
3. Chen, Ming-Hui, Shao, Qi-Man e Ibrahim, Joseph George (2000). Métodos de Monte Carlo en computación bayesiana. Saltador. ISBN 978-0-387-98935-8.{{cite book}}: CS1 maint: multiple names: authors list (link)
4. Walter, Clemente (2017). "Estimación de Monte Carlo basada en procesos puntuales". Estadística y Computación . 27 : 219–236. arXiv : 1412.6368 . doi :10.1007/s11222-015-9617-y. S2CID  14639080.
5. Jasa, Tomislav; Xiang, Ning (2012). "Muestreo anidado aplicado en el análisis de decadencia de la acústica ambiental bayesiana". Revista de la Sociedad de Acústica de América . 132 (5): 3251–3262. Código Bib : 2012ASAJ..132.3251J. doi :10.1121/1.4754550. PMID  23145609. S2CID  20876510.
6. Sitio web de John Skilling
7. Algoritmo de muestreo anidado en Haskell en Hackage
8. Algoritmo de muestreo anidado en R en el sitio web de Bojan Nikolic
9. Algoritmo de muestreo anidado en R en GitHub
10. Kester, D.; Mueller, M. (2021). "BayesicFitting, una caja de herramientas de PYTHON para ajuste bayesiano y cálculo de evidencia: incluida una implementación de muestreo anidado". Astronomía y Computación . 37 : 100503. arXiv : 2109.11976 . doi : 10.1016/j.ascom.2021.100503 .
11. Caja de herramientas de Python que contiene un algoritmo de muestreo anidado en GitHub
12. Algoritmo de muestreo anidado en C++ en GitHub
13. Algoritmo de muestreo anidado en Python en GitHub
14. Algoritmo de muestreo anidado para simulación de materiales en GitHub
15. Feroz, F.; Hobson, diputado (2008). "Muestreo anidado multimodal: una alternativa eficiente y sólida a los métodos de Markov Chain Monte Carlo para análisis de datos astronómicos". MNRAS . 384 (2): 449–463. arXiv : 0704.3704 . Código bibliográfico : 2008MNRAS.384..449F. doi :10.1111/j.1365-2966.2007.12353.x. S2CID  14226032.
16. El paquete de software de muestreo anidado MultiNest en GitHub
17. El paquete de software de muestreo anidado PolyChord en GitHub
18. Handley, voluntad; Hobson, Mike; Lasenby, Anthony (2015). "policordio: muestreo anidado de próxima generación". Avisos mensuales de la Real Sociedad Astronómica . 453 (4): 4384–4398. arXiv : 1506.00171 . Código Bib : 2015MNRAS.453.4384H. doi :10.1093/mnras/stv1911. S2CID  118882763.
19. Implementaciones de muestreo anidado de elipsoide simple y múltiple en Julia en GitHub
20. Mukherjee, P.; Parkinson, D.; Liddle, AR (2006). "Un algoritmo de muestreo anidado para la selección de modelos cosmológicos". Revista Astrofísica . 638 (2): 51–54. arXiv : astro-ph/0508461 . Código Bib : 2006ApJ...638L..51M. doi :10.1086/501068. S2CID  6208051.
21. Mthembu, L.; Marwala, T.; Friswell, Michigan; Adhikari, S. (2011). "Selección de modelo en actualización de modelos de elementos finitos utilizando la estadística de evidencia bayesiana". Sistemas Mecánicos y Procesamiento de Señales . 25 (7): 2399–2412. Código Bib : 2011MSSP...25.2399M. doi :10.1016/j.ymssp.2011.04.001.
22. Partay, Livia B. (2010). "Muestreo eficiente de espacios de configuración atómica". La Revista de Química Física B. 114 (32): 10502–10512. arXiv : 0906.3544 . doi :10.1021/jp1012973. PMID  20701382. S2CID  16834142.
23. Higson, Eduardo; Handley, voluntad; Hobson, Michael; Lasenby, Anthony (2019). "Muestreo dinámico anidado: un algoritmo mejorado para la estimación de parámetros y el cálculo de evidencia". Estadística y Computación . 29 (5): 891–913. arXiv : 1704.03459 . Código Bib : 2019S&C....29..891H. doi :10.1007/s11222-018-9844-0. S2CID  53514669.
24. El paquete de software de muestreo anidado dynesty en GitHub
25. Speagle, Josué (2020). "dynesty: un paquete de muestreo dinámico anidado para estimar evidencias y posteriores bayesianos". Avisos mensuales de la Real Sociedad Astronómica . 493 (3): 3132–3158. arXiv : 1904.02180 . doi :10.1093/mnras/staa278. S2CID  102354337.
26. Higson, Edward (2018). "dyPolyChord: muestreo dinámico anidado con PolyChord". Revista de software de código abierto . 3 (29): 965. doi : 10.21105/joss.00965 .
27. El paquete de software de muestreo dinámico anidado dyPolyChord en GitHub
28. Ashton, Gregorio; et al. (2019). "Bilby: una biblioteca de inferencia bayesiana fácil de usar para la astronomía de ondas gravitacionales". Serie de suplementos de revistas astrofísicas . 241 (2): 13. arXiv : 1811.02042 . Código Bib : 2019ApJS..241...27A. doi : 10.3847/1538-4365/ab06fc . S2CID  118677076.
29. Zucker, Catalina; et al. (2018). "Mapeo de distancias a través de la nube molecular de Perseo utilizando observaciones {CO}, fotometría estelar y mediciones de paralaje Gaia {DR}2". La revista astrofísica . 869 (1): 83. arXiv : 1803.08931 . doi : 10.3847/1538-4357/aae97c . S2CID  119446622.
30. Gunther, Maximiliano; et al. (2019). "Una súper Tierra y dos subNeptunos en tránsito por la cercana y tranquila enana M TOI-270". Astronomía de la Naturaleza . 3 (12): 1099–1108. arXiv : 1903.06107 . Código Bib : 2019NatAs...3.1099G. doi :10.1038/s41550-019-0845-5. S2CID  119286334.