Abstract
A new geometrically-motivated algorithm for topic modeling is developed and applied to the discovery of latent “topics” in text and image “document” corpora. The algorithm is based on robustly finding and clustering extreme-points of empirical cross-document word-frequencies that correspond to novel words unique to each topic. In contrast to related approaches that are based on solving non-convex optimization problems using suboptimal approximations, locally-optimal methods, or heuristics, the new algorithm is convex, has polynomial complexity, and has competitive qualitative and quantitative performance compared to the current state-of-the-art approaches on synthetic and real-world datasets.
Introduction
Topic modeling aims to uncover the hidden themes (topics) within massive collections of documents. Traditionally, this is achieved using Probabilistic Latent Semantic Analysis (pLSA) or Latent Dirichlet Allocation (LDA). However, these standard approaches face two major hurdles. First, they typically rely on non-convex optimization, which often leads to algorithms getting stuck in local optima, requiring complex approximations like Variational Bayes or Gibbs sampling. Second, traditional models struggle with the "Small $N$" problem, where short documents provide sparse, noisy empirical word frequencies that make clean topic recovery difficult.
Geometric Methodology
This research frames topic modeling as a Nonnegative Matrix Factorization (NMF) problem ($X \approx \beta\theta$) and leverages a "separability" assumption. This assumption posits that every topic contains at least one "novel" or "anchor" word that appears exclusively in that topic. Geometrically, when word-frequency vectors are normalized and plotted, these novel words become the extreme points (corners) of a convex hull in a high-dimensional word-frequency simplex. All other words, which may appear in multiple topics, fall inside this hull as convex combinations of these corners.
The proposed algorithm follows a structured five-step process:
- Normalization: Scaling the word-document matrix so rows represent probability distributions.
- Candidate Identification: Using a fast, linear-complexity routine based on random projections to identify potential extreme points.
- Subspace Clustering: Applying sparse subspace clustering to group candidate words into $K$ distinct topics, filtering out outliers that are not truly novel to a single topic.
- Group-Sparse Recovery: Expressing non-novel words as combinations of the discovered topic clusters using a group-sparsity penalty ($\ell_1/\ell_\infty$ norm).
- Renormalization: Converting results back into a valid topic-word matrix ($\beta$).
Experimental Evaluation
The researchers evaluated the approach on synthetic data, the Swimmer image benchmark, and real-world text corpora (NIPS and NY Times). On synthetic data, the algorithm consistently demonstrated lower Frobenius norm error than both LDA (Gibbs sampling) and standard NMF.
Key results include:
- Low-Data Resilience: The performance gap was most significant when the number of documents ($M$) or words per document ($N$) was small, scenarios where traditional models often fail.
- Qualitative Success: In the Swimmer dataset, the algorithm recovered all 16 ground-truth limb positions perfectly, whereas LDA and standard NMF produced noisy or blurred estimates.
- Thematic Clarity: On real-world datasets, the algorithm extracted clear, recognizable thematic clusters, such as an "IC Design" topic in the NIPS corpus.
Discussion and Conclusion
By prioritizing geometry over probability, this approach transforms a messy statistical inference problem into a structured geometric search. While the "anchor word" assumption is central to the model, it is frequently satisfied in practice (e.g., specific jargon in technical fields). The use of clustering rather than simple extreme-point selection makes the algorithm resilient to the noise inherent in short documents. Future work may address the computational intensity of the sparse subspace clustering step for extremely large vocabularies and further explore performance in cases where topics overlap heavily without unique anchor words.
Summary updated