Dlaczego optymalizacja mieszanki Gaussa bezpośrednio jest trudna obliczeniowo?

18

Rozważ logarytmiczne prawdopodobieństwo mieszanki Gaussów:

l(Sn;θ)=t=1nlogf(x(t)|θ)=t=1nlog{i=1kpif(x(t)|μ(i),σi2)}

Zastanawiałem się, dlaczego trudno było obliczeniowo bezpośrednio zmaksymalizować to równanie? Szukałem albo wyraźnej, solidnej intuicji, dlaczego powinno być oczywiste, że jest to trudne, a może bardziej rygorystyczne wyjaśnienie, dlaczego jest trudne. Czy ten problem jest NP-zupełny, czy po prostu jeszcze nie wiemy, jak go rozwiązać? Czy to dlatego stosujemy algorytm EM ( maksymalizacja oczekiwań )?


Notacja:

Sn = dane treningowe.

x(t) = punkt danych.

θ = zestaw parametrów określających Gaussa, ich średnie, odchylenia standardowe i prawdopodobieństwo wygenerowania punktu z każdej grupy / klasy / Gaussa.

pi = prawdopodobieństwo wygenerowania punktu z klastra / klasy / Gaussa i.

Pinokio
źródło

Odpowiedzi:

14

Po pierwsze, GMM jest szczególnym algorytmem grupowania, w którym próbujesz znaleźć optymalne oznakowanie swoich obserwacji. Mając możliwych klas, oznacza to, że istnieją możliwych labellings twoich danych treningowych. To staje się już ogromne dla umiarkowanych wartości i .k k n k nnkknkn

Po drugie, funkcjonalność, którą próbujesz zminimalizować, nie jest wypukła, a wraz z rozmiarem twojego problemu bardzo ją utrudnia. Wiem tylko, że k-średnie (GMM można postrzegać jako miękką wersję kmeans) jest trudne dla NP. Ale nie wiem, czy udowodniono to również w przypadku GMM.

Aby zobaczyć, że problem nie jest wypukły, rozważ przypadek jednowymiarowy: i sprawdź, czy nie możesz zagwarantować, że d 2 L

L.=log(mi-(x/σ1)2)+mi-(x/σ2))2))
dla wszystkich x.re2)L.rex2)>0

Problem niewypukły oznacza, że ​​możesz utknąć w lokalnych minimach. Zasadniczo nie masz silnych gwarancji optymalizacji wypukłej, a poszukiwanie rozwiązania jest znacznie trudniejsze.

jpmuc
źródło
3
W odniesieniu do drugiego punktu: średnie k można postrzegać jako szczególny przypadek GMM (a ściślej granicznego przypadku, w którym wariancje są zerowane). Jeśli możemy zredukować k-średnie do dopasowania GMM, ten drugi problem musi być również trudny dla NP.
Lucas,
1
@Lucas: Oto link Zweryfikowany link do Twojej uwagi.
Xi'an,
7

Oprócz punktów juampy, pozwólcie, że zasygnalizuję te trudności:

  • Funkcja jest nieograniczona, a więc wartość maksymalna wynosi + i odpowiada ľ ( I ) = x 1 (na przykład) i σ I = 0 . Prawdziwy maksymalizator powinien zatem mieć to rozwiązanie, które nie jest przydatne do celów szacowania.l(θ|S.n)+μ^(ja)=x1σ^ja=0
  • Nawet bez uwzględnienia warunków w rozkładzie iloczynu sum jako sumy iloczynu w l ( θ | S n ) , funkcja, która ma być zmaksymalizowana w θ, jest wysoce multimodalna (oprócz tego, że nie jest wypukła) stąd wyzwanie dla metod numerycznych. EM uznaje trudność, przechodząc do trybu lokalnego lub punktu siodłowego i wymagając wielu przebiegów. Jak pokazano naknl(θ|S.n)θzdjęcie poniżej

zaczerpnięte z mojej książki .

Uwaga dodatkowa: bez wywoływania algorytmu EM można użyć standardowego algorytmu optymalizacyjnego (takiego jak Newton-Raphson) po jednym parametrze na raz, to znaczy iterować

  • θ1=argmaxθ1l(θ|S.n)
  • znajdź θ2)=argmaxθ2)l(θ1,θ-1|S.n)
  • ...
  • znajdź θv=argmaxθvl(θ-v,θv|S.n)

vl(θ|S.n)

Xi'an
źródło
OK, L jest nieograniczone, jeśli wariancja wynosi 0. Ale jeśli wykluczymy je z możliwych parametrów (zakładamy więc wszystkie wariancje> 0), to L nie powinno być tak wysokie, ilekroć nieskończenie mała wybrana wariancja (z powodu innych punktów). Czy mam rację? Następnie dla tego możliwego zestawu parametrów L byłby ograniczony, co oznacza, że ​​algorytm EM jest zbieżny (zwiększenie ograniczonej sekwencji).
ahstat
@ahstat: zakładanie, że wariancje są ściśle dodatnie, nie uniemożliwia EM konwergencji do zdegenerowanego rozwiązania, jeśli zacznie się wystarczająco blisko.
Xi'an