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 grows with the size of the data set. Due to the infinity the latent features, posterior inference requires either marginalization---resulting in dependence structures that prevent efficient computation via parallelization and conjugacy---or finite truncation, which arbitrarily limits the flexibility of the model. In this paper we present a novel Markov chain Monte Carlo algorithm for posterior inference that adaptively sets the truncation level using auxiliary slice variables, enabling efficient, parallelized computation without sacrificing flexibility. In contrast to past work that achieved this on a model-by-model basis, we provide a general recipe that is applicable to the broad class of completely random measure-based priors. The efficacy of the proposed algorithm is evaluated on several popular nonparametric models, demonstrating a higher effective sample size per second compared to algorithms using marginalization as well as a higher predictive performance compared to models employing fixed truncations.
Introduction
In unsupervised learning, discovering latent structures—such as movie genres in a recommendation system or topics in a text corpus—is a fundamental task. Often, the number of these categories is unknown beforehand. Bayesian Nonparametrics (BNP) offers a solution by allowing the number of features to grow as more data is observed. The mathematical foundation for many of these models is the Completely Random Measure (CRM).
Despite their flexibility, CRMs pose significant challenges for posterior inference. Traditionally, researchers have relied on two approaches, each with drawbacks:
- Marginalization: Analytically integrating out the infinite-dimensional components. While exact, this creates dependencies that force sequential processing, making it slow for large datasets and often requiring mathematical conjugacy.
- Fixed Truncation: Capping the number of features at a pre-set limit. This allows for parallelization but introduces bias and restricts the model's inherent flexibility.
This paper, presented at UAI 2020, introduces a general-purpose MCMC algorithm that achieves the best of both worlds: a sampler that is parallelizable like truncation but remains exact and flexible like marginalization.
The Proposed Framework
The core innovation is an adaptive truncation scheme powered by slice sampling. Instead of a fixed truncation level, the authors introduce auxiliary "slice" variables ($U_n$) for each data point. These variables act as dynamic thresholds that determine which features are "active" in any given iteration.
The augmented model (shown above) ensures that the full conditional distribution of feature assignments becomes zero for all features beyond a certain index. This index, the truncation level $K$, is not static; it "breathes," expanding or contracting at each iteration based on the data's requirements.
As illustrated in the figure above, the truncation level $K$ is determined by the minimum value of the slice variables $U_n$ relative to a deterministic sequence $\xi(k)$. This mechanism allows the algorithm to ignore the infinite tail of the CRM while still targeting the exact posterior. Crucially, because data points are conditionally independent given the features and slice variables, updates can be computed in parallel across multiple CPU cores, leading to linear scaling ($O(N)$) with the number of data points.
Experimental Evaluation
The authors evaluated the "general recipe" on two primary models:
- Beta-Bernoulli Latent Feature Model: Tested on synthetic datasets with up to 20,000 observations. The slice sampler demonstrated a significantly higher Effective Sample Size (ESS) per second compared to traditional collapsed Gibbs samplers, with the performance gap widening as the dataset size increased.
- Beta-Negative Binomial (BNB) Clustering: Applied to the NeurIPS corpus (2010–2015). The proposed sampler achieved lower perplexity on held-out data compared to state-of-the-art samplers, indicating that adaptive truncation allows for a superior fit to real-world data.
Key Insights and Future Directions
A major contribution of this work is its generality. Unlike previous slice samplers designed for specific models (like the Indian Buffet Process), this framework applies to any CRM-based prior, making it a versatile tool for probabilistic programming. Furthermore, by utilizing the Bondesson representation, the authors achieve an exponentially decreasing truncation error, which is more efficient than older series representations.
While the algorithm offers a two-order-of-magnitude improvement in ESS/sec for large datasets, there is room for growth. Future work could focus on the automated selection of the sequence $\xi$ to avoid manual hyperparameter tuning. Additionally, incorporating advanced MCMC moves, such as split-merge steps, could further improve the sampler's ability to explore complex feature spaces and avoid local optima.
Overall, this slice sampling framework provides a robust path forward for scaling Bayesian nonparametric models to the demands of modern, large-scale data analysis.
Summary updated