Dlaczego algorytm Expectation Maximization gwarantuje osiągnięcie zbieżności z lokalnym optimum?

24

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.

michal
źródło
3
Prawdopodobieństwo jest ograniczone tylko dla stałych odchyleń. Oznacza to, że w sytuacji dwumianowej wariancja wynosi ; lub w sytuacji gaussowskiej, jeśli założono, że wariancja jest znana. Jeśli wariancja jest nieznana i należy ją oszacować, prawdopodobieństwo nie jest ograniczone. Ponadto w algorytmie EM istnieje ogólny podział braków i parametrów, przynajmniej dla statystycznych statystów, ale powierzchnie mogą rzeczywiście mieć siodła. p(1p)
StasK
@Stask Nie jestem pewien, czy prawdopodobieństwo jest ogólnie ograniczone, nawet przy ustalonych odchyleniach. Czy ograniczasz się do określonej rodziny?
Glen_b

Odpowiedzi:

27

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.

Tom Minka
źródło
1
Przykłady patrz str. 20 i 38 tutaj , str. 85 tutaj - wypróbuj „punkt siodłowy” w czytniku Amazon.
StasK
13

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:

tbt(θ)L(θ)θt=argmaxθbt(θ)

Oczekiwanie Maksymalizacja jako wznoszenie gradientu

tbtLθt1g=bt(θt1)=L(θt1)θtθt1+ηg

θθ

Szkic formalnego dowodu

(1)limtL(θt)bt(θt)=0.
(2)limtL(θt)=bt(θt).
(1) oraz że granice zastosowane w EM są różniczkowalne oraz że θ t = arg max θ b t ( θ ) , mamyb t ( θ t ) = 0, a zatem lim t L ( θ t ) = 0 .(2)θt=argmaxθbt(θ)bt(θt)=0limtL(θt)=0
Sobi
źródło