Jaka jest różnica między EM a Gradient Ascent?

Jaka jest różnica między algorytmami EM (Expectation Maximization) a Gradient Ascent (or descent)? Czy są jakieś warunki, w których są one równoważne?

gradient-descent expectation-maximization

— Aslan986
źródło

Odpowiedzi:

Xu L i Jordan MI (1996). O właściwościach konwergencji algorytmu EM dla mieszanek gaussowskich . Obliczenia neuronowe 2: 129-151.

Abstrakcyjny:

Pokazujemy, że krok EM w przestrzeni parametrów jest uzyskiwany z gradientu za pomocą macierzy projekcji P, i zapewniamy wyraźne wyrażenie dla macierzy.

Strona 2

W szczególności pokazujemy, że krok EM można uzyskać przez wstępne pomnożenie gradientu przez dodatnią macierz denitową. Zapewniamy wyraźne wyrażenie dla macierzy ...

Strona 3

Oznacza to, że algorytm EM może być postrzegany jako algorytm zmiennej gradientu wznoszenia gradientu ...

Oznacza to, że artykuł zawiera wyraźne przekształcenia algorytmu EM w gradient ascent, Newton, quasi-Newton.

Z wikipedii

Istnieją inne metody znajdowania oszacowań maksymalnego prawdopodobieństwa, takie jak opadanie gradientu, gradient sprzężony lub odmiany metody Gaussa-Newtona. W przeciwieństwie do EM, takie metody zazwyczaj wymagają oceny pierwszej i / lub drugiej pochodnej funkcji prawdopodobieństwa.

— Ron Coleman
źródło

Ta odpowiedź wydaje się sugerować, że EM i opadanie gradientu są w zasadzie tym samym algorytmem, z transformacjami dostępnymi do przełączania z jednego algorytmu na drugi. Z całą pewnością nie jest to prawdą i silnie zależy od uwzględnionego modelu generatywnego. W cytowanym artykule wyciągnięto jedynie wnioski dla modeli mieszanki Gaussa (które są stosunkowo prostymi modelami generatywnymi) i słusznie. Z mojego (co prawda ograniczonego) doświadczenia, kiedy model jest wysoce nieliniowy, a rola ukrytych zmiennych jest ważna, EM jest jedynym sposobem na uzyskanie rozsądnych reguł aktualizacji.

— niebieski

Nie, nie są równoważne. W szczególności konwergencja EM jest znacznie wolniejsza.

Jeśli interesuje Cię optymalizacja z punktu widzenia EM, w tym artykule zobaczysz, że algorytm EM jest szczególnym przypadkiem szerszej klasy algorytmów (algorytmy punktów bliższych).

— Elvis
źródło

Lub dla podobnego pomysłu, Hinton i Neal (1998)

— sprzężony przed

„Konwergencja EM jest znacznie wolniejsza”; nie jest to dobrze zdefiniowane i na pewno nie jest ogólnie prawdą. Algorytmy EM to cała klasa algorytmów. Dla wielu problemów, pewien algorytm EM jest stan techniki.

— Cliff AB

@CliffAB, proszę nie wahaj się rozwinąć, chciałbym przeczytać twoje argumenty - czytając tę odpowiedź od 4 lat, zdaję sobie sprawę, że nie odpowiedziałbym na to dzisiaj. Od tego czasu odkryłem, że w wielu przypadkach EM jest wznoszeniem gradientu z parametrem „szybkości uczenia się” w zależności od bieżącego punktu ... (mogę edytować tę odpowiedź, by wskazać wyniki tego rodzaju)

— Elvis

„Wolniejszą konwergencję” można zdefiniować w kategoriach współczynnika konwergencji. Współczynnik zbieżności wznoszenia gradientu będzie zależeć od „współczynnika uczenia się”, który nie jest łatwy do wyboru, co w wielu przypadkach utrudnia wznoszenie gradientu. Jednak nadal mam przeczucie, że chociaż EM może być w niektórych przypadkach jedynym wykonalnym algorytmem (pochodne prawdopodobieństwa lub samo prawdopodobieństwo są trudne do obliczenia), jego wskaźnik konwergencji jest słaby w porównaniu z metodą Newtona.

— Elvis

Algorytm „EM” to tak naprawdę cała klasa algorytmów; jedna, w której pierwotna funkcja docelowa jest trudna do optymalizacji, ale gdyby znana była jakaś inna zmienna, rozwiązanie byłoby znacznie łatwiejsze (zazwyczaj w formie zamkniętej). Podstawowym celem jest wypełnienie oczekiwanej zmiennej w zależności od bieżących wartości pozostałych parametrów, a następnie aktualizacja parametrów w oparciu o oczekiwaną wartość zmiennej. Wykazano, że szybkość zbieżności algorytmu zależy od stopnia informacyjności przypisywanych danych; im bardziej „pouczające” są brakujące dane, tym wolniejsza jest konwergencja.

— Cliff AB