¿Alguien puede explicarme NUTS en inglés?

17

Mi comprensión del algoritmo es la siguiente:

Ningún muestreador de giro en U (NUTS) es un método hamiltoniano de Monte Carlo. Esto significa que no es un método de la cadena de Markov y, por lo tanto, este algoritmo evita la parte de la caminata aleatoria, que a menudo se considera ineficiente y lenta para converger.

En lugar de hacer una caminata aleatoria, NUTS realiza saltos de longitud x. Cada salto se duplica a medida que el algoritmo continúa ejecutándose. Esto sucede hasta que la trayectoria alcanza un punto donde quiere volver al punto de partida.

Mis preguntas: ¿Qué tiene de especial el giro en U? ¿Cómo duplicar la trayectoria no omite el punto optimizado? ¿Es correcta mi descripción anterior?

user3007270
fuente
Encontré esta publicación y las simulaciones ilustradas realmente marcan la diferencia en la explicación de los conceptos.
kael

Respuestas:

13

El bit sin giro en U es cómo se generan las propuestas. HMC genera un sistema físico hipotético: imagina una pelota con una cierta energía cinética rodando alrededor de un paisaje con valles y colinas (la analogía se descompone en más de 2 dimensiones) definida por la parte posterior de la que deseas muestrear. Cada vez que desea tomar una nueva muestra de MCMC, elige aleatoriamente la energía cinética y comienza a rodar la bola desde donde se encuentra. Simula en pasos de tiempo discretos y, para asegurarse de explorar el espacio de parámetros correctamente, simula pasos en una dirección y el doble en la otra dirección, gira de nuevo, etc. En algún momento, desea detener esto y de una buena manera de hacerlo es cuando has hecho un cambio de sentido (es decir, parece que has ido por todas partes).

En este punto, el siguiente paso propuesto de su Cadena Markov se selecciona (con ciertas limitaciones) de los puntos que ha visitado. Es decir, que toda la simulación del hipotético sistema físico fue "solo" para obtener una propuesta que luego se acepta (la siguiente muestra de MCMC es el punto propuesto) o se rechaza (la siguiente muestra de MCMC es el punto de partida).

Lo inteligente es que las propuestas se hacen en función de la forma de la parte posterior y pueden estar en el otro extremo de la distribución. En contraste, Metropolis-Hastings hace propuestas dentro de una bola (posiblemente sesgada), el muestreo de Gibbs solo se mueve a lo largo de una (o al menos muy pocas) dimensiones a la vez.

Björn
fuente
¿Podría ampliar el comentario " parece que se ha ido por todas partes " por favor?
Gabriel
1
Es decir, tener alguna indicación de que ha cubierto la distribución, que NUTS intenta juzgar por si se ha dado la vuelta por completo. Si ese es el caso, es de esperar que en un paso MCMC vaya a cualquier parte de la parte posterior. Por supuesto, la condición no garantiza realmente que haya explorado toda la parte posterior, sino que indica que ha explorado la "parte actual" de la misma (si tiene alguna distribución multimodal, puede tener problemas para llegar a todas las partes). de la distribución).
Björn
6

Es incorrecto que HMC no sea un método de la cadena de Markov. Por Wikipedia :

En matemáticas y física, el algoritmo híbrido de Monte Carlo, también conocido como Hamiltoniano Monte Carlo, es un método de Monte Carlo en cadena de Markov para obtener una secuencia de muestras aleatorias a partir de una distribución de probabilidad para la cual el muestreo directo es difícil. Esta secuencia se puede usar para aproximar la distribución (es decir, para generar un histograma) o para calcular una integral (como un valor esperado).

Para mayor claridad, lea el documento arXiv de Betancourt , que menciona los criterios de terminación NUTS:

... identifique cuándo una trayectoria es lo suficientemente larga como para producir una exploración suficiente del vecindario alrededor del nivel de energía actual establecido. En particular, queremos evitar tanto la integración demasiado corta, en cuyo caso no aprovecharíamos al máximo las trayectorias hamiltonianas, como la integración demasiado larga, en cuyo caso desperdiciamos valiosos recursos computacionales en la exploración que produce rendimientos decrecientes.

El Apéndice A.3 habla de algo así como la trayectoria que duplica que menciona:

También podemos expandirnos más rápido duplicando la longitud de la trayectoria en cada iteración, produciendo una trayectoria muestreada t ∼ T (t | z) = U T2L con el estado muestreado correspondiente z ′ ∼ T (z ′ | t). En este caso, los componentes de trayectoria antiguos y nuevos en cada iteración son equivalentes a las hojas de árboles binarios ordenados perfectos (Figura 37). Esto nos permite construir los nuevos componentes de trayectoria de forma recursiva, propagando una muestra en cada paso de la recursividad ...

y amplía esto en A.4, donde habla de una implementación dinámica (la sección A.3 habla de una implementación estática):

Afortunadamente, los esquemas estáticos eficientes discutidos en la Sección A.3 se pueden repetir para lograr una implementación dinámica una vez que hayamos elegido un criterio para determinar cuándo una trayectoria ha crecido lo suficiente como para explorar satisfactoriamente el conjunto de niveles de energía correspondiente.

Creo que la clave es que no hace saltos que doblan, calcula su próximo salto usando una técnica que duplica la longitud del salto propuesto hasta que se cumpla un criterio. Al menos así es como entiendo el artículo hasta ahora.

Wayne
fuente