mały|Zbieżność algorytmu Metropolisa-Hastingsa. MCMC przybliża niebieski rozkład pomarańczowym rozkładem coraz dokładniej, gdy rośnie liczba kroków Próbkowanie Monte Carlo łańcuchami Markowa () – klasa algorytmów próbkowania z rozkładu prawdopodobieństwa. Poprzez budowę łańcucha Markowa o rozkładzie równowagowym pasującym do pożądanego rozkładu można wydajnie próbkować złożone rozkłady prawdopodobieństwa. Im większa liczba kroków w takim algorytmie, tym dokładniej rozkład próbki odpowiada pożądanemu rozkładowi.

Dziedziny stosowania Algorytmy MCMC są używane głównie do obliczania przybliżeń numerycznych dla całek wielowymiarowych, na przykład w statystyce bayesowskiej, fizyce komputerowej, biologii obliczeniowej i lingwistyce komputerowej.

W statystyce bayesowskiej rozwój algorytmów MCMC umożliwił wyliczanie dużych modeli hierarchicznych, wymagających całkowania po setkach lub tysiącach parametrów.

Przykłady Przykłady błądzenia losowego Monte Carlo obejmuje następujące algorytmy: Algorytm Metropolisa-Hastingsa – generuje błądzenie losowe w oparciu o gęstość przyjmowania i odrzucania propozycji kolejnych kroków. Próbkowanie Gibbsa – ta metoda dodatkowo wymaga, aby wszystkie warunkowe rozkłady prawdopodobieństwa docelowego rozkładu były znane (z dokładnością do stałej). Gdy próbkowanie warunkowych rozkładów nie jest łatwe, inne metody próbkowania mogą być użyte. Próbkowanie Gibbsa zawdzięcza swoją popularność głównie brakowi parametrów swobodnych. Próbkowanie przekrojów – opiera się na obserwacji, że rozkłady można wiernie próbkować poprzez jednorodne próbkowanie odpowiednich podzbiorów dziedziny. Metoda wykonuje dwa rodzaje kroków naprzemiennie: próbkę w pionie z rozkładu jednorodnego i próbkę w poziomie z podzbioru dziedziny dla której gęstość prawdopodobieństwa jest mniejsza od próbki pionowej. Wielokrotne Metropolis – odmiana algorytmu Metropolisa–Hastingsa, która pozwala na wiele prób w każdym punkcie. Poprzez umożliwienie dłuższych kroków w każdej iteracji, częściowo rozwiązuje problem „przekleństwa wymiarowości”. Odwracalny skok – kolejna odmiana algorytmu Metropolisa–Hastingsa, która pozwala na dynamiczną zmianę wymiaru przestrzeni próbkowania. Algorytmy MCMC, które zmieniają wymiar są stosowane w mechanice statystycznej, gdzie dla pewnych przypadków próbkowany rozkład układu wielkiego kanonicznego (na przykład gdy liczba cząsteczek w dziedzinie jest zmienna) zmienia wymiar dziedziny.

Redukowanie korelacji Bardziej złożone metody wykorzystują różne sposoby, aby zmniejszyć korelację pomiędzy kolejnymi próbkami. Algorytmy te mogą być trudniejsze w implementacji, ale często wykazują szybszą zbieżność (tj. mniejszą ilość kroków w celu uzyskania tej samej dokładności próbkowania).

Przykłady Przykłady MCMC, nienależących do metod błądzenia losowego obejmują następujące algorytmy: Hybrydowa metoda Monte-Carlo (HMC) – unika błądzenia losowego poprzez wprowadzenie pędu i równań hamiltonowskich, takich że energia potencjalna jest proporcjonalna do docelowego rozkładu prawdopodobieństwa. Takie podejście skutkuje szybszym poruszaniem się po dziedzinie próbkowania i daje lepszą zbieżność do docelowego rozkładu. Istnieją też warianty próbkowania przekrojów, które nie korzystają z błądzenia losowego. MCMC Langevina i inne metody oparte na gradiencie (czasem także na drugiej pochodnej) logarytmu rozkładu warunkowego pozwalają na tworzenie propozycji, które mają większą szansę na poruszanie się w kierunku dużej gęstości prawdopodobieństwa.

Przypisy

Bibliografia Christophe Andrieu, Nando De Freitas, Arnaud Doucet and Michael I. Jordan An Introduction to MCMC for Machine Learning, 2003

.

Kategoria:Metody numeryczne Kategoria:Modelowanie statystyczne Kategoria:Procesy stochastyczne