Fixed-Length Poisson MRF: Adding Dependencies to the Multinomial

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

This paper introduces a clever evolution of the Multinomial distribution—the traditional "workhorse" of natural language processing—to better capture the nuances of how words actually co-occur in written text.

TL;DR

The authors propose the Fixed-Length Poisson MRF (LPMRF), a new probability distribution that allows for dependencies between variables (like words in a document) while maintaining a fixed total count. By replacing the standard Multinomial distribution in topic models, LPMRF significantly improves text modeling performance and uncovers intuitive word-to-word relationships that traditional models miss.

The Problem with the Multinomial Distribution

Most modern topic models, such as Latent Dirichlet Allocation (LDA), are built on the Multinomial distribution. While mathematically convenient, the Multinomial has a major flaw: it assumes that words are independent of one another within a topic.

In reality, language is full of dependencies. If you see the word "neural," you are much more likely to see the word "network." Standard models only capture this by saying both words are frequent in a "Machine Learning" topic. They don't explicitly model the interaction between them.

Previous attempts to use Poisson Markov Random Fields (PMRFs) to model these dependencies ran into a "math wall": if you allow words to have positive correlations (positive dependencies), the model's normalizing constant (the partition function) becomes infinite, making the model mathematically unusable.

Methods: The LPMRF Solution

The authors solve the normalization problem with a simple but highly effective constraint: fixed length.

  1. The LPMRF Distribution: They define a distribution that has the same functional form as a PMRF but restricts the domain to vectors that sum to a fixed length $L$ (the document length). This constraint ensures the distribution is always integrable and well-behaved, even with strong positive dependencies.
Probability mass shifts in the LPMRF distribution under negative, independent, and positive dependency settings.
  1. Annealed Importance Sampling (AIS): Because calculating the exact likelihood of this distribution is computationally "intractable" (it involves summing over an exponential number of combinations), the authors developed an AIS sampling method to estimate the log partition function.
  2. Length-Dependent Scaling: They observed that as documents get longer, the influence of word dependencies can explode. They introduced a sigmoidal weighting function to scale the dependency matrix based on the document length, ensuring the model remains stable across both short abstracts and long articles.
  3. Topic Model Integration: They reformulated the standard LDA framework, replacing the Multinomial base with the LPMRF. This allows the model to learn a "dependency graph" for every topic.

Key Insights and Ideas

  • The "Fixed Length" Hack: The most elegant insight is that the Multinomial's biggest weakness (independence) and the PMRF's biggest weakness (instability) cancel each other out when you force the PMRF to have a fixed sum.
  • Beyond Word Clouds: Traditional topic models give you "word clouds" (lists of frequent words). LPMRF gives you a structured map. For example, in a library science topic, it doesn't just list "information" and "retrieval"; it identifies a strong positive edge between them.
  • Negative Dependencies: The model also captures what doesn't go together. In an Aerospace topic, "boundary" and "layer" have a strong positive link, but "boundary" and "library" have a strong negative link, helping the model disambiguate context.

Key Results

The researchers evaluated their model on two primary corpora: Classic3 (a dataset of research abstracts from medical, library science, and aerospace fields) and Wikipedia.

  • Better Predictive Power: The LPMRF consistently outperformed the Multinomial in perplexity (a standard metric for how well a model predicts unseen data, where lower is better). On the Classic3 dataset, the single LPMRF model achieved a perplexity of 34, compared to 47 for the Multinomial.
Perplexity comparison between the standard Multinomial and the proposed LPMRF on Classic3 and Wikipedia datasets.
  • Qualitative Discovery: The model successfully identified intuitive pairs like language + natural, stress + reaction, and non + linear. These relationships are often lost in standard models where frequent words like "system" or "data" drown out specific technical pairings.
  • Scalability: Despite the added complexity of sampling, the authors demonstrated that their algorithms scale linearly with the number of documents and words, making it viable for large-scale text mining.

Limitations and Future Work

  • The "Topic Gap": While LPMRF beats LDA for a small number of topics, the authors noted that standard LDA (using highly optimized Gibbs sampling) still performs better when the number of topics becomes very large.
  • Sampling Complexity: Estimating the partition function via AIS is more computationally expensive than the simple counting used in Multinomial models.
  • Future Directions: The authors suggest that incorporating more sophisticated sampling techniques directly into the training loop could help the model scale to even higher topic counts and more complex hierarchical structures.

Summary updated

Abstract

We propose a novel distribution that generalizes the Multinomial distribution to enable dependencies between dimensions. Our novel distribution is based on the parametric form of the Poisson MRF model [Yang et al., 2012] but is fundamentally different because of the domain restriction to a fixed-length vector like in a Multinomial where the number of trials is fixed or known. Thus, we propose the Fixed-Length Poisson MRF (LPMRF) distribution. We develop methods to estimate the likelihood and log partition function (i.e. the log normalizing constant), which was not developed for the Poisson MRF model. In addition, we propose novel mixture and topic models that use LPMRF as a base distribution and discuss the similarities and differences with previous topic models such as the recently proposed Admixture of Poisson MRFs [Inouye et al., 2014]. We show the effectiveness of our LPMRF distribution over Multinomial models by evaluating the test set perplexity on a dataset of abstracts and Wikipedia. Qualitatively, we show that the positive dependencies discovered by LPMRF are interesting and intuitive. Finally, we show that our algorithms are fast and have good scaling (code available online).
BibTeX
@inproceedings{inouye2015fixed,
  author = {David I. Inouye and Pradeep Ravikumar and Inderjit S. Dhillon},
  title = {{Fixed-Length Poisson MRF: Adding Dependencies to the Multinomial}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=HJ-ZiwZO-S},
}
Figure