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 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. A compelling feature of our algorithm is that it generalizes to models that incorporate topic-topic correlations, such as the Correlated Topic Model and the Pachinko Allocation Model. 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.

References in corpus (2)

• Probabilistic Latent Semantic Analysis
• The inverse moment problem for convex polytopes

Cited by in corpus (31)

• A Spectral Algorithm for Latent Dirichlet Allocation
• A Practical Algorithm for Topic Modeling with Provable Guarantees
• Successive Nonnegative Projection Algorithm for Robust Nonnegative Blind Source Separation
• On the Topic of Jets: Disentangling Quarks and Gluons at Colliders
• Mixture Proportion Estimation via Kernel Embedding of Distributions
• New Algorithms for Learning Incoherent and Overcomplete Dictionaries
• How Many Topics? Stability Analysis for Topic Models
• Provable Alternating Gradient Descent for Non-negative Matrix Factorization with Strong Correlations
• Recent Advances in Text Analysis
• Memory-Efficient Convex Optimization for Self-Dictionary Separable Nonnegative Matrix Factorization: A Frank-Wolfe Approach
• Low-dimensional Embeddings for Interpretable Anchor-based Topic Inference
• A Topic Modeling Approach to Ranking
• Robustness Analysis of Preconditioned Successive Projection Algorithm for General Form of Separable NMF Problem
• Beyond Log-concavity: Provable Guarantees for Sampling Multi-modal Distributions using Simulated Tempering Langevin Monte Carlo
• Anchored Discrete Factor Analysis
• Smoothed Analysis of Online and Differentially Private Learning
• Memory-Efficient Topic Modeling
• Combinatorial Topic Models using Small-Variance Asymptotics
• Real-time Burst Photo Selection Using a Light-Head Adversarial Network
• Learning Mixtures of Arbitrary Distributions over Large Discrete Domains
• Stability of Topic Modeling via Matrix Factorization
• Generalized Topic Modeling
• Spectral Clustering by Ellipsoid and Its Connection to Separable Nonnegative Matrix Factorization
• Spectral Learning for Supervised Topic Models
• Topic Modeling of Behavioral Modes Using Sensor Data
• Fast moment estimation for generalized latent Dirichlet models
• Convergence Rates of Latent Topic Models Under Relaxed Identifiability Conditions
• Guaranteed Model Order Estimation and Sample Complexity Bounds for LDA
• Spectral Sequence Motif Discovery
• Topic Diffusion Discovery based on Sparseness-constrained Non-negative Matrix Factorization
• Prior-aware Dual Decomposition: Document-specific Topic Inference for Spectral Topic Models