Metrópolis de múltiples intentos

En el método de Monte Carlo de cadenas de Markov , el algoritmo de Metropolis-Hastings (MH) se puede utilizar para muestrear a partir de una distribución de probabilidad que es difícil de muestrear directamente. Sin embargo, el algoritmo MH requiere que el usuario proporcione una distribución propuesta, que puede ser relativamente arbitraria. En muchos casos, se utiliza una distribución gaussiana centrada en el punto actual en el espacio de probabilidad , de la forma${\displaystyle Q(x';x^{t})={\mathcal {N}}(x^{t};\sigma ^{2}I)\,}$Esta distribución propuesta es conveniente para tomar muestras y puede ser la mejor opción si se tiene poco conocimiento sobre la distribución objetivo.${\displaystyle \pi (x)\,}$. Si se desea, se puede utilizar la distribución normal multivariada más general ,${\displaystyle Q(x';x^{t})={\mathcal {N}}(x^{t};\mathbf {\Sigma } )}$, dónde${\displaystyle \mathbf {\Sigma } }$es la matriz de covarianza que el usuario cree que es similar a la distribución objetivo.

Aunque este método debe converger a la distribución estacionaria en el límite de tamaño de muestra infinito, en la práctica el progreso puede ser extremadamente lento. Si${\displaystyle \sigma ^{2}\,}$es demasiado grande, casi todos los pasos del algoritmo MH serán rechazados. Por otro lado, si${\displaystyle \sigma ^{2}\,}$es demasiado pequeño, casi todos los pasos serán aceptados y la cadena de Markov será similar a un paseo aleatorio a través del espacio de probabilidad. En el caso más simple de${\displaystyle Q(x';x^{t})={\mathcal {N}}(x^{t};I)\,}$, vemos que${\displaystyle N\,}$pasos solo nos llevan a una distancia de${\displaystyle {\sqrt {N}}\,}$. En este caso, la cadena de Markov no explorará completamente el espacio de probabilidad en un tiempo razonable. Por lo tanto, el algoritmo MH requiere un ajuste razonable del parámetro de escala (${\displaystyle \sigma ^{2}\,}$o${\displaystyle \mathbf {\Sigma } }$).

Incluso si el parámetro de escala está bien ajustado, a medida que aumenta la dimensionalidad del problema, el progreso puede seguir siendo extremadamente lento. Para ver esto, consideremos nuevamente${\displaystyle Q(x';x^{t})={\mathcal {N}}(x^{t};I)\,}$En una dimensión, esto corresponde a una distribución gaussiana con media 0 y varianza 1. Para una dimensión, esta distribución tiene un paso medio de cero, sin embargo, el tamaño del paso cuadrático medio viene dado por

${\displaystyle \langle x^{2}\rangle =\int _{-\infty }^{\infty }x^{2}{\frac {1}{\sqrt {2\pi }}}e^{-{\frac {x^{2}}{2}}}dx=1}$

A medida que aumenta el número de dimensiones, el tamaño de paso esperado se vuelve cada vez mayor.${\displaystyle N\,}$dimensiones, la probabilidad de moverse una distancia radial${\displaystyle r\,}$está relacionada con la distribución Chi y viene dada por

${\displaystyle P_{n}(r)\propto r^{n-1}e^{-r^{2}/2}}$

Esta distribución alcanza su punto máximo en${\displaystyle r={\sqrt {N-1}}\,}$que es${\displaystyle \approx {\sqrt {N}}\,}$para grandes${\displaystyle N\,}$Esto significa que el tamaño del paso aumentará aproximadamente con la raíz cuadrada del número de dimensiones. Para el algoritmo MH, los pasos grandes casi siempre caerán en regiones de baja probabilidad y, por lo tanto, serán rechazados.

Si ahora añadimos el parámetro de escala${\displaystyle \sigma ^{2}\,}$Volviendo al tema, encontramos que para mantener una tasa de aceptación razonable, debemos realizar la transformación.${\displaystyle \sigma ^{2}\rightarrow \sigma ^{2}/N}$En esta situación, la tasa de aceptación ahora puede ser razonable, pero la exploración del espacio de probabilidad se vuelve cada vez más lenta. Para ver esto, considere un corte a lo largo de cualquier dimensión del problema. Al realizar la transformación de escala anterior, el tamaño de paso esperado es cualquier dimensión no es${\displaystyle \sigma \,}$pero en cambio es${\displaystyle \sigma /{\sqrt {N}}}$. Como este tamaño de paso es mucho menor que la escala "verdadera" de la distribución de probabilidad (suponiendo que${\displaystyle \sigma \,}$Si se conoce de alguna manera a priori, lo cual es el mejor caso posible, el algoritmo ejecuta un paseo aleatorio a lo largo de cada parámetro.

El algoritmo de Metrópolis de múltiples intentos necesita calcular la energía de${\displaystyle 2k-1}$otros estados en cada paso. Si la parte lenta del proceso es el cálculo de la energía, este método puede ser más lento. Si la parte lenta es encontrar los vecinos de un punto dado o generar números aleatorios, también puede ser más lento. Se podría argumentar que este método solo parece más rápido porque concentra mucha más computación en un solo paso que el algoritmo de Metropolis-Hastings.