Skip to main content

Learning topic models - Going beyond SVD

Publication ,  Journal Article
Arora, S; Ge, R; Moitra, A
Published in: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
December 1, 2012

Topic Modeling is an approach used for automatic comprehension and classification of data in a variety of settings, and perhaps the canonical application is in uncovering thematic structure in a corpus of documents. A number of foundational works both in machine learning and in theory have suggested a probabilistic model for documents, whereby documents arise as a convex combination of (i.e. distribution on) a small number of topic vectors, each topic vector being a distribution on words (i.e. a vector of word-frequencies). Similar models have since been used in a variety of application areas, the Latent Dirichlet Allocation or LDA model of Blei et al. is especially popular. Theoretical studies of topic modeling focus on learning the model's parameters assuming the data is actually generated from it. Existing approaches for the most part rely on Singular Value Decomposition (SVD), and consequently have one of two limitations: these works need to either assume that each document contains only one topic, or else can only recover the {\em span} of the topic vectors instead of the topic vectors themselves. This paper formally justifies Nonnegative Matrix Factorization (NMF) as a main tool in this context, which is an analog of SVD where all vectors are nonnegative. Using this tool we give the first polynomial-time algorithm for learning topic models without the above two limitations. The algorithm uses a fairly mild assumption about the underlying topic matrix called separability, which is usually found to hold in real-life data. Perhaps the most attractive feature of our algorithm is that it generalizes to yet more realistic models that incorporate topic-topic correlations, such as the Correlated Topic Model (CTM) and the Pachinko Allocation Model (PAM). We hope that this paper will motivate further theoretical results that use NMF as a replacement for SVD - just as NMF has come to replace SVD in many applications. © 2012 IEEE.

Duke Scholars

Altmetric Attention Stats
Dimensions Citation Stats

Published In

Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

DOI

ISSN

0272-5428

Publication Date

December 1, 2012

Start / End Page

1 / 10
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Arora, S., Ge, R., & Moitra, A. (2012). Learning topic models - Going beyond SVD. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 1–10. https://doi.org/10.1109/FOCS.2012.49
Arora, S., R. Ge, and A. Moitra. “Learning topic models - Going beyond SVD.” Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, December 1, 2012, 1–10. https://doi.org/10.1109/FOCS.2012.49.
Arora S, Ge R, Moitra A. Learning topic models - Going beyond SVD. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. 2012 Dec 1;1–10.
Arora, S., et al. “Learning topic models - Going beyond SVD.” Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, Dec. 2012, pp. 1–10. Scopus, doi:10.1109/FOCS.2012.49.
Arora S, Ge R, Moitra A. Learning topic models - Going beyond SVD. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS. 2012 Dec 1;1–10.

Published In

Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

DOI

ISSN

0272-5428

Publication Date

December 1, 2012

Start / End Page

1 / 10