Markov Chain Monte Carlo:
innovations and applications in statistics, physics, and
bioinformatics
(1 - 28 Mar 2004)
~ Abstracts ~
Perfect simulation
Wilfrid Kendall, University of Warwick, UK
Perfect (or exact) simulation refers to the art of converting suitable Markov Chain Monte Carlo algorithms into algorithms which return exact draws from the target distribution, instead of long-time approximations. The ideas of perfect simulation stretch back a long long way, but they sprang into prominence as a result of a groundbreaking paper of Propp and Wilson in 1996, which showed how to obtain exact draws from (for example) the critical Ising model.
In these lectures I will describe several themes of perfect simulation: (1) the original or classic Coupling From The Past algorithm (CFTP); (2) variations with exploit small-set or split-chain constructions from Markov chain theory (small-set CFTP); (3) generalizations which deal with non-monotonic and non-uniformly ergodic examples (dominated CFTP); and (4) striking results relating CFTP to an apparently different algorithm due originally to Fill. The talks (which will be organized approximately under the four headings above) will be illustrated with online animations of CFTP simulations and will describe related theoretical issues. The objective of these tutorial lectures is to give a sound and clear exposition of these themes, and hence to promote an interplay of ideas with practitioners of Markov Chain Monte Carlo.
Sequential Monte Carlo methods and
their applications: An overview and recent developments
Rong Chen, University of Illinois at Chicago
The sequential Monte Carlo (SMC) methodology recently emerged in the fields of statistics and engineering has shown a great promise in solving a large class of highly complex inference and optimization problems, opening up new frontiers for cross-fertilization between statistical science and many application areas.
SMC can be loosely defined as a family of techniques that use Monte Carlo simulations to solve on-line estimation and prediction problems in stochastic dynamic systems. By recursively generating random samples of the state variables, SMC adapts flexibly to the dynamics of the underlying stochastic systems. In this talk, we present an overview of the current status of SMC, its applications and some recent developments. Specifically, we will introduce a general framework of SMC, and discuss various strategies on fine-tuning the different components in the SMC algorithm, in order to achieve maximum efficiency. SMC applications, specially those in science, engineering, bioinformatics and financial data analysis will be discussed.
Introduction to Markov Chain Monte
Carlo (MC) simulations and their statistical analysis (with
web-based Fortran code)
Bernd A. Berg, Florida State University
The first (and possibly part of the second) lecture provides a self-contained Introduction to Statistics and, subsequently, our presentation of Markov chain MC simulations is build on this foundation. An additional advantage is that the basic statistics methods are later at hand, when data analysis techniques are needed. Our approach to statistics is strictly from the sampling perspective.
In the second lecture the conventional Markov Chain MC algorithms are defined. The point of departure in is a treatment of the 1953 Metropolis algorithm for simulations of the Gibbs canonical ensemble. The heat bath algorithm follows. To illustrate these methods, our systems of choice are discrete Potts and continuous O(n) models. Autocorrelations are encountered and, in particular, we investigate the integrated autocorrelation time in some detail. This is expected to lead well into the third lecture.
Advanced MC simulations are the last subject, covering part of lecture three and all of lecture four. Topics may include multicanonical methods, event driven simulations, cluster algorithms, parallel tempering and large scale simulations.
Numerical assignments with Fortran solutions are provided provided for all topics and the code can be downloaded from the web.
New sequential Monte Carlo methods
Armand Doucet, University of Cambridge
Sequential Monte Carlo (SMC) methods are a general class of algorithms to sample from a sequence of probability distributions defined on spaces of increasing dimension. They have become increasingly popular in physics, statistics and engineering over the last few years. Examples of applications include self-avoidoing random walks and optimal filtering. In this talk we show how it is also possible to develop SMC methods to sample from a sequence of probability distributions defined on a common space; i.e. in a context where one usually uses MCMC. A couple of algorithms have already been presented previously in the literature. Our framework is much more general. It identifies some optimal strategies leading to efficient algorithms and it has a much wider range of applications than previous methods. We demonstrate the performance of these new algorithms on sequential Bayesian estimation and global optimization problems. Precise convergence results have been established and will also be presented.
Joint work with Pierre Del Moral (CNRS, Toulouse) & Gareth Peters (Cambridge)
Time dependent update functions for
perfect sampling
Mark Huber, Duke University, USA
Perfect sampling algorithms generate random variates drawn exactly from a target distribution without the need to know mixing times of Markov chains. The most widespread technique for perfect sampling, Coupling From the Past (CFTP), used a time homogeneous update function: at every time step the state was advanced by using a random draw from the same family of functions. However, the basic technique remains the same if the update function is allowed to change with each time step. By varying the family of functions that is used based on prior outcomes, algorithms can be made both faster and easier to implement. This technique is equivalent to using a non-Markovian coupling of the chain. Examples for discrete and continuous state spaces will be considered.
Cluster simulations under a
constraint
Henk W.J. Blöte, Delft University of Technology, The
Netherlands
In most Monte Carlo simulations of lattice models, there is no conservation law acting on global properties such as the magnetization of the Ising model, or the number of vacancies in the Blume-Capel model or spin-1 Ising model. Such a conservation law can be imposed by the use of Kawasaki dynamics: local updates that leave the magnetization unchanged. However, critical-slowing down then appears to be quite serious. Here I describe the so called geometric cluster algorithm, which is applicable to models subject to a conservation law. It is found to suppresses critical slowing down in applications; for the Potts model this can be shown analytically.
Computer algorithms for percolation
processes
Robert M. Ziff, University of Michigan
The percolation model has been actively studied by computer for over forty years, and in that time enormous amounts of computer time and a great deal of effort has been expended in finding precise transition points, static and dynamic exponents, tests of universality, and more recently investigations of various crossing problems and other macroscopic universal properties. Also, in that time, several specialized computer algorithm techniques have been developed and optimized, and several of these have applications to other problems in physics (such as cluster identification). In this talk I shall review several of the methods that are used, such as the Hoshen-Kopelman, neighbor-search, and the Newman-Ziff methods, and mention some of the other "lattice-less" techniques developed recently (Vollmayr, Paul, Grassberger, etc.) Applications include finding crossing probabilities in various geometries, confirming theories of convergence of thresholds (and finding irrelevant scaling exponents), and in universal forms of critical cluster size distribution. The random number generator I use (a four-tap shift-register type) will also be discussed.
Auxiliary variable MCMC methods in
Bayesian statistical pattern recognition models, with
applications in functional genomics
Chris Holmes, University of Oxford, UK
We discuss recent work on auxiliary variable MCMC methods for automated sampling in classification (pattern recognition) models with categorical response variables, either binary or multinomial. It is well known in the binary case that the GLM with probit link affords an efficient data augmentation sampling scheme using truncated standard normal random variates. In this talk we demonstrate how this can be extended to logistic regression using scale mixtures of normals. The logit link is more often the preferred choice in applications due to the strong interpretation of the resulting regression coefficients in terms of the inter-class log-odds; it also has much better numerical properties in the tails. Furthermore we show that the generalisation to multinomial (multi-class) response data is trivial. We illustrate the approach with examples in functional genomics, using free-knot regression splines and variable covariate set GLMs.
Independent particle filters
Junni Zhang, University of Beijing
Sequential Monte Carlo methods, especially the particle filter (PF) and its various modifications, have been used effectively in dealing with state space models and other stochastic dynamic systems. The standard PF samples the current state through the underlying dynamics of the process, then uses current observation to evaluate the samples' importance weight. However, it is often the case that the current observation provides significantly more information about the current state than the state dynamics. In this case, sampling based on current observation often produces more efficient samples than using the state evolving dynamics alone. In addition, if the main objective is to make statistical inference about the current state, not the entire sequence of states, sampling using the current information achieves certain kind of discharging, i.e., removing the effect of earlier states, which improves the efficiency of statistical inference. Based on these two observations, we proposes a new variant of the particle filter, the independent particle filter (IPF). It generates independent and identically distributed samples of the current state, using only the current observation. Each sample is then matched with multiple samples of the previous states for evaluating the importance weight. We present some theoretical results showing that this strategy improves efficiency of estimation as well as reduces resampling frequency in many situations. We also discuss some extensions of the IPF. Several synthetic examples are then used to demonstrate the effectiveness of the method.
MCMC for the analysis of genetic
data on pedigrees
Elizabeth Thompson, University of Washington
Pedigree data provide a prime example of a highly structured stochastic system, on which exact computations are often infeasible, but which are well suited to MCMC methods of analysis. First I will introduce the basic laws of inheritance of genomes, that give rise to the conditional independence structure of pedigree data, and a natural characterization of latent variables. Second, assuming knowledge of Metropolis-Hastings algorithms, block-Gibbs samplers, and the Baum algorithm for HMMs, I will show how effective methods for sampling latent data conditional of genetic marker data can be developed. I will then discuss the Monte Carlo estimation of likelihood surfaces, and the particular problem of estimation of multipoint linkage likelihoods used to map genes underlying traits in human family data. (Time-permitting, I may also discuss alternative MCMC approaches to detecting genetic linkage from human pedigree data.)
Pseudo-Bayes MCMC for the
estimation of multipoint linkage likelihoods
Elizabeth Thompson, University of Washington
In localizing the genes than affect human traits, it is important to use data on multiple related individuals and at multiple genetic loci. However, the computation of likelihoods on extended pedigrees, for multiple DNA markers, is computationally intractable if there are extensive missing data. Additionally, several previous MCMC approaches have shown poor mixing. Here we combine elements of several previous approaches, and some newer elements of MCMC methodology, to address some previously intractable problems, and show how, even when exact computation is feasible, MCMC can be the more computationally efficient approach. Results are illustrated by an application to a real pedigree data set. This work is joint with Dr. Andrew George.
A survey of Quasi-Monte Carlo
methods
Harald Niederreiter, National University of Singapore
Quasi-Monte Carlo methods are deterministic versions of Monte Carlo methods, in the sense that the random samples used in the implementation of a Monte Carlo method are replaced by judiciously chosen deterministic points with good distribution properties. Quasi-Monte Carlo methods outperform classical Monte Carlo methods in many problems of scientific computing. The talk provides a survey of quasi-Monte Carlo methods, with special emphasis on their applications to high-dimensional numerical integration.
Applications of the geometric
cluster algorithm
Youjin Deng, Delft University, The Netherlands
The geometric cluster algorithm is applied to a number of model systems subject to a constraint. One of the subjects investigated concerns the critical behavior of such systems, which is strongly modified by the so called Fisher renormalization mechanism.
Cluster simulation of the quantum
transverse Potts model
Youjin Deng, Delft University, The Netherlands
We formulate a cluster Monte Carlo method for the anisotropic limit of the lattice $q$-state Potts model in $d$ dimensions, which is, in effect, equivalent with the $(d-1)$-dimensional quantum transverse $q$-state Potts model. Simulations in curved geometries by this method enable numerical applications of conformal mappings in three dimensions.
Cluster simulation of the
antiferromagnetic triangular Ising model in a field
Xiaofeng Qian, Leiden University, The Netherlands
The critical line of the triangular Ising antiferromagnet in a field is investigated by means of numerical techniques which include geometric cluster simulations. At low temperatures, the critical amplitudes decrease as predicted by the renormalization theory.
Multicanonical chain growth method
for folding lattice proteins
Wolfhard Janke, Universität Leipzig, Germany
We present a temperature-independent Monte Carlo method for the determination of the density of states of lattice proteins that combines the fast ground-state search strategy of nPERM chain growth algorithms with multicanonical reweighting ideas for sampling the full energy space. Since the density of states contains all energetic information of a statistical system, we can directly calculate the mean energy, specific heat, Helmholtz free energy, and entropy for all temperatures. We demonstrate the efficiency of this method in applications to lattice proteins described by the effective hydrophobic-polar HP model. For a selected sample of HP sequences we first discuss ground-state properties, and then identify and characterize the transitions between native, globule, and random coil states. For short sequences with up to 19 monomers we validate our numerical results by comparison with exact enumeration data.
Rugged metropolis sampling for
peptides
Bernd A. Berg, Florida State University
Metropolis simulations of all-atom models of peptides (i.e. small proteins) are considered. Inspired by the funnel picture of Bryngelson and Wolyness, a transformation of the updating probabilities of the dihedral angles is defined, which uses probability densities from a higher temperature to improve the algorithmic performance at a lower temperature. The method is suitable for canonical as well as for generalized ensemble simulations. A simple approximation to the full transformation is tested at room temperature for Met-Enkephalin in vacuum. Integrated autocorrelation times are found to be reduced by factors close to two and a similar improvement due to generalized ensemble methods enters multiplicatively.
Strategies for MCMC acceleration
David Draper, University of California
Simulation-based MCMC methods for approximating high-dimensional integrals have sparked a revolution in inferential and predictive applications of Bayesian statistics in the last 15 years. The approach is extremely general, but the output of MCMC samplers often exhibits a high degree of positive autocorrelation, limiting the rate (per CPU second) at which information about the posterior distribution of interest is obtained. In this talk I will describe two or three strategies for achieving Monte Carlo acceleration in MCMC samplers and present some preliminary results.
Markov chain Monte Carlo for
statistical inference
Julian Besag, University of Washington
Markov chain Monte Carlo (MCMC) methods have been used in physics for more than 50 years and in spatial statistics and digital image analysis for more than 20 but it is only in the last 15 that they been applied to solve a wide range of computational problems in general statistical inference. Their impact on Bayesian computation has been especially important, since MCMC enables one to carry out the high{dimensional integrations involved in analyzing extremely complex formulations, usually in a quite routine manner, to adequate accuracy. The basic idea is very simple: if one can simulate a statistical distribution, then one can learn everything about it; and, indeed, about all other distributions that are close to it.
The tutorial provides an introduction to MCMC and its applications to statistical inference. It begins by discussing ordinary Monte Carlo methods, which have the same goals but can only rarely be implemented. This leads naturally into the description and some Bayesian examples of MCMC based on Hastings' algorithm, with Metropolis' method and the Gibbs sampler as special cases. The tutorial concludes with some more specialized topics, including a selection from adaptive slice sampling, MCMC maximum likelihood, MCMC exact p{values, the Langevin{Hastings algorithm, auxiliary variables techniques, perfect MCMC sampling, and reversible jumps methods for target spaces of varying dimensions.
Adaptive sampling schemes for
Bayesian variable selection
David Nott, University of New South Wales, Australia
Variable selection in linear regression models is an important problem and the simplest example of an important class of problems in regression. Bayesian methods for variable selection and for dealing with model uncertainty have become increasingly popular in recent years, due in large part to advances in Markov chain Monte Carlo (MCMC) computational algorithms. In this talk we consider adaptive MCMC sampling schemes for Bayesian variable selection in Gaussian linear regression models which improve on standard Metropolis-Hastings MCMC algorithms by making use of accumulated information about the posterior distribution during sampling for the construction of proposal distributions. Adaptation needs to be done very carefully to ensure that sampling is from the correct ergodic distribution. We give conditions for the validity of an adaptive sampling scheme in this problem (and for simulating from a distribution on a finite state space in general), and suggest a class of adaptive proposal densities which uses best linear prediction to approximate the Gibbs sampler. Our sampling scheme is computationally much faster per iteration than the Gibbs sampler, and when this is taken into account the efficiency gains when using our sampling scheme compared to alternative approaches are substantial in terms of precision of estimation of posterior quantities of interest for a given amount of computation time. We compare our method with other sampling schemes for examples involving both real and simulated data. This is joint work with Robert Kohn.
Population Monte Carlo methods
Christian Robert, CEREMADE, Universite Paris Dauphine
Importance sampling methods have been rather neglected by MCMC algorithms since their infancy, even though they share many common features. This talk shows that importance sampling can be iterated to produce more accurate approximations to iid sampling from a target distribution, than sequential sampling from an MCMC algorithm. We first illustrate the adaptability of the joint scheme on several missing data examples, including mixtures of distributions, switching ARMA models, the ion channel model of Hodgson (1999), and stochastic volatility models.
Links to papers: http://www.ceremade.dauphine.fr/CMD/preprints02/0215ihp2.ps.gz http://www.ceremade.dauphine.fr/~xian/cmr03.pdf http://www.ceremade.dauphine.fr/CMD/preprints03/0335_gmr03.pdf
Simulation algorithms for potts
models
Jian-Sheng Wang, National University of Singapore
Many of the interesting Monte Carlo simulation algorithms are first used with the q-state Potts models. In this talk, we first review some of the early development such as the Sweeny’s algorithm and Swendsen-Wang cluster algorithm. We introduce the transition matrix Monte Carlo method. Finally, we discuss a recent new algorithm termed “binary tree summation Monte Carlo” which has a few interesting features such as independent samples for every sweep. This algorithm is a generalization of the Newman-Ziff method for percolation.
An introduction to Monte Carlo
methods in statistical physics
David P. Landau, The University of Georgia
Over the past half century Monte Carlo methods have become valuable tools for uncovering the nature of thermodynamic behavior of diverse physical systems. These lectures will provide an introduction to both simple sampling and importance sampling (e.g. Metropolis) Monte Carlo methods, and show how they can be applied to typical problems in statistical physics. A few "case studies" will be given to demonstrate how these methods can be used. Problems arising from long time scales and finite size effects will be described, and a brief overview of innovative algorithms that attempt to reduce correlation time effects will be given. (More complete treatments will be presented by other speakers.) We will also attempt to highlight strategies and the philosophy behind successful Monte Carlo studies. Lastly, a new approach to Monte Carlo simulations, the "random walk with a flat histogram" method (generally termed Wang-Landau sampling), will be described and sample results will be shown to demonstrate the effectiveness of this approach.
Learning a multivariate Gaussian
mixture model with the reversible jump MCMC algorithm
Kap Luk Chan, Nanyang Technological University, Singapore
This talk report our recent work on fully Bayesian inference in the multivariate Gaussian mixture model using the reversible jump Markov chain Monte Carlo algorithm. In order to follow the constraints of preserving the first two moments before and after the split or combine moves, we focus our attention on a multivariate Gaussian mixture model with the covariance matrices of all components sharing a common eigenvector matrix and propose an approach to the construction of the reversible jump Markov chain Monte Carlo algorithm for this model. We present the algorithm and its experimental evaluation. Experimental results on various data sets demonstrated the efficacy of our algorithm.
Bayesian color image segmentation
through MRF labeling with multivariate reversible jump Markov
Chain Monte Carlo
Kap Luk Chan, Nanyang Technological University, Singapore
In this work, we developed a method for segmentation color images. The method is developed under the Bayesian framework in which the image is modeled by a hierarchical Markov random field and its segmentation is treated as a labeling problem. Our method uses the Potts model for the unobserved label field and a multivariate Gaussian mixture model for the observed image data. Determining the number of the region in an image is through the estimation of number of Gaussian mixture components using a multivariate reversible jump Markov chain Monte Carlo method. The algorithm performs image segmentation according to the maximum a posteriori criterion using simulated annealing technique. Experimental results on synthesized color collages and natural images demonstrate the efficacy of the proposed segmentation algorithm.
Numerical simulations of critical
dynamics far from equilibrium
Bo Zheng, Zhejiang University, China
Numerical simulations of critical dynamics far from equilibrium in the past ten years will be reviewed. Recent progress in Kosterlitz-Thouless phase transitions, disordered systems and deterministic dynamics will be reported.
A decision support system for
winner determination in multi-objective combinatorial auctions
Kannan Balaji, Singapore MIT Alliance, NUS
Deciding the winners in a combinatorial auction with multiple objectives is a notoriously hard decision problem. A support system which would assist the auctioneer in making such complex decisions, is a highly desirable tool for her in that scenario. This work addresses the design of such a tool. Using the decision support system the auctioneer can set preference on the various objectives and evaluate the multiple winner sets computed by the system to determine the winner set for an auction. For computing multiple winner sets the system uses an algorithm based on the Metropolis algorithm. Through simulation experiments, the proposed system is validated to be, (i) consistent - the response of the system matches the preferences set by the auctioneer, (ii) convergent - converges to a set of pareto-optimal solution (winner set) in a reasonable amount of time, and (iii) robust - scalable for large number of bids, bidders and items in the auction.
Monte Carlo methods to calculate
the density of states and their applications
Yutaka Okabe, Tokyo Metropolitan University
The Monte Carlo methods using the recently proposed Wang-Landau algorithm together with the broad histogram relation are applied to the study of several spin models. With these methods, we can get the highly accurate data for the energy density of states. We study the two-dimensional (2D) fully-frustrated clock models to reveal the interplay of the magnetic ordering belonging to the Kosterlitz-Thouless phase transition and the chiral ordering. We also treat the 2D antiferromagnetic three-state Potts model to investigate the unusual scaling at low temperatures.
An introduction to clusters,
histograms, optimization, and an adaptive approach in Monte
Carlo simulations
Robert H. Swendsen, Carnegie Mellon University
These lectures will introduce some of the approaches and techniques used to increase the efficiency of Monte Carlo simulations in statistical physics. We will discuss cluster methods that greatly decrease the problem of critical slowing down, such as the Swendsen-Wang and Wolff algorithms, as well as the Replica Monte Carlo method for more efficient simulation of spin glasses and other models with frustration. Histogram analysis methods allow thermodynamic functions to be calculated as continuous functions of temperature and magnetic field. We will also introduce Dynamically Optimized Monte Carlo and the Acceptance Ratio Method, which provide for the simultaneous optimization of a large number of simulation parameters for such problems as the simulation of biological molecules. Finally, we will present a recent approach to adaptive sampling for the efficient calculation of free energies as a function of reaction coordinates or other variables.
The entropy of classical systems
of distinguishable particles
Robert H. Swendsen, Carnegie Mellon University
This talk will revisit the definition of the entropy that was proposed by Ludwig Boltzmann over 100 years ago. Although Boltzmann’s insights have provided the foundation of statistical mechanics, his definition will be shown to contain a flaw that becomes apparent when applied to classical systems of distinguishable particles. The flaw is significant both for the interpretation of computer simulations and the understanding of the second law of thermodynamics. A new definition will be proposed that eliminates the problems with the traditional Boltzmann definition.
Perfect perpetuity and GARCH
Wilfrid Kendall, University of Warwick
Report on work in progress. Joint work with Elke Thoennes
