Authors: Vinayak Rao and Yee Whye Teh
Abstract & Overview
The Dirichlet Process (DP) is a foundational tool in Bayesian non-parametrics, widely used for clustering and density estimation. However, the standard DP relies on the assumption of "exchangeability"—meaning the order or structure of the data does not matter. In reality, data often exhibits spatial or temporal structure; for instance, documents written in the same year are more likely to share topics than those written decades apart.
To address this, researchers have developed "Dependent DPs." Unfortunately, many existing models are mathematically cumbersome or restricted to simple 1D geometries. In this paper, the authors propose a simple, general framework for building Dependent DPs by slicing and normalizing a single underlying Gamma Process across an auxiliary space. By controlling the overlap of these slices, they create a set of random measures that are marginally DP-distributed but share information locally, enabling highly flexible non-parametric modeling for time-series and spatial data.
Constructing Dependence with Gamma Processes
The core methodological contribution of this paper relies on the properties of the Gamma Process ($\Gamma$P). Because Gamma Processes are "completely random measures," the masses they assign to disjoint sets are independent. This property makes the mathematics of overlapping regions much cleaner than previous stick-breaking approaches.
The construction follows three main steps:
- The Parent Process: A single $\Gamma$P is defined over an extended space, which is the product of the parameter space and an auxiliary "spatial" or "temporal" space.
- Slicing (Marginalization): Specific regions or "windows" are defined in this auxiliary space. For example, if the auxiliary space is time, a region might be a window around a specific year.
- Normalization: By taking the mass of the $\Gamma$P within these overlapping windows and normalizing it, the authors produce a set of DPs.
Because these windows overlap, the resulting DPs share the same underlying "atoms" (clusters). The geometry of the overlap directly dictates the statistical dependence: the more two windows overlap, the more dependent their corresponding DPs become. This turns a geometric problem into a statistical one, allowing the model to be extended to any space where overlapping regions can be defined.
Inference and Metropolis-Hastings
To make this model computationally feasible, the authors interpret it as a Mixture of DPs and develop a Markov Chain Monte Carlo (MCMC) inference scheme using Gibbs sampling.
Crucially, they found that plain Gibbs sampling is insufficient for this architecture. Without additional mechanisms, clusters often remain "frozen" in their initial temporal regions, failing to discover the true underlying dynamics of the data. To prevent the sampler from getting stuck in local optima, they introduce three Metropolis-Hastings (MH) proposals:
- Split-Merge (MH1)
- Move (MH2): Moves a cluster to a neighboring region.
- Split/Merge-Move (MH3)
Experiments on synthetic data (300 data points generated from a mixture of 10 Gaussians across 5 time steps) demonstrated that the MH2 proposal is particularly vital. It showed a high acceptance rate (~11.7%), proving it to be an efficient way to explore the model's state space and speed up convergence.
Empirical Results: Topic Modeling Through Time
The authors evaluated their Spatial Normalized Gamma Process (SN$\Gamma$P) on a corpus of NIPS (NeurIPS) conference papers from the first 13 years. This dataset includes roughly 2 million word tokens across 1,740 documents, with a vocabulary of 13,000 words.
The model successfully identified topics with specific "lifespans." As shown in the results, "Topic A" (featuring general machine learning terms like function, model, data) spanned the entire 13-year period. In contrast, "Topic I" (featuring terms like routing, load, forecasting) appeared only in the later years of the dataset.
Furthermore, the SN$\Gamma$P achieved a per-word perplexity of 3023.4 on the NIPS data, outperforming the standard Hierarchical Dirichlet Process (HDP), which scored 3046.5. This improvement suggests that explicitly capturing the temporal evolution and lifespan of topics provides a demonstrably better fit than assuming topics are static over time.
Limitations and Future Directions
While the model presents a robust step forward for Dependent DPs, the authors note a few limitations and areas for future work:
- Proposal Refinement: The "Split/Merge-Move" (MH3) proposal had a very low acceptance rate, indicating that a more intelligent design is needed to make it practically useful.
- Fixed Atom Locations: Currently, the "locations" of the clusters (e.g., the specific word distributions of a topic) are fixed and shared across all DPs. Allowing these locations to drift or vary slightly over space or time would be a valuable, albeit complex, extension.
- Broader Generalization: The framework can theoretically be extended beyond Gamma Processes to any "completely random measure." This opens the door to a wider family of Spatial Normalized Random Measures (SNRMs) for future exploration.
Summary updated