Schnelle Alternativen zum EM-Algorithmus

13

Gibt es schnelle Alternativen zum EM-Algorithmus zum Lernen von Modellen mit latenten Variablen (insbesondere pLSA)? Ich finde es in Ordnung, die Präzision zugunsten der Geschwindigkeit zu opfern.

machine-learning optimization expectation-maximization lsa Aslan986
quelle
1
Haben Sie eine Literaturübersicht durchgeführt? Dieses Papier sieht besonders relevant aus: Konvexe Relaxationen des latent variablen Trainings
Emre
1
Wie wäre es mit LSA? :-)
conjugateprior
1
Ein allgemeiner Weg, eine EM zu beschleunigen, heißt "Aitken-Beschleuniger". Wenn Präzision keine Rolle spielt, versuchen Sie es stattdessen mit einer Momentschätzung oder einer verallgemeinerten Momentschätzung.
JohnRos

Antworten:

4

Newton-Raphson-Algorithmen können oft verwendet werden. Ich bin mit pSLA nicht vertraut, aber es ist ziemlich üblich, Newton-Raphson-Algorithmen für Modelle latenter Klassen zu verwenden. Newton-Raphson-Algorithmen haben etwas mehr mit schlechten Anfangswerten zu tun als EM. Daher besteht eine Strategie darin, zuerst einige Iterationen (z. B. 20) der EM zu verwenden und dann auf einen Newton-Raphson-Algorithmus zu wechseln. Ein Algorithmus, mit dem ich viel Erfolg hatte, ist: Zhu, Ciyou, Richard H. Byrd, Peihuang Lu und Jorge Nocedal (1997). eingeschränkte Optimierung, "ACM Transactions on Mathematical Software (TOMS) Archiv, 23 (4), 550-60.

Tim
quelle
4

Dem EM-Algorithmus sehr ähnlich ist der MM-Algorithmus der typischerweise die Konvexität ausnutzt, anstatt Daten beim Erhöhen oder Minimieren einer Zielfunktion zu fehlen. Sie müssen jedoch prüfen, ob der MM-Algorithmus für Ihr spezielles Problem geeignet ist.

sebp
quelle
3

Für LDA ist "Online-LDA" eine schnelle Alternative zu Batch-Methoden wie Standard-EM (http://www.cs.princeton.edu/~blei/papers/HoffmanBleiBach2010b.pdf).

David Blei stellt Software auf seiner Seite zur Verfügung: http://www.cs.princeton.edu/~blei/topicmodeling.html

user1149913
quelle
2

Eine weitere bisher in den Antworten nicht erwähnte Alternative sind Variationsnäherungen. Obwohl diese Algorithmen nicht in allen Fällen genau EM-Algorithmen sind, sind EM-Algorithmen in einigen Fällen einschränkende Fälle von Bayes'schen Mittelfeld-Variationsalgorithmen. Die Grenze bezieht sich auf den Grenzfall der Hyperparameter, und die Auswahl der Grenzwerte - in einigen Fällen - gibt Ihnen den EM-Algorithmus.

In beiden Fällen (EM-, VB- oder sogar MM-Algorithmen) gibt es zwei generische Möglichkeiten, die Dinge zu beschleunigen:

pp univariaten Problemen. Dies sind normalerweise Algorithmen für den Koordinatenabstieg, aber ich habe MM-Algorithmen gesehen, die auch diese Art der Beschleunigung durchführen.

(2) Verbesserung der Konvergenzrate Ihres EM-Algorithmus (oder eines anderen Typs). In einem Kommentar erwähnte JohnRos die Aitken-Beschleunigung. Dies stammt aus der Welt der numerischen Analyse, wird jedoch im EM-Buch von McLachlan und Krishnan erörtert.

Es mag andere geben, die ich verpasst habe, aber diese scheinen die beiden großen zu sein.

Lucas Roberts
quelle