Capturing Semantically Meaningful Word Dependencies with an Admixture of Poisson MRFs

David I. Inouye, Pradeep Ravikumar, Inderjit S. DhillonNeurIPS 2014 · OpenReview

Introduction

Standard topic models like Latent Dirichlet Allocation (LDA) treat documents as a "bag of words," assuming that words within a topic are independent of each other. However, human language is inherently built on dependencies: if you see the word "classification," you are much more likely to see "supervised."

The Admixture of Poisson MRFs (APM) is a topic model designed to explicitly capture how words within a topic depend on one another. Despite its promise, APM previously faced severe computational bottlenecks and lacked an evaluation metric that could adequately measure its ability to capture these semantic links. This paper introduces a scalable training algorithm for APM and proposes a novel, human-centric "evocation" metric to demonstrate that APM identifies far more semantically rich word relationships than traditional models.

Overcoming the Computational Bottleneck

Estimating dependencies between all pairs of words in a vocabulary of size $p$ requires learning $O(p^2)$ parameters. Previous APM implementations could only handle tiny vocabularies of about 200 words.

To tackle this scalability issue, the authors developed a parallel alternating Newton-like algorithm.

  • Alternating Optimization: The training process is split into two subproblems: one for document-topic weights and one for word-dependency parameters. This mirrors approaches used in Non-negative Matrix Factorization (NMF).
  • Sparsity & Newton Steps: By applying $\ell_1$ regularization, the model encourages sparsity, focusing the optimization only on the most important word relationships.
  • Parallelism: Because the subproblems for different words or documents are independent, the algorithm can be parallelized across many CPU cores.
Parallel speedup and training time for the APM algorithm.

This approach allows APM to scale to vocabularies of 10,000 words—a 50x increase over previous research—achieving near-linear speedup when parallelized across multiple workers.

A Novel Metric: Human Evocation

Traditional metrics for topic models don't directly measure how well a model captures the conceptual "links" between words. The authors argue that "evocation"—how much one word brings another to mind—is a superior metric to simple "similarity." For example, "work" and "lazy" are opposites and not strictly similar, but they have high evocation.

To evaluate this, the authors used a specialized benchmark where humans scored word pairs based on evocation (e.g., "rose" evokes "flower"). They compared APM against models like LDA, Correlated Topic Models (CTM), and Hierarchical Dirichlet Processes (HDP) using the British National Corpus (BNC).

Key Results and Insights

Quantitative Superiority: On the evocation metric, APM significantly outperformed traditional models. Furthermore, because APM captures word dependencies directly, it produces highly meaningful results with as few as 5 topics, whereas traditional models often require 50 to 100 topics to appear coherent.

Comparison of APM against other topic models on the evocation metric.

Qualitative Quality: When examining the top word pairs generated by the models, APM found highly intuitive, specific relationships like [smoke ↔ cigarette] and [boil ↔ potato]. In contrast, LDA often picked up weaker, more generic associations like [year ↔ day] or [tell ↔ get].

Poisson MRFs as a Better Fit: The success of APM also highlights that real-world text data often violates the Multinomial distribution assumptions of LDA. Using Poisson Markov Random Fields (MRFs) allows the model to naturally account for the interdependent nature of word counts.

Limitations and Future Work

While APM shows significant improvements, the evocation metric is currently limited by human data sparsity, as only a small fraction of all possible word pairs have been human-scored. Additionally, to maintain algorithmic speed, the authors used a "pseudo-likelihood" approach that ignores certain symmetry constraints in the model's parameters.

Looking forward, APM’s ability to map word dependencies could be highly valuable for downstream tasks like Word Sense Induction (distinguishing different meanings of the same word) and automated document summarization.

Summary updated

Abstract

We develop a fast algorithm for the Admixture of Poisson MRFs (APM) topic model and propose a novel metric to directly evaluate this model. The APM topic model recently introduced by Inouye et al. (2014) is the first topic model that allows for word dependencies within each topic unlike in previous topic models like LDA that assume independence between words within a topic. Research in both the semantic coherence of a topic models (Mimno et al. 2011, Newman et al. 2010) and measures of model fitness (Mimno & Blei 2011) provide strong support that explicitly modeling word dependencies---as in APM---could be both semantically meaningful and essential for appropriately modeling real text data. Though APM shows significant promise for providing a better topic model, APM has a high computational complexity because $O(p^2)$ parameters must be estimated where $p$ is the number of words (Inouye et al. could only provide results for datasets with $p = 200$). In light of this, we develop a parallel alternating Newton-like algorithm for training the APM model that can handle $p = 10^4$ as an important step towards scaling to large datasets. In addition, Inouye et al. only provided tentative and inconclusive results on the utility of APM. Thus, motivated by simple intuitions and previous evaluations of topic models, we propose a novel evaluation metric based on human evocation scores between word pairs (i.e. how much one word brings to mind" another word (Boyd-Graber et al. 2006)). We provide compelling quantitative and qualitative results on the BNC corpus that demonstrate the superiority of APM over previous topic models for identifying semantically meaningful word dependencies. (MATLAB code available at: http://bigdata.ices.utexas.edu/software/apm/)"
BibTeX
@inproceedings{inouye2014capturing,
  author = {David I. Inouye and Pradeep Ravikumar and Inderjit S. Dhillon},
  title = {{Capturing Semantically Meaningful Word Dependencies with an Admixture of Poisson MRFs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=HyZY3IZ_WH},
}
Figure