Szybkie alternatywy dla algorytmu EM

13

Czy istnieją jakieś szybkie alternatywy dla algorytmu EM do uczenia się modeli z ukrytymi zmiennymi (zwłaszcza pLSA)? Nie przeszkadza mi poświęcanie precyzji na rzecz prędkości.

Aslan986
źródło
1
Czy zrobiłeś badanie literatury? Ten artykuł wydaje się szczególnie istotny: wypukłe relaksacje utajonego treningu zmiennego
Emre
1
Co powiesz na LSA? :-)
conjugateprior
1
Ogólny sposób na przyspieszenie EM nazywany jest „akceleratorem Aitkena”. Jeśli precyzja nie jest problemem, może zamiast tego spróbuj oszacowania momentu lub ogólnego oszacowania momentu.
JohnRos

Odpowiedzi:

4

Często można zastosować algorytmy Newtona-Raphsona. Nie znam pSLA, ale dość powszechne jest używanie algorytmów Newtona-Raphsona dla modeli klas ukrytych. Algorytmy Newtona-Raphsona są nieco bardziej zaniepokojone słabymi wartościami początkowymi niż EM, więc jedną ze strategii jest najpierw użycie kilku iteracji (powiedzmy 20) EM, a następnie przejście na algorytm Newtona-Raphsona. Jednym z algorytmów, z którym miałem wiele sukcesów, są: Zhu, Ciyou, Richard H. Byrd, Peihuang Lu i Jorge Nocedal (1997), „Algorytm 778: L-BFGS-B: Podprogramy Fortrana dla dużych granic granicznych ograniczona optymalizacja, „Transakcje ACM na oprogramowaniu matematycznym (TOMS), 23 (4), 550–60.

Tim
źródło
4

Bardzo podobny do algorytmu EM jest algorytm MM, który zazwyczaj wykorzystuje wypukłość, a nie brak danych w głównym lub minimalnym celu funkcji. Musisz jednak sprawdzić, czy algorytm MM ma zastosowanie do konkretnego problemu.

wrz
źródło
3

W przypadku LDA „online LDA” jest szybką alternatywą dla metod wsadowych, takich jak standardowe EM (http://www.cs.princeton.edu/~blei/papers/HoffmanBleiBach2010b.pdf).

David Blei zapewnia oprogramowanie na swojej stronie: http://www.cs.princeton.edu/~blei/topicmodeling.html

użytkownik1149913
źródło
2

Inną alternatywą nie wymienioną dotychczas w odpowiedziach są przybliżenia wariacyjne. Chociaż algorytmy te nie są dokładnie algorytmami EM we wszystkich przypadkach, w niektórych przypadkach algorytmy EM ograniczają przypadki algorytmów wariacyjnych pola średniego Bayesa. Limit dotyczy przypadku granicznego hiper-parametrów, wybranie wartości granicznych - w niektórych przypadkach - da ci algorytm EM.

W obu przypadkach (algorytmy EM, VB, a nawet MM) istnieją 2 ogólne sposoby przyspieszenia:

pp

(2) poprawa współczynnika konwergencji algorytmu EM (lub innego typu). W komentarzu JohnRos wspomniał o przyspieszeniu Aitkena. To pochodzi ze świata analiz numerycznych, ale jest omówione w książce EM przez McLachlana i Krishnana.

Mogą być inne, za którymi tęskniłem, ale te wydają się być tymi dwoma dużymi.

Lucas Roberts
źródło