Maksymalizacja oczekiwań (EM) jest rodzajem probabilistycznej metody klasyfikacji danych. Proszę poprawić mnie, jeśli się mylę, jeśli nie jest to klasyfikator.
Jakie jest intuicyjne wyjaśnienie tej techniki EM? Co expectation
tu jest i co się dzieje maximized
?
machine-learning
cluster-analysis
data-mining
mathematical-optimization
expectation-maximization
Facet z Londynu
źródło
źródło
Odpowiedzi:
Uwaga: kod odpowiadający za tę odpowiedź można znaleźć tutaj .
Załóżmy, że mamy pewne dane pobrane z dwóch różnych grup, czerwonej i niebieskiej:
Tutaj możemy zobaczyć, który punkt danych należy do grupy czerwonej lub niebieskiej. Ułatwia to znalezienie parametrów charakteryzujących każdą grupę. Na przykład, średnia grupy czerwonej wynosi około 3, średnia grupy niebieskiej wynosi około 7 (i moglibyśmy znaleźć dokładną średnią, gdybyśmy chcieli).
Jest to ogólnie znane jako oszacowanie maksymalnego prawdopodobieństwa . Biorąc pod uwagę pewne dane, obliczamy wartość parametru (lub parametrów), który najlepiej wyjaśnia te dane.
Teraz wyobraź sobie, że nie możemy zobaczyć, która wartość była próbkowana z której grupy. Dla nas wszystko wygląda na fioletowe:
Tutaj wiemy, że istnieją dwie grupy wartości, ale nie wiemy, do której grupy należy dana wartość.
Czy nadal możemy oszacować średnie dla grupy czerwonej i niebieskiej, które najlepiej pasują do tych danych?
Tak, często możemy! Maksymalizacja oczekiwań daje nam na to sposób. Bardzo ogólna idea algorytmu jest taka:
Te kroki wymagają dalszych wyjaśnień, więc omówię problem opisany powyżej.
Przykład: szacowanie średniej i odchylenia standardowego
W tym przykładzie użyję Pythona, ale kod powinien być dość łatwy do zrozumienia, jeśli nie znasz tego języka.
Załóżmy, że mamy dwie grupy, czerwoną i niebieską, z wartościami rozłożonymi jak na powyższym obrazku. W szczególności każda grupa zawiera wartość pobraną z rozkładu normalnego z następującymi parametrami:
Oto ponownie obraz tych czerwonych i niebieskich grup (aby uniknąć konieczności przewijania w górę):
Kiedy widzimy kolor każdego punktu (tj. Do której grupy należy), bardzo łatwo jest oszacować średnią i odchylenie standardowe dla każdej grupy. Po prostu przekazujemy wartości czerwony i niebieski do funkcji wbudowanych w NumPy. Na przykład:
Ale co, jeśli nie widzimy kolorów punktów? Oznacza to, że zamiast czerwonego lub niebieskiego każdy punkt został pokolorowany na fioletowo.
Aby spróbować odzyskać średnią i parametry odchylenia standardowego dla grup czerwonych i niebieskich, możemy użyć maksymalizacji oczekiwań.
Naszym pierwszym krokiem ( krok 1 powyżej) jest odgadnięcie wartości parametrów dla średniej i odchylenia standardowego każdej grupy. Nie musimy inteligentnie zgadywać; możemy wybrać dowolne liczby:
Te oszacowania parametrów dają krzywe dzwonowe, które wyglądają następująco:
To są złe szacunki. Oba środki (pionowe przerywane linie) wyglądają na daleko od wszelkiego rodzaju „środka”, na przykład w przypadku rozsądnych grup punktów. Chcemy poprawić te szacunki.
Następnym krokiem ( krok 2 ) jest obliczenie prawdopodobieństwa pojawienia się każdego punktu danych pod bieżącymi domysłami parametrów:
Tutaj po prostu umieściliśmy każdy punkt danych w funkcji gęstości prawdopodobieństwa dla rozkładu normalnego, używając naszych aktualnych przypuszczeń na temat średniej i odchylenia standardowego dla czerwieni i niebieskiego. To mówi nam na przykład, że przy naszych aktualnych domysłach punkt danych przy 1,761 jest znacznie bardziej prawdopodobny, że będzie czerwony (0,189) niż niebieski (0,00003).
Dla każdego punktu danych możemy zamienić te dwie wartości prawdopodobieństwa na wagi ( krok 3 ), aby sumowały się do 1 w następujący sposób:
Dzięki naszym bieżącym szacunkom i nowo obliczonym wagom możemy teraz obliczyć nowe oszacowania średniej i odchylenia standardowego grup czerwonych i niebieskich ( krok 4 ).
Dwukrotnie obliczamy średnią i odchylenie standardowe przy użyciu wszystkich punktów danych, ale z różnymi wagami: raz dla wag czerwonych i raz dla wag niebieskich.
Kluczową intuicją jest to, że im większa waga koloru w punkcie danych, tym bardziej punkt danych wpływa na następne oszacowania parametrów tego koloru. Powoduje to „ciągnięcie” parametrów we właściwym kierunku.
Mamy nowe szacunki parametrów. Aby je ponownie ulepszyć, możemy wrócić do kroku 2 i powtórzyć proces. Robimy to do osiągnięcia zbieżności szacunków lub po wykonaniu pewnej liczby iteracji ( krok 5 ).
W przypadku naszych danych pierwsze pięć iteracji tego procesu wygląda następująco (ostatnie iteracje mają silniejszy wygląd):
Widzimy, że średnie już zbiegają się na niektórych wartościach, a kształty krzywych (regulowane odchyleniem standardowym) również stają się bardziej stabilne.
Jeśli będziemy kontynuować przez 20 iteracji, otrzymamy co następuje:
Proces EM zbiegał się do następujących wartości, które okazują się bardzo zbliżone do rzeczywistych wartości (gdzie widzimy kolory - brak ukrytych zmiennych):
W powyższym kodzie mogłeś zauważyć, że nowe oszacowanie odchylenia standardowego zostało obliczone przy użyciu oszacowania średniej z poprzedniej iteracji. Ostatecznie nie ma znaczenia, czy najpierw obliczymy nową wartość dla średniej, ponieważ właśnie znajdujemy (ważoną) wariancję wartości wokół jakiegoś centralnego punktu. Nadal będziemy widzieć zbieżność szacunków parametrów.
źródło
EM to algorytm maksymalizacji funkcji wiarygodności, gdy niektóre zmienne w twoim modelu są niezauważone (np. Gdy masz zmienne latentne).
Możesz uczciwie zapytać, jeśli po prostu próbujemy zmaksymalizować funkcję, dlaczego nie wykorzystamy po prostu istniejącej maszyny do maksymalizacji funkcji. Cóż, jeśli spróbujesz to zmaksymalizować, biorąc pochodne i ustawiając je na zero, okaże się, że w wielu przypadkach warunki pierwszego rzędu nie mają rozwiązania. Istnieje problem typu kura i jajko, aby rozwiązać parametry modelu, musisz znać dystrybucję nieobserwowanych danych; ale rozkład twoich nieobserwowanych danych jest funkcją parametrów twojego modelu.
EM próbuje obejść ten problem poprzez iteracyjne odgadywanie rozkładu nieobserwowanych danych, a następnie szacowanie parametrów modelu poprzez maksymalizację czegoś, co jest dolną granicą rzeczywistej funkcji wiarygodności i powtarzanie aż do zbieżności:
Algorytm EM
Zacznij od odgadnięcia wartości parametrów modelu
E-krok: dla każdego punktu danych, który ma brakujące wartości, użyj równania modelu, aby znaleźć rozkład brakujących danych, biorąc pod uwagę aktualne przypuszczenie parametrów modelu i dane obserwowane (zwróć uwagę, że rozwiązujesz rozkład dla każdego brakującego wartość, a nie wartość oczekiwana). Teraz, gdy mamy rozkład dla każdej brakującej wartości, możemy obliczyć oczekiwanie funkcji wiarygodności w odniesieniu do nieobserwowanych zmiennych. Jeśli nasze przypuszczenie dla parametru modelu było poprawne, to oczekiwane prawdopodobieństwo będzie rzeczywistym prawdopodobieństwem zaobserwowanych przez nas danych; jeśli parametry nie były prawidłowe, będzie to tylko dolna granica.
M-step: Teraz, gdy mamy oczekiwaną funkcję prawdopodobieństwa bez nieobserwowanych zmiennych, zmaksymalizuj funkcję tak, jak w przypadku w pełni obserwowanego, aby uzyskać nowe oszacowanie parametrów modelu.
Powtarzaj do zbieżności.
źródło
Oto prosty przepis na zrozumienie algorytmu maksymalizacji oczekiwań:
1- Przeczytaj ten samouczek EM autorstwa Do i Batzoglou.
2- Możesz mieć w głowie znaki zapytania, spójrz na wyjaśnienia na tej stronie wymiany stosów matematycznych .
3- Spójrz na ten kod, który napisałem w Pythonie, który wyjaśnia przykład w dokumencie instruktażowym EM w punkcie 1:
Ostrzeżenie: kod może być niechlujny / nieoptymalny, ponieważ nie jestem programistą Pythona. Ale spełnia swoje zadanie.
źródło
Technicznie termin „EM” jest nieco niedookreślony, ale zakładam, że odnosisz się do techniki analizy skupień Gaussian Mixture Modeling, która jest przykładem ogólnej zasady EM.
W rzeczywistości analiza skupień EM nie jest klasyfikatorem . Wiem, że niektórzy uważają tworzenie klastrów za „klasyfikację nienadzorowaną”, ale w rzeczywistości analiza skupień to coś zupełnie innego.
Kluczowa różnica i wielkie niezrozumienie klasyfikacji, które ludzie zawsze mają w analizie skupień, jest takie, że: w analizie klastrów nie ma „poprawnego rozwiązania” . Jest to metoda odkrywania wiedzy , w rzeczywistości ma na celu znalezienie czegoś nowego ! To sprawia, że ocena jest bardzo trudna. Często jest oceniany przy użyciu znanej klasyfikacji jako odniesienia, ale nie zawsze jest to właściwe: klasyfikacja, którą posiadasz, może, ale nie musi, odzwierciedlać to, co jest w danych.
Podam przykład: masz duży zbiór danych klientów, w tym dane dotyczące płci. Metoda dzieląca ten zestaw danych na „mężczyzna” i „kobieta” jest optymalna, gdy porównuje się go z istniejącymi klasami. W myśleniu „przewidywania” jest to dobre, ponieważ w przypadku nowych użytkowników można teraz przewidzieć ich płeć. W myśleniu „odkrywania wiedzy” jest to właściwie złe, ponieważ chciałeś odkryć jakąś nową strukturę danych. Metoda, która np. Podzieliłaby dane na osoby starsze i dzieci, uzyskałaby jednak gorsze wyniki, jak to możliwe w odniesieniu do klasy mężczyzn / kobiet. Byłby to jednak doskonały wynik grupowania (gdyby nie podano wieku).
Wróćmy teraz do EM. Zasadniczo zakłada się, że dane składają się z wielu wielowymiarowych rozkładów normalnych (zwróć uwagę, że jest to bardzo mocne założenie, zwłaszcza gdy ustalasz liczbę klastrów!). Następnie próbuje znaleźć optymalny model lokalny, na przemian ulepszając model i przypisanie obiektu do modelu .
Aby uzyskać najlepsze wyniki w kontekście klasyfikacji, wybierz liczbę klastrów większą niż liczba klas, a nawet zastosuj grupowanie tylko do pojedynczych klas (aby dowiedzieć się, czy w klasie jest jakaś struktura!).
Załóżmy, że chcesz nauczyć klasyfikatora rozróżniać „samochody”, „rowery” i „ciężarówki”. Zakładanie, że dane składają się z dokładnie trzech rozkładów normalnych, jest mało przydatne. Możesz jednak założyć, że istnieje więcej niż jeden typ samochodów (oraz ciężarówek i motocykli). Więc zamiast trenować klasyfikator dla tych trzech klas, grupujesz samochody, ciężarówki i motocykle w 10 grup (lub może 10 samochodów, 3 ciężarówki i 3 rowery, cokolwiek), następnie trenujesz klasyfikator, aby rozróżniał te 30 klas, a następnie scal wynik klasy z powrotem do klas oryginalnych. Możesz również odkryć, że istnieje jeden klaster, który jest szczególnie trudny do sklasyfikowania, na przykład Trikes. To trochę samochody i trochę motocykle. Albo samochody dostawcze, które bardziej przypominają duże samochody niż ciężarówki.
źródło
Jeśli inne odpowiedzi są dobre, spróbuję przedstawić inną perspektywę i zająć się intuicyjną częścią pytania.
Algorytm EM (Expectation-Maximization) jest wariantem klasy iteracyjnych algorytmów wykorzystujących dualność
Fragment (moje podkreślenie):
Zwykle podwójne B obiektu A jest w jakiś sposób powiązane z A, co pozwala zachować pewną symetrię lub zgodność . Na przykład AB = const
Przykłady algorytmów iteracyjnych wykorzystujących dualność (w poprzednim znaczeniu) to:
W podobny sposób algorytm EM można również postrzegać jako dwa podwójne kroki maksymalizacji :
W iteracyjnym algorytmie wykorzystującym dualność istnieje jawne (lub niejawne) założenie równowagi (lub ustalonego) punktu zbieżności (dla EM jest to udowodnione za pomocą nierówności Jensena)
Zatem zarys takich algorytmów jest następujący:
Zauważ, że kiedy taki algorytm zbiega się do (globalnego) optimum, to znalazł konfigurację, która jest najlepsza z obu względów (tj. Zarówno w domenie / parametrach x, jak i w domenie / parametrach y ). Jednak algorytm może po prostu znaleźć optimum lokalne, a nie optymalne globalne .
powiedziałbym, że jest to intuicyjny opis zarysu algorytmu
W przypadku argumentów statystycznych i zastosowań inne odpowiedzi dały dobre wyjaśnienia (sprawdź również odniesienia w tej odpowiedzi)
źródło
Przyjęta odpowiedź odwołuje się do Chuong EM Paper , który porządnie wyjaśnia EM. Istnieje również wideo z YouTube, które bardziej szczegółowo wyjaśnia artykuł.
Podsumowując, oto scenariusz:
W przypadku pytania z pierwszej próby, intuicyjnie myślelibyśmy, że B wygenerował je, ponieważ proporcja orłów bardzo dobrze pasuje do odchylenia B ... ale ta wartość była tylko przypuszczeniem, więc nie możemy być pewni.
Mając to na uwadze, lubię myśleć o rozwiązaniu EM w następujący sposób:
Może to być nadmierne uproszczenie (lub nawet fundamentalnie błędne na niektórych poziomach), ale mam nadzieję, że pomoże to na poziomie intuicyjnym!
źródło
EM służy do maksymalizacji prawdopodobieństwa modelu Q ze zmiennymi latentnymi Z.
To iteracyjna optymalizacja.
e-step: biorąc pod uwagę bieżące oszacowanie Z, oblicz oczekiwaną funkcję loglikwidencji
m-step: znajdź theta, który maksymalizuje to Q
Przykład GMM:
e-step: oszacowanie przypisań etykiet dla każdego punktu danych przy aktualnym oszacowaniu parametru gmm
m-step: maksymalizuj nowe theta biorąc pod uwagę nowe przypisania etykiet
K-średnie jest również algorytmem EM i istnieje wiele animacji wyjaśniających K-średnich.
źródło
Korzystając z tego samego artykułu autorstwa Do i Batzoglou, cytowanego w odpowiedzi Zhubarba, zaimplementowałem EM dla tego problemu w Javie . Komentarze do jego odpowiedzi pokazują, że algorytm utknie na lokalnym optimum, co również ma miejsce w mojej implementacji, jeśli parametry thetaA i thetaB są takie same.
Poniżej znajduje się standardowe wyjście mojego kodu, pokazujące zbieżność parametrów.
Poniżej znajduje się moja implementacja EM w Javie w celu rozwiązania problemu w (Do i Batzoglou, 2008). Podstawową częścią implementacji jest pętla do uruchamiania EM do momentu zbieżności parametrów.
Poniżej znajduje się cały kod.
źródło