Konwergencja z algorytmu EM z dwuwymiarowym rozkładem mieszanin

9

Mam model mieszanki, w którym chcę znaleźć estymator maksymalnego prawdopodobieństwa dla danego zestawu danych i zestawu częściowo zaobserwowanych danych . I realizowane zarówno E etapie (obliczenie oczekiwania dane i aktualnych parametrów ), i M-etapie, w celu zminimalizowania negatywnych log-Likelihood względu na spodziewany .xzzxθkz

Jak rozumiem, maksymalne prawdopodobieństwo wzrasta z każdą iteracją, co oznacza, że ​​ujemne prawdopodobieństwo log musi maleć przy każdej iteracji? Jednak, jak to powtarzam, algorytm tak naprawdę nie generuje malejących wartości ujemnego prawdopodobieństwa log. Zamiast tego może się zmniejszać i zwiększać. Na przykład były to wartości ujemnego prawdopodobieństwa logarytmicznego do momentu konwergencji:

wprowadź opis zdjęcia tutaj

Czy jest tu coś, co źle zrozumiałem?

Ponadto w przypadku danych symulowanych, gdy wykonuję maksymalne prawdopodobieństwo dla prawdziwych ukrytych (nieobserwowanych) zmiennych, mam prawie idealne dopasowanie, co wskazuje na brak błędów programistycznych. W przypadku algorytmu EM często zbiega się on z wyraźnie nieoptymalnymi rozwiązaniami, szczególnie dla określonego podzbioru parametrów (tj. Proporcji zmiennych klasyfikujących). Dobrze wiadomo, że algorytm może zbiegać się do lokalnych minimów lub punktów stacjonarnych, czy istnieje konwencjonalna heurystyka wyszukiwania lub podobnie w celu zwiększenia prawdopodobieństwa znalezienia globalnego minimum (lub maksimum) . Wydaje mi się, że w przypadku tego konkretnego problemu istnieje wiele brakujących klasyfikacji, ponieważ w przypadku dwuwymiarowej mieszanki jeden z dwóch rozkładów przyjmuje wartości z prawdopodobieństwem jeden (jest to mieszanka okresów życia, w których prawdziwy czas życia znajduje się na podstawieT=zT0+(1z) gdzie oznacza przynależność do dowolnego rozkładu. Wskaźnik jest oczywiście cenzurowany w zbiorze danych. zzwprowadź opis zdjęcia tutaj

Dodałem drugą liczbę, gdy zaczynam od rozwiązania teoretycznego (które powinno być bliskie optymalnemu). Jednak, jak można zauważyć, prawdopodobieństwo i parametry różnią się od tego rozwiązania na takie, które jest wyraźnie gorsze.

edycja: pełne dane są w postaci gdzie jest obserwowanym czasem dla podmiotu , wskazuje, czy czas jest powiązany z faktycznym zdarzeniem lub jeśli jest poprawnie ocenzurowany (1 oznacza zdarzenie, a 0 oznacza prawą cenzurę), jest czasem obcięcia obserwacji (ewentualnie 0) ze wskaźnikiem obcięcia a na koniec jest wskaźnikiem, do którego populacji należy obserwacja (ponieważ jego dwuwymiarowy musimy wziąć pod uwagę tylko 0 i 1).xi=(ti,δi,Li,τi,zi)tiiδiLiτizi

Dla mamy funkcję gęstości , podobnie jest to związane z funkcją rozkładu ogona . Dla zdarzenie będące przedmiotem zainteresowania nie wystąpi. Chociaż z tym rozkładem nie ma żadnego , definiujemy go jako , a więc i . Daje to również następujący pełny rozkład mieszaniny:z=1fz(t)=f(t|z=1)Sz(t)=S(t|z=1)z=0tinff(t|z=0)=0S(t|z=0)=1

f(t)=i=01pif(t|z=i)=pf(t|z=1) i S(t)=1p+pSz(t)

Kontynuujemy definiowanie ogólnej formy prawdopodobieństwa:

L(θ;xi)=Πif(ti;θ)δiS(ti;θ)1δiS(Li)τi

Teraz obserwuje się tylko częściowo, gdy , w przeciwnym razie nie jest to znane. Staje się pełne prawdopodobieństwozδ=1

L(θ,p;xi)=Πi((pfz(ti;θ))zi)δi((1p)(1zi)(pSz(ti;θ))zi)1δi((1p)(1zi)(pSz(Li;θ))zi)τi

gdzie jest wagą odpowiedniego rozkładu (ewentualnie związanego z niektórymi zmiennymi towarzyszącymi i ich odpowiednimi współczynnikami przez jakąś funkcję link). W większości literatur jest to uproszczone do następującego prawdopodobieństwa logicznegop

(ziln(p)+(1p)ln(1p)τi(ziln(p)+(1zi)ln(1p))+δizifz(ti;θ)+(1δi)ziSz(ti;θ)τiSz(Li;θ))

Dla kroku M funkcja ta jest zmaksymalizowana, chociaż nie w całości w 1 metodzie maksymalizacji. Zamiast tego nie możemy tego podzielić na części .l(θ,p;)=l1(θ,)+l2(p,)

Dla kroku k: th + 1 musimy znaleźć oczekiwaną wartość (częściowo) nieobserwowanych zmiennych ukrytych . Korzystamy z faktu, że dla , a następnie .ziδ=1z=1

E(zi|xi,θ(k),p(k))=δi+(1δi)P(zi=1;θ(k),p(k)|xi)

Oto, przezP(zi=1;θ(k),p(k)|xi)=P(xi;θ(k),p(k)|zi=1)P(zi=1;θ(k),p(k))P(xi;θ(k),p(k))

co daje namP(zi=1;θ(k),p(k)|xi)=pSz(ti;θ(k))1p+pSz(ti;θ(k))

(Zauważ tutaj, że , więc nie ma obserwowanego zdarzenia, dlatego prawdopodobieństwo danych jest określone przez funkcję rozkładu ogona.δi=0xi

Dobry facet Mike
źródło
Czy mógłbyś od początku zapisać zmienne naszego problemu oraz swoje równania E i M?
alberto
1
Oczywiście zredagowałem pytanie, podając więcej szczegółów dotyczących kroku E i M
Good Guy Mike
Aby wyjaśnić, przedstawione wartości są pełnym MLE, biorąc pod uwagę szacunkowe wartości niekompletnych danych.
Dobry facet Mike
Co to jest ? Nie rozumiem „chociaż nie ma żadnego związku z tym rozkładem, definiujemy go jako inf…”. Sz
wij
1
Algorytm EM bezpośrednio maksymalizuje oczekiwane prawdopodobieństwo danych kompletnych, ale może zagwarantować wzrost prawdopodobieństwa danych obserwowanych. Czy sprawdzasz wzrost prawdopodobieństwa zaobserwowanych danych?
Randel

Odpowiedzi:

6

Celem EM jest maksymalne zaobserwowane prawdopodobieństwo dziennika danych,

l(θ)=iln[zp(xi,z|θ)]

Niestety jest to trudne do optymalizacji w odniesieniu do . Zamiast tego EM wielokrotnie tworzy i maksymalizuje funkcję pomocnicząθ

Q(θ,θt)=Ez|θt(ilnp(xi,zi|θ))

Jeśli maksymalizuje , EM to gwarantujeθt+1Q(θ,θt)

l(θt+1)Q(θt+1,θt)Q(θt,θt)=l(θt)

Jeśli chcesz dokładnie wiedzieć, dlaczego tak się dzieje, rozdział 11.4.7 Uczenia maszynowego Murphy'ego : perspektywa probabilistyczna daje dobre wytłumaczenie. Jeśli twoja implementacja nie zaspokoi tych nierówności, gdzieś popełniłeś błąd. Mówiąc rzeczy takie jak

Mam prawie idealne dopasowanie, co wskazuje na brak błędów programistycznych

jest niebezpieczny. Dzięki wielu algorytmom optymalizacji i uczenia się bardzo łatwo jest popełniać błędy, ale przez większość czasu nadal uzyskuje się poprawnie wyglądające odpowiedzi. Intuicja, którą lubię, polega na tym, że te algorytmy są przeznaczone do radzenia sobie z niechlujnymi danymi, więc nic dziwnego, że dobrze radzą sobie również z błędami!


W drugiej połowie twojego pytania

czy istnieje konwencjonalna heurystyka wyszukiwania lub podobnie, aby zwiększyć prawdopodobieństwo znalezienia globalnego minimum (lub maksimum)

Losowe ponowne uruchomienie jest najłatwiejszym podejściem; kolejnym najłatwiejszym jest prawdopodobnie symulowane wyżarzanie nad parametrami początkowymi. Słyszałem także o wariancie EM zwanym wyżarzaniem deterministycznym , ale nie użyłem go osobiście, więc nie mogę ci o nim wiele powiedzieć.

Andy Jones
źródło
1
Dobra odpowiedź (+1). Byłoby jeszcze lepiej, gdybyś załączył formalne odniesienia (w szczególności odniesienie do częściowo cytowanego źródła „Uczenie maszynowe: perspektywa probabilistyczna”).
Aleksandr Blekh
Dziękuję bardzo za odpowiedź. Przekonałem się, że algorytm jest teraz właściwie zbieżny po naprawieniu błędu w kodzie, ale tylko wtedy, gdy wykluczę moje obcięte dane. W przeciwnym razie szaleje. Uważam, że jest to wynikiem niektórych błędów.
Dobry facet Mike
W rzeczywistości problem polega na tym, że mam do czynienia z „heterogenicznym obcięciem”, tj. Istnieje indywidualny punkt obcięcia dla każdej obserwacji, a nie jednomyślny próg obcięcia dla wszystkich obserwacji. Nigdy nie spotkałem lub nie mogę znaleźć tych ustawień w literaturze, więc nie mogę zweryfikować, czy rozwiązuję je poprawnie. Jeśli przypadkiem zobaczyłbyś to ustawienie, chciałbym rzucić okiem na te referencje! Li
Dobry facet Mike