¿Puede alguien explicarme NUTS en inglés?

Question

Mi entendimiento del algoritmo es el siguiente:

El muestreador sin vuelta en U (NUTS) es un método de Monte Carlo hamiltoniano. Esto significa que no es un método de cadenas de Markov y, por lo tanto, este algoritmo evita la parte del paseo aleatorio, que a menudo se considera ineficiente y lento para converger.

En lugar de realizar el paseo aleatorio, NUTS realiza saltos de longitud x. Cada salto se duplica a medida que el algoritmo continúa ejecutándose. Esto ocurre hasta que la trayectoria llega a un punto en el que quiere volver al punto de partida.

Mis preguntas: ¿Qué tiene de especial la vuelta en U? ¿Cómo es que al duplicar la trayectoria no se salta el punto optimizado? ¿Es correcta mi descripción anterior?

Answer 1

La parte de no dar la vuelta es cómo se generan las propuestas. El HMC genera un sistema físico hipotético: imagina una pelota con una determinada energía cinética rodando por un paisaje con valles y colinas (la analogía se rompe con más de 2 dimensiones) definido por la parte posterior de la que quieres tomar muestras. Cada vez que quieras tomar una nueva muestra MCMC, eliges al azar la energía cinética y empiezas a rodar la pelota desde donde estás. Simulas en pasos de tiempo discretos, y para asegurarte de que exploras bien el espacio de parámetros, simulas pasos en una dirección y el doble en la otra, vuelves a girar, etc. En algún momento querrás parar esto y una buena forma de hacerlo es cuando hayas dado una vuelta en U (es decir, que parezca que has ido por todos lados).

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

Lo inteligente es que las propuestas se hacen en base a la forma de la posterior y pueden estar en el otro extremo de la distribución. A diferencia de Metrópolis-Hastings, que hace propuestas dentro de una bola (posiblemente sesgada), el muestreo de Gibbs sólo se mueve a lo largo de una (o al menos muy pocas) dimensiones a la vez.

Answer 2

Te equivocas al decir que el HMC no es un método de cadenas de Markov. En Wikipedia :

En matemáticas y física, el algoritmo híbrido de Montecarlo, también conocido como Montecarlo Hamiltoniano, es un método de Montecarlo con cadena de Markov para obtener una secuencia de muestras aleatorias de una distribución de probabilidad para la que el muestreo directo es difícil. Esta secuencia puede utilizarse 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 Artículo arXiv de Betancourt que menciona los criterios de terminación de la NUTS:

... identificar cuándo una trayectoria es lo suficientemente larga como para producir una exploración suficiente de la vecindad alrededor del conjunto de niveles de energía actual. 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 una exploración que sólo produce rendimientos decrecientes.

El Apéndice A.3 habla de algo parecido a la duplicación de la trayectoria que mencionas:

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

y lo amplía 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 pueden ser iterados 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 está en que no hace saltos que se duplican, sino que calcula su siguiente salto mediante una técnica que duplica la longitud del salto propuesto hasta que se cumple un criterio. Al menos así es como entiendo el documento hasta ahora.