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.
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.
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