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?
bayesian
monte-carlo
markov-process
użytkownik3007270
źródło
źródło
Odpowiedzi:
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.
źródło
Mylisz się, że konsola HMC nie jest metodą łańcucha Markowa. Według Wikipedii :
Dla większej przejrzystości przeczytaj artykuł arXiv autorstwa Betancourt , w którym wspomniano kryteria zakończenia NUTS:
Dodatek A.3 mówi o podwojeniu trajektorii, o której wspominasz:
i rozwija to w A.4, gdzie mówi o implementacji dynamicznej (sekcja A.3 mówi o implementacji statycznej):
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ę.
źródło