Próbkowanie przekrojów
Próbkowanie przekrojów – algorytm należący do klasy algorytmów próbkowania Monte Carlo łańcuchami Markowa generujący pseudo-losowych próbki z zadanej dystrybucji. Metoda opiera się na obserwacji, że aby próbkować zmienną losową można jednorodnie próbkować wnętrza konturów jej dystrybucji.
Motywacja
Powiedzmy, że chcemy otrzymać próbki zmiennej losowej X o rozkładzie f(x). Niech poniższy wykres odpowiada funkcji f(x). Wysokość f(x) odpowiada gęstości prawdopodobieństwa dla danej wartości.
Gdybyśmy jednorodnie próbkowali oś X, każdy wynik miałby taką samą gęstość prawdopodobieństwa. Zamiast otrzymać szukaną dystrybucję otrzymalibyśmy rozkład podobny do tego poniżej (niebieska linia).
Aby wygenerować próbki X w taki sposób aby wiernie oddać rozkład f(x), należy posłużyć się metodą która częściej zwraca wartości X odpowiadające dużym wartościom f(x).
Algorytm
Prosta wersja próbkowania przekrojów wybiera próbki z rozkładu jednostajnego na konturach f(x) bez potrzeby odrzucania próbek według poniższej procedury:
- Inicjalizuj x0 takie dla którego f(x0)>0.
- Wybierz y z jednorodnego rozkładu między 0 a f(x0).
- Znajdź poziomice f(x) = y.
- Wybierz wartość x z jednorodnego rozkładu z wewnątrz tej poziomicy.
- Wróć do kroku 2 używając nowej wartości x.
Motywacją dla takiej procedury jest obserwacja że zamiast próbkować trudny rozkład f(x) można próbkować jednorodnie małe poziome plastry f(x) jeśli plastry są losowane w odpowiedni sposób. Używając wartości x z poprzedniej iteracji w stanie równowagowym prawdopodobieństwo wylosowania danego plastra jest proporcjonalne do jego powierzchni.
Zazwyczaj problemem w implementacji jest znalezienie konturów, co zazwyczaj wymaga użycia funkcji odwrotnej do dystrybucji. To jest szczególnie trudne dla funkcji wielo-modalnych, gdzie kontur nie musi być spójny. Często można zminimalizować ten problem jeśli kontur jest podzbiorem nieco większego zbioru - można wtedy zastosować próbkowanie z odrzucaniem jako pod-algorytm dla punku 2 opisanej procedury.
Bibliografia
- P. Damlen, J. Wakefield, S. Walker. Gibbs sampling for Bayesian non‐conjugate and hierarchical models by using auxiliary variables. „Journal of the Royal Statistical Society, Series B (Statistical Methodology)”. 61(2), s. 331-344, 1999. Chicago.
- Radford M. Neal. Slice Sampling. „Annals of Statistics”. 31 (3), s. 705–767, 2003. DOI: 10.1214/aos/1056562461.
- Slice sampling. W: Christopher Bishop: Pattern Recognition and Machine Learning. Springer, 2006. ISBN 0-387-31073-8.