Jakie algorytmy / techniki MCMC są stosowane do dyskretnych parametrów?

Wiem sporo o dopasowywaniu parametrów ciągłych, szczególnie metod opartych na gradiencie, ale niewiele o dopasowywaniu parametrów dyskretnych.

Jakie są powszechnie stosowane algorytmy / techniki MCMC do dopasowania dyskretnych parametrów? Czy istnieją algorytmy, które są zarówno dość ogólne, jak i dość wydajne? Czy istnieją algorytmy, które dobrze radzą sobie z przekleństwem wymiarowości? Na przykład powiedziałbym, że Hamiltonian MCMC jest ogólny, potężny i dobrze się skaluje.

Próbkowanie z dowolnego dyskretnego rozkładu wydaje się trudniejsze niż próbkowanie z ciągłego rozkładu, ale jestem ciekawy, jaki jest stan techniki.

Edycja : JMS poprosił mnie o opracowanie.

Nie mam na myśli konkretnych aplikacji, ale oto kilka modeli, które sobie wyobrażam:

• Wybór modelu między kilkoma rodzajami modeli regresji ciągłej. Masz dyskretny pojedynczy parametr „model”
• Model ciągły, w którym każda obserwacja może być „wartością odstającą” i czerpać ze znacznie bardziej rozproszonego rozkładu. Przypuszczam, że to model mieszany.

Spodziewałbym się, że wiele modeli będzie zawierało parametry ciągłe i dyskretne.

Prosta odpowiedź brzmi: tak: Metropolis-Hastings i jego szczególny przypadek Próbkowanie Gibbsa :) Ogólne i potężne; to, czy skaluje się, zależy od danego problemu.

Nie jestem pewien, dlaczego uważasz, że próbkowanie arbitralnej dystrybucji dyskretnej jest trudniejsze niż arbitralna dystrybucja ciągła. Jeśli potrafisz obliczyć rozkład dyskretny, a przestrzeń próbki nie jest ogromna, to jest o wiele, wiele łatwiej (chyba że rozkład ciągły jest standardowy). Obliczyć prawdopodobieństwo dla każdej kategorii, a następnie znormalizować, aby uzyskać prawdopodobieństwa i zastosować odwrotne próbkowanie z transformacją (narzucenie arbitralnej kolejności na ) .$f(k)$$P(\tilde k = k) = f(k)/\sum f(k)$$k$

Czy masz na myśli konkretny model? Istnieją różne podejścia MCMC do dopasowywania modeli mieszanin, na przykład, gdy ukryte przypisania komponentów są dyskretnymi parametrami. Są to od bardzo prostych (Gibbs) do dość złożonych.

Jak duża jest przestrzeń parametrów? Czy jest potencjalnie ogromny (np. W przypadku modelu mieszanki ma N pod względem liczby składników mieszanki)? Możesz nie potrzebować niczego więcej niż samplera Gibbsa, ponieważ sprzężenie nie jest już problemem (możesz uzyskać stałą normalizującą bezpośrednio, aby obliczyć pełne warunki warunkowe). W rzeczywistości gridowe Gibbs były popularne w tych przypadkach, w których ciągłe przejęcie jest dyskretne, aby ułatwić obliczenia.

Nie sądzę, aby istniało szczególne „najlepsze” rozwiązanie dla wszystkich problemów mających dyskretną przestrzeń parametrów, tak jak w przypadku ciągłym. Ale jeśli powiesz nam więcej o modelach, którymi jesteś zainteresowany, być może możemy sformułować jakieś zalecenia.

Edycja: OK, mogę podać trochę więcej informacji na temat: waszych przykładów.

Twój pierwszy przykład ma długą historię, jak możesz sobie wyobrazić. Ostatnia recenzja znajduje się w [1], patrz także [2]. Spróbuję podać tutaj kilka szczegółów: Odpowiednim przykładem jest stochastyczny wybór zmiennych wyszukiwania. Pierwotnym sformułowaniem było użycie absolutnie ciągłych priorów, takich jak . To faktycznie okazuje się działać słabo w porównaniu z priors, takimi jak gdzie jest masą punktową na 0. Zauważ, że oba pasują do twojego oryginalnego sformułowania; podejście MCMC zwykle następowałoby poprzez rozszerzenie o (dyskretny) wskaźnik modelu (powiedzmy ). Jest to równoważne z indeksem modelu; Jeśli masz$p(\beta)\sim \pi N(\beta; 0, \tau) + (1-\pi) N(\beta, 0, 1000\tau)$$p(\beta)\sim \pi \delta_0 (\beta) + (1-\pi) N(\beta, 0, \tau)$$\delta_0$$\beta$$Z$$Z_1\dots, Z_p$ wtedy oczywiście możesz możliwe możliwe konfiguracje na liczby w skali .$2^p$$1:2^p$

Jak więc ulepszyć MCMC? W wielu z tych modeli można próbkować z według składu, tj. Używając tego . Takie aktualizacje bloków mogą znacznie poprawić miksowanie, ponieważ korelacja między i jest teraz nieistotna dla samplera$p(Z, \beta|y)$$p(Z, \beta|y) = p(\beta | Y, Z)p(Z|Y)$$Z$$\beta$

SSVS osadza całą przestrzeń modelu w jednym dużym modelu. Często jest to łatwe do wdrożenia, ale daje słabe wyniki. Skok odwracalny MCMC jest innym rodzajem podejścia, które pozwala wyraźnie zmieniać wymiary przestrzeni parametrów; przegląd [3] i kilka praktycznych uwag. Bardziej szczegółowe uwagi na temat implementacji w różnych modelach można znaleźć w literaturze.

Często kompletne podejście MCMC jest niewykonalne; powiedzmy, że masz regresję liniową ze zmiennymi i używasz podejścia takiego jak SSVS. Nie możesz mieć nadziei, że twój sampler się zbiegnie; nie ma wystarczającej ilości czasu lub mocy obliczeniowej, aby odwiedzić wszystkie te konfiguracje modeli, a jesteś szczególnie urażony, jeśli niektóre z twoich zmiennych są nawet umiarkowanie skorelowane. Powinieneś szczególnie sceptycznie podchodzić do osób próbujących w ten sposób oszacować takie czynniki, jak zmienne prawdopodobieństwa włączenia. Dla takich przypadków zaproponowano różne algorytmy wyszukiwania stochastycznego stosowane w połączeniu z MCMC. Jednym z przykładów jest BAS [4], innym jest [5] (Sylvia Richardson ma także inne istotne prace); większość innych, o których wiem, są ukierunkowane na konkretny model.$p=1000$

Innym podejściem, które zyskuje na popularności, jest stosowanie absolutnie ciągłych priorów skurczu, które naśladują uśrednione wyniki modelu. Zazwyczaj są one formułowane jako mieszanki skali normalnych. Lasso bayesowskie jest jednym przykładem, który jest szczególnym przypadkiem priorów normalnej gamma i ograniczającym przypadkiem normalnych wykładniczych gamorów. Inne opcje obejmują podkowę i ogólną klasę normalnych rozkładów z odwróconymi wersjami beta priorów ich wariancji. Aby uzyskać więcej informacji na ten temat, sugeruję zacząć od [6] i przejrzeć referencje (zbyt wiele, żebym mógł je tutaj powtórzyć :))

Później dodam więcej o modelach odstających, jeśli będę miał szansę; klasyczne odniesienie to [7]. Są bardzo podobni duchem do kurczących się priorów. Zwykle są one bardzo łatwe do zrobienia dzięki próbkowaniu Gibbsa.

Być może nie tak praktyczne, jak się spodziewałeś; w szczególności wybór modelu jest trudnym problemem, a im bardziej rozbudowany model, tym gorzej. Blokowanie aktualizacji, gdy tylko jest to możliwe, jest jedyną ogólną radą, jaką mam. Próbkowanie z wielu dystrybucji często powoduje problem polegający na tym, że wskaźniki członkostwa i parametry komponentu są wysoce skorelowane. Nie poruszyłem również kwestii zmiany etykiety (lub braku zmiany etykiety); jest tam sporo literatury, ale trochę z mojej sterówki.

W każdym razie uważam, że warto zacząć od niektórych z odniesień tutaj, aby poznać różne sposoby, w jakie inni podchodzą do podobnych problemów.

[1] Merlise Clyde i EI George. Model niepewności statystyczny 19 (2004): 81--94. http://www.isds.duke.edu/~clyde/papers/statsci.pdf

[2] http://www-personal.umich.edu/~bnyhan/montgomery-nyhan-bma.pdf

[3] Green & Hastie Reversible jump MCMC (2009) http://www.stats.bris.ac.uk/~mapjg/papers/rjmcmc_20090613.pdf

[4] http://www.stat.duke.edu/~clyde/BAS/

[5] http://ba.stat.cmu.edu/journal/2010/vol05/issue03/bottolo.pdf

[6] http://www.uv.es/bernardo/Polson.pdf

[7] Modele Mike'a Westa Outliera i wcześniejsze rozkłady w regresji liniowej Bayesa (1984) JRSS-B