Existem alternativas rápidas para o algoritmo EM para aprender modelos com variáveis latentes (especialmente pLSA)? Eu estou bem em sacrificar a precisão em favor da velocidade.
13
Existem alternativas rápidas para o algoritmo EM para aprender modelos com variáveis latentes (especialmente pLSA)? Eu estou bem em sacrificar a precisão em favor da velocidade.
Respostas:
Algoritmos de Newton-Raphson podem frequentemente ser empregados. Não conheço o pSLA, mas é bastante comum o uso de algoritmos de Newton-Raphson para modelos de classes latentes. Os algoritmos de Newton-Raphson são um pouco mais problemáticos por valores iniciais ruins que o EM, portanto, uma estratégia é usar primeiro algumas iterações (digamos 20) do EM e depois mudar para um algoritmo de Newton-Raphson. Um algoritmo com o qual tive muito sucesso é: Zhu, Ciyou, Richard H. Byrd, Peihuang Lu e Jorge Nocedal (1997), "Algorithm 778: L-BFGS-B: sub-rotinas Fortran para ligações em larga escala". otimização restrita ", arquivo ACOM Transactions on Mathematical Software (TOMS), 23 (4), 550-60.
fonte
Muito parecido com o algoritmo EM, é o algoritmo MM, que normalmente explora a convexidade, em vez de perder dados ao aumentar ou diminuir uma função objetiva. Você deve verificar se o algoritmo MM é aplicável ao seu problema específico.
fonte
Para o LDA, o "LDA on-line" é uma alternativa rápida aos métodos de lote, como o EM padrão (http://www.cs.princeton.edu/~blei/papers/HoffmanBleiBach2010b.pdf).
David Blei fornece software em sua página: http://www.cs.princeton.edu/~blei/topicmodeling.html
fonte
Outra alternativa não mencionada até agora nas respostas são aproximações variacionais. Embora esses algoritmos não sejam exatamente algoritmos EM em todos os casos, em alguns casos, os algoritmos EM são casos limitantes de algoritmos variacionais de campo médio Bayesiano. O limite refere-se ao caso limitador dos hiperparâmetros, escolhendo os valores limite - em alguns casos - fornecerá o algoritmo EM.
Em ambos os casos (algoritmos EM, VB ou mesmo MM), existem 2 maneiras genéricas de acelerar as coisas:
(1) reduzir a dimensionalidade do problema - de ump -dim problema para p problemas univariados. Geralmente, são algoritmos de descida coordenada, mas já vi algoritmos MM que também fazem esse tipo de aceleração.
(2) melhorar a taxa de convergência do seu algoritmo EM (ou outro tipo). Em um comentário, JohnRos mencionou a aceleração da Aitken. Isso é do mundo da análise numérica, mas é discutido no livro EM por McLachlan e Krishnan.
Pode haver outros que eu perdi, mas esses parecem ser os dois grandes.
fonte