Hypothesis Tests of Convergence in Markov Chain Monte Carlo

Abstract

Deciding when a Markov chain has reached its stationary distribution is a major problem in applications of Markov Chain Monte Carlo methods. Many methods have been proposed ranging from simple graphical methods to complicated numerical methods. Most such methods require a lot of user interaction with the chain which can be very tedious and time-consuming for a slowly mixing chain. This article describes a system to reduce the burden on the user in assessing convergence. The method uses simple nonparametric hypothesis testing techniques to examine the output of several independent chains and so determines whether there is any evidence against the hypothesis of convergence. We illustrate the proposed method on some examples from the literature.     

Structured Markov Chain Monte Carlo

Abstract

This article introduces a general method for Bayesian computing in richly parameterized models, structured Markov chain Monte Carlo (SMCMC), that is based on a blocked hybrid of the Gibbs sampling and Metropolis—Hastings algorithms. SMCMC speeds algorithm convergence by using the structure that is present in the problem to suggest an appropriate Metropolis—Hastings candidate distribution. Although the approach is easiest to describe for hierarchical normal linear models, we show that its extension to both nonnormal and nonlinear cases is straightforward. After describing the method in detail we compare its performance (in terms of run time and autocorrelation in the samples) to other existing methods, including the single-site updating Gibbs sampler available in the popular BUGS software package. Our results suggest significant improvements in convergence for many problems using SMCMC, as well as broad applicability of the method, including previously intractable hierarchical nonlinear model settings.     

Markov Chain Monte Carlo Convergence Assessment via Two-Way Analysis of Variance

Abstract

In this article we discuss the problem of assessing the performance of Markov chain Monte Carlo (MCMC) algorithms on the basis of simulation output. In essence, we extend the original ideas of Gelman and Rubin and, more recently, Brooks and Gelman, to problems where we are able to split the variation inherent within the MCMC simulation output into two distinct groups. We show how such a diagnostic may be useful in assessing the performance of MCMC samplers addressing model choice problems, such as the reversible jump MCMC algorithm. In the model choice context, we show how the reversible jump MCMC simulation output for parameters that retain a coherent interpretation throughout the simulation, can be used to assess convergence. By considering various decompositions of the sampling variance of this parameter, we can assess the performance of our MCMC sampler in terms of its mixing properties both within and between models and we illustrate our approach in both the graphical Gaussian models and normal mixtures context. Finally, we provide an example of the application of our diagnostic to the assessment of the influence of different starting values on MCMC simulation output, thereby illustrating the wider utility of our method beyond the Bayesian model choice and reversible jump MCMC context.     

On Markov Chain Monte Carlo Acceleration

Abstract

Markov chain Monte Carlo (MCMC) methods are currently enjoying a surge of interest within the statistical community. The goal of this work is to formalize and support two distinct adaptive strategies that typically accelerate the convergence of an MCMC algorithm. One approach is through resampling; the other incorporates adaptive switching of the transition kernel. Support is both by analytic arguments and simulation study. Application is envisioned in low-dimensional but nontrivial problems. Two pathological illustrations are presented. Connections with reparameterization are discussed as well as possible difficulties with infinitely often adaptation.     

Conditioning in Markov Chain Monte Carlo

Abstract

The so-called “Rao-Blackwellized” estimators proposed by Gelfand and Smith do not always reduce variance in Markov chain Monte Carlo when the dependence in the Markov chain is taken into account. An illustrative example is given, and a theorem characterizing the necessary and sufficient condition for such an estimator to always reduce variance is proved.     

Markov Chain Monte Carlo from Lagrangian Dynamics

Hamiltonian Monte Carlo (HMC) improves the computational efficiency of the Metropolis–Hastings algorithm by reducing its random walk behavior. Riemannian HMC (RHMC) further improves the performance of HMC by exploiting the geometric properties of the parameter space. However, the geometric integrator used for RHMC involves implicit equations that require fixed-point iterations. In some cases, the computational overhead for solving implicit equations undermines RHMC’s benefits. In an attempt to circumvent this problem, we propose an explicit integrator that replaces the momentum variable in RHMC by velocity. We show that the resulting transformation is equivalent to transforming Riemannian Hamiltonian dynamics to Lagrangian dynamics. Experimental results suggest that our method improves RHMC’s overall computational efficiency in the cases considered. All computer programs and datasets are available online (http://www.ics.uci.edu/babaks/Site/Codes.html) to allow replication of the results reported in this article.     

Phylogenetic Inference for Binary Data on Dendograms Using Markov Chain Monte Carlo

Abstract

Using a stochastic model for the evolution of discrete characters among a group of organisms, we derive a Markov chain that simulates a Bayesian posterior distribution on the space of dendograms. A transformation of the tree into a canonical cophenetic matrix form, with distinct entries along its superdiagonal, suggests a simple proposal distribution for selecting candidate trees “close” to the current tree in the chain. We apply the consequent Metropolis algorithm to published restriction site data on nine species of plants. The Markov chain mixes well from random starting trees, generating reproducible estimates and confidence sets for the path of evolution.     

Markov chain Monte Carlo Using an Approximation

This article presents a method for generating samples from an unnormalized posterior distribution f(·) using Markov chain Monte Carlo (MCMC) in which the evaluation of f(·) is very difficult or computationally demanding. Commonly, a less computationally demanding, perhaps local, approximation to f(·) is available, say f^**_x(·). An algorithm is proposed to generate an MCMC that uses such an approximation to calculate acceptance probabilities at each step of a modified Metropolis–Hastings algorithm. Once a proposal is accepted using the approximation, f(·) is calculated with full precision ensuring convergence to the desired distribution. We give sufficient conditions for the algorithm to converge to f(·) and give both theoretical and practical justifications for its usage. Typical applications are in inverse problems using physical data models where computing time is dominated by complex model simulation. We outline Bayesian inference and computing for inverse problems. A stylized example is given of recovering resistor values in a network from electrical measurements made at the boundary. Although this inverse problem has appeared in studies of underground reservoirs, it has primarily been chosen for pedagogical value because model simulation has precisely the same computational structure as a finite element method solution of the complete electrode model used in conductivity imaging, or “electrical impedance tomography.” This example shows a dramatic decrease in CPU time, compared to a standard Metropolis–Hastings algorithm.     

A Practical Sequential Stopping Rule for High-Dimensional Markov Chain Monte Carlo

A current challenge for many Bayesian analyses is determining when to terminate high-dimensional Markov chain Monte Carlo simulations. To this end, we propose using an automated sequential stopping procedure that terminates the simulation when the computational uncertainty is small relative to the posterior uncertainty. Further, we show this stopping rule is equivalent to stopping when the effective sample size is sufficiently large. Such a stopping rule has previously been shown to work well in settings with posteriors of moderate dimension. In this article, we illustrate its utility in high-dimensional simulations while overcoming some current computational issues. As examples, we consider two complex Bayesian analyses on spatially and temporally correlated datasets. The first involves a dynamic space-time model on weather station data and the second a spatial variable selection model on fMRI brain imaging data. Our results show the sequential stopping rule is easy to implement, provides uncertainty estimates, and performs well in high-dimensional settings. Supplementary materials for this article are available online.     

Counting Contingency Tables via Multistage Markov Chain Monte Carlo

This article describes a multistage Markov chain Monte Carlo (MSMCMC) procedure for estimating the count, , where denotes the set of all a × b contingency tables with specified row and column sums and m total entries. On each stage s = 1, …, r, Hastings–Metropolis (HM) sampling generates states with equilibrium distribution , with inverse-temperature schedule β₁ = 0 < β₂ < ??? < β _r < β _{r + 1} = ∞; nonnegative penalty function H, with global minima H(x) = 0 only for ; and superset , which facilitates sampling by relaxing column sums while maintaining row sums. Two kernels are employed for nominating states. For small β _s , one admits moderate-to-large penalty changes. For large β _s , the other allows only small changes. Neither kernel admits local minima, thus avoiding an impediment to convergence. Preliminary sampling determines when to switch from one kernel to the other to minimize relative error. Cycling through stages in the order r to 1, rather than 1 to r, speeds convergence for large β _s . A comparison of estimates for examples, whose dimensions range from 15 to 24, with exact counts based on Barvinok’s algorithm and estimates based on sequential importance sampling (SIS) favors these alternatives. However, the comparison strongly favors MSMCMC for an example with 64 dimensions. It estimated count with 3.3354 × 10^{? 3} relative error, whereas the exact counting method was unable to produce a result in more than 182 CPU (computational) days of execution, and SIS would have required at least 42 times as much CPU time to generate an estimate with the same relative error. This latter comparison confirms the known limitations of exact counting methods and of SIS for larger-dimensional problems and suggests that MSMCMC may be a suitable alternative. Proofs not given in the article appear in the Appendix in the online supplemental materials.     

Adaptive Markov Chain Monte Carlo for Bayesian Variable Selection

We describe adaptive Markov chain Monte Carlo (MCMC) methods for sampling posterior distributions arising from Bayesian variable selection problems. Point-mass mixture priors are commonly used in Bayesian variable selection problems in regression. However, for generalized linear and nonlinear models where the conditional densities cannot be obtained directly, the resulting mixture posterior may be difficult to sample using standard MCMC methods due to multimodality. We introduce an adaptive MCMC scheme that automatically tunes the parameters of a family of mixture proposal distributions during simulation. The resulting chain adapts to sample efficiently from multimodal target distributions. For variable selection problems point-mass components are included in the mixture, and the associated weights adapt to approximate marginal posterior variable inclusion probabilities, while the remaining components approximate the posterior over nonzero values. The resulting sampler transitions efficiently between models, performing parameter estimation and variable selection simultaneously. Ergodicity and convergence are guaranteed by limiting the adaptation based on recent theoretical results. The algorithm is demonstrated on a logistic regression model, a sparse kernel regression, and a random field model from statistical biophysics; in each case the adaptive algorithm dramatically outperforms traditional MH algorithms. Supplementary materials for this article are available online.     

Importance Link Function Estimation for Markov Chain Monte Carlo Methods

Abstract

This article focuses on improving estimation for Markov chain Monte Carlo simulation. The proposed methodology is based upon the use of importance link functions. With the help of appropriate importance sampling weights, effective estimates of functionals are developed. The method is most easily applied to irreducible Markov chains, where application is typically immediate. An important conceptual point is the applicability of the method to reducible Markov chains through the use of many-to-many importance link functions. Applications discussed include estimation of marginal genotypic probabilities for pedigree data, estimation for models with and without influential observations, and importance sampling for a target distribution with thick tails.     

Markov Chain Monte Carlo With Mixtures of Mutually Singular Distributions

Markov chain Monte Carlo (MCMC) methods for Bayesian computation are mostly used when the dominating measure is the Lebesgue measure, the counting measure, or a product of these. Many Bayesian problems give rise to distributions that are not dominated by the Lebesgue measure or the counting measure alone. In this article we introduce a simple framework for using MCMC algorithms in Bayesian computation with mixtures of mutually singular distributions. The idea is to find a common dominating measure that allows the use of traditional Metropolis-Hastings algorithms. In particular, using our formulation, the Gibbs sampler can be used whenever the full conditionals are available. We compare our formulation with the reversible jump approach and show that the two are closely related. We give results for three examples, involving testing a normal mean, variable selection in regression, and hypothesis testing for differential gene expression under multiple conditions. This allows us to compare the three methods considered: Metropolis-Hastings with mutually singular distributions, Gibbs sampler with mutually singular distributions, and reversible jump. In our examples, we found the Gibbs sampler to be more precise and to need considerably less computer time than the other methods. In addition, the full conditionals used in the Gibbs sampler can be used to further improve the estimates of the model posterior probabilities via Rao-Blackwellization, at no extra cost.     

Estimation of Binary Markov Random Fields Using Markov chain Monte Carlo

This article compares three binary Markov random fields (MRFs) which are popular Bayesian priors for spatial smoothing. These are the Ising prior and two priors based on latent Gaussian MRFs. Concern is given to the selection of a suitable Markov chain Monte Carlo (MCMC) sampling scheme for each prior. The properties of the three priors and sampling schemes are investigated in the context of three empirical examples. The first is a simulated dataset, the second involves a confocal fluorescence microscopy dataset, while the third is based on the analysis of functional magnetic resonance imaging (fMRI) data. In the case of the Ising prior, single site and multi-site Swendsen-Wang sampling schemes are both considered. The single site scheme is shown to work consistently well, while it is shown that the Swendsen-Wang algorithm can have convergence problems. The sampling schemes for the priors are extended to generate the smoothing parameters, so that estimation becomes fully automatic. Although this works well, it is found that for highly contiguous images fixing smoothing parameters to very high values can improve results by injecting additional prior information concerning the level of contiguity in the image. The relative properties of the three binary MRFs are investigated, and it is shown how the Ising prior in particular defines sharp edges and encourages clustering. In addition, one of the latent Gaussian MRF priors is shown to be unable to distinguish between higher levels of smoothing. In the context of the fMRI example we also undertake a simulation study.     

基于贝叶斯MCMC算法的美式期权定价

鉴于美式期权的定价具有后向迭代搜索特征,本文结合Longstaff和Schwartz提出的美式期权定价的最小二乘模拟方法,研究基于马尔科夫链蒙特卡洛算法对回归方程系数的估计,实现对美式期权的双重模拟定价.通过对无红利美式看跌股票期权定价进行大量实证模拟,从期权价值定价误差等方面同著名的最小二乘蒙特卡洛模拟方法进行对比分析,结果表明基于MCMC回归算法给出的美式期权定价具有更高的精确度.模拟实证结果表明本文提出的对美式期权定价方法具有较好的可行性、有效性与广泛的适用性.该方法的不足之处就是类似于一般的蒙特卡洛方法,会使得求解的计算量有所加大.     

Resampling Markov Chain Monte Carlo Algorithms: Basic Analysis and Empirical Comparisons

Sampling from complex distributions is an important but challenging topic in scientific and statistical computation. We synthesize three ideas, tempering, resampling, and Markov moving, and propose a general framework of resampling Markov chain Monte Carlo (MCMC). This framework not only accommodates various existing algorithms, including resample-move, importance resampling MCMC, and equi-energy sampling, but also leads to a generalized resample-move algorithm. We provide some basic analysis of these algorithms within the general framework, and present three simulation studies to compare these algorithms together with parallel tempering in the difficult situation where new modes emerge in the tails of previous tempering distributions. Our analysis and empirical results suggest that generalized resample-move tends to perform the best among all the algorithms studied when the Markov kernels lead to fast mixing or even locally so toward restricted distributions, whereas parallel tempering tends to perform the best when the Markov kernels lead to slow mixing, without even converging fast to restricted distributions. Moreover, importance resampling MCMC and equi-energy sampling perform similarly to each other, often worse than independence Metropolis resampling MCMC. Therefore, different algorithms seem to have advantages in different settings.     

A Markov Chain Monte Carlo comparison of variance estimators for the sampling of particulate mixtures

During the sampling of particulate mixtures, samples taken are analyzed for their mass concentration, which generally has non‐zero sample‐to‐sample variance. Bias, variance, and mean squared error (MSE) of a number of variance estimators, derived by Geelhoed, were studied in this article. The Monte Carlo simulation was applied using an observable first‐order Markov Chain with transition probabilities that served as a model for the sample drawing process. Because the bias and variance of a variance estimator could depend on the specific circumstances under which it is applied, Monte Carlo simulation was performed for a wide range of practically relevant scenarios. Using the ‘smallest mean squared error’ as a criterion, an adaptation of an estimator based on a first‐order Taylor linearization of the sample concentration is the best. An estimator based on the Horvitz–Thompson estimator is not practically applicable because of the potentially high MSE for the cases studied. The results indicate that the Poisson estimator leads to a biased estimator for the variance of fundamental sampling error (up to 428% absolute value of relative bias) in case of low levels of grouping and segregation. The uncertainty of the results obtained by the simulations was also addressed and it was found that the results were not significantly affected. The potentials of a recently described other approach are discussed for extending the first‐order Markov Chain described here to account also for higher levels of grouping and segregation. Copyright © 2013 John Wiley & Sons, Ltd.     

Interweaving Markov Chain Monte Carlo Strategies for Efficient Estimation of Dynamic Linear Models

In dynamic linear models (DLMs) with unknown fixed parameters, a standard Markov chain Monte Carlo (MCMC) sampling strategy is to alternate sampling of latent states conditional on fixed parameters and sampling of fixed parameters conditional on latent states. In some regions of the parameter space, this standard data augmentation (DA) algorithm can be inefficient. To improve efficiency, we apply the interweaving strategies of Yu and Meng to DLMs. For this, we introduce three novel alternative DAs for DLMs: the scaled errors, wrongly scaled errors, and wrongly scaled disturbances. With the latent states and the less well known scaled disturbances, this yields five unique DAs to employ in MCMC algorithms. Each DA implies a unique MCMC sampling strategy and they can be combined into interweaving and alternating strategies that improve MCMC efficiency. We assess these strategies using the local level model and demonstrate that several strategies improve efficiency relative to the standard approach and the most efficient strategy interweaves the scaled errors and scaled disturbances. Supplementary materials are available online for this article.     

The Alive Particle Filter and Its Use in Particle Markov Chain Monte Carlo

In the following article, we investigate a particle filter for approximating Feynman–Kac models with indicator potentials and we use this algorithm within Markov chain Monte Carlo (MCMC) to learn static parameters of the model. Examples of such models include approximate Bayesian computation (ABC) posteriors associated with hidden Markov models (HMMs) or rare-event problems. Such models require the use of advanced particle filter or MCMC algorithms to perform estimation. One of the drawbacks of existing particle filters is that they may “collapse,” in that the algorithm may terminate early, due to the indicator potentials. In this article, using a newly developed special case of the locally adaptive particle filter, we use an algorithm that can deal with this latter problem, while introducing a random cost per-time step. In particular, we show how this algorithm can be used within MCMC, using particle MCMC. It is established that, when not taking into account computational time, when the new MCMC algorithm is applied to a simplified model it has a lower asymptotic variance in comparison to a standard particle MCMC algorithm. Numerical examples are presented for ABC approximations of HMMs.