Dlaczego optymalizacja mieszanki Gaussa bezpośrednio jest trudna obliczeniowo?

18

Rozważ logarytmiczne prawdopodobieństwo mieszanki Gaussów:

l (S_{n}; θ) = \sum_{t = 1}^{n} \log f (x^{(t)} | θ) = \sum_{t = 1}^{n} \log {\sum_{i = 1}^{k} p_{i} f (x^{(t)} | μ^{(i)}, σ_{i}^{2})}

$l(S_n; \theta) = \sum^n_{t=1}\log f(x^{(t)}|\theta) = \sum^n_{t=1}\log\left\{\sum^k_{i=1}p_i f(x^{(t)}|\mu^{(i)}, \sigma^2_i)\right\}$

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:

$S_n$ = dane treningowe.

$x^{(t)}$ = punkt danych.

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

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

machine-learning gaussian-mixture expectation-maximization

— Pinokio
źródło

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 . $n$ $k$ $k^n$ $k$ $n$

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

L. = \log ({mi}^{- (x / σ_{1})^{2)}} + {mi}^{- (x / σ_{2)})^{2)}})

$L = \log \left(e^{-({x}/{\sigma_{1}})^2} + e^{-({x}/{\sigma_{2}})^2}\right)$

dla wszystkich x.

\frac{d^{2} L}{d x^{2}} > 0

$\frac{d^2L}{dx^2} > 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 (na przykład) i . Prawdziwy maksymalizator powinien zatem mieć to rozwiązanie, które nie jest przydatne do celów szacowania. $l(\theta|S_n)$ $+\infty$ $\hat\mu^{(i)}=x_1$ $\hat\sigma_i=0$
Nawet bez uwzględnienia warunków w rozkładzie iloczynu sum jako sumy iloczynu w , 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 na $k^n$ $l(\theta|S_n)$ $\theta$

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ć

$\theta_1^\prime=\arg\max_{\theta_1} l(\theta|S_n)$
znajdź $\theta_2^\prime=\arg\max_{\theta_2} l(\theta_1^\prime,\theta_{-1}|S_n)$
...
znajdź $\theta_v^\prime=\arg\max_{\theta_v} l(\theta_{-v}^\prime,\theta_v|S_n)$

$v$ $l(\theta|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