Przejdź do treści
Wróć do wyników wyszukiwania

Łańcuchowe metody Monte Carlo (MCMC) — Metropolis-Hastings i próbkowanie Gibbsa

Autor metody
Metropolis et al. (1953); Gibbs sampler formalised by Geman & Geman (1984)
Rok
1953 (Metropolis-Hastings); 1984 (Gibbs)
Typ
Simulation-based Bayesian inference / numerical integration

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Łańcuchowe metody Monte Carlo (MCMC) to rodzina algorytmów symulacyjnych, które konstruują łańcuch Markowa, którego rozkład stacjonarny jest docelowym rozkładem aposteriori, umożliwiając wnioskowanie bayesowskie i obliczanie całek w przestrzeniach wielowymiarowych, które w przeciwnym razie byłyby analitycznie nieuchwytne.

Zapoczątkowane przez Metropolisa i współpracowników w 1953 r. i rozszerzone przez Hastingsa w 1970 r., MCMC stanowią podstawę współczesnej statystyki bayesowskiej. Dwie najczęściej stosowane odmiany to Metropolis-Hastings, która proponuje ruchy z ogólnego rozkładu propozycji, oraz próbkowanie Gibbsa, które losuje każdy parametr po kolei z jego pełnego rozkładu warunkowego.

Intuicja stojąca za metodą

Wyobraźmy sobie, że chcemy poznać kształt pasma górskiego ukrytego we mgle. Nie widzimy go w całości naraz, ale możemy zrobić krok w losowym kierunku i zdecydować, czy się poruszyć, w zależności od tego, czy teren jest wyższy, czy niższy. Idąc wystarczająco długo i zapisując, gdzie byliśmy, miejsca, które odwiedzaliśmy najczęściej, wyznaczają szczyty — jest to rozkład aposteriori. MCMC robi to samo w wielowymiarowej przestrzeni parametrów: buduje łańcuch próbek, który stopniowo wędruje w rejony o wysokim prawdopodobieństwie, tak że histogram odwiedzonych wartości przybliża docelowy rozkład bez potrzeby posiadania jego jawnej postaci analitycznej.

Historia

Podstawowy algorytm Metropolisa został opublikowany w 1953 roku przez Metropolisa, Rosenbluth, Rosenbluth, Tellera i Tellera do symulacji molekularnych. Hastings (1970) uogólnił go na asymetryczne rozkłady propozycji, tworząc algorytm Metropolis-Hastings. Geman i Geman (1984) wprowadzili próbkowanie Gibbsa w kontekście rekonstrukcji obrazu. Algorytm stał się głównym narzędziem statystycznym na początku lat 90. po tym, jak Gelfand i Smith (1990) zademonstrowali jego szeroką stosowalność do obliczeń bayesowskich, a Gelman i Rubin (1992) dostarczyli diagnostykę zbieżności R̂. Późniejszy rozwój hamiltonowskiego Monte Carlo przez Duane et al. (1987) i jego automatyczną odmianę NUTS przez Hoffmana i Gelmana (2014) rozszerzył MCMC na problemy wielowymiarowe. Bayesian Data Analysis Gelmana et al. (2013) oraz Handbook of Markov Chain Monte Carlo (Brooks et al., 2011) są standardowymi, kompleksowymi opracowaniami.

Kiedy stosować

MCMC jest odpowiednim narzędziem, gdy określono model bayesowski, a rozkładu aposteriori nie można obliczyć analitycznie — co jest częstym przypadkiem dla modeli z więcej niż kilkoma parametrami lub z rozkładami a priori niebędącymi sprzężonymi. Jest to również standardowe podejście dla modeli ze zmiennymi ukrytymi, modeli hierarchicznych i każdego ustawienia, gdzie niepewność musi być w pełni propagowana przez złożony potok obliczeniowy. Nie są wymagane żadne założenia dotyczące rozkładu danych poza specyfikacją funkcji wiarygodności. Głównym praktycznym wymogiem jest wystarczająca liczba iteracji, aby łańcuch zbiegł: mniej niż około 1 000 próbek po okresie rozgrzewki zazwyczaj nie zapewni wiarygodnej charakterystyki rozkładu aposteriori, a w ustawieniach wielowymiarowych potrzeba znacznie więcej. Gdy przestrzeń parametrów jest bardzo wielowymiarowa, hamiltonowskie Monte Carlo (HMC) lub No-U-Turn Sampler (NUTS) — automatyczne rozszerzenia idei MCMC — są znacznie wydajniejsze niż podstawowe Metropolis-Hastings.

Ograniczenia i uwagi

  • Zbieżność nie jest gwarantowana w skończonym czasie; łańcuch, który wydaje się zbieżny, może nadal utknąć w lokalnym regionie rozkładu aposteriori.
  • Autokorelacja między kolejnymi próbkami oznacza, że efektywna liczba próbek jest mniejsza niż surowa liczba iteracji, co wymaga dłuższych przebiegów niż potrzebowałaby równoważna niezależna próba.
  • W wielowymiarowych przestrzeniach parametrów Metropolis-Hastings typu random-walk słabo miesza; hamiltonowskie Monte Carlo lub NUTS jest potrzebne do wydajnej eksploracji.
  • Specyfikacja modelu wymaga od analityka przemyślanego wyboru rozkładów a priori, a źle dobrane rozkłady a priori lub błędnie określone funkcje wiarygodności mogą zniekształcić rozkład aposteriori w sposób trudny do wykrycia.

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Umożliwia dokładne (asymptotycznie) wnioskowanie bayesowskie dla modeli, w których rozkład aposteriori nie ma postaci zamkniętej, obejmując modele hierarchiczne, problemy z brakującymi danymi i złożone funkcje wiarygodności.
  • Produkuje pełną próbkę wspólnego rozkładu aposteriori, dzięki czemu każda pochodna wielkość, predykcja lub decyzja może być obliczona z poprawnie propagowaną niepewnością.
  • Ma zastosowanie do wyników ciągłych, binarnych i zliczeniowych i nie nakłada żadnych założeń dotyczących rozkładu danych poza specyfikacją funkcji wiarygodności przez modelującego.
  • Uruchamianie wielu równoległych łańcuchów sprawia, że weryfikacja zbieżności jest systematyczna dzięki diagnostyce R̂ Gelmana-Rubina.

Zastosowania

  • Dopasowywanie hierarchicznych modeli bayesowskich w psychologii, edukacji i medycynie, gdzie dane są grupowane i pożądane jest częściowe poolingowanie.
  • Estymacja parametrów epidemiologicznych modeli kompartmentowych (SIR, SEIR) na podstawie obserwowanych liczby przypadków, w tym kwantyfikacja niepewności.
  • Bayesowskie modelowanie równań strukturalnych i modele ze zmiennymi ukrytymi w badaniach nauk społecznych.
  • Wnioskowanie aposteriori dla modeli teorii odpowiedzi na pozycje (IRT) w pomiarach edukacyjnych.
  • Kalibracja złożonych modeli symulacyjnych na podstawie obserwowanych danych, gdy funkcja wiarygodności jest dostępna, ale nie jest sprzężona.
  • Modelowanie ryzyka finansowego i wycena opcji przy bayesowskiej niepewności parametrów.

Jak to działa

Jak to działa

1

Analityk definiuje model bayesowski: funkcję wiarygodności łączącą parametry z obserwowanymi danymi oraz rozkłady a priori kodujące przekonania o każdym parametrze przed zobaczeniem danych. Razem definiują one nieunormowany rozkład aposteriori, który będzie eksplorowany przez MCMC. Wybór rozkładów a priori i rodziny funkcji wiarygodności determinuje strukturę łańcucha i musi być oparty na wiedzy dziedzinowej.

2

Ustawia się wartości początkowe dla wszystkich parametrów, liczbę łańcuchów, długość okresu rozgrzewki (burn-in) oraz całkowitą liczbę iteracji po okresie rozgrzewki. Standardową praktyką jest uruchamianie wielu niezależnych łańcuchów — zazwyczaj czterech — z różnych punktów startowych, ponieważ pozwala to ocenić zbieżność poprzez porównanie łańcuchów, zamiast polegania na pojedynczej trajektorii.

3

W każdej iteracji algorytm proponuje ruch w przestrzeni parametrów. W metodzie Metropolis-Hastings kandydat jest losowany z rozkładu propozycji i akceptowany z prawdopodobieństwem zależnym od stosunku gęstości aposteriori w pozycjach kandydata i obecnej, zapewniając, że rozkład stacjonarny łańcucha jest docelowym rozkładem aposteriori. W próbkowaniu Gibbsa każdy parametr jest aktualizowany po kolei przez losowanie bezpośrednio z jego pełnego rozkładu warunkowego, co eliminuje potrzebę jawnego kroku akceptacji. Ponieważ kolejne próbki dzielą informacje, łańcuch wykazuje autokorelację; rzadzenie (thinning) — zachowywanie co k-tej próbki — może ją zmniejszyć kosztem mniejszej liczby przechowywanych próbek.

4

Po odrzuceniu okresu rozgrzewki ocenia się zbieżność. Statystyka R̂ Gelmana-Rubina porównuje wariancję wewnątrz łańcucha z wariancją między łańcuchami dla wielu łańcuchów; wartości poniżej 1,05 wskazują, że łańcuchy wymieszały się i zbiegły do tego samego rozkładu. Inspekcji podlegają również wykresy śladów (trace plots — sekwencja próbowanych wartości w kolejnych iteracjach) oraz efektywna liczba próbek. Jeśli R̂ jest duże lub wykresy śladów pokazują słabe mieszanie, model, rozkłady a priori lub ustawienia próbnika muszą zostać poprawione przed przystąpieniem do wnioskowania.

5

Zbiór próbek po okresie rozgrzewki stanowi empiryczne przybliżenie rozkładu aposteriori. Estymatory punktowe (średnia lub mediana aposteriori), przedziały wiarygodności i aposteriorne rozkłady predykcyjne są obliczane bezpośrednio z próby. Ponieważ próbki są losowaniami ze wspólnego rozkładu aposteriori, każda pochodna wielkość — stosunki, różnice, nieliniowe funkcje parametrów — może być oszacowana przez zastosowanie tej samej funkcji do każdej próbki i podsumowanie wynikowego rozkładu.

Częste pułapki

  • Pominięcie lub skrócenie okresu rozgrzewki oznacza, że wczesna niestacjonarna część łańcucha zanieczyszcza estymaty aposteriori — zawsze należy odrzucać hojny okres rozgrzewki.
  • Uruchomienie tylko jednego łańcucha uniemożliwia wykrycie, czy próbnik zbiegł, czy utknął w jednym regionie; zawsze należy uruchamiać co najmniej cztery niezależne łańcuchy.
  • Traktowanie dużej liczby surowych iteracji jako dowodu zbieżności bez obliczania R̂ lub inspekcji wykresów śladów może dać fałszywą pewność — wymagane jest R̂ < 1,05, a nie tylko wiele iteracji.
  • Ignorowanie autokorelacji i raportowanie efektywnej liczby próbek, jakby była to surowa liczba, zawyża precyzję; należy raportować efektywną liczbę próbek obok surowych liczb.
  • Zastosowanie MCMC do modelu z mniej niż około 1 000 iteracji po okresie rozgrzewki zazwyczaj nie da wiarygodnego rozkładu aposteriori; jeśli budżet obliczeniowy jest tak ograniczony, należy rozważyć analityczne metody bayesowskie lub model sprzężony.

Najczęściej zadawane pytania

Skąd mam wiedzieć, czy mój łańcuch MCMC zbiegł?

Główną diagnostyką jest statystyka R̂ Gelmana-Rubina, obliczana przez uruchomienie co najmniej czterech niezależnych łańcuchów z różnych punktów startowych i porównanie wariancji wewnątrz łańcucha z wariancją między łańcuchami. Wartości R̂ poniżej 1,05 dla wszystkich parametrów są konwencjonalnym progiem. Wykresy śladów powinny pokazywać łańcuchy, które się nakładają i eksplorują ten sam region; wykresy w kształcie lejka lub dryfujące wskazują na słabe mieszanie. Należy również sprawdzić efektywną liczbę próbek — bardzo mała efektywna liczba próbek w stosunku do surowej liczby sygnalizuje wysoką autokorelację i potrzebę większej liczby iteracji lub lepszego próbnika.

Jaka jest różnica między Metropolis-Hastings a próbkowaniem Gibbsa?

Metropolis-Hastings proponuje ruch dla wszystkich parametrów jednocześnie (lub w blokach) z rozkładu propozycji określonego przez użytkownika i akceptuje lub odrzuca propozycję z prawdopodobieństwem, które zachowuje docelowy rozkład aposteriori jako rozkład stacjonarny. Próbkowanie Gibbsa zamiast tego aktualizuje każdy parametr po kolei, losując bezpośrednio z jego pełnego rozkładu warunkowego — rozkładu tego parametru przy danych pozostałych parametrach i danych. Próbkowanie Gibbsa wymaga, aby te pełne rozkłady warunkowe były dostępne w postaci zamkniętej, co ma miejsce w przypadku wielu modeli sprzężonych; gdy są dostępne, próbkowanie Gibbsa jest bardzo wydajne, ponieważ każda propozycja jest akceptowana. Metropolis-Hastings jest bardziej ogólnie stosowalny, ale wymaga dostrojenia propozycji w celu uzyskania akceptowalnych wskaźników akceptacji.

Kiedy powinienem używać hamiltonowskiego Monte Carlo zamiast Metropolis-Hastings?

Hamiltonian Monte Carlo (HMC) i jego automatyczna odmiana NUTS wykorzystują informacje o gradiencie z logarytmu rozkładu aposteriori do proponowania dużych, świadomych ruchów, które są jednak akceptowane z wysokim prawdopodobieństwem. Czyni je to znacznie wydajniejszymi niż Metropolis-Hastings typu random-walk w wielowymiarowych przestrzeniach parametrów, gdzie losowe propozycje są prawie zawsze odrzucane. Jako praktyczna zasada, jeśli model ma więcej niż około dziesięciu parametrów lub jeśli łańcuchy Metropolis-Hastings wykazują słabe mieszanie i bardzo niskie efektywne liczby próbek, zaleca się przejście na HMC lub NUTS.

Ile iteracji potrzebuję?

Nie ma uniwersalnej odpowiedzi, ale powszechnym punktem wyjścia jest 1 000 iteracji rozgrzewki (burn-in) plus 2 000 iteracji próbkowania na łańcuch, w czterech łańcuchach, co daje 8 000 próbek po okresie rozgrzewki. Adekwatność tego zależy od autokorelacji łańcucha i złożoności rozkładu aposteriori. Łańcuch jest wystarczający, gdy R̂ < 1,05 dla wszystkich parametrów, a efektywna liczba próbek jest wystarczająco duża, aby scharakteryzować interesujące cechy rozkładu aposteriori — zazwyczaj co najmniej kilkaset efektywnych próbek dla średnich i kilka tysięcy dla kwantyli ogonowych.

Pokrewne metody

Źródła

  1. Gelman, A., Carlin, J.B., Stern, H.S., Dunson, D.B., Vehtari, A. & Rubin, D.B. (2013). Bayesian Data Analysis (3rd ed.). Chapman & Hall/CRC.

    Otwórz odnośnik DOI
    Skopiowano.
  2. Brooks, S., Gelman, A., Jones, G.L. & Meng, X.-L. (Eds.) (2011). Handbook of Markov Chain Monte Carlo. Chapman & Hall/CRC.

    Otwórz odnośnik DOI
    Skopiowano.