A Practical Algorithm for Topic Modeling with Provable Guarantees

By Sanjeev Arora, Rong Ge, Yoni Halpern, David Mimno, Ankur Moitra, David A. Sontag, Yichen Wu, Michael Zhu. 2012

462 citations recorded by the source corpus.

Topic models provide a useful method for dimensionality reduction and exploratory data analysis in large text corpora. Most approaches to topic model inference have been based on a maximum likelihood objective. Efficient algorithms exist that approximate this objective, but they have no provable guarantees. Recently, algorithms have been introduced that provide provable bounds, but these algorithms are not practical because they are inefficient and not robust to violations of model assumptions. In this paper we present an algorithm for topic model inference that is both provable and practical. The algorithm produces results comparable to the best MCMC implementations while running orders of magnitude faster.

Subfields: Artificial Intelligence, Natural Language Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Natural Language Processing

Citations in the corpus

Beyond CCA: Moment Matching for Multi-View Models (2016, neutral): “…1996; Comon & Jutten, 2010), mixtures of Gaus-sians (e.g., Arora & Kannan, 2005; Hsu & Kakade, 2013), latent Dirichlet allocation and topic models (Arora et al., 2012; 2013; Anandkumar et al., 2012; Podosinnikova et al., 2015), supervised topic models (Wang & Zhu, 2014), Indian buffet process…”
Rethinking LDA: Moment Matching for Discrete ICA (2015, neutral): “Semi-synthetic data are constructed by analogy with [29]: (1) the LDA parameters D and c are learned from the real datasets with variational inference and (2) toy data are sampled from a model of interest with the given parameters D and c.”
How to make causal inferences using texts (2018, unknown): “Roberts, Stewart and Tingley (2016) advocate a deterministic initialization based on the spectral method of moments (Arora et al., 2013) which we refer to below as the spectral initialization.”
Variance Reduction for Faster Non-Convex Optimization (2016, methodology): “For some models, probabilistic and other assumptions on the input can be used to give specially designed polynomial-time algorithms [2, 3, 14].”
Supervised topic models for clinical interpretability (2016, background): “To remedy this, future work can explore better initializations such as tensor methods (Arora et al., 2013).”
Exact Recovery of Sparsely Used Overcomplete Dictionaries (2013, background): “There are various recent works providing guaranteed methods for learning topic models, e.g [1, 6, 5, 4].”
Learning Sparsely Used Overcomplete Dictionaries via Alternating Minimization (2013, methodology): “[3], we guarantee exact recovery of the true solution (A∗, X∗) when the alternating procedure is initialized with the output of [1] or [3].”
Spectral Methods for Supervised Topic Models (2014, background): “Although spectral decomposition (as well as NMF) methods have achieved increasing success in recovering latent variable models, their applicability is quite limited.”
Anchored Correlation Explanation: Topic Modeling with Minimal Domain Knowledge (2016, methodology): “Although the original algorithm proposed by Arora et. al and subsequent improvements to their approach ﬁnd these anchor words automatically (Arora et al., 2013; Lee and Mimno, 2014), recent adaptations allow manual insertion of anchor words and other metadata (Nguyen et al., 2014; Nguyen et al.,…”
Applications of Topic Models (2017, background): “Novel approaches view topic model inference as a factorization of a co-occurence matrix [Arora et al., 2013] or as a spectral decomposition [Anandkumar et al.”
Computing a nonnegative matrix factorization -- provably (2011, background): “[5] and Gillis and Vavasis [17] recently gave a purely combinatorial algorithm, thus removing the need to use linear programming altogether.”
A Signal Processing Perspective on Hyperspectral Unmixing: Insights from Remote Sensing (2014, methodology): “In machine learning, SPA has been used for document classification where the pure pixel assumption is referred to as the separability assumption and requires that, for each topic, there exists at least one word used only by that topic; see [22] and the references therein.”
An analysis of the coherence of descriptors in topic modeling (2015, methodology): “Although it has been used in multiple domains, it is also applicable to topic modeling (Arora et al., 2012).”
Leveraging Just a Few Keywords for Fine-Grained Aspect Detection Through Weakly Supervised Co-Training (2019, methodology): “(2017) use LDA with fixed topic-word distributions, which are learned using seed words as “anchors” for topic inference (Arora et al., 2013).”
Topic Modeling using Topics from Many Domains, Lifelong Learning and Big Data (2014, background): “Recently, it has become popular to use Topic Coherence to evaluate topic models (Arora et al., 2013).”