Abstract
Completely random measures provide a principled approach to creating flexible unsupervised models, where the number of latent features is infinite and the number of features that influence the data is finite. This paper introduces a novel Markov chain Monte Carlo (MCMC) algorithm for posterior inference in models based on Completely Random Measures (CRMs). By using auxiliary "slice" variables, the algorithm adaptively determines the necessary truncation level of an infinite-dimensional model, allowing for efficient, parallelized computation that targets the exact posterior without the accuracy loss of fixed truncation or the scaling bottlenecks of marginalization.
The Challenge of Inference in Bayesian Nonparametrics
In Bayesian Nonparametrics (BNP), models often assume an infinite number of latent features—such as topics in a document or genres in a movie database. CRMs serve as the mathematical foundation for these priors. However, learning these features from data presents a significant computational challenge. Traditionally, researchers have relied on two suboptimal strategies:
- Marginalization: Analytically "integrating out" infinite components. While mathematically exact, this introduces dependencies that prevent parallelization and often requires restrictive mathematical conjugacy.
- Fixed Truncation: Imposing an arbitrary limit on the number of features. This is fast and parallelizable but risks losing the model's inherent flexibility if the truncation level is set too low.
The proposed slice sampling framework offers a "third way": an inference recipe that maintains the flexibility of marginalization while achieving the speed and parallelizability of truncation-based methods.
Adaptive Slice Sampling Framework
The core innovation is the introduction of auxiliary slice variables $U_n$ for each data point $n$. These variables define a dynamic threshold that determines which latent features are "active" in a given iteration.
Key Technical Components
- Adaptive Truncation: Instead of a static cutoff, the model activates a finite number of features $K$ based on the slice variables. The authors realized that error bounds previously used to justify fixed truncation could be applied dynamically within the sampling loop to determine the optimal truncation level in each iteration.
- Series Representations: The algorithm utilizes the Bondesson or Lawrance-Lévy representations of CRMs, which express them as infinite sums of jumps. The slice sampler instantiates only the jumps necessary for the current calculation, leading to exponentially decreasing truncation error.
- Parallelization: Given the slice variables and instantiated features, data point assignments are conditionally independent. This allows the most computationally intensive steps to be distributed across multiple processors.
Empirical Evaluation
The authors evaluated the slice sampler on both synthetic and real-world datasets:
- Synthetic Scaling: Testing a Beta-Bernoulli latent feature model with up to 20,000 observations, the slice sampler achieved a runtime complexity closer to linear ($O(N)$) per iteration, whereas traditional collapsed samplers often scale quadratically ($O(N^2)$).
- NeurIPS Corpus: On a dataset of research papers, the method was used for a Beta-Negative Binomial combinatorial clustering model. The slice sampler achieved lower perplexity than previous superposition-based samplers, indicating superior predictive power.
Key Results
The proposed method demonstrated significantly higher Effective Sample Size (ESS) per second. In Beta-Bernoulli tests, ESS/s scaled at $O(N^{-0.6})$ for the slice sampler compared to $O(N^{-1.34})$ for state-of-the-art accelerated collapsed Gibbs samplers. Furthermore, the method reduces redundancy by avoiding the high number of unused atoms common in other BNP samplers.
Conclusion and Future Work
The slice sampling framework provides a general, efficient recipe for CRM-based models. While it offers significant improvements in scalability and accuracy, future work could focus on automated selection of the decay sequence $\xi$ and the incorporation of "split-merge" moves to better navigate complex posterior landscapes. Additionally, extending the framework to handle extremely complex non-conjugate likelihoods remains an area for further development.
Summary updated