Sequential Monte Carlo Samplers for Dirichlet Process Mixtures

Yener Ülker, Bilge Günsel, Ali Taylan CemgilAISTATS 2010

Abstract

Dirichlet Process Mixture (DPM) models are powerful tools for non-parametric Bayesian clustering, allowing the number of clusters to be inferred from data. However, standard online inference methods like particle filters often suffer from "stickiness," where early cluster assignments become fixed, leading to poor posterior approximations. This paper presents a novel online inference framework using Sequential Monte Carlo (SMC) samplers. By incorporating retrospective updates and bridging techniques, the proposed algorithms effectively overcome degeneracy issues, providing more accurate and robust clustering solutions compared to traditional sequential methods.

Introduction

Dirichlet Process Mixtures (DPMs) represent a cornerstone of non-parametric Bayesian statistics, particularly for clustering applications where the number of underlying components is unknown. While batch methods like Gibbs sampling are effective, they are computationally intensive for large datasets and unsuitable for streaming data. Online inference methods, such as standard particle filters (PF), offer a sequential alternative but are plagued by a fundamental flaw: stickiness.

In a standard PF, once an observation is assigned to a cluster at time $t$, this decision is typically immutable for all future time steps. As more data arrives, an initial assignment may become suboptimal, yet the algorithm lacks a mechanism to revise past decisions. This leads to high estimation variance and entrapment in local modes, where the sampler fails to represent the true posterior distribution accurately.

Methodology: SMC Samplers for DPMs

To address these limitations, this research leverages the SMC Samplers framework to develop a more flexible online inference engine. The approach introduces three primary innovations:

  1. Active Block Updates: The algorithm identifies an "active block" of past observations. Instead of only labeling the most recent data point, it performs MCMC-style Gibbs steps to re-evaluate and update the cluster assignments of these past points.
  2. Extended State Space: To maintain mathematical validity during retrospective updates, the algorithm operates on an extended state space using forward and backward Markov kernels. This ensures that importance weights can be updated efficiently without requiring intractable integrations.
  3. Bridging (Annealing): A "bridging" technique is introduced (specifically in the SMC-3 variant) where the "novelty" parameter ($\kappa$) of the Dirichlet Process is temporarily modified. By "annealing" the distribution, the sampler can more easily traverse low-probability regions to discover better clustering configurations, preventing it from becoming stuck in local optima.

The authors propose three variants: SMC-1 (basic block updates), SMC-2 (utilizing mixture kernels), and SMC-3 (incorporating the bridging/annealing trick).

Experimental Setup

The proposed algorithms were evaluated on two synthetic datasets designed to challenge density estimation and clustering capabilities:

  • Dataset-1 (D-1): Comprises 1,000 points from a mixture of three overlapping Gaussians with equal weights.
  • Dataset-2 (D-2): Comprises 1,000 points from a mixture of three Gaussians with unequal weights and varying variances.

These datasets serve as benchmarks to determine if an algorithm can correctly identify the underlying components of a distribution in a sequential Bayesian setting.

Results and Discussion

The experimental results demonstrate the superiority of the SMC sampler approach over traditional particle filters.

Comparison of PDF estimates. (a) illustrates the high variance and "stickiness" often seen in standard sequential methods, while (b) shows the more stable and accurate density estimation achieved by the proposed SMC samplers.

Quantitative Performance

As shown in the table below, SMC-2 and SMC-3 consistently achieved log-marginal likelihoods and mean cluster estimates that closely align with the "gold standard" batch Gibbs sampler (GS). In contrast, standard particle filters (PF) and the simpler SMC-1 variant frequently underestimated the number of components or exhibited significantly higher variance.

Quantitative comparison of log-marginal likelihoods and estimated means for Dataset-1 and Dataset-2 with $\kappa = 0.5$. The SMC variants, particularly SMC-3, show performance comparable to the batch Gibbs sampler.

Key Findings

  • Retrospection and Accuracy: The ability to "look back" and update past assignments is crucial. In the D-1 test case, SMC samplers achieved approximately 8 times lower Monte Carlo error than the standard particle filter at $n=1000$ observations.
  • Robustness to Local Modes: While the standard PF often failed to identify all three clusters (frequently getting stuck with only two), the SMC-3 variant correctly identified all three components in nearly every experimental run.
  • Computational Efficiency: Despite the retrospective updates, the computational complexity remains manageable. By carefully designing the sequential approximation, the authors ensure that the load increases only linearly with the size of the "active block" ($Q$), making the method practical for real-time applications.

Conclusion

This paper introduces a robust framework for online inference in DPM models. By moving beyond the strictly forward-looking nature of standard particle filters, SMC samplers provide a principled way to perform retrospective updates and escape local posterior modes.

While the current work assumes conjugacy to simplify the integration of parameters, future research could extend this framework to non-conjugate settings. Additionally, exploring more sophisticated strategies for selecting the "active block" of observations could further enhance the efficiency and accuracy of the sampler in complex, high-dimensional hierarchical Bayesian models.

Summary updated

BibTeX
@article{ulker2010sequential,
  author = {Yener Ülker and Bilge Günsel and Ali Taylan Cemgil},
  title = {{Sequential Monte Carlo Samplers for Dirichlet Process Mixtures}},
  journal = {AISTATS},
  year = {2010},
}
Figure