The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
Learning Topic Models -- Going beyond SVD
Abstract
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Maximum Likelihood from Incomplete Data Via the EM Algorithm
Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1977.tb01600.x · Cited by 50,444
(2003) · Journal of Machine Learning Research · doi:10.5555/944919.944937 · Cited by 32,337
UCI Machine Learning Repository
Asuncion, A. (2007) · Medical Entomology and Zoology · Cited by 24,155
Learning the parts of objects by non-negative matrix factorization
Lee, D. D., & Seung, H. S. (1999) · Nature · doi:10.1038/44565 · Cited by 13,868
Indexing by latent semantic analysis
Deerwester, S., Dumais, S. T., Furnas, G. W., Landauer, T. K., & Harshman, R. (1990) · Journal of the American Society for Information Science · doi:10.1002/(sici)1097-4571(199009)41:6<391::aid-asi1>3.0.co;2-9 · Cited by 12,751
ALGORITHMS FOR NON-NEGATIVE MATRIX FACTORIZATION
Lee, D. D., & Seung, H. S. (2000) · Cited by 7,952
Independent Component Analysis
(2004) · Independent Component Analysis · doi:10.7551/mitpress/3717.003.0014 · Cited by 7,903
Blei, D. M. (2012) · Communications of the ACM · doi:10.1145/2133806.2133826 · Cited by 5,516
Independent Component Analysis
Hyvärinen, A., Karhunen, J., & Oja, E. (2001) · Wiley eBooks · doi:10.1002/0471221317 · Cited by 5,007
ALGORITHMS FOR NON-NEGATIVE MATRIX FACTORIZATION
Seung, D., & Lee, L.-W. (2001) · Cited by 4,753
An Introduction to Variational Methods for Graphical Models
Jordan, M. I., Ghahramani, Z., Jaakkola, T. S., & Saul, L. K. (1999) · Machine Learning · doi:10.1023/a:1007665907178 · Cited by 3,791
(2000) · CrossRef Listing of Deleted DOIs · doi:10.1162/jmlr.2003.3.4-5.993 · Cited by 3,024
Graphical Models, Exponential Families, and Variational Inference
Wainwright, M. J., & Jordan, M. I. (2007) · now publishers, Inc. eBooks · doi:10.1561/9781601981851 · Cited by 2,959
Mixture Densities, Maximum Likelihood and the EM Algorithm
Redner, R. A., & Walker, H. F. (1984) · SIAM Review · doi:10.1137/1026034 · Cited by 2,693
Non-negative matrix factorization with sparseness constraints
Hoyer, P. O. (2004) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0408058 · Cited by 2,591
Blei, D. M., & Lafferty, J. D. (2006) · Proceedings of the 23rd international conference on Machine learning - ICML '06 · doi:10.1145/1143844.1143859 · Cited by 2,386
Probabilistic Latent Semantic Analysis
Hofmann, T. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1301.6705 · Cited by 2,047
Document clustering based on non-negative matrix factorization
Xu, W., Liu, X., & Gong, Y. (2003) · Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval · doi:10.1145/860435.860485 · Cited by 1,860
A correlated topic model of Science
Blei, D. M., & Lafferty, J. (2018) · doi:10.1184/r1/6587330.v1 · Cited by 1,088
A correlated topic model of Science
Blei, D. M., & Lafferty, J. D. (2007) · The Annals of Applied Statistics · doi:10.1214/07-aoas114 · Cited by 953
Latent semantic indexing: a probabilistic analysis
Papadimitriou, C. H., Tamaki, H., Raghavan, P., & Vempala, S. (1998) · Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems · doi:10.1145/275487.275505 · Cited by 863
When Does Non-Negative Matrix Factorization Give a Correct Decomposition into Parts?
Donoho, D. L., & Stodden, V. (2004) · doi:10.7916/d88d05n7 · Cited by 685
Pachinko allocation: DAG-structured mixture models of topic correlations
Li, W., & McCallum, A. (2006) · Proceedings of the 23rd international conference on Machine learning - ICML '06 · doi:10.1145/1143844.1143917 · Cited by 609
On the Complexity of Nonnegative Matrix Factorization
Vavasis, S. A. (2010) · SIAM Journal on Optimization · doi:10.1137/070709967 · Cited by 588
Spectral partitioning of random graphs
McSherry, F. (2001) · Proceedings 42nd IEEE Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959929 · Cited by 584
Latent Semantic Indexing: A Probabilistic Analysis
Papadimitriou, C. H., Raghavan, P., Tamaki, H., & Vempala, S. (2000) · Journal of Computer and System Sciences · doi:10.1006/jcss.2000.1711 · Cited by 556
Azar, Y., Fiat, A., Karlin, A., McSherry, F., & Saia, J. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380859 · Cited by 289
Computing a nonnegative matrix factorization -- provably
Arora, S., Ge, R., Kannan, R., & Moitra, A. (2012) · Proceedings of the forty-fourth annual ACM symposium on Theory of computing · doi:10.1145/2213977.2213994 · Cited by 280
Self-citationA Method of Moments for Mixture Models and Hidden Markov ModelsPreprint
Anandkumar, A., Hsu, D., & Kakade, S. M. (2012) · arXiv (Cornell University) · doi:10.48550/arxiv.1203.0683 · Cited by 229
Pachinko allocation: dag-structured mixture models of topic correlations
McCallum, A., & Li, W. (2007) · Cited by 143
Recommendation systems: a probabilistic analysis
Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1998.743517 · Cited by 100
Complexity of Inference in Latent Dirichlet Allocation
Sontag, D. A., & Roy, D. M. (2011) · Cited by 85
The Inverse Moment Problem for Convex Polytopes
Gravin, N., Lasserre, J. B., Ṗasechnik, D. V., et al. (2012) · Discrete & Computational Geometry · doi:10.1007/s00454-012-9426-4 · Cited by 60
Pachinko Allocation: DAG-Structured Mixture Models of Topic Correlations
Li, W., & Mccallum, A. (2006) · ScholarWorks@UMassAmherst (University of Massachusetts Amherst) · Cited by 46
Recommendation Systems: A Probabilistic Analysis
Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. (2001) · Journal of Computer and System Sciences · doi:10.1006/jcss.2001.1757 · Cited by 40
Using mixture models for collaborative filtering
Kleinberg, J. M., & Sandler, M. (2007) · Journal of Computer and System Sciences · doi:10.1016/j.jcss.2007.04.013 · Cited by 27
Cited by
Tensor decompositions for learning latent variable models
(2012) · arXiv (Cornell University) · doi:10.5555/2627435.2697055 · Cited by 779
Self-citationA Model of Text for Experimentation in the Social Sciences
Roberts, M. E., Stewart, B. M., & Airoldi, E. M. (2016) · Journal of the American Statistical Association · doi:10.1080/01621459.2016.1141684 · Cited by 728
An analysis of the coherence of descriptors in topic modeling
O’Callaghan, D., Greene, D., Carthy, J., & Cunningham, P. (2015) · Expert Systems with Applications · doi:10.1016/j.eswa.2015.02.055 · Cited by 370
Günther, F., Rinaldi, L., & Marelli, M. (2019) · Perspectives on Psychological Science · doi:10.1177/1745691619861372 · Cited by 341
UTOPIAN: User-Driven Topic Modeling Based on Interactive Nonnegative Matrix Factorization
Choo, J., Lee, C., Reddy, C. K., & Park, H. (2013) · IEEE Transactions on Visualization and Computer Graphics · doi:10.1109/tvcg.2013.212 · Cited by 262
Metadata
- Authors
- Arora, S., Ge, R., & Moitra, A.
- Venue
- 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science
- Publisher
- IEEE
- Published
- 2012-10
- Pages
- 1-10
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2128521126
- Cited by
- 302
- References
- 36
- FWCI
- 16.99
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.