PaperlayerView exact revision on arXiv

Source-linked AI summary

Retrospective Markov chain Monte Carlo methods for Dirichlet process hierarchical model

Omiros Papaspiliopoulos, Gareth Roberts

arXiv:0710.4228v1stat.MEstat.CO

TL;DR

Inference for Dirichlet process hierarchical models requires either marginalizing the infinite-dimensional process or approximating it within conditional sampling. The paper introduces retrospective conditional MCMC algorithms that avoid approximation, support posterior functionals, and compare favorably with marginal methods in settings where both apply.

  • Problem

    Conditional inference requires imputing infinite-dimensional weights and component parameters, while marginal inference is considerably more complicated for non-conjugate models.

  • Method

    The paper develops two conditional Markov chain Monte Carlo implementations using retrospective sampling to simulate infinite-dimensional processes exactly in finite time.

  • Results

    Tailored label-switching moves significantly improve the algorithm's Monte Carlo efficiency, while marginal methods slightly outperform conditional methods where both can be applied.

  • Takeaways & Limitations

    The algorithms avoid finite approximations and can sample posterior distributions of functionals of the Dirichlet process.

  • Takeaways & Limitations

    Estimating τ remains a notoriously difficult problem, and extensions to more general models were not explicitly shown.

Abstract

from arXiv · show

Inference for Dirichlet process hierarchical models is typically performed using Markov chain Monte Carlo methods, which can be roughly categorised into marginal and conditional methods. The former integrate out analytically the infinite-dimensional component of the hierarchical model and sample from the marginal distribution of the remaining variables using the Gibbs sampler. Conditional methods impute the Dirichlet process and update it as a component of the Gibbs sampler. Since this requires imputation of an infinite-dimensional process, implementation of the conditional method has relied on finite approximations. In this paper we show how to avoid such approximations by designing two novel Markov chain Monte Carlo algorithms which sample from the exact posterior distribution of quantities of interest. The approximations are avoided by the new technique of retrospective sampling. We also show how the algorithms can obtain samples from functionals of the Dirichlet process. The marginal and the conditional methods are compared and a careful simulation study is included, which involves a non-conjugate model, different datasets and prior specifications.

1. Introduction

Dirichlet process hierarchical models support flexible mixture modeling, but inference must balance marginal methods that simplify the process against conditional methods that retain it. This paper introduces exact retrospective conditional algorithms, addresses posterior multimodality, and compares the approaches empirically.

  • Model and inference framework: Dirichlet process hierarchical models represent flexible mixture models in which data are allocated to components through latent variables and component parameters.The hierarchy uses stick-breaking weights and component parameters drawn from a base measure.
  • Marginal method: Marginal Gibbs sampling integrates out the random probabilities and samples allocations, cluster parameters, and weights, but is considerably more complicated for non-conjugate models.Analytic integration also induces dependence among allocation variables and makes cluster labels unidentifiable.
  • Conditional method: Conditional Gibbs sampling imputes the weights and component parameters, enabling simultaneous updates and avoiding the need to integrate model components analytically.Its flexibility supports extensions such as more general stick-breaking measures and covariate-dependent models, and it permits inference for the latent random measure.
  • Computational challenge: The conditional method traditionally approximates the infinite-dimensional process through truncation, although truncation error can sometimes be controlled.The paper motivates avoiding these approximations altogether.
  • Paper contributions: Two conditional Markov chain Monte Carlo implementations use retrospective sampling to avoid approximation and enable exact finite-time simulation involving infinite-dimensional processes.The algorithms can also sample posterior functionals of the Dirichlet process and extend readily to more general stick-breaking models.
  • Evaluation and comparison: Weak label identifiability makes the posterior multimodal, so tailored label-switching moves are designed to improve Markov chain Monte Carlo performance.The paper also compares retrospective conditional algorithms with state-of-the-art marginal implementations for non-conjugate models in terms of Monte Carlo efficiency.

2. Retrospective sampling from the Dirichlet process prior

The prior can be simulated without generating its infinite-dimensional representation by making finite decisions and retrospectively sampling only the required components. This principle extends the prior simulation scheme toward computationally feasible posterior methods.

  • Marginal simulation: A Dirichlet process sample can be generated through allocation variables that assign observations to existing or newly created clusters.The marginal construction sequentially samples allocations and cluster parameters, retaining only components associated with data points.
  • The infinite-dimensional obstacle: Direct hierarchical simulation is infeasible because it requires generating the infinite vectors of mixture weights and component parameters.Retrospective simulation avoids this requirement by changing the order in which uniforms and component pairs are generated.
  • Retrospective simulation: Retrospective sampling first simulates a decision variable, then generates additional weight-parameter pairs only until that decision can be resolved.If the currently available partial sums are insufficient, further pairs are simulated retrospectively.
  • General principle: The approach can make exact decisions depending on an infinite-dimensional object without approximation when the decision is reducible to finite-dimensional summaries.The toy construction compares a uniform variable with partial sums and terminates in finite time without approximation error.
  • Extension to inference: Retrospective posterior simulation is computationally feasible in principle, but its conditional simulation steps are more complicated than the prior illustration.The method may require retrospective simulation of the random object conditional on finite-dimensional summaries.

Posterior inference

Posterior inference is organized around the allocation variables, stick-breaking variables, and component parameters. Retrospective updates avoid finite truncation while addressing intractable allocation probabilities and yield a sampler targeting the joint posterior.

  • Motivation: The conditional approach imputes countably infinite weights and component parameters, making direct Gibbs sampling challenging and motivating finite approximations.The paper instead parameterizes the model using (K, V, Z) and aims to avoid approximation altogether.
  • Posterior parameterization: The proposed algorithms iteratively update K, V, and Z using full conditional distributions or invariant mechanisms such as Metropolis-Hastings.The resulting componentwise sampler has the joint posterior distribution of (K, V, Z) as its stationary distribution.
  • Allocation updates: Given V and Z, each allocation K_i has probability proportional to p_j f(Y_i | Z_j, λ), but its normalizing constant requires an infinite random sum.This makes direct simulation of K_i highly nontrivial without an approximation.
  • Retrospective MCMC: A retrospective quasi-independence Metropolis-Hastings update proposes existing components from conditional probabilities and new components from prior probabilities.The proposal updates allocation variables sequentially while preserving invariance with respect to the full conditional distribution of K.
  • Target distribution: The algorithm can explore the joint distribution of allocations, stick-breaking variables, and component parameters without truncating the infinite representation.After completion, it is capable of exploring the joint distribution of (K, V, Z).

Accelerations of the main algorithm

Several modifications improve mixing and proposal behavior in the retrospective sampler. The paper emphasizes heavier-tailed allocation proposals and extra updates that substantially improve Monte Carlo efficiency.

  • Proposal design: Choosing M_i(k) so the proposal assigns more new-component mass than the prior produces heavier proposal tails than the target.This choice is theoretically advisable for the independence-sampler structure and ensures geometric-ergodicity conditions described in the paper.
  • Proposal design: Simulation studies found that the recommended M_i(k) choice leads to faster mixing than alternative proposal schemes.The paper reports this comparison through the distribution of the random proposal quantity ρ.
  • Extra updates: Updating Z and V after each allocation update can improve the algorithm's Monte Carlo efficiency significantly.The modification samples dead-component parameters from the prior while leaving alive-component parameters unchanged.
  • Extra updates: Synchronizing N* with max{k} reduces storage by requiring only alive parameters and weights through the current maximum allocation.The implementation sets N* = max{k} before the relevant update step.
  • Empirical effects: Simulations verified that the extra updates improve mixing significantly, although extending posterior proposals beyond max{k} yielded no observed gains.The latter modification changes the proposal boundary by a fixed integer l.

Multimodality and label-switching moves

Weak identifiability of mixture-component labels creates multimodal posteriors, especially challenging for large datasets. Complementary label-switching moves help the sampler cross modes, reducing integrated autocorrelation times substantially.

  • Why switching matters: In large datasets, separated modes can be divided by regions of negligible probability, making label-switching moves particularly important.The conditional sampler must explore these multimodal posterior distributions.
  • Source of multimodality: Weakly identifiable component labels produce multiple posterior modes because nearby component weights can exchange ordering.The posterior can retain nonnegligible probability for reversed weight orderings.
  • Observed-process case: For observed Dirichlet-process samples, uncertainty remains about component probabilities and the infinite-component indices generating observed clusters.A Gibbs sampler for these quantities requires a variation of the retrospective MCMC algorithm.
  • Move design: The algorithm introduces two complementary moves: swapping labels of randomly chosen components and exchanging neighboring labels together with their stick-breaking variables.The first favors similarly weighted components, while the second targets neighboring components in the stick-breaking order.
  • Empirical effect: Integrated autocorrelation times for updated variables can be reduced by as much as 50-90% with the proposed label-switching moves.The reduction was found through extensive simulation experimentation.

Exact retrospective sampling of the allocation variables

The paper develops retrospective sampling to draw exactly from allocation-variable posteriors involving an infinite Dirichlet random measure, avoiding finite approximations under suitable boundedness conditions.

  • Exact retrospective sampling of the allocation variables: Retrospective sampling targets discrete allocation variables whose probability masses depend on a Dirichlet random measure.The method is presented as a general scheme for the conditional posterior distribution of allocation variables.
  • Exact retrospective sampling of the allocation variables: Unknown normalising constants prevent direct simulation, so the algorithm uses converging lower and upper bounding sequences.It simulates stick-breaking quantities retrospectively until the selection condition can be verified.
  • Exact retrospective sampling of the allocation variables: The algorithm increases the truncation level and simulates additional weights and component values until a valid allocation is identified.This makes simulation from the unnormalised discrete distribution feasible without fixing a finite approximation in advance.
  • Exact retrospective sampling of the allocation variables: Constructing the bounds is generally challenging, and the paper treats the case where all likelihood terms are almost surely bounded by a finite constant.When the terms are unbounded, an elaborate coupling construction is required and deferred elsewhere.

Posterior inference for functionals of Dirichlet processes

The retrospective algorithms extend beyond allocation variables to posterior simulation of linear and nonlinear functionals of the Dirichlet process, including the predominant species.

  • Posterior inference for functionals of Dirichlet processes: Posterior draws of a Dirichlet-process functional can be represented using finitely many sampled atoms plus a residual term with a prior-distributed draw.The representation is stated as equality in distribution conditional on the observed data.
  • Posterior inference for functionals of Dirichlet processes: The approach applies to functionals I = ∫g(x)P(dx), where P is the Dirichlet random measure and g is real-valued.The model defines P and the component parameters within the hierarchical construction.
  • Posterior inference for functionals of Dirichlet processes: The conditional implementation finds posterior simulation of I as difficult as simulation from its prior.The retrospective algorithm provides an alternative posterior simulation route from a finite state of the chain.
  • Posterior inference for functionals of Dirichlet processes: The algorithm also supports nonlinear functionals, illustrated by posterior simulation of the predominant species.The predominant species is associated with the atom having the largest stick-breaking weight, with retrospective extension until the identity is determined.
  • Posterior inference for functionals of Dirichlet processes: The predominant-species procedure was used to produce the results shown in Figure 1(c).Additional prior atoms are simulated until the stopping condition involving the remaining mass is satisfied.

Inference for hyperparameters

A modification of retrospective sampling permits Bayesian updates of hierarchical hyperparameters despite their dependence on infinitely many latent process variables.

  • Inference for hyperparameters: The retrospective algorithm can be extended to simulate hyperparameters according to their full conditional distributions.This adds a further update step for the hyperparameters to the retrospective Markov chain Monte Carlo procedure.
  • Inference for hyperparameters: Although the latent variables contain infinite information about (Θ, α), conditional independence allows the update to use only finite information.The hyperparameters can be updated jointly with the unobserved process components conditional on a finite subset of latent variables.
  • Inference for hyperparameters: The paper notes that reducibility can arise in hierarchical hidden-process MCMC and that the conditional-independence construction circumvents this problem.This issue is identified as a broader convergence problem in related hierarchical models.
  • Inference for hyperparameters: In practice, (Θ, α) are simulated conditional on a finite latent subset, while λ is sampled by its standard full conditional distribution.The finite subset contains enough information for the hyperparameter update in the described construction.

4. Comparison between marginal and conditional methods

The simulation compares retrospective and marginal algorithms with conditional methods across simulated datasets, prior specifications, and monitored functionals. Algorithms 7 and 8 perform best, but differences are moderate and computing times were not included in the formal comparison.

  • 4. Comparison between marginal and conditional methods: The comparison monitors cluster count M, density deviance D, and selected allocation variables using integrated autocorrelation measures.These functionals were chosen to assess algorithmic performance and include quantities with different levels of data identification.
  • 4. Comparison between marginal and conditional methods: Algorithms 7 and 8 perform better than the competing algorithms, although the performance differences are moderate.The comparison reports Monte Carlo efficiency using lag autocorrelations and integrated autocorrelation times.
  • 4. Comparison between marginal and conditional methods: No computing-time adjustment was included in the formal comparison.The authors state that their FORTRAN 77 implementation was not optimized for computational time.
  • 4. Comparison between marginal and conditional methods: At α = 1, no-gaps, Algorithm 7, and the retrospective algorithm have roughly similar computing times, whereas Algorithm 8 is more intensive.The retrospective algorithm's computing time increases with α.
  • 4. Comparison between marginal and conditional methods: Marginal approaches generally achieve smaller integrated autocorrelation times because they avoid exploring multimodal posterior distributions caused by ambiguous cluster labels.The conditional approach must explore multiple modes in the posterior random-measure representation, while marginal approaches work with the unidentifiable allocation structure.
  • 4. Comparison between marginal and conditional methods: Including label-switching moves substantially improves the performance of the retrospective algorithm.This modification addresses the algorithm's exploration of alternative cluster-label configurations.

5. Discussion

The discussion emphasizes the conditional approach's ability to infer the latent random measure and extends retrospective-sampling ideas beyond the Dirichlet process. It also identifies mathematical complexity and limits on explicitly demonstrated generalization.

  • The conditional approach can infer the latent random measure, unlike methods that focus only on clustering-related quantities.
  • Retrospective sampling can extend to more general stick-breaking random measures because the crucial conditional independence structure remains present.
  • The authors did not explicitly show extensions to more general models, although they state that such extensions should be direct.
  • The paper discusses an exact Gibbs sampler in which allocation variables are simulated directly from their conditional distribution.
  • For unbounded likelihoods, the method requires an intricate coupling of the Dirichlet process to bound normalising constants and retrospectively simulate related variables.
  • The mathematical construction behind the resulting algorithm is complicated, despite the implementation being simple.
  • Retrospective sampling is presented as applicable to other stochastic-process simulation and inference problems, including exact diffusion-process simulation and estimation.
Loading 0710.4228v1…