Jak wyjaśniłbyś laikowi Markov Chain Monte Carlo (MCMC)?

Może koncepcja, dlaczego jest używana i przykład.

Po pierwsze, musimy zrozumieć, czym jest łańcuch Markowa. Rozważ następujący przykład pogody z Wikipedii. Załóżmy, że pogodę w danym dniu można zaklasyfikować tylko do dwóch stanów: słonecznego i deszczowego. W oparciu o wcześniejsze doświadczenia wiemy, co następuje:

$P(\text{Next day is Sunny}\,\vert \,\text{Given today is Rainy)}=0.50$

Ponieważ pogoda na następny dzień jest słoneczna lub deszczowa, wynika z tego, że:

$P(\text{Next day is Rainy}\,\vert \,\text{Given today is Rainy)}=0.50$

Podobnie pozwól:

$P(\text{Next day is Rainy}\,\vert \,\text{Given today is Sunny)}=0.10$

Wynika stąd, że:

$P(\text{Next day is Sunny}\,\vert \,\text{Given today is Sunny)}=0.90$

Powyższe cztery liczby można w zwięzły sposób przedstawić jako macierz przejściową, która przedstawia prawdopodobieństwo przejścia pogody z jednego stanu do drugiego w następujący sposób:

$P = \begin{bmatrix} & S & R \\ S& 0.9 & 0.1 \\ R& 0.5 & 0.5 \end{bmatrix}$

Możemy zadać kilka pytań, na które odpowiedzą:

P1: Jeśli dzisiaj jest słoneczna pogoda, jaka będzie jutro pogoda?

A1: Ponieważ nie wiemy na pewno, co się wydarzy, najlepiej możemy powiedzieć, że istnieje szans, że będzie słonecznie, a , że będzie deszcz.10 $90\%$$10\%$

Q2: Co powiesz na dwa dni od dzisiaj?

A2: Prognoza na jeden dzień: słonecznie, deszczowo. Dlatego za dwa dni:10 $90\%$$10\%$

Pierwszego dnia może być słonecznie, a następnego dnia może być słonecznie. Szanse na to są następujące: .$0.9 \times 0.9$

Lub

Pierwszego dnia może być deszczowo, a drugiego dnia może być słonecznie. Szanse na to są następujące: .$0.1 \times 0.5$

Dlatego prawdopodobieństwo, że pogoda będzie słoneczna za dwa dni, wynosi:

$P(\text{Sunny 2 days from now} = 0.9 \times 0.9 + 0.1 \times 0.5 = 0.81 + 0.05 = 0.86$

Podobnie prawdopodobieństwo, że będzie padać, to:

$P(\text{Rainy 2 days from now} = 0.1 \times 0.5 + 0.9 \times 0.1 = 0.05 + 0.09 = 0.14$

W algebrze liniowej (macierze przejściowe) obliczenia te odpowiadają wszystkim permutacjom w przejściach między krokami (słoneczny do słonecznego ( ), słoneczny do deszczowego ( ), deszczowy do słonecznego ( ) lub deszczowa do deszczowej ( )) z ich obliczonymi prawdopodobieństwami:S 2 R R 2 S R 2$S_2S$$S_2R$$R_2S$$R_2R$

W dolnej części obrazu widzimy, jak obliczyć prawdopodobieństwo przyszłego stanu ( lub ), biorąc pod uwagę prawdopodobieństwa (funkcja masy prawdopodobieństwa, ) dla każdego stanu (słonecznego lub deszczowego) w czasie zero (teraz lub ) jako proste mnożenie macierzy.t + 2 P M F t $t+1$$t+2$$PMF$$t_0$

Jeśli nadal będziesz prognozować pogodę w ten sposób, zauważysz, że ostatecznie prognoza dnia, gdzie jest bardzo duża (powiedzmy ), ustala się na następujące prawdopodobieństwa „równowagi”:n $n$$n$$30$

$P(\text{Sunny}) = 0.833$

i

$P(\text{Rainy}) = 0.167$

Innymi słowy, twoja prognoza na ty dzień i ty dzień pozostają takie same. Ponadto można również sprawdzić, czy prawdopodobieństwo „równowagi” nie zależy dziś od pogody. Otrzymasz taką samą prognozę pogody, jeśli zaczniesz od założenia, że ​​dzisiaj pogoda jest słoneczna lub deszczowa.n + $n$$n+1$

Powyższy przykład będzie działał tylko wtedy, gdy prawdopodobieństwo przejścia do stanu spełni kilka warunków, których nie będę tutaj omawiać. Zwróć jednak uwagę na następujące cechy tego „ładnego” łańcucha Markowa (nice = prawdopodobieństwo przejścia spełnia warunki):

Niezależnie od początkowego stanu początkowego ostatecznie osiągniemy równowagę rozkładu prawdopodobieństwa stanów.

Markov Chain Monte Carlo wykorzystuje powyższą funkcję w następujący sposób:

Chcemy generować losowe losowania z rozkładu docelowego. Następnie określamy sposób budowy „ładnego” łańcucha Markowa, tak aby rozkład prawdopodobieństwa równowagi był naszym rozkładem docelowym.

Jeśli uda nam się zbudować taki łańcuch, wówczas dowolnie zaczniemy od pewnego punktu i wielokrotnie iterujemy łańcuch Markowa (np. Jak prognozujemy pogodę razy). W końcu generowane przez nas losowania wyglądałyby tak, jakby pochodziły z naszej dystrybucji docelowej.$n$

Następnie przybliżamy wielkości odsetek (np. Średnią), biorąc średnią próbną losowań po odrzuceniu kilku początkowych losowań, które są składnikiem Monte Carlo.

Istnieje kilka sposobów konstruowania „ładnych” łańcuchów Markowa (np. Sampler Gibbsa, algorytm Metropolis-Hastings).

Myślę, że można uzyskać przyjemną i prostą intuicję z algorytmu Metropolis-Hastings (łańcuch niezależności).

Po pierwsze, jaki jest cel? Celem MCMC jest pobieranie próbek z pewnego rozkładu prawdopodobieństwa bez konieczności znajomości jego dokładnej wysokości w dowolnym punkcie. Sposób, w jaki MCMC to osiąga, polega na „przechadzaniu się” po tym rozkładzie w taki sposób, aby ilość czasu spędzonego w każdej lokalizacji była proporcjonalna do wysokości rozkładu. Jeśli proces „wędrówki dookoła” jest skonfigurowany poprawnie, możesz upewnić się, że ta proporcjonalność (między czasem spędzonym a wysokością dystrybucji) zostanie osiągnięta.

Intuicyjnie chcemy chodzić po jakiejś (nierównej) powierzchni w taki sposób, aby ilość czasu, który spędziliśmy (lub # pobrano próbki) w każdym miejscu, była proporcjonalna do wysokości powierzchni w tym miejscu. Na przykład chcielibyśmy spędzić dwa razy więcej czasu na wzgórzu na wysokości 100 m niż na pobliskim wzgórzu na wysokości 50 m. Zaletą jest to, że możemy to zrobić, nawet jeśli nie znamy bezwzględnych wysokości punktów na powierzchni: wszystko, co musimy wiedzieć, to wysokości względne . np. jeśli jeden szczyt A jest dwa razy wyższy niż szczyt B, wówczas chcielibyśmy spędzić dwa razy więcej czasu w A niż w B.

Najprostszy wariant algorytmu Metropolis-Hastings (próbkowanie łańcucha niezależności) osiąga to w następujący sposób: załóżmy, że w każdym (dyskretnym) kroku czasowym wybieramy losową nową „proponowaną” lokalizację (wybraną równomiernie na całej powierzchni). Jeśli proponowana lokalizacja jest wyższa niż obecnie, przejdź do niej. Jeśli proponowana lokalizacja jest niższa, przejdź do nowej lokalizacji z prawdopodobieństwem p, gdzie p jest stosunkiem wysokości tego punktu do wysokości bieżącej lokalizacji. (tj. rzuć monetą z prawdopodobieństwem zdobycia głów; jeśli pojawi się głowa, przejdź do nowej lokalizacji; jeśli pojawi się ogon, pozostań tam, gdzie jesteśmy). Zachowaj listę lokalizacji, w których przebywałeś na każdym kroku, a ta lista (egiptycznie) będzie miała odpowiednią część czasu spędzonego w każdej części powierzchni.

Istnieją bardziej skomplikowane schematy proponowania nowych lokalizacji i zasady ich akceptacji, ale podstawową ideą jest nadal: (1) wybranie nowej „proponowanej” lokalizacji; (2) dowiedzieć się, o ile wyżej lub niżej ta lokalizacja jest porównywana z twoją bieżącą lokalizacją; (3) prawdopodobnie pozostanie w miejscu lub przeniesie się do tej lokalizacji w sposób zgodny z ogólnym celem spędzenia czasu proporcjonalnie do wysokości lokalizacji.

Do czego to jest przydatne? Załóżmy, że mamy probabilistyczny model pogody, który pozwala nam ocenić A * P (pogodę), gdzie A jest nieznaną stałą. (Często się to zdarza - wiele modeli jest wygodnych w formułowaniu w taki sposób, że nie można ustalić, czym jest A). Dlatego nie możemy dokładnie oszacować P („jutro będzie padać”). Możemy jednak uruchomić próbnik MCMC na chwilę, a następnie zapytać: jaka część próbek (lub „lokalizacji”) skończyła w stanie „jutro padającego deszczu”. Ta część będzie (opartą na modelu) probabilistyczną prognozą pogody.

Prawdopodobnie powiedziałbym coś takiego:

„Za każdym razem, gdy chcemy porozmawiać o prawdopodobieństwach, naprawdę integrujemy gęstość. W analizie Bayesa wiele wymyślonych przez nas gęstości nie jest możliwych do analizy: możesz je tylko zintegrować - jeśli w ogóle możesz je zintegrować - z wielkim cierpieniem. Dlatego zamiast tego dużo symulujemy zmienną losową, a następnie obliczamy prawdopodobieństwa na podstawie naszych symulowanych liczb losowych. Jeśli chcemy poznać prawdopodobieństwo, że X jest mniejsze niż 10, liczymy odsetek wyników symulowanej zmiennej losowej mniejszej niż 10 i użyj jej jako naszego oszacowania. To część „Monte Carlo”, jest to oszacowanie prawdopodobieństwa oparte na liczbach losowych. Przy wystarczającej liczbie symulowanych liczb losowych oszacowanie jest bardzo dobre, ale nadal jest z natury losowy.

„Więc po co„ Łańcuch Markowa ”? Ponieważ w pewnych warunkach technicznych można wygenerować proces bez pamięci (zwany także Markowskim), który ma taki sam rozkład ograniczający jak zmienna losowa, którą próbujesz zasymulować. liczba różnych rodzajów procesów symulacyjnych, które generują skorelowane liczby losowe (oparte tylko na bieżącej wartości tych liczb), a masz gwarancję, że po zebraniu wystarczającej liczby wyników otrzymasz stos liczb, który wygląda „ tak jakby „udało ci się w jakiś sposób pobrać niezależne próbki ze skomplikowanej dystrybucji, o której chciałeś wiedzieć.

„Na przykład, jeśli chcę oszacować prawdopodobieństwo, że standardowa normalna zmienna losowa była mniejsza niż 0,5, mógłbym wygenerować dziesięć tysięcy niezależnych realizacji ze standardowego rozkładu normalnego i policzyć liczbę mniejszą niż 0,5; powiedzmy, że otrzymałem 6905, które były mniej niż 0,5 na 10000 wszystkich próbek; moje oszacowanie dla P (Z <0,5) wynosi 0,6905, co nie jest tak dalekie od rzeczywistej wartości. To byłby szacunek Monte Carlo.

lista liczb, które otrzymuję z procedury, będzie rozłożona jak duża liczba losowań z czegoś, co generuje normalne zmienne losowe. To dałoby mi symulację Monte Carlo Markov Chain dla standardowej normalnej zmiennej losowej. Gdybym użył tego do oszacowania prawdopodobieństwa, byłby to szacunek MCMC. ”

Wyobraź sobie, że chcesz znaleźć lepszą strategię na pokonanie znajomych w grze planszowej Monopoly. Uprość rzeczy, które są ważne w grze, do pytania: na jakich właściwościach ludzie lądują najbardziej? Odpowiedź zależy od struktury planszy, zasad gry i rzutów dwiema kostkami.

Jednym ze sposobów odpowiedzi na to pytanie jest: Po prostu rzuć kostką wokół planszy, rzucając kostkami i przestrzegaj zasad. Policz, ile razy lądujesz na każdej nieruchomości (lub zaprogramuj komputer, aby wykonał pracę za Ciebie). W końcu, jeśli masz wystarczająco dużo cierpliwości lub wystarczająco dobrze zaprogramowałeś zasady na swoim komputerze, uzyskasz dobry obraz tego, które nieruchomości cieszą się największym zainteresowaniem. To powinno pomóc ci częściej wygrywać.

To, co zrobiłeś, to analiza Markov Chain Monte Carlo (MCMC). Plansza określa zasady. To, gdzie wylądujesz jako następny, zależy tylko od tego, gdzie jesteś teraz, a nie od tego, gdzie byłeś wcześniej, a konkretne prawdopodobieństwa są określone przez rozkład rzutów dwoma kostkami. MCMC to zastosowanie tego pomysłu do systemów matematycznych lub fizycznych, takich jak jaka będzie jutrzejsza pogoda lub gdzie skończy się losowe zbieranie pyłku przez cząsteczki gazu.

OK, oto moja najlepsza próba nieformalnego i prostego wyjaśnienia.

Łańcuch Markowa jest procesem losowym, który ma właściwość polegającą na tym, że przyszłość zależy tylko od bieżącego stanu procesu, a nie przeszłości, tzn. Jest bez pamięci. Przykładem losowego procesu może być giełda papierów wartościowych. Przykładem łańcucha Markowa może być gra planszowa, taka jak Monopoly lub Snakes and Ladders, w której twoja przyszła pozycja (po rzucie kostką) zależałaby tylko od tego, od czego zacząłeś przed rzutem, a nie od twoich poprzednich pozycji. Podręcznikowym przykładem Łańcucha Markowa jest „spacer pijaka”. Wyobraź sobie kogoś, kto jest pijany i może poruszać się tylko w lewo lub w prawo o jedno tempo. Pijany porusza się w lewo lub w prawo z jednakowym prawdopodobieństwem. Jest to Łańcuch Markowa, w którym przyszłość / pozycja pijaka zależy tylko od tego, gdzie jest obecnie.

Metody Monte Carlo to algorytmy obliczeniowe (po prostu zestawy instrukcji), które losowo pobierają próbki z niektórych badanych procesów. Są sposobem na oszacowanie czegoś, co jest zbyt trudne lub czasochłonne, aby znaleźć deterministycznie. Są one w zasadzie formą komputerowej symulacji jakiegoś procesu matematycznego lub fizycznego. Moniker Monte Carlo pochodzi z analogii między kasynem a generacją liczb losowych. Wracając do naszego przykładu gry planszowej, być może chcemy wiedzieć, czy niektóre nieruchomości na planszy Monopoly są odwiedzane częściej niż inne. Eksperyment w Monte Carlo wymagałby wielokrotnego rzucania kostkami i liczenia liczby wylądowań na każdej nieruchomości. Może być również wykorzystywany do obliczania całek numerycznych. (Bardzo nieformalnie możemy myśleć o całce jako o obszarze pod wykresem pewnej funkcji. ) Integracja Monte Carlo działa doskonale w przypadku funkcji wielowymiarowych, pobierając losową próbkę punktów funkcji i obliczając pewnego rodzaju średnią w tych różnych punktach. Zwiększając wielkość próby, prawo dużych liczb mówi nam, że możemy zwiększyć dokładność naszego przybliżenia, obejmując coraz więcej funkcji.

Te dwie koncepcje można połączyć w celu rozwiązania niektórych trudnych problemów w takich obszarach, jak wnioskowanie bayesowskie, biologia obliczeniowa itp., W których całki wielowymiarowe muszą zostać obliczone w celu rozwiązania typowych problemów. Chodzi o to, aby zbudować Łańcuch Markowa, który zbiega się do pożądanego rozkładu prawdopodobieństwa po kilku krokach. Stan łańcucha po dużej liczbie etapów jest następnie wykorzystywany jako próbka z pożądanego rozkładu, a proces powtarza się. Istnieje wiele różnych algorytmów MCMC, które wykorzystują różne techniki do generowania łańcucha Markowa. Do najczęstszych należą Metropolis-Hastings i Gibbs Sampler.

Fragment z Bayesowskich metod dla hakerów

Krajobraz bayesowski

Kiedy ustawiamy problem wnioskowania bayesowskiego z niewiadomymi, domyślnie tworzymy wymiarową przestrzeń, w której mogą istnieć wcześniejsze rozkłady. Z przestrzenią związany jest dodatkowy wymiar, który możemy opisać jako powierzchnię lub krzywą przestrzeni , co odzwierciedla wcześniejsze prawdopodobieństwo określonego punktu. Powierzchnia przestrzeni jest określona przez nasze wcześniejsze rozkłady. Na przykład, jeśli mamy dwie niewiadome i i oba są równomierne na [0,5], utworzona przestrzeń jest kwadratem o długości 5, a powierzchnia jest płaską płaszczyzną, która leży na szczycie kwadratu (reprezentując ten każdy punkt jest równie prawdopodobne).N p 1 p $N$$N$$p_1$$p_2$

Alternatywnie, jeśli dwa priory to i , wówczas spacja jest liczbą dodatnią na płaszczyźnie 2-D, a powierzchnia wywołana przez priory wygląda jak woda spadek, który zaczyna się w punkcie (0,0) i przepływa przez liczby dodatnie.Exp ( 10 $\text{Exp}(3)$$\text{Exp}(10)$

Poniższa wizualizacja to pokazuje. Im bardziej ciemny czerwony kolor, tym większe prawdopodobieństwo, że nieznane osoby znajdują się w tym miejscu. I odwrotnie, obszary o ciemniejszym błękicie oznaczają, że nasze priorytety przypisują bardzo małe prawdopodobieństwo nieznanym.

Są to proste przykłady w przestrzeni 2D, w których nasz mózg dobrze rozumie powierzchnie. W praktyce przestrzenie i powierzchnie generowane przez naszych przełożonych mogą mieć znacznie większy wymiar.

Jeśli powierzchnie te opisują nasze wcześniejsze dystrybucje na niewiadomych, co dzieje się po naszej przestrzeni zaobserwowaliśmy danych . Dane nie zmieniają przestrzeni, ale zmieniają powierzchnię przestrzeni, ciągnąc i rozciągając tkaninę powierzchni, aby odzwierciedlić tam, gdzie prawdopodobnie żyją prawdziwe parametry. Więcej danych oznacza więcej ciągnięcia i rozciągania, a nasz oryginalny kształt staje się zniekształcony lub nieznaczny w porównaniu do nowo utworzonego kształtu. Mniej danych, a nasz oryginalny kształt jest bardziej obecny. Niezależnie od tego uzyskana powierzchnia opisuje rozkład tylny . Znów muszę podkreślić, że niestety nie jest możliwe zwizualizowanie tego w większych wymiarach. W przypadku dwóch wymiarów dane zasadniczo$X$$X$podnosi oryginalną powierzchnię, tworząc wysokie góry . Wielkość wypychania opiera się wcześniejszemu prawdopodobieństwu, tak że mniejsze wcześniejsze prawdopodobieństwo oznacza większy opór. Tak więc w powyższym przypadku podwójnego wykładniczego wcześniejszego góra (lub wiele gór), która może wybuchnąć w pobliżu (0,0) rogu, byłaby znacznie wyższa niż góry, które wybuchną bliżej (5,5), ponieważ w pobliżu występuje większy opór (5,5). Góra, a może bardziej ogólnie, pasma górskie, odzwierciedlają prawdopodobieństwo prawdopodobieństwa znalezienia prawdziwych parametrów.

Załóżmy, że wymienione wyżej priory reprezentują różne parametry dwóch rozkładów Poissona. Obserwujemy kilka punktów danych i wizualizujemy nowy krajobraz.$\lambda$

Wykres po lewej to zdeformowany krajobraz z priorysem , a wykres po prawej to zdeformowany krajobraz z wykładniczym wykładnikiem. Tylne krajobrazy wyglądają inaczej. Krajobraz z pierwszeństwem wykładniczym kładzie bardzo mały nacisk na wartości tylne w prawym górnym rogu: dzieje się tak, ponieważ przeor nie kładzie tam dużego ciężaru , podczas gdy krajobraz z uprzednim mundurem z przyjemnością kładzie tam ciężar tylny. Również najwyższy punkt, odpowiadający najciemniejszej czerwieni, jest odchylany w kierunku (0,0) w przypadku wykładniczym, co jest wynikiem wykładniczego wcześniejszego umieszczenia większej wcześniejszej wiarytht w rogu (0,0).$\text{Uniform}(0,5)$

Czarna kropka reprezentuje prawdziwe parametry. Nawet z 1 punktem próbnym, jak symulowano powyżej, góry próbują zawrzeć prawdziwy parametr. Oczywiście wnioskowanie o wielkości próbki 1 jest niezwykle naiwne, a wybór tak małej wielkości próbki był jedynie ilustracyjny.

Odkrywanie krajobrazu za pomocą MCMC

Powinniśmy zbadać zdeformowaną przestrzeń tylną wygenerowaną przez naszą poprzednią powierzchnię i obserwowane dane, aby znaleźć tylne pasma górskie. Nie możemy jednak naiwnie przeszukiwać przestrzeni: każdy informatyk powie ci, że przemierzanie wymiarowej przestrzeni jest wykładniczo trudne w : wielkość przestrzeni szybko rośnie, gdy zwiększamy (patrz przekleństwo wymiarowości ). Jaką mamy nadzieję znaleźć te ukryte góry? Ideą MCMC jest inteligentne przeszukiwanie przestrzeni. Powiedzieć „szukaj” oznacza, że ​​szukamy konkretnego obiektu, co być może nie jest dokładnym opisem tego, co robi MCMC. Przypomnij: MCMC zwraca próbkiN $N$$N$$N$z rozkładu tylnego, a nie z samego rozkładu. Rozciągając naszą górską analogię do granic możliwości, MCMC wykonuje zadanie podobne do wielokrotnego zadawania pytania: „Jak prawdopodobny jest ten kamyk z góry, której szukam?” I wykonuje swoje zadanie, zwracając tysiące zaakceptowanych kamyków w nadziei na odtworzenie oryginalna góra. W żargonie MCMC i PyMC zwracaną sekwencją „kamyków” są próbki, częściej nazywane śladami .

Kiedy mówię MCMC inteligentnie wyszukuje, to znaczy MCMC będzie nadzieją zbiegają się w kierunku obszarów o wysokim prawdopodobieństwem a posteriori. MCMC robi to, badając pobliskie pozycje i poruszając się w obszarach o większym prawdopodobieństwie. Ponownie, być może „zbieżność” nie jest dokładnym określeniem postępu MCMC. Konwergencja zwykle oznacza przejście w kierunku punktu w przestrzeni, ale MCMC przesuwa się w kierunku szerszego obszaru w przestrzeni i losowo chodzi po tym obszarze, zbierając próbki z tego obszaru.

Początkowo zwracanie użytkownikowi tysięcy próbek może wydawać się nieefektywnym sposobem opisu rozkładów bocznych. Twierdziłbym, że jest to niezwykle wydajne. Rozważ alternatywne możliwości:

1. Zwrócenie wzoru matematycznego dla „pasm górskich” wymagałoby opisu powierzchni N-wymiarowej z dowolnymi szczytami i dolinami.
2. Zwrócenie „szczytu” krajobrazu, choć możliwe z matematycznego punktu widzenia i sensowne, ponieważ najwyższy punkt odpowiada najbardziej prawdopodobnemu oszacowaniu niewiadomych, ignoruje kształt krajobrazu, który, jak wcześniej argumentowaliśmy, jest bardzo ważny przy określaniu pewności tylnej w niewiadomych.

Oprócz powodów obliczeniowych, prawdopodobnie najsilniejszym powodem zwracania próbek jest to, że możemy z łatwością użyć Prawa Dużych Liczb, aby rozwiązać problemy, które byłyby trudne do rozwiązania. Odkładam tę dyskusję na następny rozdział.

Algorytmy do wykonywania MCMC

Istnieje duża rodzina algorytmów wykonujących MCMC. Mówiąc najprościej, większość algorytmów można wyrazić na wysokim poziomie w następujący sposób:

1. Start at current position.
2. Propose moving to a new position (investigate a pebble near you ).
3. Accept the position based on the position's adherence to the data 
and prior distributions (ask if the pebble likely came from the mountain).
4. If you accept: Move to the new position. Return to Step 1.
5. After a large number of iterations, return the positions.

W ten sposób poruszamy się w ogólnym kierunku w kierunku regionów, w których istnieją rozkłady tylne i oszczędnie pobieramy próbki podczas podróży. Po osiągnięciu rozkładu tylnego możemy łatwo pobrać próbki, ponieważ prawdopodobnie wszystkie należą do rozkładu tylnego.

Jeśli bieżąca pozycja algorytmu MCMC znajduje się w obszarze o bardzo niskim prawdopodobieństwie, co często ma miejsce w momencie rozpoczęcia algorytmu (zazwyczaj w przypadkowej lokalizacji w przestrzeni), algorytm będzie się przemieszczał w pozycjach , które prawdopodobnie nie są z tyłu ale lepsze niż wszystko inne w pobliżu. Zatem pierwsze ruchy algorytmu nie odzwierciedlają tylnej części.

Istnieje więc wiele odpowiedzi sparafrazowanych ze statystyk / podręczników prawdopodobieństwa, Wikipedii itp. Uważam, że mamy „laików”, w których pracuję; Myślę, że są w dziale marketingu. Jeśli kiedykolwiek muszę im wyjaśnić coś technicznego, stosuję zasadę „pokaż, nie mów”. Mając to na uwadze, prawdopodobnie pokazałbym im coś takiego.

Chodzi o to, aby spróbować zakodować algorytm, którego mogę nauczyć się przeliterować - nie ucząc się wszystkich setek (tysięcy?) Reguł, takich jak dodając końcówkę do słowa kończącego się cichym e, upuść końcowe e jeśli zakończenie zaczyna się samogłoską . Jednym z powodów, dla których to nie zadziała, jest to, że nie znam tych zasad (nie jestem nawet pewien, czy ten, który właśnie wyrecytowałem, jest poprawny). Zamiast tego nauczę go literować, pokazując mu kilka poprawnie napisanych słów i pozwalając mu wyodrębnić reguły z tych słów, co jest mniej więcej istotą uczenia maszynowego, niezależnie od algorytmu - ekstrakcja wzorca i rozpoznawanie wzorca .

Kryterium sukcesu jest poprawna pisownia słowa, którego algorytm nigdy wcześniej nie widział (zdaję sobie sprawę, że może się to zdarzyć przypadkiem, ale nie przydarzy się to marketingowcom, więc zignoruję - plus będę miał algorytm spróbuj przeliterować nie jedno słowo, ale dużo, więc nie jest prawdopodobne, że nas zwiedzie kilka szczęśliwych domysłów).

Mniej więcej godzinę temu pobrałem (jako zwykły plik tekstowy) z doskonałej witryny Project Gutenberg, powieści Hermana Hessego Siddhartha . Użyję słów z tej powieści, by nauczyć algorytmu pisowni.

Więc kodowałem poniższy algorytm, który skanował tę powieść, trzy litery na raz (każde słowo ma jeden dodatkowy znak na końcu, którym jest „biała spacja” lub koniec słowa). Trzyliterowe sekwencje mogą wiele powiedzieć - na przykład po literze „q” prawie zawsze następuje „u”; sekwencja „ty” zwykle występuje na końcu słowa; z rzadko to robi i tak dalej. (Uwaga: równie łatwo mógłbym podać mu całe słowa, aby wyszkolić go do mówienia pełnymi zdaniami - dokładnie ten sam pomysł, tylko kilka poprawek do kodu).

Nie dotyczy to jednak MCMC, co dzieje się po treningu, gdy algorytmowi podajemy kilka losowych liter (jako zarodek) i zaczyna on tworzyć „słowa”. Jak algorytm buduje słowa? Wyobraź sobie, że ma blok „qua”; jaki list dodaje dalej? Podczas szkolenia algorytm skonstruował ogromną matrycę częstotliwości * eterów z wszystkich tysięcy słów w powieści. Gdzieś w tej macierzy jest trzyliterowy blok „qua” i częstotliwości dla znaków, które mogą podążać za sekwencją. Algorytm wybiera literę na podstawie częstotliwości, które mogłyby za nią podążać. Zatem litera wybierana przez algorytm zależy od - i wyłącznie od - ostatnich trzech w kolejce konstruowania słów.

To jest algorytm Monte Carlo Markov Chain.

Myślę, że najlepszym sposobem zilustrowania tego, jak to działa, jest pokazanie wyników w oparciu o różne poziomy szkolenia. Poziom szkolenia jest zróżnicowany przez zmianę liczby przebiegów, które algorytm sprawia, że ​​powieść - im więcej przejść, tym większa wierność macierzy częstotliwości sekwencji liter. Poniżej znajdują się wyniki - w postaci 100-znakowych ciągów wyprowadzanych przez algorytm - po szkoleniu na temat nowatorskiej „Siddharta”.

Jedno przejście przez powieść Siddhartha :

wtedy krzyczy ger wiff wszystkie mothany stoją czy żyjesz tępy ponury posąg bojąc się jego biblii jego

(Od razu nauczyłem się mówić prawie idealnie walijskim; nie spodziewałem się tego.)

Po dwóch przejściach powieści:

The acor wor prenskinith show was not twor se not not theady theatin land rhatingle był tam

Po 10 przejściach:

mimo, że powinna modlić się z Aka teraz mieć wodę, jej pies dźwiga ból stóp, każdy nie słabe wspomnienie

A oto kod (w Pythonie jestem prawie pewien, że można to zrobić w R przy użyciu pakietu MCMC, którego jest kilka, w zaledwie 3-4 liniach)

def create_words_string(raw_string) :
  """ in case I wanted to use training data in sentence/paragraph form; 
      this function will parse a raw text string into a nice list of words;
      filtering: keep only words having  more than 3 letters and remove 
      punctuation, etc.
  """
  pattern = r'\b[A-Za-z]{3,}\b'
  pat_obj = re.compile(pattern)
  words = [ word.lower() for word in pat_obj.findall(raw_string) ]
  pattern = r'\b[vixlm]+\b'
  pat_obj = re.compile(pattern)
  return " ".join([ word for word in words if not pat_obj.search(word) ])

def create_markov_dict(words_string):
  # initialize variables
  wb1, wb2, wb3 = " ", " ", " "
  l1, l2, l3 = wb1, wb2, wb3
  dx = {}
  for ch in words_string :
    dx.setdefault( (l1, l2, l3), [] ).append(ch)
    l1, l2, l3 = l2, l3, ch
  return dx

def generate_newtext(markov_dict) :
  simulated_text = ""
  l1, l2, l3 = " ", " ", " "
  for c in range(100) :
    next_letter = sample( markov_dict[(l1, l2, l3)], 1)[0]
    simulated_text += next_letter
    l1, l2, l3 = l2, l3, next_letter
  return simulated_text

if __name__=="__main__" :
  # n = number of passes through the training text
  n = 1
  q1 = create_words_string(n * raw_str)
  q2 = create_markov_dict(q1)
  q3 = generate_newtext(q2)
  print(q3)

MCMC jest zwykle stosowana jako alternatywa dla surowych technik symulacji Monte Carlo. Zarówno MCMC, jak i inne techniki Monte Carlo są używane do oceny trudnych całek, ale MCMC można stosować bardziej ogólnie.

Na przykład częstym problemem w statystyce jest obliczanie średniego wyniku związanego z pewnym modelem probabilistycznym / stochastycznym. Zarówno techniki MCMC, jak i Monte Carlo rozwiązałyby ten problem, generując sekwencję symulowanych wyników, które moglibyśmy wykorzystać do oszacowania prawdziwej średniej.

Zarówno MCMC, jak i surowe techniki Monte Carlo działają, ponieważ długoterminowa proporcja symulacji, które są równe danemu wynikowi, będzie równa * modelowanemu prawdopodobieństwu tego wyniku. Dlatego, generując wystarczającą liczbę symulacji, wyniki uzyskane obiema metodami będą dokładne.

* Mówię równy, chociaż ogólnie powinienem mówić o mierzalnych zestawach. Jednak laik prawdopodobnie nie byłby tym zainteresowany *

Jednak podczas gdy surowy Monte Carlo wymaga wytworzenia wielu niezależnych symulacji, z których każda jest dystrybuowana zgodnie z modelowanym rozkładem, MCMC obejmuje generowanie losowego spaceru, który w długim okresie „odwiedza” każdy wynik z pożądaną częstotliwością.

Sztuczka dla MCMC polega zatem na wybraniu losowego marszu, który „odwiedzi” każdy wynik z pożądanymi częstotliwościami długofalowymi.

Prostym przykładem może być symulacja z modelu, który mówi, że prawdopodobieństwo wyniku „A” wynosi 0,5, a wyniku „B” 0,5. W takim przypadku, jeśli rozpocznę losowy spacer w pozycji „A” i zalecę, że na każdym kroku przełącza się on na inną pozycję z prawdopodobieństwem 0,2 (lub innym prawdopodobieństwem większym niż 0), mógłbym być pewien, że po dużym liczba kroków, które losowy spacer odwiedziłby każdy z „A” i „B” w około 50% kroków - zgodnie z prawdopodobieństwami określonymi przez nasz model.

To oczywiście bardzo nudny przykład. Okazuje się jednak, że MCMC często ma zastosowanie w sytuacjach, w których trudno jest zastosować standardowe Monte Carlo lub inne techniki.

Możesz znaleźć artykuł, który opisuje podstawy tego, co to jest i dlaczego działa tutaj:

http://wellredd.uk/basics-markov-chain-monte-carlo/

Jestem analitykiem DNA, który używa w pełni ciągłego probabilistycznego oprogramowania do genotypowania do interpretowania dowodów DNA i muszę wyjaśnić, jak to działa przed ławą przysięgłych. Trzeba przyznać, że upraszczamy i zdaję sobie sprawę, że niektóre z tych uproszczeń poświęcają dokładność określonych szczegółów w imię poprawy ogólnego zrozumienia. Ale w kontekście jury, które rozumie, jak ten proces jest wykorzystywany w interpretacji DNA bez stopni naukowych i wieloletniego doświadczenia zawodowego, dostają sedno :)

Tło: Oprogramowanie wykorzystuje metropolię Hastings MCMC i model biologiczny, który naśladuje znane zachowanie profili DNA (model jest zbudowany na podstawie danych walidacyjnych wygenerowanych przez laboratorium analizujące wiele profili DNA ze znanych warunków reprezentujących zakres napotkany w nieznanej pracy). Istnieje 8 niezależnych łańcuchów i oceniamy zbieżność, aby ustalić, czy uruchomić ponownie, zwiększając wypalenie i po zaakceptowaniu (domyślne spalanie 100k przyjmuje i po 400k przyjmuje)

Zapytany przez prokuraturę / obronę o MCMC: wyjaśniamy, że oznacza łańcuch Markowa Monte Carlo i reprezentuje specjalną klasę / rodzaj algorytmu wykorzystywanego do kompleksowego rozwiązywania problemów oraz że algorytm jest tylko wymyślnym słowem odnoszącym się do serii procedur lub rutyny przeprowadzone przez komputer ... Algorytmy MCMC działają, proponując rozwiązanie, symulując to rozwiązanie, a następnie oceniając, jak dobrze ta symulacja odzwierciedla rzeczywiste obserwowane dane dowodowe ... symulacja, która dobrze pasuje do obserwacji dowodów ma większe prawdopodobieństwo niż symulacja, która nie pasuje dobrze do obserwacji ... w wielu powtarzanych próbkach / domysłach proponowanych rozwiązań, łańcuchy Markowa odchodzą od rozwiązań o niskim prawdopodobieństwie w kierunku rozwiązań o wysokim prawdopodobieństwie, które lepiej pasują / wyjaśniają obserwowany profil dowodów, aż w końcu równowaga jest osiągniętyco oznacza, że ​​algorytm ma ograniczoną możliwość próbkowania nowych propozycji, co znacznie zwiększa prawdopodobieństwo

Zapytany o metropolię Hastings: wyjaśniamy, że jest to ulepszenie algorytmu MCMC opisującego proces decyzyjny przyjmujący lub odrzucający propozycję ... zwykle jest to wyjaśnione przez analogię do gry dla dzieci „na ciepło / zimno”, ale mogłem rozważyć użycie „ przesuń w prawo lub w lewo ”, gdy jury jest szczególnie młode !! : p Ale korzystając z naszej analogii gorący / zimny, zawsze akceptujemy zgadywanie na gorąco i od czasu do czasu akceptujemy zgadywanie na zimno przez ułamek czasu i wyjaśniamy, że celem czasami akceptowania zgadywania na zimno jest zapewnienie próbkom łańcuchów szerszego zakresu możliwości, ponieważ w przeciwieństwie do utknięcia wokół konkretnej propozycji przed faktyczną równowagą

Edytowane w celu dodania / wyjaśnienia: za pomocą analogii gorące / zimne wyjaśniamy, że w grze dla dzieci lider wybiera docelowy obiekt / obszar w pokoju, a gracze na zmianę zgadują, w którym kierunku poruszać się w stosunku do ich obecnej pozycji / pozycji. Lider mówi im, aby zmienili pozycję / wykonali ruch, jeśli jest to zgadywanka, a stracą swoją turę / pozostaną w pozycji, jeśli jest to zgadywanka. Podobnie w naszym oprogramowaniu decyzja o przeniesieniu / przyjęciu zależy tylko od prawdopodobieństwa propozycji w porównaniu z prawdopodobieństwem aktualnie zajmowanej pozycji ... JEDNAK cel jest wstępnie określony / znany przez lidera w grze dla dzieci, podczas gdy cel w naszym oprogramowaniu nie jest wstępnie zdefiniowany - jest całkowicie nieznany (również dlaczego „

Tak jak powiedziałem, bardzo super podstawowy i absolutnie pozbawiony szczegółów technicznych w celu poprawy zrozumienia - staramy się wyjaśniać na poziomie edukacji w gimnazjum. Zapraszam do sugestii. Włączę je.

To pytanie jest szerokie, ale odpowiedzi są często dość przypadkowe. Alternatywnie możesz przeczytać ten artykuł, który zawiera zwięzły opis matematyczny szerokiej klasy algorytmów MCMC, w tym algorytmów Metropolis-Hastings, próbkowania Gibbs, Metropolis wewnątrz Gibbs i metod zmiennych pomocniczych, próbkowania plastra, propozycji rekurencyjnych, próbkowania kierunkowego, Langevina i Hamiltonian Monte Carlo, próbkowanie NUTS, pseudo-marginalne algorytmy Metropolis-Hastings oraz pseudo-marginalny Hamiltonian Monte Carlo, jak omówili autorzy.

Wiarygodna recenzja znajduje się tutaj

Znajdę więcej czasu na opracowanie jego zawartości w formacie stackexchange.

Po pierwsze, powinniśmy wyjaśnić laikowi pobieranie próbek z Monte-Carlo. Wyobraź sobie, że nie masz dokładnej postaci funkcji (na przykład ), ale w Europie istnieje maszyna (i Los Alamos), która się replikuje ta funkcja (numerycznie). Możemy włożyć do niego tyle par , co da nam wartość z. To numeryczne powtórzenie jest próbkowaniem, a ten proces jest symulacją Monte-Carlo . Po 10000 iteracjach prawie wiemy, co to jest funkcja . $f(x,y)=z=x^2+2*x*y$$(x,y)$$f(x,y)$$f(x,y)$

Zakładając, że laik zna Monte-Carlo, w MCMC nie chcesz marnować wysiłku / czasu procesora podczas próbkowania z przestrzeni wielowymiarowej , podobnie jak standardowe próbkowanie Monte-Carlo. Kluczową różnicą jest to, że w MCMC musisz mieć łańcuch Markowa jako mapę, która poprowadzi twoje wysiłki.$f(x,y,z,t,s,...,zzz)$

Ten film (od 5:50) ma bardzo dobrą intuicję.

Wyobraź sobie, że chcesz próbkować punkty znajdujące się na zielonych (wielowymiarowych) gałęziach na tym obrazie. Jeśli rzucasz punktami w czarną superprzestrzeń i sprawdzasz ich wartość, marnujesz dużo energii próbkowania (wyszukiwania). Bardziej sensowne byłoby więc kontrolowanie strategii próbkowania (którą można zautomatyzować), aby wybierać punkty bliżej zielonych gałęzi (tam, gdzie ma to znaczenie). Zielone gałęzie można znaleźć, trafiając je przypadkowo (lub kontrolowane), a reszta wysiłku próbkowania (czerwone punkty) zostanie wygenerowana później. Powodem przyciągania czerwieni do zielonej linii jest matryca przejścia łańcucha Markowa, która działa jako silnik próbkowania.

Mówiąc w skrócie, MCMC jest energooszczędną (niskokosztową) metodą próbkowania, szczególnie podczas pracy w ogromnej i „ciemnej” (wielowymiarowej) przestrzeni.