Learning Topic Models -- Going beyond SVD

By Sanjeev Arora, Rong Ge, Ankur Moitra. 2012

459 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, General Social Sciences

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 General Social Sciences

Citations in the corpus

Beyond CCA: Moment Matching for Multi-View Models (2016, neutral): “, 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 inference (Tung & Smola, 2014), stochastic languages (Balle et ”
Robust Estimators in High Dimensions without the Computational Intractability (2016, background): “…learning several fundamental classes of high-dimensional distributions: (1) a single Gaussian, (2) a product distribution on the hypercube, (3) mixtures of two product distributions (under a natural balancedness condition), and (4) mixtures of k Gaussians with identical spherical covariances.”
Recovery Guarantees for One-hidden-layer Neural Networks (2017, background): “Without making any assumptions, those non-convex problems are intractable (Arora et al., 2012a; Gillis & Vavasis, 2015; Song et al., 2017a; Gillis & Glineur, 2011; Razen-shteyn et al., 2016; Sontag & Roy, 2011; Hardt & Moitra, 2013; Arora et al., 2012b; Yi et al., 2014).”
Efficient Representations for Lifelong Learning and Autoencoding (2014, methodology): “We give an efficient algorithm for finding the fewest product-based metafeatures for a given set of target monomials under an “anchor-variable” assumption analogous to the anchor-word assumption of [2], and prove bounds on its performance for learning a series of target functions arriving online.”
Discriminative Improvements to Distributional Sentence Similarity (2013, background): “…recent work has demonstrated the robustness of nonnegative matrix factorization (NMF; Lee and Seung, 2001) for text mining tasks (Xu et al., 2003; Arora et al., 2012); the difference from SVD is the addition of a non-negativity constraint in the latent representation based on non-orthogonal…”
Provable Bounds for Learning Some Deep Representations (2013, background): “, for which learning algorithms with provable guarantees were given (Hsu et al., 2012; Moitra & Valiant, 2010; Hsu & Kakade, 2013; Arora et al., 2012; Anandkumar et al., 2012).”
Tensor decompositions for learning latent variable models (2012, methodology): “For some models such as latent trees [Roc06] and topic models [AGM12], maximum likelihood estimation is NP-hard, which suggests that other estimation approaches may be more attractive.”
Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method (2014, methodology): “Some recent works providing algorithms and analysis include [AFH + 12, AGM12, BCMV14, BCV14].”
A Model of Text for Experimentation in the Social Sciences (2016, background): “While exactly characterizing the theoretical complexity of the optimization problem is beyond the scope of this article, we note that inference even in simple topic models has been shown to be NP-hard (Arora et al. 2012).”
Provable Alternating Gradient Descent for Non-negative Matrix Factorization with Strong Correlations (2017, unknown): “For theoretical analysis, (Arora et al., 2012b) provided a ﬁxed-parameter tractable algo-rithm for NMF using algebraic equations.”
UTOPIAN: User-Driven Topic Modeling Based on Interactive Nonnegative Matrix Factorization (2013, background): “Nonnegative matrix factorization (NMF) [30, 25] has been one of the most active research areas in data mining and machine learning fields, and it has been applied in the context of topic modeling mainly from a computational perspective [3].”
Recovery Guarantee of Non-negative Matrix Factorization via Alternating Updates (2016, methodology): “For example, [AGM12] and [AGH13] assume that the topic-word matrix contains “anchor words”.”
New Algorithms for Learning Incoherent and Overcomplete Dictionaries (2013, methodology): “Our goal is to design an algorithm for this problem with provable guarantees in the same spirit as recent work on nonnegative matrix factorization [7], topic models [8, 6] and mixtures models [43, 12].”
Computing a nonnegative matrix factorization -- provably (2011, methodology): “[5] gave a probabilistic variant of the algorithm in [4] which inherits its provable guarantees, but is additionally highly practical.”
Contextual Bandits with Latent Confounders: An NMF Approach (2016, background): “have shown that if the matrix is separable and has some robustness properties [4], then NMF is solvable efficiently.”
Sample-Optimal Parametric Q-Learning Using Linearly Additive Features (2019, background): “The notion of “anchor” is a natural analog of the anchor word condition from topic modeling (Arora et al., 2012) and nonnegative matrix factorization (Donoho & Stodden, 2004).”
A Spectral Algorithm for Latent Dirichlet Allocation (2012, methodology): “Furthermore, Arora et al. (2012) provides results for certain correlated topic models.”