12
$\begingroup$

Are there any speedy alternatives to the EM algorithm for learning models with latent variables (especially pLSA)? I'm okay with sacrificing precision in favor of speed.

$\endgroup$
  • 1
    $\begingroup$ Have you done a literature survey? This paper looks particularly relevant: Convex Relaxations of Latent Variable Training $\endgroup$ – Emre Apr 24 '12 at 8:54
  • 1
    $\begingroup$ How about LSA? :-) $\endgroup$ – conjugateprior Apr 24 '12 at 12:21
  • 1
    $\begingroup$ A general way to accelerate an EM is called "Aitken accelerator". If precision is not an issue, maybe try moment estimation or generalized moment estimation instead. $\endgroup$ – JohnRos Apr 29 '12 at 19:42
4
$\begingroup$

Newton-Raphson algorithms can often be employed. I am not familiar with pSLA, but it is pretty common to use Newton-Raphson algorithms for latent class models. Newton-Raphson algorithms are a little more troubled by poor initial values than EM, so one strategy is to first use a few iterations (say 20) of the EM and then switch to a Newton-Raphson algorithm. One algorithm that I have had a lot of success with is: Zhu, Ciyou, Richard H. Byrd, Peihuang Lu, and Jorge Nocedal (1997), "Algorithm 778: L-BFGS-B: Fortran subroutines for large-scale bound-constrained optimization," ACM Transactions on Mathematical Software (TOMS) archive, 23 (4), 550-60.

$\endgroup$
4
$\begingroup$

Very similar to the EM algorithm is the MM algorithm which typically exploits convexity rather than missing data in majorizing or minorizing an objective function. You have to check if MM algorithm is applicable for your particular problem, though.

$\endgroup$
3
$\begingroup$

For LDA, "online LDA" is fast alternative to than batch methods like standard EM (http://www.cs.princeton.edu/~blei/papers/HoffmanBleiBach2010b.pdf).

David Blei provides software on his page: http://www.cs.princeton.edu/~blei/topicmodeling.html

$\endgroup$
2
$\begingroup$

Another alternative not mentioned so far in the answers are variational approximations. Although these algorithms are not exactly EM algorithms in all cases, in some cases EM algorithms are limiting cases of Bayesian mean-field variational algorithms. The limit pertains to the limiting case of the hyper-parameters, choosing the limiting values-in some cases-will give you the EM algorithm.

In either case (EM, VB, or even MM algorithms) there are 2 generic ways to speed things up:

(1) reduce the dimensionality of the problem-from a $p$-dim problem to $p$ univariate problems. These are usually coordinate descent algorithms but I've seen MM algorithms that also do this type of speedup.

(2) improving the convergence rate of your EM (or other type) algorithm. In a comment JohnRos mentioned Aitken acceleration. This is from the numerical analysis world but is discussed in the EM book by McLachlan and Krishnan.

There may be others I missed but these seem to be the two big ones.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.