A hybrid sampler for Poisson-Kingman mixture models

Maria Lomeli, Stefano Favaro, Yee Whye Teh

Bayesian Nonparametric (BNP) models are powerful tools that allow model complexity—such as the number of clusters in a mixture—to grow automatically with data. However, performing inference on these models is notoriously difficult due to their "infinite-dimensional" components. This paper introduces a novel Markov Chain Monte Carlo (MCMC) scheme for posterior sampling in BNP mixture models, specifically those with priors in the broad Poisson-Kingman (PK) class. By combining the strengths of traditional sampling approaches, the authors create a "hybrid" method that is both memory-efficient and statistically robust.

The Challenge: Marginal vs. Conditional Samplers

To handle infinite-dimensional components, researchers typically choose between two paths:

  1. Marginal Samplers: These "integrate out" the infinite component. While memory-efficient, they often suffer from poor "mixing," meaning the algorithm gets stuck and takes a long time to explore possible solutions.
  2. Conditional Samplers: These truncate the infinite component at a fixed level (e.g., assuming a maximum of 1000 clusters). This improves mixing but wastes significant memory and computation on empty clusters not supported by the data.

The authors aim to bridge this gap for the Poisson-Kingman family, a very broad class of priors that includes well-known models like the Dirichlet Process and the Pitman-Yor Process.

Methodology: A "Lazy" Hybrid Approach

The core innovation is a "varying table size Chinese restaurant representation." Instead of pre-truncating the model or ignoring the infinite component entirely, the authors employ a "lazy sampling" scheme.

They explicitly represent the weights (masses) of clusters currently occupied by data points. For the infinite "tail" of unoccupied clusters, they maintain a single random variable representing the surplus mass.

Visual representation of the lazy sampling scheme, explicitly tracking occupied clusters and grouping the remainder into a surplus mass.

Key technical components include:

  • Size-Biased Representation: Leveraging the fact that PK processes can be viewed as a sequence of "picks" from a stick-breaking process.
  • Hybrid Gibbs Sampling: Deriving complete conditional distributions for occupied cluster weights and the surplus mass. When a new cluster is needed, the algorithm "breaks off" a piece of the surplus mass to create it.
  • Handling Intractability: For certain PK processes (like $\sigma$-Stable processes) with mathematically complex densities, they introduce auxiliary variables or Metropolis-Hastings (MH) steps to maintain efficiency.

Key Insights

  • Lazy is Better: Exact inference doesn't require knowing the entire infinite measure—only the parts the data has "seen" and the total mass of the remainder.
  • Unified Framework: Unlike previous research focused on specific models, this paper provides a general-purpose recipe for the entire Poisson-Kingman class.
  • Memory vs. Mixing Trade-off: By explicitly representing the random probability measure only where needed, the method achieves the comprehensive representation useful for computing expectations without the overhead of fixed truncation.

Empirical Results

The authors evaluated their sampler using the classic Roeder galaxy dataset (velocities of 82 galaxies) as a benchmark to test cluster identification. They compared the Hybrid sampler against standard marginal and conditional samplers across several processes, including Pitman-Yor, Normalized Stable, and Normalized Generalized Gamma.

Performance comparison of the Hybrid sampler against Marginal and Conditional samplers across various processes.
  • Effective Sample Size (ESS): In almost all test cases, the Hybrid sampler produced a significantly higher ESS than both marginal and conditional samplers. A higher ESS indicates less correlated samples, providing a more accurate picture of the posterior distribution in fewer iterations.
  • Computational Speed: For $\sigma$-Stable processes with $\sigma=0.5$, the Hybrid sampler was roughly 3x faster than the conditional sampler while maintaining a much higher ESS.
  • Robustness: The sampler remained stable even when the total mass density was intractable, thanks to the proposed auxiliary variable methods.

Limitations and Future Work

The authors note a few areas for future improvement:

  • High Dimensionality: While the sampler handles the infinite-dimensional prior well, sampling cluster parameters in very high-dimensional feature spaces remains challenging.
  • Proposal Distributions: In the "Hybrid-MH" version, acceptance rates suggest that better proposal distributions for the surplus mass could further boost performance.
  • Parameter Sensitivity: Performance varies based on the discount parameter ($\sigma$). For very small $\sigma$ values (e.g., 0.3), rejection sampling steps become more computationally expensive.

Summary updated

Abstract

This paper concerns the introduction of a new Markov Chain Monte Carlo scheme for posterior sampling in Bayesian nonparametric mixture models with priors that belong to the general Poisson-Kingman class. We present a novel and compact way of representing the infinite dimensional component of the model such that while explicitly representing this infinite component it has less memory and storage requirements than previous MCMC schemes. We describe comparative simulation results demonstrating the efficacy of the proposed MCMC algorithm against existing marginal and conditional MCMC samplers.
BibTeX
@inproceedings{lomeli2015hybrid,
  author = {Maria Lomeli and Stefano Favaro and Yee Whye Teh},
  title = {{A hybrid sampler for Poisson-Kingman mixture models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2015},
  url = {https://openreview.net/forum?id=HyZ7swb_br},
}
Figure