Przeczytałem kilka wyjaśnień algorytmu EM (np. Z Bishop's Pattern Recognition and Machine Learning oraz z Roger i Gerolami First Course on Machine Learning). Wyprowadzenie EM jest w porządku, rozumiem to. Rozumiem również, dlaczego algorytm obejmuje coś: na każdym etapie poprawiamy wynik, a prawdopodobieństwo jest ograniczone przez 1,0, więc używając prostego faktu (jeśli funkcja rośnie i jest ograniczona, to się zbiega) wiemy, że algorytm zbiega się do jakieś rozwiązanie.

Skąd jednak wiemy, że jest to lokalne minimum? Na każdym kroku rozważamy tylko jedną współrzędną (zmienną ukrytą lub parametry), więc możemy coś przeoczyć, na przykład lokalne minimum wymaga przesunięcia o obie współrzędne jednocześnie.

Wydaje mi się, że jest to podobny problem do ogólnej klasy algorytmów wspinania się na wzniesienia, których EM jest przykładem. Tak więc dla ogólnego algorytmu wspinania się na wzgórze mamy ten problem dla funkcji f (x, y) = x * y. Jeśli zaczniemy od punktu (0, 0), to tylko rozważając oba kierunki jednocześnie, możemy przejść w górę od wartości 0.

EM nie gwarantuje, że zbiegnie się do lokalnego minimum. Gwarantowane jest jedynie zbiegnięcie się do punktu o zerowym gradiencie względem parametrów. Może więc utknąć w punktach siodłowych.

Po pierwsze, możliwe jest, że EM zbiega się do lokalnej wartości minimalnej , lokalnej wartości maksymalnej lub punktu siodłowego funkcji wiarygodności. Mówiąc dokładniej, jak zauważył Tom Minka , gwarantuje się, że EM zbliży się do punktu o zerowym gradiencie .

Mogę wymyślić dwa sposoby, aby to zobaczyć; pierwszy widok to czysta intuicja, a drugi to szkic formalnego dowodu. Najpierw krótko wyjaśnię, jak działa EM:

$t$$b_t(\theta)$$L(\theta)$$\theta_t = \arg\max_\theta b_t(\theta)$

Oczekiwanie Maksymalizacja jako wznoszenie gradientu

$t$$b_t$$L$$\theta_{t-1}$$g = \nabla b_t(\theta_{t-1}) = \nabla L(\theta_{t-1})$$\theta_t$$\theta_{t-1} + \eta g$

$\theta^*$$\theta^*$

Szkic formalnego dowodu