Adaptive Reconfiguration Moves for MCMC inference in Dirichlet Process Mixtures

Tue Herlau, Morten Mørup, Mikkel N. Schmidt, Yee Whye Teh2016

TL;DR

This paper introduces Adaptive Reconfiguration Moves (ARM), a novel Markov Chain Monte Carlo (MCMC) method for Dirichlet Process Mixture models. ARM significantly improves sampling efficiency by allowing more flexible transitions between partitions, leveraging multiple chains in parallel, and adaptively using past states to guide proposals, outperforming traditional Gibbs and split-merge methods.

What Problem Does This Paper Address?

Bayesian mixture models are powerful tools for unsupervised learning, but inferring their parameters using MCMC can be challenging. Standard methods like Gibbs sampling can get stuck in local modes, leading to slow convergence. Split-merge (SM) sampling offers more flexible moves but often suffers from low acceptance rates and struggles with problems where multiple blocks need to change configuration simultaneously. This paper tackles the problem of inefficient MCMC sampling in Dirichlet Process Mixture models by developing a method that allows for more complex, adaptive, and parallelized transitions, aiming to achieve better mixing and higher acceptance rates.

Methods

The core contribution is the Adaptive Reconfiguration Moves (ARM) algorithm. Unlike traditional methods that focus on single-observation moves (Gibbs) or simple block splits/merges (SM), ARM introduces:

  • Broader Transitions: ARM allows observations to move not just between the blocks being split or merged, but also between these blocks and other blocks in the partition. This is achieved by considering a "coarsest common refinement" of multiple past states.
  • Parallel Chains and Adaptive Proposals: ARM utilizes multiple chains running in parallel. The past states of these chains are used adaptively to inform the proposal distribution for the current chain. This means the sampler "learns" from its history to make better suggestions for the next state.
  • Joint Updates: ARM can perform joint updates on multiple blocks of observations, enabling more significant and potentially more favorable transitions than single-block operations.
  • Simplified Reconfiguration Moves (sRM): A precursor to ARM, sRM focuses on ensuring unique sampling paths for moves, a crucial aspect for accurate transition probability calculations.

The method is designed to address limitations of existing approaches, particularly the "coupling problem" (where only a few variables can change configuration) and the "poor candidates" problem (where proposed states are highly improbable).

Datasets

The paper evaluates ARM on two types of problems:

  • Bernoulli Mixture Model: Artificial data generated to mimic scenarios with varying numbers of attributes (d=6, 8, 10) and components. This is a standard benchmark used in prior work.
  • Infinite Relational Model (IRM): Real-world network datasets were used, including:
  • NIPS coauthor network
    • USAir network
    • Caltech network
    • Hagmann structural brain network

These datasets represent diverse structures, from well-defined communities to more complex, translation-invariant grid-like structures.

Key Insights and Ideas

  • Beyond Simple Splits/Merges: The key insight is that for efficient MCMC in complex partition models, transitions need to be more flexible than just splitting or merging single blocks. Allowing observations to move more freely between blocks, informed by past states, is crucial.
  • Parallelism as a Feature, Not Just Speedup: Using multiple chains in parallel isn't just for faster computation; it's integral to ARM's adaptive strategy. The disagreement between chains helps identify good split/merge candidates, and shared history improves proposal quality.
  • Past States are Gold: The adaptive nature of ARM, using past states to guide proposals, is a significant departure from static MCMC methods. This "memory" allows the sampler to avoid repeatedly exploring unpromising regions.
  • Uniqueness is Key for Transition Probabilities: A significant technical challenge addressed is ensuring that the sequence of moves leading to a new state is unique. This is critical for correctly calculating transition probabilities in MCMC.

Key Results

  • Superior Mixing: ARM consistently demonstrated better mixing (faster convergence to the stationary distribution) compared to Gibbs sampling and Split-Merge (SM) sampling across various datasets.
  • Higher Acceptance Rates: ARM achieved significantly higher acceptance rates for its proposed moves, especially on more complex network datasets, compared to SM.
  • Computational Efficiency: While ARM might require more computational effort per iteration than Gibbs, it reaches a comparable or better likelihood value in significantly fewer normalized iterations (representing equivalent computational effort). For instance, ARM converged in tens of iterations where SM took thousands for some network datasets.
  • Robustness: The performance improvements of ARM were observed across different datasets and under variations of the method itself, suggesting its core principles are sound.

Limitations and Future Work

  • Computational Cost: ARM is described as being "about three times more expensive than a Gibbs sweep" per iteration, though its superior mixing often makes it more efficient overall.
  • Initialization Dependence: The method relies on initial states (za, zb) and selected observations (i, j) to construct proposals. While adaptive, the initial choice can still influence performance.
  • Future Research Directions:
    • Softening Restrictions: Exploring ways to relax the strict requirement of splitting/merging only two observations (i, j) at a time.
  • More Past States: Investigating the use of more than two past states to inform the transition kernel.
  • Block Movement: Allowing blocks of variables to move more freely, not just those initially involved in the split/merge.
  • Non-conjugate Models: Extending the framework to handle models where parameters cannot be analytically marginalized out.
  • Alternative Information Gathering: Exploring different ways to gather and utilize past state information beyond simple agreement/disagreement.

Summary updated

Abstract

Bayesian mixture models are widely applied for unsupervised learning and exploratory data analysis. Markov chain Monte Carlo based on Gibbs sampling and split-merge moves are widely used for inference in these models. However, both methods are restricted to limited types of transitions and suffer from torpid mixing and low accept rates even for problems of modest size. We propose a method that considers a broader range of transitions that are close to equilibrium by exploiting multiple chains in parallel and using the past states adaptively to inform the proposal distribution. The method significantly improves on Gibbs and split-merge sampling as quantified using convergence diagnostics and acceptance rates. Adaptive MCMC methods which use past states to inform the proposal distribution has given rise to many ingenious sampling schemes for continuous problems and the present work can be seen as an important first step in bringing these benefits to partition-based problems. 1.
BibTeX
@misc{herlau2016adaptive,
  author = {Tue Herlau and Morten Mørup and Mikkel N. Schmidt and Yee Whye Teh},
  title = {{Adaptive Reconfiguration Moves for MCMC inference in Dirichlet Process Mixtures}},
  year = {2016},
}
Figure