SpectralLeader: Online Spectral Learning for Single Topic Models
Preprint
Abstract
We study the problem of learning a latent variable model from a stream of data. Latent variable models are popular in practice because they can explain observed data in terms of unobserved concepts. These models have been traditionally studied in the offline setting. In the online setting, on the other hand, the online EM is arguably the most popular algorithm for learning latent variable models. Although the online EM is computationally efficient, it typically converges to a local optimum. In this work, we develop a new online learning algorithm for latent variable models, which we call SpectralLeader. SpectralLeader always converges to the global optimum, and we derive a sublinear upper bound on its $n$-step regret in the bag-of-words model. In both synthetic and real-world experiments, we show that SpectralLeader performs similarly to or better than the online EM with tuned hyper-parameters.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- A Spectral Algorithm for Latent Dirichlet AllocationAlgorithmica, 2014
- Tensor Decompositions for Learning Latent Variable Models2012
- Structured Learning and Prediction in Computer VisionFoundations and Trends in Computer Graphics and Vision, 2011
- On-Line Expectation–Maximization Algorithm for latent Data ModelsJournal of the Royal Statistical Society Series B: Statistical Methodology, 2009
- A tutorial on hidden Markov models and selected applications in speech recognitionProceedings of the IEEE, 1989
- The Rotation of Eigenvectors by a Perturbation. IIISIAM Journal on Numerical Analysis, 1970
- Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung)Mathematische Annalen, 1912