Spectral Methods for Supervised Topic Models

Yining Wang, Jun ZhuNeurIPS 2014 · OpenReview

This paper, "Spectral Methods for Supervised Topic Models" by Yining Wang and Jun Zhu, introduces a provably efficient way to learn Supervised Latent Dirichlet Allocation (sLDA) models. By moving away from traditional iterative search methods and toward spectral tensor decomposition, the authors provide an algorithm that is not only faster but also avoids the common trap of local optima.

TL;DR

The authors present Spectral-sLDA, the first spectral decomposition algorithm for supervised topic models that is both computationally efficient and provably correct. It replaces slow, local-search-based inference (like Gibbs sampling) with a method based on "moment matching" that can be 15x faster while providing theoretical guarantees on parameter recovery.

What Problem Does This Paper Address?

Topic models like LDA are usually unsupervised—they find patterns in text but don't care about external labels. Supervised LDA (sLDA) adds a "response variable" (like a star rating for a movie review) to the mix, allowing the model to find topics that are specifically predictive of that response.

Graphical models for sLDA variants, illustrating the relationship between latent topics and the response variable.

Traditionally, sLDA is trained using Maximum Likelihood Estimation (MLE) via Variational Inference or Gibbs Sampling. These methods have two major flaws:

  1. Local Optima: They are "local search" methods, meaning they can get stuck in sub-optimal solutions depending on where they start.
  2. Computational Cost: They require many passes over the data, making them slow for massive datasets.

While "spectral methods" (which use linear algebra and tensor decomposition to find parameters) had been successful for unsupervised LDA, applying them to supervised models was tricky. Specifically, it was hard to "match" the discovered topics with their corresponding regression weights, especially if multiple topics had similar effects on the response variable.

Methods

The authors propose a novel algorithm called Spectral-sLDA. The core idea is to estimate the model parameters by looking at the "moments" of the data—essentially the statistics of how often words appear alone ($M_1$), in pairs ($M_2$), or in triplets ($M_3$).

Key Innovations:

  • The $M_y$ Moment: The authors define a new empirical moment, $M_y$, which incorporates the response variable $y$. This moment captures the relationship between word co-occurrences and the supervised signal.
  • Power Update Method: Instead of trying to decompose $M_y$ directly (which leads to the "matching problem"), they first recover the topics using standard tensor methods on word co-occurrences. They then use a "power update" to project the supervised signal onto these recovered topics. This ensures the regression weights are correctly assigned to the right topics, even if those weights are identical.
  • Computational Efficiency: They utilize a "speed-up trick" that avoids explicitly constructing massive tensors. This reduces the complexity from $O(V^3)$ (where $V$ is vocabulary size) to something that scales linearly with the number of documents and topics.

Datasets

The algorithm was evaluated on:

  1. Synthetic Data: Used to verify the "sample complexity" (how much data is needed to reach a certain accuracy) and to prove the algorithm converges to the true parameters as data increases.
  2. Amazon Movie Reviews: A massive real-world dataset containing ~7.9 million reviews. The goal was to predict the 1-5 star rating based on the review text.

Key Insights and Ideas

  • Provable Correctness: Unlike Gibbs sampling, which might never find the "true" model, Spectral-sLDA is "provably correct." Given enough documents, it is guaranteed to recover the true parameters with high probability.
  • Identifiability: The paper derives a sufficient condition for when an sLDA model can actually be uniquely identified from data—a fundamental theoretical contribution.
  • Hybrid Potential: The authors found that while spectral methods are fast, they aren't always as "clean" as iterative methods on real-world (non-synthetic) data. However, using the spectral result as a starting point (initialization) for a Gibbs sampler yields the best of both worlds: the speed and global view of spectral methods combined with the refinement of MCMC.

Key Results

  • Speed: Spectral-sLDA is significantly faster than Gibbs sampling. On the Amazon dataset, it was over 15 times faster for large document collections.
  • Accuracy: On synthetic data, the reconstruction error for topics ($\mu$), regression weights ($\eta$), and Dirichlet priors ($\alpha$) dropped sharply as the number of training documents increased, validating the theoretical bounds.
Reconstruction error for model parameters decreases sharply as the number of training documents increases.
  • Performance: When used as an initialization for a hybrid approach, the model achieved better predictive $R^2$ and lower negative log-likelihood than standard Gibbs sampling, proving it helps avoid local optima.

Limitations and Future Work

  • Full Rank Requirement: The algorithm requires the topic-word matrix to be full rank. In the Amazon experiments, the authors noted that if they tried to find more than 8 topics, performance deteriorated. This suggests the "intrinsic rank" of the data limits how many topics the spectral method can reliably extract.
  • Hyperparameter Sensitivity: The method assumes the sum of the Dirichlet priors ($\alpha_0$) is known beforehand. While common in literature, estimating this directly from the spectral moments remains an open challenge.
  • Non-Gaussian Noise: The current model assumes Gaussian noise for the response variable. Extending this to other distributions (like Poisson for count data) would broaden its applicability.

Summary updated

Abstract

Supervised topic models simultaneously model the latent topic structure of large collections of documents and a response variable associated with each document. Existing inference methods are based on either variational approximation or Monte Carlo sampling. This paper presents a novel spectral decomposition algorithm to recover the parameters of supervised latent Dirichlet allocation (sLDA) models. The Spectral-sLDA algorithm is provably correct and computationally efficient. We prove a sample complexity bound and subsequently derive a sufficient condition for the identifiability of sLDA. Thorough experiments on a diverse range of synthetic and real-world datasets verify the theory and demonstrate the practical effectiveness of the algorithm.
BibTeX
@inproceedings{wang2014spectral,
  author = {Yining Wang and Jun Zhu},
  title = {{Spectral Methods for Supervised Topic Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=HyW1AIW_-S},
}
Figure