Metropolis–Hastings algorithms with adaptive proposals

Different strategies have been proposed to improve mixing and convergence properties of Markov Chain Monte Carlo algorithms. These are mainly concerned with customizing the proposal density in the Metropolis–Hastings algorithm to the specific target density and require a detailed exploratory analysis of the stationary distribution and/or some preliminary experiments to determine an efficient proposal. Various Metropolis–Hastings algorithms have been suggested that make use of previously sampled states in defining an adaptive proposal density. Here we propose a general class of adaptive Metropolis–Hastings algorithms based on Metropolis–Hastings-within-Gibbs sampling. For the case of a one-dimensional target distribution, we present two novel algorithms using mixtures of triangular and trapezoidal densities. These can also be seen as improved versions of the all-purpose adaptive rejection Metropolis sampling (ARMS) algorithm to sample from non-logconcave univariate densities. Using various different examples, we demonstrate their properties and efficiencies and point out their advantages over ARMS and other adaptive alternatives such as the Normal Kernel Coupler.     

Improved Sampling-Importance Resampling and Reduced Bias Importance Sampling

Abstract.  The sampling-importance resampling (SIR) algorithm aims at drawing a random sample from a target distribution π. First, a sample is drawn from a proposal distribution q , and then from this a smaller sample is drawn with sample probabilities proportional to the importance ratios π/ q . We propose here a simple adjustment of the sample probabilities and show that this gives faster convergence. The results indicate that our version converges better also for small sample sizes. The SIR algorithms are compared with the Metropolis–Hastings (MH) algorithm with independent proposals. Although MH converges asymptotically faster, the results indicate that our improved SIR version is better than MH for small sample sizes. We also establish a connection between the SIR algorithms and importance sampling with normalized weights. We show that the use of adjusted SIR sample probabilities as importance weights reduces the bias of the importance sampling estimate.     

Stochastic approximation Monte Carlo EM for change-point analysis

In the expectation–maximization (EM) algorithm for maximum likelihood estimation from incomplete data, Markov chain Monte Carlo (MCMC) methods have been used in change-point inference for a long time when the expectation step is intractable. However, the conventional MCMC algorithms tend to get trapped in local mode in simulating from the posterior distribution of change points. To overcome this problem, in this paper we propose a stochastic approximation Monte Carlo version of EM (SAMCEM), which is a combination of adaptive Markov chain Monte Carlo and EM utilizing a maximum likelihood method. SAMCEM is compared with the stochastic approximation version of EM and reversible jump Markov chain Monte Carlo version of EM on simulated and real datasets. The numerical results indicate that SAMCEM can outperform among the three methods by producing much more accurate parameter estimates and the ability to achieve change-point positions and estimates simultaneously.     

Mode Jumping Proposals in MCMC

Markov chain Monte Carlo algorithms generate samples from a target distribution by simulating a Markov chain. Large flexibility exists in specification of transition matrix of the chain. In practice, however, most algorithms used only allow small changes in the state vector in each iteration. This choice typically causes problems for multi-modal distributions as moves between modes become rare and, in turn, results in slow convergence to the target distribution. In this paper we consider continuous distributions on R ⁿ and specify how optimization for local maxima of the target distribution can be incorporated in the specification of the Markov chain. Thereby, we obtain a chain with frequent jumps between modes. We demonstrate the effectiveness of the approach in three examples. The first considers a simple mixture of bivariate normal distributions, whereas the two last examples consider sampling from posterior distributions based on previously analysed data sets.     

Simulation from a Target Distribution Based on Discretization and Weighting

We present a simulation method which is based on discretization of the state space of the target distribution (or some of its components) followed by proper weighting of the simulated output. The method can be used in order to simplify certain Monte Carlo and Markov chain Monte Carlo algorithms. Its main advantage is that the autocorrelations of the weighted output almost vanish and therefore standard methods for iid samples can be used for estimating the Monte Carlo standard errors. We illustrate the method via toy examples as well as the well-known dugongs and Challenger datasets.     

Convergence of Heavy-tailed Monte Carlo Markov Chain Algorithms

Abstract.  In this paper, we use recent results of Jarner & Roberts ( Ann. Appl. Probab., 12, 2002, 224) to show polynomial convergence rates of Monte Carlo Markov Chain algorithms with polynomial target distributions, in particular random-walk Metropolis algorithms, Langevin algorithms and independence samplers. We also use similar methodology to consider polynomial convergence of the Gibbs sampler on a constrained state space. The main result for the random-walk Metropolis algorithm is that heavy-tailed proposal distributions lead to higher rates of convergence and thus to qualitatively better algorithms as measured, for instance, by the existence of central limit theorems for higher moments. Thus, the paper gives for the first time a theoretical justification for the common belief that heavy-tailed proposal distributions improve convergence in the context of random-walk Metropolis algorithms. Similar results are shown to hold for Langevin algorithms and the independence sampler, while results for the mixing of Gibbs samplers on uniform distributions on constrained spaces are rather different in character.     

An empirical study of five multivariate tests for the single-factor repeated measures model

A Monte Carlo study was used to examine the Type I error and power values of five multivariate tests for the single-factor repeated measures model The performance of Hotelling's T2 and four nonparametric tests, including a chi-square and an F-test version of a rank-transform procedure, were investigated for different distributions, sample sizes, and numbers of repeated measures. The results indicated that both Hotellings T* and the F-test version of the rank-transform performed well, producing Type I error rates which were close to the nominal value. The chi-square version of the rank-transform test, on the other hand, produced inflated Type I error rates for every condition studied. The Hotelling and F-test version of the rank-transform procedure showed similar power for moderately-skewed distributions, but for strongly skewed distributions the F-test showed much better power. The performance of the other nonparametric tests depended heavily on sample size. Based on these results, the F-test version of the rank-transform procedure is recommended for the single-factor repeated measures model.     

Generation of multivariate distributions by vertical density representation

Troutt (1991,1993) proposed the idea of the vertical density representation (VDR) based on Box-Millar method. Kotz, Fang and Liang (1997) provided a systematic study on the multivariate vertical density representation (MVDR). Suppose that we want to generate a random vector X[d]Rⁿthat has a density function ?(x). The key point of using the MVDR is to generate the uniform distribution on [D]_?(v) = {x :?(x) = v} for any v > 0 which is the surface in RⁿIn this paper we use the conditional distribution method to generate the uniform distribution on a domain or on some surface and based on it we proposed an alternative version of the MVDR(type 2 MVDR), by which one can transfer the problem of generating a random vector X with given density f to one of generating (X, X_n+i) that follows the uniform distribution on a region in Rⁿ⁺¹defined by ?. Several examples indicate that the proposed method is quite practical.     

Mixture Kalman filters

In treating dynamic systems, sequential Monte Carlo methods use discrete samples to represent a complicated probability distribution and use rejection sampling, importance sampling and weighted resampling to complete the on-line 'filtering' task. We propose a special sequential Monte Carlo method, the mixture Kalman filter, which uses a random mixture of the Gaussian distributions to approximate a target distribution. It is designed for on-line estimation and prediction of conditional and partial conditional dynamic linear models, which are themselves a class of widely used non-linear systems and also serve to approximate many others. Compared with a few available filtering methods including Monte Carlo methods, the gain in efficiency that is provided by the mixture Kalman filter can be very substantial. Another contribution of the paper is the formulation of many non-linear systems into conditional or partial conditional linear form, to which the mixture Kalman filter can be applied. Examples in target tracking and digital communications are given to demonstrate the procedures proposed.     

Latin hypercube sampling with multidimensional uniformity

Complex models can only be realized a limited number of times due to large computational requirements. Methods exist for generating input parameters for model realizations including Monte Carlo simulation (MCS) and Latin hypercube sampling (LHS). Recent algorithms such as maximinLHS seek to maximize the minimum distance between model inputs in the multivariate space. A novel extension of Latin hypercube sampling (LHSMDU) for multivariate models is developed here that increases the multidimensional uniformity of the input parameters through sequential realization elimination. Correlations are considered in the LHSMDU sampling matrix using a Cholesky decomposition of the correlation matrix. Computer code implementing the proposed algorithm supplements this article. A simulation study comparing MCS, LHS, maximinLHS and LHSMDU demonstrates that increased multidimensional uniformity can significantly improve realization efficiency and that LHSMDU is effective for large multivariate problems.     

Algorithms

Abstract

The main reason for the limited use of multivariate discrete models is the difficulty in calculating the required probabilities. The task is usually undertaken via recursive relationships which become quite computationally demanding for high dimensions and large values. The present paper discusses efficient algorithms that make use of the recurrence relationships in a manner that reduces the computational effort and thus allow for easy and cheap calculation of the probabilities. The most common multivariate discrete distribution, the multivariate Poisson distribution is treated. Real data problems are provided to motivate the use of the proposed strategies. Extensions of our results are discussed. It is shown that probabilities, for a large family of multivariate distributions, can be computed efficiently via our algorithms.     

Numerical computation of multivariate t-probabilities with application to power calculation of multiple contrasts

A new method to calculate the multivariate t-distribution is introduced. We provide a series of substitutions, which transform the starting q-variate integral into one over the (q—1)-dimensional hypercube. In this situation standard numerical integration methods can be applied. Three algorithms are discussed in detail. As an application we derive an expression to calculate the power of multiple contrast tests assuming normally distributed data.     

Copula, marginal distributions and model selection: a Bayesian note

Copula functions and marginal distributions are combined to produce multivariate distributions. We show advantages of estimating all parameters of these models using the Bayesian approach, which can be done with standard Markov chain Monte Carlo algorithms. Deviance-based model selection criteria are also discussed when applied to copula models since they are invariant under monotone increasing transformations of the marginals. We focus on the deviance information criterion. The joint estimation takes into account all dependence structure of the parameters’ posterior distributions in our chosen model selection criteria. Two Monte Carlo studies are conducted to show that model identification improves when the model parameters are jointly estimated. We study the Bayesian estimation of all unknown quantities at once considering bivariate copula functions and three known marginal distributions.     

On Block Updating in Markov Random Field Models for Disease Mapping

Gaussian Markov random field (GMRF) models are commonly used to model spatial correlation in disease mapping applications. For Bayesian inference by MCMC, so far mainly single-site updating algorithms have been considered. However, convergence and mixing properties of such algorithms can be extremely poor due to strong dependencies of parameters in the posterior distribution. In this paper, we propose various block sampling algorithms in order to improve the MCMC performance. The methodology is rather general, allows for non-standard full conditionals, and can be applied in a modular fashion in a large number of different scenarios. For illustration we consider three different applications: two formulations for spatial modelling of a single disease (with and without additional unstructured parameters respectively), and one formulation for the joint analysis of two diseases. The results indicate that the largest benefits are obtained if parameters and the corresponding hyperparameter are updated jointly in one large block. Implementation of such block algorithms is relatively easy using methods for fast sampling of Gaussian Markov random fields ( Rue, 2001 ). By comparison, Monte Carlo estimates based on single-site updating can be rather misleading, even for very long runs. Our results may have wider relevance for efficient MCMC simulation in hierarchical models with Markov random field components.     

New sequential Monte Carlo methods for nonlinear dynamic systems

In this paper we present several new sequential Monte Carlo (SMC) algorithms for online estimation (filtering) of nonlinear dynamic systems. SMC has been shown to be a powerful tool for dealing with complex dynamic systems. It sequentially generates Monte Carlo samples from a proposal distribution, adjusted by a set of importance weight with respect to a target distribution, to facilitate statistical inferences on the characteristic (state) of the system. The key to a successful implementation of SMC in complex problems is the design of an efficient proposal distribution from which the Monte Carlo samples are generated. We propose several such proposal distributions that are efficient yet easy to generate samples from. They are efficient because they tend to utilize both the information in the state process and the observations. They are all Gaussian distributions hence are easy to sample from. The central ideas of the conventional nonlinear filters, such as extended Kalman filter, unscented Kalman filter and the Gaussian quadrature filter, are used to construct these proposal distributions. The effectiveness of the proposed algorithms are demonstrated through two applications—real time target tracking and the multiuser parameter tracking in CDMA communication systems.This work was supported in part by the U.S. National Science Foundation (NSF) under grants CCR-9875314, CCR-9980599, DMS-9982846, DMS-0073651 and DMS-0073601.     

Optimal scaling of discrete approximations to Langevin diffusions

We consider the optimal scaling problem for proposal distributions in Hastings–Metropolis algorithms derived from Langevin diffusions. We prove an asymptotic diffusion limit theorem and show that the relative efficiency of the algorithm can be characterized by its overall acceptance rate, independently of the target distribution. The asymptotically optimal acceptance rate is 0.574. We show that, as a function of dimension n , the complexity of the algorithm is O ( n ^1/3), which compares favourably with the O ( n ) complexity of random walk Metropolis algorithms. We illustrate this comparison with some example simulations.     

Exact monte carlo tests using several statistics

Concepts of ranking and boundary of multivariate statistics are discussed and applied to the simultaneous use of several test statistics calculated for data and simulated replicates. An example of residual analysis in regression is given using layer ranks and supplementary simulation with a stopping rule.     

Maximizing generalized linear mixed model likelihoods with an automated Monte Carlo EM algorithm

Two new implementations of the EM algorithm are proposed for maximum likelihood fitting of generalized linear mixed models. Both methods use random (independent and identically distributed) sampling to construct Monte Carlo approximations at the E-step. One approach involves generating random samples from the exact conditional distribution of the random effects (given the data) by rejection sampling, using the marginal distribution as a candidate. The second method uses a multivariate t importance sampling approximation. In many applications the two methods are complementary. Rejection sampling is more efficient when sample sizes are small, whereas importance sampling is better with larger sample sizes. Monte Carlo approximation using random samples allows the Monte Carlo error at each iteration to be assessed by using standard central limit theory combined with Taylor series methods. Specifically, we construct a sandwich variance estimate for the maximizer at each approximate E-step. This suggests a rule for automatically increasing the Monte Carlo sample size after iterations in which the true EM step is swamped by Monte Carlo error. In contrast, techniques for assessing Monte Carlo error have not been developed for use with alternative implementations of Monte Carlo EM algorithms utilizing Markov chain Monte Carlo E-step approximations. Three different data sets, including the infamous salamander data of McCullagh and Nelder, are used to illustrate the techniques and to compare them with the alternatives. The results show that the methods proposed can be considerably more efficient than those based on Markov chain Monte Carlo algorithms. However, the methods proposed may break down when the intractable integrals in the likelihood function are of high dimension.     

Adaptive methods for sequential importance sampling with application to state space models

In this paper we discuss new adaptive proposal strategies for sequential Monte Carlo algorithms—also known as particle filters—relying on criteria evaluating the quality of the proposed particles. The choice of the proposal distribution is a major concern and can dramatically influence the quality of the estimates. Thus, we show how the long-used coefficient of variation (suggested by Kong et al. in J. Am. Stat. Assoc. 89(278–288):590–599, 1994) of the weights can be used for estimating the chi-square distance between the target and instrumental distributions of the auxiliary particle filter. As a by-product of this analysis we obtain an auxiliary adjustment multiplier weight type for which this chi-square distance is minimal. Moreover, we establish an empirical estimate of linear complexity of the Kullback-Leibler divergence between the involved distributions. Guided by these results, we discuss adaptive designing of the particle filter proposal distribution and illustrate the methods on a numerical example. This work was partly supported by the National Research Agency (ANR) under the program “ANR-05-BLAN-0299”.     

Importance sampling type estimators based on approximate marginal Markov chain Monte Carlo

We consider importance sampling (IS) type weighted estimators based on Markov chain Monte Carlo (MCMC) targeting an approximate marginal of the target distribution. In the context of Bayesian latent variable models, the MCMC typically operates on the hyperparameters, and the subsequent weighting may be based on IS or sequential Monte Carlo (SMC), but allows for multilevel techniques as well. The IS approach provides a natural alternative to delayed acceptance (DA) pseudo-marginal/particle MCMC, and has many advantages over DA, including a straightforward parallelization and additional flexibility in MCMC implementation. We detail minimal conditions which ensure strong consistency of the suggested estimators, and provide central limit theorems with expressions for asymptotic variances. We demonstrate how our method can make use of SMC in the state space models context, using Laplace approximations and time-discretized diffusions. Our experimental results are promising and show that the IS-type approach can provide substantial gains relative to an analogous DA scheme, and is often competitive even without parallelization.