Beyond LDA: A Unified Framework for Learning Latent Normalized Infinitely Divisible Topic Models through Spectral Methods

Forough Arabshahi, Animashree AnandkumararXiv 2016 · OpenReview

TL;DR

This paper introduces a new class of topic models called Latent Normalized Infinitely Divisible (NID) topic models, which generalize the popular Latent Dirichlet Allocation (LDA) by allowing for arbitrary correlations between topics. The authors develop a novel spectral method that can learn these models efficiently using only third-order moments, achieving guaranteed recovery with polynomial complexity.

What Problem Does This Paper Address?

Topic models are powerful tools for uncovering hidden themes in large collections of text documents. The most widely used topic model is Latent Dirichlet Allocation (LDA). However, LDA has a significant limitation: it can only model negative correlations between topics, meaning topics tend to be distinct and not co-occurring. This is due to the assumption that topic proportions in a document are drawn from a Dirichlet distribution. In reality, topics can have complex, arbitrary correlations (both positive and negative), which LDA cannot capture. Existing methods to address this often have limited correlation structures or lack guaranteed learning algorithms. This paper aims to bridge this gap by proposing a more flexible topic model that can capture arbitrary topic correlations and providing a provably correct and efficient learning algorithm for it.

Methods

The core of this paper lies in two main contributions:

  • Latent Normalized Infinitely Divisible (NID) Topic Models: The authors propose a new generative model where the latent topic proportions for each document are drawn from a Normalized Infinitely Divisible (NID) distribution. NID distributions are formed by normalizing independent draws from a broader class of Infinitely Divisible (ID) distributions. This flexibility allows for modeling a wide range of correlations among topics, going beyond the limitations of the Dirichlet distribution. The Dirichlet distribution itself is a special case of NID distributions (when the underlying ID distributions are Gamma).
  • Spectral Learning Algorithm: The paper presents a novel spectral method for learning the parameters of these NID topic models. This method leverages the properties of NID distributions and their moments. A key technical innovation is a technique to diagonalize the moments of the NID distribution using only univariate integrals, even when dealing with high-dimensional multivariate moments. This allows for efficient computation of the topic-word matrix and other model parameters. The algorithm relies on computing and decomposing third-order moment tensors of the observed data.

Datasets

The authors evaluate their proposed Latent NID topic model on two real-world datasets:

  • New York Times: A collection of approximately 300,000 articles.
  • Pubmed: A collection of approximately 8 million articles.

The vocabulary size for both datasets is around 100,000 words. These datasets are standard benchmarks for topic modeling research.

Key Insights and Ideas

  • Beyond Dirichlet: The Dirichlet distribution, while foundational for LDA, is too restrictive for modeling real-world topic correlations. NID distributions offer a principled and flexible way to generalize this, allowing for both positive and negative correlations.
  • Spectral Methods for General Models: The paper demonstrates that spectral methods, which have been successful for simpler models like LDA, can be extended to more complex latent variable models like NID topic models. This is a significant step towards learning more expressive probabilistic models.
  • Univariate Integrals for High Dimensions: The technical breakthrough of using univariate integrals to diagonalize high-dimensional moments is crucial. It makes the spectral learning approach computationally feasible and efficient, even for large vocabularies.
  • Third-Order Moments Suffice: Surprisingly, for this flexible class of NID models, moments up to the third order are sufficient for guaranteed learning. This is a more parsimonious requirement than might be expected for such a general model.

Key Results

  • Improved Perplexity: The Latent NID topic model achieved improved perplexity scores on both the New York Times and Pubmed datasets compared to spectral LDA (which uses a fixed Dirichlet prior). This indicates better generalization performance on held-out data.
  • Guaranteed Recovery: The proposed spectral method provides theoretical guarantees for consistently recovering the topic-word matrix and model parameters with polynomial sample and computational complexity, under certain assumptions (e.g., non-degenerate topic-word matrix).
  • Efficient Learning: The spectral approach is computationally efficient, with the authors noting that their implementation takes about a minute for the NYtimes dataset and 15 minutes for the Pubmed dataset, making it scalable for large corpora.

Limitations and Future Work

  • Assumptions: The theoretical guarantees rely on certain assumptions, such as the topic-word matrix having linearly independent columns and the parameters being positive. The practical implications of violating these assumptions are not fully explored.
  • Hyperparameter Tuning: While the paper mentions tuning for hyperparameters to compute the best fitting weights, the process of selecting the specific NID family (Gamma, y-stable, Inverse Gaussian) or a non-parametric approach is not detailed.
  • Future Work: The authors suggest that this work opens the door to learning other flexible latent variable models using spectral methods. Further exploration of different NID families and their applications could be a natural next step. The paper also hints at the potential for non-parametric estimation of the Lévy-Khintchine representation, which could lead to even more flexible models.

Summary updated

Abstract

In this paper, we propose guaranteed spectral methods for learning a broad range of topic models, which generalize the popular Latent Dirichlet Allocation (LDA). We overcome the limitation of LDA to incorporate arbitrary topic correlations, by assuming that the hidden topic proportions are drawn from a flexible class of Normalized Infinitely Divisible (NID) distributions. NID distributions are generated through the process of normalizing a family of independent Infinitely Divisible (ID) random variables. The Dirichlet distribution is a special case obtained by normalizing a set of Gamma random variables. We prove that this flexible topic model class can be learned via spectral methods using only moments up to the third order, with (low order) polynomial sample and computational complexity. The proof is based on a key new technique derived here that allows us to diagonalize the moments of the NID distribution through an efficient procedure that requires evaluating only univariate integrals, despite the fact that we are handling high dimensional multivariate moments. In order to assess the performance of our proposed Latent NID topic model, we use two real datasets of articles collected from New York Times and Pubmed. Our experiments yield improved perplexity on both datasets compared with the baseline.
BibTeX
@misc{arabshahi2016beyond,
  author = {Forough Arabshahi and Animashree Anandkumar},
  title = {{Beyond LDA: A Unified Framework for Learning Latent Normalized Infinitely Divisible Topic Models through Spectral Methods}},
  year = {2016},
  eprint = {1605.09080},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1605.09080},
}
Figure