Algorytm EM

Algorytm Expectation–Maximization (algorytm EM) to metoda estymacji parametrów modelu probabilistycznego ze zmiennymi ukrytymi polegająca na iteracyjnej maksymalizacji funkcji wiarygodności. Każda iteracja algorytmu EM składa się z dwóch kroków: kroku E, w którym wyznaczana jest wartość oczekiwana logarytmicznej funkcji wiarygodności w oparciu o aktualne wartości parametrów modelu, oraz kroku M, w którym wyznaczane są wartości parametrów modelu maksymalizujące aktualnie wyznaczoną wartość oczekiwaną logarytmicznej funkcji wiarygodności.

Algorytm EM – wprowadzenie

Rozważmy model probabilistyczny \(\mathcal{M}\) z parametrami \(\mathbf{\theta}\), z którego pochodzi próbka zaobserwowanych danych \(\mathbf{X}\) oraz próbka ukrytych danych \(\mathbf{Z}\). Funkcja wiarygodności modelu probabilistycznego \(\mathcal{M}\) z parametrami \(\mathbf{\theta}\) ma więc postać

\(L(\mathbf{\theta} | \mathbf{X}, \mathbf{Z}) = p(\mathbf{X}, \mathbf{Z} | \mathbf{\theta}).\)

Estymator największej wiarygodności \(\hat{\mathbf{\theta}}\) parametrów modelu probabilistycznego \(\mathcal{M}\) definiowany jest w oparciu o rozkład brzegowy próbki zaobserowanych danych

\(L(\mathbf{\theta} | \mathbf{X}) = p(\mathbf{X} | \mathbf{\theta}) = \int p(\mathbf{X}, \mathbf{Z} | \mathbf{\theta}) d \mathbf{Z}\)

jako

\(\hat{\mathbf{\theta}} = \mbox{arg max}_{\mathbf{\theta}} L(\mathbf{\theta} | \mathbf{X}).\)

Algorytm EM maksymalizuje \(L(\mathbf{\theta} | \mathbf{X})\) iteracyjnie, w każdej iteracji \(t=1,2,\ldots,T\) wykonując dwa kroki:

Krok E: Obliczanie wartości oczekiwanej logarytmicznej funkcji wiarygodności modelu probabilistycznego \(\mathcal{M}\) z parametrami \(\mathbf{\theta}\) względem warunkowego rozkładu prawdopodobieństwa \(\mathbf{Z}\) pod warunkiem \(\mathbf{X}\) i ustalonych wartości \(\mathbf{\theta}^{(t-1)}\) parametrów modelu probabilistycznego \(\mathcal{M}\):

\(Q^{(t)}(\mathbf{\theta} | \mathbf{\theta}^{(t-1)}) = \mathbb{E}_{\mathbf{Z} | \mathbf{X}, \mathbf{\theta}^{(t-1)}} [\log L(\mathbf{\theta} | \mathbf{X}, \mathbf{Z})]\)

Krok M: Wyznaczenie wartości \(\mathbf{\theta}^{(t)}\) parametrów modelu probabilistycznego \(\mathcal{M}\) maksymalizujących wartość oczekiwaną logarytmicznej funkcji wiarygodności z kroku E:

\(\mathbf{\theta}^{(t)} = \mbox{arg max}_{\mathbf{\theta}} Q^{(t)}(\mathbf{\theta} | \mathbf{\theta}^{(t-1)})\)

Algorytm EM – zastosowania

Algorytm EM ma wiele zastosowań w inteligencji obliczeniowej, statystyce matematycznej i uczeniu maszynowym. Jednym z zastosowań algorytmu EM może być estymacja parametrów mieszanin rozkładów gaussowskich.

Algorytm EM – modelowanie mieszanin rozkładów gaussowskich

Poniższy przykład ilustruje zastosowanie algorytmu EM do estymacji parametrów mieszaniny trzech jednowymiarowych rozkładów gaussowskich. Pierwszy rysunek przedstawia histogram danych wejściowych. Jest to zestaw 1500 jednowymiarowych wektorów (w zasadzie więc liczb), które zostały wygenerowane z pewnej mieszaniny trzech jednowymiarowych rozkładów gaussowskich. Celem działania algorytmu EM jest znalezienie parametrów tej mieszaniny rozkładów gaussowskich.

algorytm EM - mieszanina rozkładów gaussowskich - histogram

Kolejny rysunek przedstawia gęstość oryginalnej mieszaniny rozkładów gaussowskich, z której pochodzą dane wejściowe. Składa się ona z trzech rozkładów gaussowskich o średnich odpowiednio 10, 30 i 60 i wariancjach odpowiednio 16, 64 i 144. Prawdopodobieństwa składników mieszaniny są równe i wynoszą 1/3.

algorytm EM - mieszanina rozkładów gaussowskich - gęstość oryginalna

Ostatni rysunek przedstawia gęstość mieszaniny rozkładów gaussowskich wyznaczonej przez algorytm EM. Składa się ona z trzech rozkładów gaussowskich (liczba składników mieszaniny była parametrem algorytmu EM) o średnich odpowiednio 10.26545365, 30.86045637 i 59.35403925 i wariancjach odpowiednio 16.48814537, 50.35195228 i 144.22753706. Prawdopodobieństwa składników mieszaniny wynoszą odpowiednio 0.35018841, 0.30707701 i 0.34273457. Chociaż wyznaczone parametry różnią się od parametrów oryginalnej mieszaniny rozkładów gaussowskich, sama gęstość wyznaczonej mieszaniny jest podobna do gęstości mieszaniny oryginalnej, a zatem wiarygodność wyznaczonej mieszaniny jest wysoka.

algorytm EM - mieszanina rozkładów gaussowskich - gęstość estymowana algorytmem EM

Dokładna implementacja algorytmu EM do estymacji parametrów mieszanin rozkładów gaussowskich zostanie opisana w kolejnym artykule.