Conjunto multicanónico

En estadística y física , el conjunto multicanónico (también llamado muestreo multicanónico o histograma plano ) es una técnica de muestreo de Monte Carlo de cadena de Markov que utiliza el algoritmo Metropolis-Hastings para calcular integrales donde el integrando tiene un paisaje aproximado con múltiples mínimos locales . Muestrea estados de acuerdo con la inversa de la densidad de estados , ^[1] que debe conocerse a priori o calcularse utilizando otras técnicas como el algoritmo de Wang y Landau . ^[2] El muestreo multicanónico es una técnica importante para sistemas de espín como el modelo de Ising o los vidrios de espín . ^{[1] [3] [4]}

Motivación

En sistemas con una gran cantidad de grados de libertad, como los sistemas de espín , se requiere la integración de Monte Carlo . En esta integración, el muestreo de importancia y, en particular, el algoritmo Metropolis , es una técnica muy importante. ^[3] Sin embargo, el algoritmo Metropolis muestrea estados según donde beta es la inversa de la temperatura. Esto significa que una barrera de energía de en el espectro de energía es exponencialmente difícil de superar. ^[1] Los sistemas con múltiples mínimos de energía locales como el modelo de Potts se vuelven difíciles de muestrear ya que el algoritmo se queda atascado en los mínimos locales del sistema. ^[3] Esto motiva otros enfoques, a saber, otras distribuciones de muestreo. ${\displaystyle \exp(-\beta E)}$ ${\displaystyle \Delta E}$

Descripción general

El conjunto multicanónico utiliza el algoritmo Metropolis-Hastings con una distribución de muestreo dada por la inversa de la densidad de estados del sistema, al contrario de la distribución de muestreo del algoritmo Metropolis. ^[1] Con esta elección, en promedio, el número de estados muestreados en cada energía es constante, es decir, es una simulación con un "histograma plano" sobre la energía. Esto conduce a un algoritmo para el cual las barreras energéticas ya no son difíciles de superar. Otra ventaja sobre el algoritmo Metropolis es que el muestreo es independiente de la temperatura del sistema, lo que significa que una simulación permite la estimación de variables termodinámicas para todas las temperaturas (de ahí el nombre "multicanónico": varias temperaturas). Esto es una gran mejora en el estudio de las transiciones de fase de primer orden . ^[1] ${\displaystyle \exp(-\beta E)}$

El mayor problema al realizar un conjunto multicanónico es que la densidad de estados debe conocerse a priori . ^{[2] [3]} Una contribución importante al muestreo multicanónico fue el algoritmo de Wang y Landau , que converge asintóticamente a un conjunto multicanónico mientras calcula la densidad de estados durante la convergencia. ^[2]

El conjunto multicanónico no se limita a los sistemas físicos. Puede emplearse en sistemas abstractos que tienen una función de costo F. Al utilizar la densidad de estados con respecto a F, el método se vuelve general para calcular integrales de dimensiones superiores o encontrar mínimos locales. ^[5]

Motivación

Considérese un sistema y su espacio de fases caracterizado por una configuración en y una función de "costo" F desde el espacio de fases del sistema a un espacio unidimensional : , el espectro de F . ${\displaystyle \Omega }$ ${\displaystyle {\boldsymbol {r}}}$ ${\displaystyle \Omega }$ ${\displaystyle \Gamma }$ ${\displaystyle F(\Omega )=\Gamma =[\Gamma _{\min },\Gamma _{\max }]}$

El cálculo de una cantidad promedio sobre el espacio de fases requiere la evaluación de una integral: ${\displaystyle \langle Q\rangle }$

${\displaystyle \langle Q\rangle =\int _{\Omega }Q({\boldsymbol {r}})P_{r}({\boldsymbol {r}})\,d{\boldsymbol {r}}}$

donde es el peso de cada estado (por ejemplo corresponde a estados distribuidos uniformemente). ${\displaystyle P_{r}({\boldsymbol {r}})}$ ${\displaystyle P_{r}({\boldsymbol {r}})=1/V}$

Cuando Q no depende del estado particular sino solo del valor particular de F del estado , la fórmula para se puede integrar sobre f agregando una función delta de Dirac y escribirse como ${\displaystyle F({\boldsymbol {r}})=F_{\boldsymbol {r}}}$ ${\displaystyle \langle Q\rangle }$

${\displaystyle {\begin{aligned}\langle Q\rangle &=\int _{\Gamma _{\min }}^{\Gamma _{\max }}\int _{\Omega }Q(F_{\boldsymbol {r}})P_{r}(F_{\boldsymbol {r}})\delta (f-F_{\boldsymbol {r}})\,d{\boldsymbol {r}}\,df\\&=\int _{\Gamma _{\min }}^{\Gamma _{\max }}Q(f)\int _{\Omega }\delta (f-F_{\boldsymbol {r}})P_{r}(F_{\boldsymbol {r}})\,d{\boldsymbol {r}}\,df\\&=\int _{\Gamma _{\min }}^{\Gamma _{\max }}Q(f)P(f)\,df\\\end{aligned}}}$

dónde

${\displaystyle P(f)=\int _{\Omega }P_{r}(r)\delta (f-F({\boldsymbol {r}}))\,d{\boldsymbol {r}}}$

es la distribución marginal de F.

Cuando el sistema tiene una gran cantidad de grados de libertad, suele ser difícil obtener una expresión analítica para y, por lo general, se emplea la integración de Monte Carlo para calcular . En la formulación más simple, el método elige N estados distribuidos uniformemente y utiliza el estimador ${\displaystyle \langle Q\rangle }$ ${\displaystyle \langle Q\rangle }$ ${\displaystyle {\boldsymbol {r}}_{i}\in \Omega }$

${\displaystyle {\overline {Q}}_{N}=\sum _{i=1}^{N}Q({\boldsymbol {r}}_{i})VP_{r}({\boldsymbol {r}}_{i})}$

para calcular porque converge casi con seguridad a por la ley fuerte de los grandes números : ${\displaystyle \langle Q\rangle }$ ${\displaystyle {\overline {Q}}_{N}}$ ${\displaystyle \langle Q\rangle }$

${\displaystyle \lim _{N\rightarrow \infty }{\overline {Q}}_{N}=\langle Q\rangle .}$

Un problema típico de esta convergencia es que la varianza de Q puede ser muy alta, lo que conduce a un alto esfuerzo computacional para lograr resultados razonables.

Para mejorar esta convergencia se propuso el algoritmo Metropolis-Hastings . En general, la idea de los métodos de Monte Carlo es utilizar el muestreo por importancia para mejorar la convergencia del estimador muestreando estados según una distribución arbitraria y utilizando el estimador apropiado: ${\displaystyle {\overline {Q}}_{N}}$ ${\displaystyle \pi ({\boldsymbol {r}})}$

${\displaystyle {\overline {Q}}_{N}=\sum _{i=1}^{N}Q({\boldsymbol {r}}_{i})\pi ^{-1}({\boldsymbol {r}}_{i})P_{r}({\boldsymbol {r}}_{i})}$.

Este estimador generaliza el estimador de la media para muestras extraídas de una distribución arbitraria. Por lo tanto, cuando es una distribución uniforme, corresponde a la utilizada en un muestreo uniforme anterior. ${\displaystyle \pi ({\boldsymbol {r}})}$

Cuando el sistema es un sistema físico en contacto con un baño de calor, cada estado se pondera según el factor de Boltzmann , . En Monte Carlo, el conjunto canónico se define eligiendo que sea proporcional a . En esta situación, el estimador corresponde a una media aritmética simple: ${\displaystyle {\boldsymbol {r}}}$ ${\displaystyle P_{r}({\boldsymbol {r}}_{i})\propto \exp(-\beta F_{\boldsymbol {r}})}$ ${\displaystyle \pi ({\boldsymbol {r}})}$ ${\displaystyle P_{r}({\boldsymbol {r}}_{i})}$

${\displaystyle {\overline {Q}}_{N}={\frac {1}{N}}\sum _{i=1}^{N}Q({\boldsymbol {r}}_{i})}$

Históricamente, esto ocurrió porque la idea original ^[6] era utilizar el algoritmo Metropolis-Hastings para calcular promedios en un sistema en contacto con un baño de calor donde el peso está dado por el factor de Boltzmann, . ^[3] ${\displaystyle P({\boldsymbol {x}})\propto \exp(-\beta E({\boldsymbol {r}}))}$

Si bien es frecuente que se elija la distribución de muestreo como distribución de peso , no es necesario que así sea. Una situación en la que el conjunto canónico no es una opción eficiente es cuando tarda un tiempo arbitrario en converger. ^[1] Una situación en la que esto sucede es cuando la función F tiene múltiples mínimos locales. El costo computacional para que el algoritmo abandone una región específica con un mínimo local aumenta exponencialmente con el valor del mínimo de la función de costo. Es decir, cuanto más profundo sea el mínimo, más tiempo pasará allí el algoritmo y más difícil será abandonarlo (crece exponencialmente con la profundidad del mínimo local). ${\displaystyle \pi }$ ${\displaystyle P_{r}}$

Una forma de evitar quedarse estancado en los mínimos locales de la función de costo es hacer que la técnica de muestreo sea "invisible" para los mínimos locales. Esta es la base del conjunto multicanónico.

Conjunto multicanónico

El conjunto multicanónico se define eligiendo la distribución de muestreo que se va a utilizar.

${\displaystyle \pi ({\boldsymbol {r}})\propto {\frac {1}{P(F_{\boldsymbol {r}})}}}$

donde es la distribución marginal de F definida anteriormente. La consecuencia de esta elección es que el número promedio de muestras con un valor dado de f , m(f), viene dado por ${\displaystyle P(f)}$

${\displaystyle m(f)=\int _{\Omega }\delta (f-F_{\boldsymbol {r}})\pi ({\boldsymbol {r}})P_{r}({\boldsymbol {r}})\,d{\boldsymbol {r}}\propto \int _{\Omega }\delta (f-F_{\boldsymbol {r}})P_{r}({\boldsymbol {r}}){\frac {1}{P(F_{\boldsymbol {r}})}}d{\boldsymbol {r}}={\frac {1}{P(f)}}\int _{\Omega }\delta (f-F_{\boldsymbol {r}})P_{r}({\boldsymbol {r}})d{\boldsymbol {r}}=1}$

Es decir, el número medio de muestras no depende de f : todos los costes f se muestrean por igual, independientemente de que sean más o menos probables. Esto motiva el nombre de "histograma plano". Para sistemas en contacto con un baño de calor, el muestreo es independiente de la temperatura y una simulación permite estudiar todas las temperaturas.

Tiempo de tunelización y desaceleración crítica

Como en cualquier otro método de Monte Carlo, existen correlaciones de las muestras extraídas de . Una medida típica de la correlación es el tiempo de tunelización . El tiempo de tunelización se define por el número de pasos de Markov (de la cadena de Markov) que la simulación necesita para realizar un viaje de ida y vuelta entre el mínimo y el máximo del espectro de F . Una motivación para utilizar el tiempo de tunelización es que cuando cruza los espectros, pasa por la región del máximo de la densidad de estados, descorrelacionando así el proceso. Por otro lado, el uso de viajes de ida y vuelta garantiza que el sistema visite todo el espectro. ${\displaystyle P({\boldsymbol {r}})}$

Debido a que el histograma es plano en la variable F , un conjunto multicanónico puede verse como un proceso de difusión (es decir, un paseo aleatorio ) en la línea unidimensional de valores F . El balance detallado del proceso dicta que no hay deriva en el proceso. ^[7] Esto implica que el tiempo de tunelización, en dinámica local, debería escalar como un proceso de difusión y, por lo tanto, el tiempo de tunelización debería escalar cuadráticamente con el tamaño del espectro, N :

${\displaystyle \tau _{tt}\propto N^{2}}$

Sin embargo, en algunos sistemas (siendo el modelo de Ising el más paradigmático), el escalamiento sufre una desaceleración crítica: es donde depende del sistema particular. ^[4] ${\displaystyle N^{2+z}}$ ${\displaystyle z>0}$

Se desarrollaron dinámicas no locales para mejorar el escalamiento a un escalamiento cuadrático ^[8] (ver el algoritmo de Wolff ), superando la desaceleración crítica. Sin embargo, aún queda por saber si existe una dinámica local que no sufra una desaceleración crítica en sistemas de espín como el modelo de Ising.

Referencias

1. Berg, B.; Neuhaus, T. (1992). "Conjunto multicanónico: un nuevo enfoque para simular transiciones de fase de primer orden". Physical Review Letters . 68 (1): 9–12. arXiv : hep-lat/9202004 . Código Bibliográfico :1992PhRvL..68....9B. doi :10.1103/PhysRevLett.68.9. PMID  10045099. S2CID  19478641.
2. Wang, F.; Landau, D. (2001). "Algoritmo de paseo aleatorio eficiente de rango múltiple para calcular la densidad de estados". Physical Review Letters . 86 (10): 2050–2053. arXiv : cond-mat/0011174 . Código Bibliográfico :2001PhRvL..86.2050W. doi :10.1103/PhysRevLett.86.2050. PMID  11289852. S2CID  2941153.
3. Newmann, MEJ; Barkema, GT (2002). Métodos de Monte Carlo en Física Estadística . Estados Unidos: Oxford University Press. ISBN 0198517971.
4. Dayal, P.; Trebst, S.; Wessel, S.; Würtz, D.; Troyer, M.; Sabhapandit, S.; Coppersmith, S. (2004). "Limitaciones de rendimiento de los métodos de histograma plano". Physical Review Letters . 92 (9): 097201. arXiv : cond-mat/0306108 . Código Bibliográfico :2004PhRvL..92i7201D. doi :10.1103/PhysRevLett.92.097201. PMID  15089505. S2CID  1128445.
5. Lee, J.; Choi, M. (1994). "Optimización mediante recocido multicanónico y el problema del viajante". Physical Review E . 50 (2): R651–R654. Bibcode :1994PhRvE..50..651L. doi :10.1103/PhysRevE.50.R651. PMID  9962167.
6. Metropolis, N.; Rosenbluth, A. W.; Rosenbluth, M. N.; Teller, A. H.; Teller, E. (1953). "Cálculos de ecuaciones de estado mediante máquinas de computación rápida". The Journal of Chemical Physics . 21 (6): 1087. Bibcode :1953JChPh..21.1087M. doi :10.1063/1.1699114. OSTI  4390578. S2CID  1046577.
7. Robert, Christian; Casella, George (2004). Métodos estadísticos de Monte Carlo. Springer. ISBN 978-0-387-21239-5.
8. Wolff, U. (1989). "Actualización colectiva de Monte Carlo para sistemas de espín". Physical Review Letters . 62 (4): 361–364. Código Bibliográfico :1989PhRvL..62..361W. doi :10.1103/PhysRevLett.62.361. PMID  10040213.