Alguém pode me explicar NUTS em inglês?

Meu entendimento do algoritmo é o seguinte:

No U-Turn Sampler (NUTS) é um método Hamiltoniano de Monte Carlo. Isso significa que não é um método da cadeia de Markov e, portanto, esse algoritmo evita a parte do passeio aleatório, que geralmente é considerado ineficiente e lento para convergir.

Em vez de fazer o passeio aleatório, o NUTS faz saltos de comprimento x. Cada salto dobra à medida que o algoritmo continua em execução. Isso acontece até que a trajetória alcance um ponto em que deseja retornar ao ponto de partida.

Minhas perguntas: O que há de tão especial na inversão de marcha? Como dobrar a trajetória não pula o ponto otimizado? Minha descrição acima está correta?

O bit sem retorno é como as propostas são geradas. O HMC gera um sistema físico hipotético: imagine uma bola com uma certa energia cinética rolando em torno de uma paisagem com vales e colinas (a analogia se divide em mais de duas dimensões) definida pela parte posterior da qual você deseja amostrar. Toda vez que você deseja coletar uma nova amostra do MCMC, você escolhe aleatoriamente a energia cinética e começa a bola rolar de onde você está. Você simula em etapas de tempo discretas e, para certificar-se de explorar adequadamente o espaço dos parâmetros, simula etapas em uma direção e o dobro na outra direção, vira novamente etc. Em algum momento, deseja interromper isso e uma boa maneira de fazer isso é quando você faz uma inversão de marcha (ou seja, parece ter ido por todo o lado).

Nesse ponto, a próxima etapa proposta da sua cadeia de Markov é escolhida (com certas limitações) dos pontos que você visitou. Ou seja, que toda a simulação do sistema físico hipotético foi "apenas" para obter uma proposta que depois é aceita (a próxima amostra do MCMC é o ponto proposto) ou rejeitada (a próxima amostra do MCMC é o ponto de partida).

O mais inteligente é que as propostas são feitas com base na forma da parte posterior e podem estar no outro extremo da distribuição. Em contraste, Metropolis-Hastings faz propostas dentro de uma bola (possivelmente distorcida), a amostra de Gibbs se move apenas ao longo de uma (ou pelo menos muito poucas) dimensões de cada vez.

Você está incorreto ao saber que o HMC não é um método da cadeia de Markov. Por Wikipedia :

Em matemática e física, o algoritmo híbrido de Monte Carlo, também conhecido como Hamiltoniano Monte Carlo, é um método de Monte Carlo da cadeia de Markov para obter uma sequência de amostras aleatórias a partir de uma distribuição de probabilidade para a qual a amostragem direta é difícil. Essa sequência pode ser usada para aproximar a distribuição (ou seja, para gerar um histograma) ou para calcular uma integral (como um valor esperado).

Para maior clareza, leia o artigo arXiv de Betancourt , que menciona os critérios finais da NUTS:

... identificar quando uma trajetória é longa o suficiente para gerar uma exploração suficiente da vizinhança em torno do atual nível de energia definido. Em particular, queremos evitar a integração muito curta, caso em que não tiraríamos o máximo proveito das trajetórias hamiltonianas e a integração por muito tempo, caso em que desperdiçamos recursos computacionais preciosos na exploração que produz apenas retornos decrescentes.

O Apêndice A.3 fala sobre algo como a trajetória dobrada que você menciona:

Também podemos expandir mais rapidamente dobrando o comprimento da trajetória a cada iteração, produzindo uma trajetória amostrada t ∼ T (t | z) = U T2L com o estado amostrado correspondente z ′ ∼ T (z ′ | t). Nesse caso, os componentes antigos e novos da trajetória a cada iteração são equivalentes às folhas das árvores binárias perfeitas e ordenadas (Figura 37). Isso nos permite construir recursivamente os novos componentes da trajetória, propagando uma amostra a cada etapa da recursão ...

e expande isso em A.4, onde fala sobre uma implementação dinâmica (a seção A.3 fala sobre uma implementação estática):

Felizmente, os esquemas estáticos eficientes discutidos na Seção A.3 podem ser iterados para obter uma implementação dinâmica, uma vez que escolhemos um critério para determinar quando uma trajetória cresceu o suficiente para explorar satisfatoriamente o conjunto de níveis de energia correspondente.

Eu acho que a chave é que ele não faz saltos que dobram, calcula seu próximo salto usando uma técnica que dobra o comprimento do salto proposto até que um critério seja atendido. Pelo menos é assim que eu entendo o artigo até agora.