Nie jestem w stanie zrozumieć, jak działa Thompson Sampling . Czytałem o Multi Arm Bandit i po przeczytaniu algorytmu Upper Confidence Bound Algorytm wiele tekstów sugerowało, że próbkowanie Thompsona działa lepiej niż UCB. Co to jest próbkowanie Thompsona, w laika lub po prostu?
Zapraszam do dostarczenia artykułów referencyjnych w celu dalszego zrozumienia.
Odpowiedzi:
Spróbuję wyjaśnić bez matematyki. Część tej odpowiedzi została powtórzona z niektórych punktów, które przedstawiłem w odpowiedzi na inne pytanie dotyczące problemów MAB .
Kompromis strategiczne problemy bandyckich wieloramienne: W problemach bandyckich wieloramienne hazardzista gra jedną „bandytów” każdej rundy oraz prób, aby zmaksymalizować jego całkowitego oczekiwanego zwrotu w ciągu określonej liczby rund. Oczekiwany zwrot każdego z bandytów jest opisany przez niektóre nieznane parametry w problemie, a więc gdy obserwujemy więcej wyników w każdej rundzie, otrzymujemy więcej informacji o tych nieznanych parametrach, a zatem o oczekiwanym zwrocie każdego z bandytów . W każdej rundzie gry (oprócz ostatniej) problem MAB wiąże się ze strategicznym kompromisem gracza między dwoma celami:
Nagrody natychmiastowe: W każdej rundzie chciałby wybrać dystrybucję, która zapewni mu wysoką oczekiwaną nagrodę w tej rundzie, co pociąga za sobą preferencje dla dystrybucji, które (obecnie) proponuje, aby otrzymać wysoką średnią nagrodę;
Przyszłe nagrody (zależne od zdobywania informacji): Z drugiej strony chce udoskonalić swoją wiedzę o prawdziwych oczekiwanych nagrodach, zdobywając więcej informacji na temat dystrybucji (szczególnie tych, w które nie grał tak często jak inni), aby mógł poprawić swoje wybory w przyszłych rundach.
Względne znaczenie tych dwóch rzeczy determinuje kompromis, a na to względne znaczenie ma wpływ wiele czynników. Na przykład, jeśli w problemie pozostała tylko niewielka liczba rund, wnioskowanie dla przyszłych prób jest względnie mniej cenne, podczas gdy jeśli jest duża liczba pozostałych rund, wnioskowanie o przyszłe nagrody jest relatywnie bardziej wartościowe. Gracz musi więc zastanowić się, na ile chce się skoncentrować na maksymalizacji natychmiastowych nagród w bieżącej rundzie i na ile chce się od tego odstąpić, aby dowiedzieć się więcej o nieznanych parametrach, które określają oczekiwaną nagrodę każdego z bandytów.
Próbkowanie Thompsona: podstawową ideą próbkowania Thompsona jest to, że w każdej rundzie bierzemy naszą obecną wiedzę na temat maszyn, która ma postać późniejszego przekonania o nieznanych parametrach i „próbkujemy” parametry z tego rozkładu tylnego. Ten próbkowany parametr daje zestaw oczekiwanych nagród dla każdej maszyny, a teraz stawiamy na tę, która ma najwyższy oczekiwany zwrot, pod tym próbkowanym parametrem.
Na pierwszy rzut oka schemat próbkowania Thompsona wydaje się obejmować próbę maksymalizacji natychmiastowego oczekiwanego zwrotu w każdej rundzie (ponieważ obejmuje on ten krok maksymalizacji po próbkowaniu parametru). Ponieważ jednak wiąże się to z losowym próbkowaniem parametru z tyłu, schemat obejmuje niejawneodmiana maksymalizacji obecnej nagrody, w porównaniu do szukania dodatkowych informacji. Przez większość czasu otrzymamy parametr „próbka”, który znajduje się gdzieś w głównej części tylnej części ciała, a wybór maszyny z grubsza przybliża maksymalizację natychmiastowej nagrody. Czasami jednak losowo próbkujemy wartość parametru, która jest daleko w ogonach rozkładu bocznego, i w takim przypadku ostatecznie wybieramy maszynę, która nie maksymalizuje natychmiastowej nagrody - tj. Będzie to bardziej „wyszukiwanie” „aby pomóc w przyszłych nagrodach.
Schemat Thompsona ma również tę przyjemną właściwość, że zmniejszamy nasze „wyszukiwanie”, gdy otrzymujemy więcej informacji, a to naśladuje pożądany kompromis strategiczny w problemie, w którym chcemy skupić się mniej na wyszukiwaniu, gdy uzyskujemy więcej informacji. W miarę, jak gramy coraz więcej rund i zdobywamy coraz więcej danych, a posterior zbiega się bliżej prawdziwych wartości parametrów, a zatem losowe „próbkowanie” w schemacie Thompsona staje się ściślejsze wokół wartości parametrów, co doprowadzi do maksymalizacji natychmiastowa nagroda. W związku z tym istnieje domyślna tendencja do tego, aby ten program był bardziej „zorientowany na wyszukiwanie” wcześnie z niewielką ilością informacji, a mniej „zorientowany na wyszukiwanie” później, gdy jest dużo danych.
Teraz, powiedziawszy to, jedną wyraźną wadą schematu próbkowania Thompsona jest to, że nie bierze on pod uwagę liczby rund pozostałych w problemie MAB. Ten schemat jest czasem formułowany na podstawie gry z nieskończonymi rundami, w tym przypadku nie stanowi to problemu. Jednak w przypadku problemów MAB ze skończonymi rundami lepiej jest wziąć pod uwagę liczbę pozostałych rund, aby zmniejszyć „wyszukiwanie” wraz ze spadkiem liczby przyszłych rund. (A w szczególności, optymalną grą w ostatniej rundzie jest całkowite zignorowanie wyszukiwań i po prostu postawienie na bandyty z najwyższym oczekiwanym zwrotem z tyłu.) Schemat Thompsona tego nie robi, więc będzie w pewien sposób grać w gry o skończonej rundzie w niektórych przypadkach jest to wyraźnie nieoptymalne.
Spróbuję i mam nadzieję, że ci się spodoba! Istnieje kilka wzorów, które mogą Cię wystraszyć. Nie mam takiej nadziei, ponieważ dołożę wszelkich starań, aby wyjaśnić je w najprostszy możliwy sposób.
Są to dwie formuły:
TL; DR
Thompson Sampling pozwala
Prawdopodobieństwo??
Co z tym dziwnym kręgiem?
, wiesz, jak kontekst + działania odnoszą się do nagrody, i łatwo jest działać optymalnie.
Jak więc poznać te parametry modelu, aby uzyskać maksymalną nagrodę?
Nie powiedziałeś nic o tym późniejszym
Co sugeruje Thomson Sampling w związku z tymi wszystkimi niepewnościami?
Próbkowanie Thomsona sugeruje coś bardzo prostego: wystarczy wybrać losowy parametr modelu z tylnej części ciała, podjąć działanie i obserwować, co się stanie. Na przykład, jeśli nigdy wcześniej nie byłeś na zewnątrz, parametr nieszczęścia przy deszczu na głowie może być dowolny. Więc wybieramy jeden, zakładamy, że jesteśmy naprawdę niezadowoleni, gdy deszcz pada na naszą głowę. Widzimy, że pada deszcz (kontekst), więc podejmujemy parasol (działanie), ponieważ nasz parametr modelu mówi nam, że w ten sposób możemy uzyskać maksymalną nagrodę. Rzeczywiście, zauważasz, że jesteś trochę zrzędliwy, chodząc w deszczu z parasolem, ale nie bardzo niezadowolony. Dowiadujemy się z tego, że deszcz + parasol jest zrzędliwy. Następnym razem, gdy pada deszcz, ponownie wybierasz przypadkowe przekonanie o tym, co dzieje się, gdy deszcz pada na twoją głowę. Tym razem może to wcale nie przeszkadzać. Jednak, gdy jesteś już w połowie drogi do celu, załamujesz się i dowiadujesz się, że deszcz bez parasola jest naprawdę zły. Zmniejsza to twoją niepewność związaną z nieszczęściem podczas deszczu na głowie, ponieważ teraz wiesz, że jest ona prawdopodobnie wysoka.
To brzmi tak prosto !!
Tak, to nie jest takie skomplikowane. Trudną częścią jest pobieranie próbek z parametru modelu z tyłu. Uzyskiwanie i utrzymywanie rozkładu wszystkich parametrów modelu, który jest również odpowiedni dla konkretnego problemu, jest trudne. Ale ... to zdecydowanie wykonalne :).