Czy ktoś może mi wyjaśnić NUTS po angielsku?

Moje rozumienie algorytmu jest następujące:

No U-Turn Sampler (NUTS) to hamiltonowska metoda Monte Carlo. Oznacza to, że nie jest to metoda łańcucha Markowa, a zatem algorytm ten omija część chodzenia losowego, która często uważana jest za nieefektywną i powolną do zbieżności.

Zamiast wykonywać losowy spacer, NUTS wykonuje skoki o długości x. Każdy skok podwaja się w miarę działania algorytmu. Dzieje się tak, dopóki trajektoria nie osiągnie punktu, w którym chce wrócić do punktu początkowego.

Moje pytania: co jest takiego specjalnego w zawracaniu? W jaki sposób podwojenie trajektorii nie pomija zoptymalizowanego punktu? Czy mój powyższy opis jest prawidłowy?

Bit bez zawracania służy do generowania propozycji. HMC generuje hipotetyczny układ fizyczny: wyobraź sobie piłkę o pewnej energii kinetycznej toczącą się wokół krajobrazu z dolinami i wzgórzami (analogia rozkłada się na więcej niż 2 wymiary) zdefiniowanym przez tylną próbkę. Za każdym razem, gdy chcesz pobrać nową próbkę MCMC, losowo wybierasz energię kinetyczną i zaczynasz toczyć piłkę z miejsca, w którym się znajdujesz. Symulujesz w dyskretnych krokach czasowych, a aby upewnić się, że prawidłowo eksplorujesz przestrzeń parametrów, symulujesz kroki w jednym kierunku, a dwa razy więcej w drugim kierunku, ponownie się odwracasz itp. W pewnym momencie chcesz to zatrzymać i dobry sposób robienia tego jest wtedy, gdy wykonałeś zwrot zawracania (tzn. wydaje się, że przeszedłeś wszędzie).

W tym momencie proponowany następny etap łańcucha Markowa zostanie wybrany (z pewnymi ograniczeniami) z punktów, które odwiedziłeś. To znaczy, że cała symulacja hipotetycznego układu fizycznego była „tylko”, aby uzyskać propozycję, która następnie zostaje zaakceptowana (następna próbka MCMC jest proponowanym punktem) lub odrzucona (następna próbka MCMC jest punktem początkowym).

Sprytne jest to, że propozycje są oparte na kształcie tylnej części ciała i mogą znajdować się na drugim końcu rozkładu. W przeciwieństwie do Metropolis-Hastings przedstawia propozycje w obrębie (prawdopodobnie przekrzywionej) kulki, próbkowanie Gibbsa porusza się tylko wzdłuż jednego (lub przynajmniej bardzo niewielu) wymiarów na raz.

Mylisz się, że konsola HMC nie jest metodą łańcucha Markowa. Według Wikipedii :

W matematyce i fizyce hybrydowy algorytm Monte Carlo, znany również jako Hamiltonian Monte Carlo, jest metodą Monte Carlo z łańcuchem Markowa do uzyskiwania sekwencji losowych próbek z rozkładu prawdopodobieństwa, dla którego bezpośrednie próbkowanie jest trudne. Sekwencję tę można wykorzystać do przybliżenia rozkładu (tj. Do wygenerowania histogramu) lub do obliczenia całki (takiej jak wartość oczekiwana).

Dla większej przejrzystości przeczytaj artykuł arXiv autorstwa Betancourt , w którym wspomniano kryteria zakończenia NUTS:

... określ, kiedy trajektoria jest wystarczająco długa, aby zapewnić wystarczającą eksplorację okolicy wokół aktualnego ustawionego poziomu energii. W szczególności chcemy uniknąć zarówno integracji zbyt krótkiej, w którym to przypadku nie skorzystalibyśmy w pełni z trajektorii hamiltonowskich, jak i integracji zbyt długiej, w którym to przypadku marnujemy cenne zasoby obliczeniowe na eksplorację, która przynosi jedynie malejące zyski.

Dodatek A.3 mówi o podwojeniu trajektorii, o której wspominasz:

Możemy również rozwijać się szybciej, podwajając długość trajektorii przy każdej iteracji, uzyskując próbkowaną trajektorię t ∼ T (t | z) = U T2L z odpowiednim próbkowanym stanem z ′ ∼ T (z ′ | t). W tym przypadku zarówno stare, jak i nowe elementy trajektorii przy każdej iteracji są równoważne z liśćmi doskonałych, uporządkowanych drzew podwójnych (ryc. 37). Dzięki temu możemy rekurencyjnie budować nowe komponenty trajektorii, propagując próbkę na każdym etapie rekurencji ...

i rozwija to w A.4, gdzie mówi o implementacji dynamicznej (sekcja A.3 mówi o implementacji statycznej):

Na szczęście wydajne schematy statyczne omówione w części A.3 można iterować w celu osiągnięcia dynamicznej implementacji, gdy wybraliśmy kryterium określania, kiedy trajektoria urosła wystarczająco długo, aby zadowalająco zbadać odpowiedni zestaw poziomów energii.

Myślę, że kluczem jest to, że nie wykonuje podwójnych skoków, oblicza swój następny skok, stosując technikę, która podwaja długość proponowanego skoku, dopóki nie zostaną spełnione kryteria. Przynajmniej tak rozumiem do tej pory gazetę.