Przejdź do treści
Wróć do wyników wyszukiwania

Algorytm EM

Autor metody
Dempster, Laird & Rubin
Rok
1977
Typ
Iterative optimization algorithm
Rodzina
Estimation

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Algorytm EM (Expectation-Maximization) jest iteracyjną procedurą optymalizacyjną służącą do znajdowania estymatorów największej wiarygodności lub estymatorów a posteriori parametrów w modelach statystycznych z ukrytymi zmiennymi lub brakującymi danymi.

Wprowadzony przez Dempstera, Lairda i Rubina w ich przełomowej pracy z 1977 roku, EM przeplata obliczanie oczekiwanej log-wiarygodności kompletnych danych (krok E) z maksymalizacją tejże względem parametrów (krok M), gwarantując monotoniczny, niemalejący wzrost wiarygodności w każdej iteracji.

Intuicja stojąca za metodą

Wyobraźmy sobie próbę poznania zasad gry poprzez obserwowanie graczy, których kart nie widzimy. W każdej rundzie zgadujemy, jakie karty prawdopodobnie trzymają, bazując na tym, co obserwujemy, a następnie aktualizujemy nasz model zasad, zakładając, że te przypuszczenia są poprawne. Algorytm EM działa dokładnie w ten sposób: krok E probabilistycznie uzupełnia brakujące informacje przy użyciu bieżących estymatorów parametrów, a krok M ponownie dopasowuje model, tak jakby uzupełnione wartości były rzeczywistymi obserwacjami.

Historia

Algorytm został formalnie ujednolicony i nazwany przez Arthura Dempstera, Nan Laird i Donalda Rubina w ich artykule w JRSS-B z 1977 roku, który pozostaje jednym z najczęściej cytowanych artykułów statystycznych w historii. Praca ta uogólniła wcześniejsze procedury przypadków szczególnych, opracowane niezależnie dla konkretnych problemów brakujących danych. Kolejne dekady przyniosły liczne rozszerzenia, w tym algorytmy ECM, ECME, AECM i SEM, poszerzając zastosowalność i przyspieszając zbieżność w wielu praktycznych zastosowaniach.

Kiedy stosować

Używaj algorytmu EM, gdy dane zawierają brakujące wartości, ukryte stany lub zmienne ukryte, a potrzebujesz estymatorów największej wiarygodności. Jest on dobrze dopasowany do modeli mieszanin Gaussa, ukrytych modeli Markowa, analizy czynnikowej i imputacji brakujących danych. Kluczowe założenia obejmują to, że brakujące dane są brakujące losowo (MAR) i że model kompletnych danych jest rozwiązywalny analitycznie. Ograniczenia obejmują wrażliwość na inicjalizację, możliwość zbieżności do lokalnych maksimów i wolną zbieżność w pobliżu punktów siodłowych. Alternatywy obejmują optymalizację opartą na gradiencie z całkowaniem numerycznym, wnioskowanie wariacyjne lub metody MCMC.

Ograniczenia i uwagi

  • Zbieżność do lokalnego maksimum, a nie globalnego, gdy powierzchnia wiarygodności jest multimodalna
  • Może wykazywać bardzo wolną (liniową) zbieżność, gdy odsetek brakujących informacji jest duży
  • Wymaga od analityka określenia modelu kompletnych danych i rozkładu zmiennych ukrytych
  • Standardowy algorytm EM nie dostarcza bezpośrednio macierzy kowariancji obserwowanych danych dla estymatorów; dodatkowy krok (np. metoda Louisa lub algorytm SEM) jest potrzebny do uzyskania błędów standardowych

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Gwarantowany monotoniczny wzrost log-wiarygodności obserwowanych danych w każdej iteracji, zapewniający stabilną zbieżność
  • Przekształca trudny problem brakujących danych w sekwencję rozwiązywalnych analitycznie optymalizacji kompletnych danych
  • Szeroko stosowalny w modelach rodziny wykładniczej, modelach mieszanin i ramach zmiennych ukrytych
  • Dostępne są analityczne aktualizacje kroku M dla wielu standardowych modeli, co czyni implementację wydajną

Zastosowania

  • Dopasowywanie modeli mieszanin Gaussa do klasteryzacji i estymacji gęstości
  • Trenowanie ukrytych modeli Markowa do rozpoznawania mowy i analizy sekwencji biologicznych
  • Wielokrotna imputacja i analiza brakujących danych w badaniach klinicznych i społecznych
  • Estymacja parametrów w analizie czynnikowej i analizie klas ukrytych
  • Segmentacja i rekonstrukcja obrazów w medycynie

Jak to działa

Jak to działa

1

Przed rozpoczęciem iteracji analityk wybiera wartości początkowe dla nieznanych parametrów, oznaczane jako theta-0. Mogą one być wybrane losowo, na podstawie uproszczonego dopasowania lub wiedzy dziedzinowej. Jakość inicjalizacji może wpłynąć na to, do którego lokalnego maksimum zbiegnie algorytm, co sprawia, że wielokrotne losowe restarty są powszechną praktyką.

Wzór
\text{Choose initial parameter estimates } \theta^{(0)}
2

Mając bieżący estymator parametrów theta-t, krok E oblicza Q, czyli wartość oczekiwaną log-wiarygodności kompletnych danych względem rozkładu nieobserwowanych zmiennych ukrytych Z, warunkowaną obserwowanymi danymi X. To oczekiwanie efektywnie zastępuje nieznane ilości ich probabilistycznymi estymatami, bez przypisywania pojedynczej wartości imputowanej.

Wzór
Q(\theta \mid \theta^{(t)}) = \mathbb{E}_{Z \mid X, \theta^{(t)}}[\log p(X, Z \mid \theta)]
3

Krok M maksymalizuje funkcję Q z kroku E względem theta, generując zaktualizowany estymator theta-(t+1). Ponieważ maksymalizacja log-wiarygodności kompletnych danych jest często prostsza niż maksymalizacja marginalnej log-wiarygodności obserwowanych danych, ten krok jest często rozwiązywalny analitycznie, nawet gdy bezpośrednia estymacja największej wiarygodności nie jest.

Wzór
\theta^{(t+1)} = \arg\max_{\theta} \, Q(\theta \mid \theta^{(t)})
4

Kroki E i M są powtarzane naprzemiennie. Po każdym pełnym cyklu ewaluowana jest log-wiarygodność obserwowanych danych. Iteracja kończy się, gdy zmiana w log-wiarygodności (lub w wektorze parametrów) spadnie poniżej zdefiniowanej przez użytkownika tolerancji epsilon. Dempster i wsp. udowodnili, że każdy cykl nie może zmniejszyć log-wiarygodności obserwowanych danych, zapewniając stabilną zbieżność.

Wzór
\text{Repeat E- and M-steps until } |\ell(\theta^{(t+1)}) - \ell(\theta^{(t)})| < \epsilon

Częste pułapki

  • Użycie pojedynczej losowej inicjalizacji grozi zakończeniem w słabym lokalnym maksimum; zawsze przeprowadzaj wiele restartów i wybierz rozwiązanie z najwyższą końcową log-wiarygodnością
  • Zbyt wczesne uznanie zbieżności poprzez monitorowanie jedynie zmiany parametrów zamiast log-wiarygodności obserwowanych danych może prowadzić do niedokładnych estymatorów
  • Zastosowanie algorytmu EM, gdy dane są brakujące nie losowo (MNAR) bez modyfikacji modelu, może wprowadzić systematyczne błędy w estymatorach
  • Ignorowanie problemu zamiany etykiet w modelach mieszanin prowadzi do nieinterpretowalnych przypisań komponentów nawet po poprawnej zbieżności

Najczęściej zadawane pytania

Czy algorytm EM zawsze zbiega do maksimum globalnego?

Nie. Algorytm EM gwarantuje zbieżność jedynie do lokalnego maksimum (lub punktu siodłowego) log-wiarygodności obserwowanych danych. Gdy powierzchnia wiarygodności ma wiele maksimów, ostateczne rozwiązanie zależy od inicjalizacji. Uruchamianie algorytmu z kilku różnych punktów startowych i zachowanie rozwiązania z najwyższą log-wiarygodnością jest standardowym praktycznym rozwiązaniem.

Czym algorytm EM różni się od bezpośredniej optymalizacji największej wiarygodności?

Bezpośrednia estymacja największej wiarygodności (MLE) maksymalizuje log-wiarygodność obserwowanych danych, co może obejmować nieciągłe całki po zmiennych ukrytych. Algorytm EM omija ten problem, iteracyjnie maksymalizując oczekiwaną log-wiarygodność kompletnych danych, która jest często analitycznie rozwiązywalna. Kompromisem jest to, że algorytm EM może zbiegać wolno, podczas gdy metody oparte na gradiencie mogą być szybsze, gdy dostępne są gradienty marginalnej wiarygodności.

Kiedy powinienem preferować imputację MICE nad algorytmem EM?

MICE (Multiple Imputation by Chained Equations) jest preferowane, gdy dane zawierają zmienne różnych typów, nieliniowe zależności lub złożone struktury interakcji, które są trudne do ujęcia w jednym parametrycznym modelu kompletnych danych. Algorytm EM jest bardziej naturalny, gdy istnieje dobrze określony model łączny dla wszystkich zmiennych, a wnioskowanie dotyczy parametrów modelu, a nie zaimputowanych zbiorów danych.

Pokrewne metody

Źródła

  1. Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B, 39(1), 1–38.

    Otwórz odnośnik DOI
    Skopiowano.