Source-linked AI summary
Learning Topic Models - Going beyond SVD
Sanjeev Arora, Rong Ge, Ankur Moitra
TL;DR
Topic-model learning needs to recover actual topics from documents that mix multiple topics, whereas existing SVD-based methods impose restrictive assumptions or recover only topic spans. The paper uses separable NMF to obtain a polynomial-time learner for the topic matrix, with recovery of additional distributional structure in some cases and extension to correlated-topic models.
Problem
Existing SVD-based approaches either assume each document contains one topic or recover only the span of the topics instead of the topics themselves.
Method
The paper applies nonnegative matrix factorization under separability, using documents as sampled distributions generated by an unknown topic matrix A and topic-mixture matrix W.
Results
The paper gives a polynomial-time algorithm that learns A to additive error ǫ, can learn R(T) with additional documents, and extends to correlated-topic models.
Takeaways & Limitations
The approach recovers topic vectors rather than only their span and applies to models with topic-topic correlations, including CTM and PAM.
Takeaways & Limitations
The method assumes separability through anchor words, and its analysis notes that some distributional parameters cannot generally be recovered; stronger multi-anchor separability remains an open problem.
Abstract
from arXiv · showhide
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.
1 Introduction
Topic modeling represents documents as mixtures of word-distribution topics, but existing SVD-based methods either restrict documents to one topic or recover only the topics’ span. This paper develops an NMF-based polynomial-time approach that recovers topic structure under separability and extends to correlated-topic models.
- Documents are modeled as convex combinations of a small number of topic vectors, each a distribution over words.
- Maximum-likelihood fitting is NP-hard, motivating provable algorithms for recovering model parameters from data generated by the topic model.
- The paper studies learning an unknown topic matrix A and the generating-distribution parameters for W from samples of document distributions AW.
- SVD-based approaches either assume one topic per document or recover only the span of the topic vectors, rather than the topics themselves.
- Its NMF algorithm addresses highly noisy document vectors, recovers A despite the impossibility of generally recovering W, and operates under separability based on anchor words.
- The main theorem gives a polynomial-time learner with additive-error recovery of A and, with additional samples, the topic-topic covariance matrix R(T).
- The method also extends to correlated-topic models such as the Correlated Topic Model and Pachinko Allocation Model, even when T is not identifiable.
2 Tools for (Noisy) Nonnegative Matrix Factorization
This section develops condition measures and robust NMF tools for recovering nonnegative factors under separability, including a variant that identifies almost anchor words from noisy data.
- Condition measures: The ℓ1 condition number Γ(B) measures separation among normalized nonnegative rows and extends by row normalization when needed.For disjoint row supports, Γ(B)=1; it also relates to standard singular-value bounds through ℓ1 and ℓ2 norms.
- Condition measures: Robust simpliciality requires every column of A to remain at least β away in ℓ1 distance from the convex hull of the other columns.This provides a geometric separation condition for topic matrices.
- Condition measures: If A is p-separable, then A^T has ℓ1 condition number at least p, and suitable row normalization implies robust simpliciality with parameter Γ(A^T)/2.These relationships connect anchor-word separability to the conditioning needed by the recovery analysis.
- Condition measures: The composition lemma gives Γ(BC) at least the product of Γ(B) and Γ(C), yielding γp/2-robust simpliciality for R(T)A^T.The result combines the topic-separation parameter p with the covariance conditioning parameter γ.
- Noisy NMF: Unlike the earlier robust NMF guarantee, the paper targets almost anchor words directly rather than estimates close to anchor rows in ℓ1 norm.This change in recovery objective is presented as enabling better bounds for the paper’s application.
- Noisy NMF: Robust NMF recovers r almost anchor words in polynomial time when A is separable, W is γ-robustly simplicial, and rowwise noise is below γ/100.Each selected row corresponds to a row of M that is a mixture of one target row and a convex combination of the others, with contamination O(ε/γ).
3 Algorithm for Learning a Topic Model: Proof of Theorem 1.4
The algorithm converts noisy document data into a word-word Gram matrix whose limiting structure factors through the topic matrix and topic covariance, then uses anchor words to recover both.
- Algorithmic idea: Separability makes anchor-word rows expose scaled rows of the document-topic factor, so identifying anchors enables recovery of the remaining factors.If anchor words are known, the corresponding rows of AB directly reveal rows of B up to scaling.
- Algorithmic idea: The algorithm forms the empirical Gram matrix M M^T from the noisy term-by-document matrix, which converges to a matrix involving topic-topic second moments.This transformation reduces the impact of document-level sampling noise before applying robust NMF.
- Idealized recovery: In the idealized case Q=A R(T) A^T, treating Q as A times R(T)A^T lets NMF identify anchor words and then recover R(T)A^T and A.The same anchor words are used first for factor identification and then for recovery of the topic matrix.
- Idealized recovery: With true anchor words, the recovery procedure exactly outputs A and R when Q exactly equals A R A^T.The method extracts submatrices D R D and D R A^T, then solves for the diagonal scaling matrix D.
- Approximate recovery: Almost anchor words yield bounded reconstruction error: each column of A has ℓ1 error at most 6ε and R has additive error at most 8ε in the idealized noisy-anchor setting.The bounds apply when the deviation matrix satisfies the stated ℓ1 condition ε<1/10.
- Approximate recovery: For the general procedure, each entry of A and the corresponding error measure for R are bounded by O(ε + (raε^2/p^3 + ε_1r/p^2)/γ).The bound combines approximation, scaling, and perturbation terms governed by separability and covariance conditioning.
- Error analysis: The analysis estimates Q against empirical R=(1/m)WW^T rather than R(T), because R(T) cannot be learned from only one document even as document length grows.Using empirical R permits an inverse-polynomial relationship with document length N and improves performance when documents contain more words.
- Error analysis: Concentration bounds show that every entry of Q deviates from its expectation by at most ε_Q with probability much smaller than 1/n^2.The argument uses Bernstein inequalities after bounding entry variances and higher moments.
4 The Dirichlet Subcase
The Dirichlet subcase shows that the topic matrix and Dirichlet parameters can be recovered from sampled documents when the topic matrix is separable. The approach robustly recovers Dirichlet parameters from the covariance matrix and runs in polynomial time.
- The algorithm robustly recovers Dirichlet parameters from the covariance matrix R(T).
- The Dirichlet parameter algorithm assumes max αi/min αi = a and total parameter sum α0.
- Theorem 4.1 states that a polynomial-time algorithm learns A with high probability to additive error ε from documents sampled from the LDA model.
- The method bounds the ℓ1-condition number of the Dirichlet covariance matrix before recovering distribution parameters.
- The Dirichlet algorithm estimates parameters with error at most O(ar(α0 + 1)εR) when R(α) has ℓ1 error εR.
5 Obtaining Almost Anchor Words
The algorithm identifies almost anchor words from a perturbed matrix by testing convex-hull relationships among rows. Separability supplies canonical rows near topic vectors, while robust simpliciality enables polynomial-time recovery under perturbation.
- When ε < γ/100, a polynomial-time algorithm finds r almost anchor words from a perturbed matrix.
- A (δ, ε)-close relation requires an ε-accurate convex combination placing at least 1 − δ weight on the designated row.
- Separability creates canonical rows within ε in ℓ1 distance of the topic rows Wᵢ.
- The algorithm tests whether each row is close to the convex hull of rows outside its neighborhood to identify robust loners.
- Canonical rows are robust loners, whereas rows whose topic coefficients remain below 1 − 10ε/γ cannot be robust loners.
- Connected components of close robust loners partition them by the topic row they approximate, yielding one almost anchor word per component.
6 Maximum Likelihood Estimation is Hard
The paper proves that maximum-likelihood estimation for topic models is computationally hard by reducing MIN-BISECTION to the two-topic TM-MLE problem. The reduction remains hard even when the topic matrix is required to be separable.
- TM-MLE asks for the topic matrix with the largest probability of generating observed documents under a uniform Dirichlet distribution.
- Theorem 6.2 gives a polynomial-time reduction from MIN-BISECTION to TM-MLE with r = 2 topics.
- The reduction creates repeated-word documents for each vertex and two-word documents for each graph edge.
- Candidate maximum-likelihood solutions are constrained to have nearly equal row ℓ1 norms and concentrate almost all row weight in one topic.
- Among canonical solutions, maximizing the objective corresponds to finding a minimum bisection because cut edges change the objective by log 2.
- Computing the MLE remains NP-hard even when the topic matrix is known and required to be separable.
7 Conclusions
The paper identifies open directions concerning the practicality of its algorithm and the role of separability in polynomial-time learning.
- The practicality of versions of the algorithm remains under investigation.
- Real-life topic matrices may satisfy stronger separability assumptions, including many anchor words per topic.
- Leveraging multiple anchor words per topic in the algorithm remains an open problem.
- Whether separability is necessary for polynomial-time learning remains unresolved.
- The paper suggests average-case intractability may be more plausible than NP-completeness for non-separable topic matrices.