A new geometric approach to latent topic modeling and discovery

Weicong Ding, Mohammad H. Rohban, Prakash Ishwar, Venkatesh SaligramaICASSP 2013 · OpenReview

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.

Geometric representation of the topic-word matrix and the probability simplex.

The proposed algorithm follows a structured five-step process:

  1. Normalization: Scaling the word-document matrix so rows represent probability distributions.
  2. Candidate Identification: Using a fast, linear-complexity routine based on random projections to identify potential extreme points.
  3. 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.
  4. Group-Sparse Recovery: Expressing non-novel words as combinations of the discovered topic clusters using a group-sparsity penalty ($\ell_1/\ell_\infty$ norm).
  5. 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.

Performance comparison showing error rates against document length (N) and number of documents (M).

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

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.
BibTeX
@inproceedings{ding2013new,
  author = {Weicong Ding and Mohammad H. Rohban and Prakash Ishwar and Venkatesh Saligrama},
  title = {{A new geometric approach to latent topic modeling and discovery}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2013},
  url = {https://openreview.net/forum?id=RmnajOPJBE},
}
Figure