A Practical Algorithm for Topic Modeling with Provable Guarantees

Abstract

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.

26 pages

References in corpus (3)

• Factoring nonnegative matrices with linear programs
• Learning Topic Models - Going beyond SVD
• Computing a Nonnegative Matrix Factorization -- Provably

Cited by in corpus (19)

• Deep matrix factorizations
• On the Topic of Jets: Disentangling Quarks and Gluons at Colliders
• On Identifiability of Nonnegative Matrix Factorization
• A Fast Hyperplane-Based Minimum-Volume Enclosing Simplex Algorithm for Blind Hyperspectral Unmixing
• Crime Topic Modeling
• Semidefinite Programming Based Preconditioning for More Robust Near-Separable Nonnegative Matrix Factorization
• From Optimizing Engagement to Measuring Value
• Generalized Separable Nonnegative Matrix Factorization
• A Fast Gradient Method for Nonnegative Sparse Regression with Self Dictionary
• A Clustering Approach to Learn Sparsely-Used Overcomplete Dictionaries
• Recovering Joint Probability of Discrete Random Variables from Pairwise Marginals
• Learning Nonlinear Mixtures: Identifiability and Algorithm
• Recent Advances in Text Analysis
• Memory-Efficient Convex Optimization for Self-Dictionary Separable Nonnegative Matrix Factorization: A Frank-Wolfe Approach
• Learning Hidden Markov Models from Pairwise Co-occurrences with Application to Topic Modeling
• Mining DEV for social and technical insights about software development
• Maximum Volume Inscribed Ellipsoid: A New Simplex-Structured Matrix Factorization Framework via Facet Enumeration and Convex Optimization
• Conic Scan-and-Cover algorithms for nonparametric topic modeling
• Geometric Dirichlet Means algorithm for topic inference