Sieć Markowa Monte Carlo - Markov chain Monte Carlo

W statystycznych , łańcuchów Markowa Monte Carlo ( MCMC ) sposoby obejmują klasę algorytmu do pobierania próbek z rozkładu prawdopodobieństwa . Konstruując łańcuch Markowa, który ma pożądany rozkład jako rozkład równowagi , można uzyskać próbkę żądanego rozkładu rejestrując stany z łańcucha. Im więcej kroków jest uwzględnionych, tym bardziej rozkład próbki jest zgodny z faktycznie pożądanym rozkładem. Istnieją różne algorytmy do konstruowania łańcuchów, w tym algorytm Metropolis-Hastings .

Domeny aplikacji

Metody MCMC są wykorzystywane przede wszystkim do obliczania przybliżeń liczbowych z całek wielowymiarowych , na przykład w statystyce Bayesa , fizyce obliczeniowej , biologii obliczeniowej i lingwistyki .

W statystyce bayesowskiej niedawny rozwój metod MCMC umożliwił obliczanie dużych modeli hierarchicznych, które wymagają integracji setek do tysięcy nieznanych parametrów.

W przypadku próbkowania rzadkich zdarzeń są one również wykorzystywane do generowania próbek, które stopniowo zapełniają region rzadkich awarii.

Ogólne wyjaśnienie

Zbieżność algorytmu Metropolis-Hastings . Sieć Markowa Monte Carlo próbuje przybliżyć rozkład niebieski z rozkładem pomarańczowym.

Metody Monte Carlo łańcucha Markowa tworzą próbki z ciągłej zmiennej losowej , z gęstością prawdopodobieństwa proporcjonalną do znanej funkcji. Próbki te można wykorzystać do oceny całki po tej zmiennej, jako jej oczekiwanej wartości lub wariancji .

Praktycznie ogólnie tworzy się zespół łańcuchów, zaczynając od zbioru punktów dowolnie wybranych i wystarczająco odległych od siebie. Łańcuchy te to stochastyczne procesy „spacerów”, które poruszają się losowo zgodnie z algorytmem, który szuka miejsc o stosunkowo wysokim udziale w całce, aby przejść do następnego, przypisując im wyższe prawdopodobieństwa.

Metody losowego spaceru metodą Monte Carlo są rodzajem symulacji losowej lub metodą Monte Carlo . Jednakże, podczas gdy losowe próbki całki użyte w konwencjonalnej całkowaniu Monte Carlo są statystycznie niezależne , te użyte w MCMC są autokorelacji . Korelacje próbek wprowadzają konieczność stosowania centralnego twierdzenia granicznego łańcucha Markowa przy szacowaniu błędu wartości średnich.

Algorytmy te tworzą łańcuchy Markowa w taki sposób, że mają rozkład równowagi proporcjonalny do podanej funkcji.

Zmniejszenie korelacji

Chociaż metody MCMC zostały stworzone w celu rozwiązywania problemów wielowymiarowych lepiej niż ogólne algorytmy Monte Carlo, gdy liczba wymiarów wzrasta, one również mają tendencję do cierpienia z powodu przekleństwa wymiarowości : regiony o wyższym prawdopodobieństwie mają tendencję do rozciągania się i gubienia w coraz większej objętości przestrzeni to niewiele wnosi do całki. Jednym ze sposobów rozwiązania tego problemu może być skrócenie kroków chodzika, tak aby nie próbował on ciągle wychodzić z obszaru o najwyższym prawdopodobieństwie, chociaż w ten sposób proces byłby wysoce autokorelacji i kosztowny (tj. wiele kroków byłoby wymaganych do dokładny wynik). Bardziej wyrafinowane metody, takie jak Hamiltonian Monte Carlo i algorytm Wanga i Landaua, wykorzystują różne sposoby zmniejszania tej autokorelacji, jednocześnie utrzymując proces w regionach, które dają wyższy udział w całce. Algorytmy te zwykle opierają się na bardziej skomplikowanej teorii i są trudniejsze do wdrożenia, ale zazwyczaj szybciej się zbiegają.

Przykłady

Losowy spacer

Algorytm Metropolis-Hastings : Ta metoda generuje łańcuch Markowa przy użyciu gęstości propozycji dla nowych kroków i metody odrzucania niektórych proponowanych ruchów. W rzeczywistości jest to ogólna struktura, która obejmuje jako szczególne przypadki pierwszy i prostszy MCMC (algorytm Metropolis) i wiele nowszych alternatyw wymienionych poniżej.
- Próbkowanie Gibbsa : ta metoda wymaga dokładnego próbkowania wszystkich rozkładów warunkowych dystrybucji docelowej. Gdy czerpanie z rozkładów w pełni warunkowych nie jest proste, używa się innych próbników w obrębie Gibbsa (np. patrz ). Samplowanie Gibbsa jest popularne częściowo dlatego, że nie wymaga żadnego „dostrajania”. Struktura algorytmu próbkowania Gibbsa bardzo przypomina wnioskowanie o zmienności wzniosu współrzędnych, ponieważ oba algorytmy wykorzystują rozkłady w pełni warunkowe w procedurze aktualizacji.
- Algorytm Langevina dostosowany do Metropolis i inne metody, które opierają się na gradiencie (i prawdopodobnie drugiej pochodnej) docelowej gęstości logarytmicznej, aby zaproponować kroki, które z większym prawdopodobieństwem będą zmierzać w kierunku wyższej gęstości prawdopodobieństwa.
- Pseudomarginalna Metropolis-Hastings : Ta metoda zastępuje ocenę gęstości rozkładu docelowego bezstronnym oszacowaniem i jest przydatna, gdy gęstość docelowa nie jest dostępna analitycznie, np . modele zmiennych ukrytych .
Próbkowanie wycinkowe : Metoda ta opiera się na zasadzie, że można pobierać próbki z rozkładu, próbując jednolicie z obszaru pod wykresem jego funkcji gęstości. Zamienia jednolite próbkowanie w kierunku pionowym z jednolitym próbkowaniem z poziomego „plasterka” określonego przez bieżącą pozycję pionową.
Metropolis z wieloma próbami : Ta metoda jest odmianą algorytmu Metropolis-Hastings, która umożliwia wiele prób w każdym punkcie. Umożliwiając podejmowanie większych kroków w każdej iteracji, pomaga stawić czoła przekleństwu wymiarowości.
Odwracalny skok : Ta metoda jest wariantem algorytmu Metropolis-Hastings, który pozwala na propozycje zmiany wymiarowości przestrzeni. Metody Monte Carlo z łańcuchem Markowa, które zmieniają wymiarowość, są od dawna stosowane w zastosowaniach fizyki statystycznej , gdzie dla niektórych problemów stosuje się rozkład, który jest wielkim zespołem kanonicznym (np. gdy liczba cząsteczek w pudełku jest zmienna). Jednak wariant odwracalnego skoku jest przydatny podczas próbkowania metodą Monte Carlo lub Gibbsa w łańcuchu Markowa w nieparametrycznych modelach bayesowskich, takich jak te związane z procesem Dirichleta lub chińskim procesem restauracyjnym , gdzie liczba mieszanych składników/klastrów/itd. jest automatycznie wywnioskowane z danych.
Hamiltonian (lub hybrydowy) Monte Carlo (HMC): Próbuje uniknąć losowego spaceru przez wprowadzenie pomocniczego wektora pędu i implementację dynamiki hamiltonianu , więc funkcją energii potencjalnej jest gęstość docelowa. Próbki pędu są odrzucane po pobraniu. Efektem końcowym Hybrid Monte Carlo jest to, że propozycje poruszają się w przestrzeni próbki w większych krokach; są zatem mniej skorelowane i szybciej zbliżają się do rozkładu docelowego.

Oddziałujące metody cząstek

Interakcyjne metodologie MCMC to klasa metod cząstek średniego pola do uzyskiwania losowych próbek z sekwencji rozkładów prawdopodobieństwa o rosnącym poziomie złożoności próbkowania. Te modele probabilistyczne obejmują modele stanu przestrzeni ścieżki z rosnącym horyzontem czasowym, rozkłady a posteriori z sekwencją obserwacji cząstkowych, rosnące zestawy poziomów ograniczeń dla rozkładów warunkowych, malejące rozkłady temperatur związane z niektórymi rozkładami Boltzmanna-Gibbsa i wiele innych. W zasadzie każdy próbnik Monte Carlo łańcucha Markowa można przekształcić w interaktywny próbnik Monte Carlo łańcucha Markowa. Te oddziałujące próbniki Monte Carlo łańcucha Markowa mogą być interpretowane jako sposób na równoległe uruchomienie sekwencji próbników Monte Carlo łańcucha Markowa. Na przykład, współdziałające algorytmy symulowanego wyżarzania oparte są na niezależnych ruchach Metropolis-Hastings oddziałujących sekwencyjnie z mechanizmem typu selekcja-resampling. W przeciwieństwie do tradycyjnych metod Monte Carlo łańcucha Markowa, parametr precyzji tej klasy oddziałujących próbników Monte Carlo łańcucha Markowa jest związany tylko z liczbą oddziałujących próbników Monte Carlo łańcucha Markowa. Te zaawansowane metodologie cząstek należą do klasy modeli cząstek Feynmana-Kaca, zwanych również sekwencyjnymi metodami Monte Carlo lub metodami filtrów cząstek w społecznościach wnioskowania bayesowskiego i przetwarzania sygnałów . Interakcyjne metody Monte Carlo łańcucha Markowa można również interpretować jako algorytm cząstek genetycznych selekcji mutacji z mutacjami Monte Carlo łańcucha Markowa.

Łańcuch Markowa quasi-Monte Carlo (MCQMC).

Dobrze znana jest przewaga ciągów o małej rozbieżności zamiast liczb losowych w prostym niezależnym próbkowaniu metodą Monte Carlo. Ta procedura, znana jako metoda Quasi-Monte Carlo (QMC), daje błąd całkowania, który zanika szybciej niż uzyskany przez próbkowanie IID, przez nierówność Koksmy-Hlawki . Empirycznie pozwala to na redukcję zarówno błędu estymacji, jak i czasu zbieżności o rząd wielkości. Metoda Array-RQMC łączy randomizowaną symulację łańcucha quasi-Monte Carlo i Markowa poprzez symulację łańcuchów jednocześnie w taki sposób, że empiryczny rozkład stanów na dowolnym etapie jest lepszym przybliżeniem prawdziwego rozkładu łańcucha niż w przypadku zwykłego MCMC. W eksperymentach empirycznych wariancja średniej funkcji stanu czasami zbiega się w tempie lub nawet szybciej niż w tempie Monte Carlo. ${\ Displaystyle n}$ ${\ Displaystyle n}$ ${\ Displaystyle O (n ^ {-2})}$ ${\ Displaystyle O (n ^ {-1})}$

Konwergencja

Zwykle nie jest trudno skonstruować łańcuch Markowa o pożądanych właściwościach. Trudniejszym problemem jest określenie, ile kroków jest potrzebnych do uzyskania zbieżności do rozkładu stacjonarnego z dopuszczalnym błędem. Dobry łańcuch będzie miał szybkie mieszanie : dystrybucja stacjonarna jest osiągana szybko, zaczynając od dowolnej pozycji. Standardową metodą empiryczną oceny zbieżności jest uruchomienie kilku niezależnych symulowanych łańcuchów Markowa i sprawdzenie, czy stosunek wariancji międzyłańcuchowych do wariancji wewnątrzłańcuchowych dla wszystkich próbkowanych parametrów jest bliski 1.

Zazwyczaj próbkowanie metodą Monte Carlo w łańcuchu Markowa może jedynie przybliżyć rozkład docelowy, ponieważ zawsze istnieje pewien efekt rezydualny pozycji początkowej. Bardziej wyrafinowane algorytmy oparte na łańcuchu Markowa Monte Carlo, takie jak sprzężenie z przeszłości, mogą generować dokładne próbki kosztem dodatkowych obliczeń i nieograniczonego (choć skończonego w oczekiwaniu) czasu działania .

Wiele metod błądzenia losowego Monte Carlo porusza się wokół rozkładu równowagi w stosunkowo małych krokach, bez tendencji, aby kroki przebiegały w tym samym kierunku. Metody te są łatwe do wdrożenia i analizy, ale niestety, eksploracja całej przestrzeni może zająć spacerowiczowi dużo czasu. Chodzik często cofa się i pokonuje już pokryty teren.

Dalsze rozważania na temat zbieżności dotyczą centralnego twierdzenia granicznego łańcucha Markowa . Zobacz omówienie teorii związanej z konwergencją i stacjonarnością algorytmu Metropolis-Hastings.

Oprogramowanie

Kilka programów zapewnia możliwości próbkowania MCMC, na przykład:

ParaMonte , wysokowydajne oprogramowanie do obsługi połączeń szeregowych/równoległych do symulacji Monte Carlo, w tym Adaptive Metropolis-Hastings MCMC z funkcją
Delayed-Rejection, dostępne w
- python ,
- MATLAB ,
- C/C++/Fortran w systemach Windows , Linux i macOS .
Pakiet Vandal
, Vandal oferuje wiele opcji symulacji Monte Carlo, takich jak pomiar ryzyka i histogram reguł empirycznych i wiele innych, dostępnych w
- Pyton
Pakiety używające dialektów języka modelowego BUGS :
- WinBUGS / OpenBUGS / MultiBUGS
- JAGS
- ZWINNY
greta , pakiet Bayesowskiego języka modelowania statystycznego / R, który wykorzystuje TensorFlow za kulisami, podobnie jak PyMC3 wykorzystujący Theano jako zaplecze obliczeniowe
MCSim
PyMC3
Pymcmcstat
R (język programowania) z pakietami adaptMCMC, atmcmc, BRugs, mcmc, MCMCpack, ramcmc, rjags, rstan itp.
Stan
TensorFlow Probability ( probabilistyczna biblioteka programistyczna zbudowana na TensorFlow )
MCL (algorytm klastrowy dla wykresów) i HipMCL (wersja zrównoleglona)
emcee (licencjonowana przez MIT implementacja w czystym Pythonie próbnika Monte Carlo Ensemble firmy Goodman & Weare Affine Invariant Markowa)
Keanu — probabilistyczna biblioteka programistyczna ogólnego przeznaczenia zbudowana w Javie
Zeus to czysta implementacja Pythona metody Ensemble Slice Sampling
Turing.jl , pakiet do ogólnego programowania probabilistycznego w Julia
Mamba.jl , platforma dla metody MCMC w Julii

Zobacz też

Bibliografia

Cytaty

Źródła

Christophe Andrieu, Nando De Freitas, Arnaud Doucet i Michael I. Jordan Wprowadzenie do MCMC dla uczenia maszynowego , 2003
Asmussen, Søren; Glynn, Peter W. (2007). Symulacja stochastyczna: algorytmy i analiza . Modelowanie stochastyczne i prawdopodobieństwo stosowane. 57 . Skoczek.
Atzberger, P. "Wprowadzenie do Monte-Carlo Methods" (PDF) .
Berg, Bernd A. (2004). Symulacje Monte Carlo łańcucha Markowa i ich analiza statystyczna . Światowy Naukowy .
Bolstad, William M. (2010). Zrozumienie obliczeniowej statystyki bayesowskiej . Wileya. Numer ISBN 978-0-470-04609-8.
Casella, George; George Edward I. (1992). „Wyjaśnienie próbnika Gibbsa”. Statystyk amerykański . 46 (3): 167–174. CiteSeerX 10.1.1.554.3993 . doi : 10.2307/2685208 . JSTOR 2685208 .
Gelfand, AE; Smith, AFM (1990). „Podejścia oparte na próbkach do obliczania gęstości krańcowych”. Dziennik Amerykańskiego Towarzystwa Statystycznego . 85 (410): 398-409. CiteSeerX 10.1.1.512.2330 . doi : 10.1080/01621459.199.10476213 .
Gelman, Andrzej ; Carlin, John B.; Stern, Hal S.; Rubin, Donald B. (1995). Bayesowska analiza danych (wyd. 1). Chapman i Hall . (Patrz rozdział 11.)
Niemcy, S.; Niemcy, D. (1984). „Relaks stochastyczny, rozkłady Gibbsa i Bayesowskie przywracanie obrazów”. Transakcje IEEE dotyczące analizy wzorców i inteligencji maszynowej . 6 (6): 721–741. doi : 10.1109/TPAMI.1984.4767596 . PMID 22499653 .
Gilks, WR; Richardson, S.; Spiegelhalter, DJ (1996). Łańcuch Markowa Monte Carlo w praktyce . Chapman i Hall /CRC.
Gill, Jeff (2008). Metody bayesowskie: podejście nauk społecznych i behawioralnych (wyd. 2). Chapman i Hall /CRC. Numer ISBN 978-1-58488-562-7.
Zielony, PJ (1995). „Reversible-skok łańcuchowy Markowa obliczenia Monte Carlo i Bayesowskie wyznaczanie modelu”. Biometria . 82 (4): 711–732. CiteSeerX 10.1.1.407.8942 . doi : 10.1093/biomet/82.4.711 .
Neal, Radford M. (2003). „Próbkowanie plastra” . Roczniki Statystyczne . 31 (3): 705–767. doi : 10.1214/aos/1056562461 . JSTOR 3448413 .
Neal, Radford M. (1993). " Wnioskowanie probabilistyczne przy użyciu metod Monte Carlo łańcuchów Markowa " .
Robert, Christian P.; Casella, G. (2004). Metody statystyczne Monte Carlo (wyd. 2). Skoczek. Numer ISBN 978-0-387-21239-5.
Rubinstein, RY; Kroese, DP (2007). Symulacja i metoda Monte Carlo (wyd. 2). Wiley . Numer ISBN 978-0-470-17794-5.
Smith, RL (1984). „Skuteczne procedury Monte Carlo do generowania punktów równomiernie rozmieszczonych na obszarach ograniczonych”. Badania operacyjne . 32 (6): 1296–1308. doi : 10.1287/opre.32.6.1296 . hdl : 2027,42/7681 .
Spall, JC (kwiecień 2003). „Oszacowanie za pomocą łańcucha Markowa Monte Carlo”. Magazyn IEEE Systemy Sterowania . 23 (2): 34–45. doi : 10.1109/mcs.2003.1188770 .
Stramer, O.; Tweedie, R. (1999). „Langevin-Type Models II: Self-Kierowanie Kandydaci do algorytmów MCMC”. Metodologia i obliczenia w stosowanym prawdopodobieństwie . 1 (3): 307–328. doi : 10.1023/A: 1010090512027 .

Dalsza lektura

Diaconis, Persi (kwiecień 2009). „Rewolucja Monte Carlo w łańcuchu Markowa” (PDF) . Byk. Amer. Matematyka. Soc. 46 (2): 179–205. doi : 10.1090/s0273-0979-08-01238-x . S 0273-0979(08)01238-X.
Prasa, WH ; Teukolski SA ; Vetterling, WT; Flannery, BP (2007), "Sekcja 15,8. Łańcuch Markowa Monte Carlo" , Przepisy numeryczne: The Art of Scientific Computing (3rd ed.), Cambridge University Press , ISBN 978-0-521-88068-8
Richey, Mateusz (maj 2010). „Ewolucja metod Monte Carlo łańcucha Markowa” (PDF) . Amerykański miesięcznik matematyczny . 117 (5): 383–413. CiteSeerX 10.1.1.295.4478 . doi : 10.4169/000298910x485923 .

Languages

In other projects