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 longtime 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 smallset or
splitchain constructions from Markov chain theory (smallset
CFTP); (3) generalizations which deal with nonmonotonic and
nonuniformly 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.
« Back...
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 crossfertilization between statistical science and many
application areas.
SMC can be loosely defined as a family of techniques that
use Monte Carlo simulations to solve online 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
finetuning 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.
« Back...
Introduction to Markov Chain Monte
Carlo (MC) simulations and their statistical analysis (with
webbased Fortran code)
Bernd A. Berg, Florida State University
The first (and possibly part of the second) lecture
provides a selfcontained 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.
« Back...
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 selfavoidoing 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)
« Back...
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 nonMarkovian
coupling of the chain. Examples for discrete and continuous
state spaces will be considered.
« Back...
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 BlumeCapel model or spin1 Ising model. Such a
conservation law can be imposed by the use of Kawasaki
dynamics: local updates that leave the magnetization
unchanged. However, criticalslowing 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.
« Back...
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 HoshenKopelman, neighborsearch, and the NewmanZiff
methods, and mention some of the other "latticeless"
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 fourtap shiftregister type)
will also be discussed.
« Back...
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 interclass logodds; it also has
much better numerical properties in the tails. Furthermore we
show that the generalisation to multinomial (multiclass)
response data is trivial. We illustrate the approach with
examples in functional genomics, using freeknot regression
splines and variable covariate set GLMs.
« Back...
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.
« Back...
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
MetropolisHastings algorithms, blockGibbs 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. (Timepermitting, I may also
discuss alternative MCMC approaches to detecting genetic
linkage from human pedigree data.)
« Back...
PseudoBayes 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.
« Back...
A survey of QuasiMonte Carlo
methods
Harald Niederreiter, National University of Singapore
QuasiMonte 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. QuasiMonte Carlo methods outperform classical
Monte Carlo methods in many problems of scientific computing.
The talk provides a survey of quasiMonte Carlo methods, with
special emphasis on their applications to highdimensional
numerical integration.
« Back...
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.
« Back...
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
$(d1)$dimensional quantum transverse $q$state Potts model.
Simulations in curved geometries by this method enable
numerical applications of conformal mappings in three
dimensions.
« Back...
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.
« Back...
Multicanonical chain growth method
for folding lattice proteins
Wolfhard Janke, Universität Leipzig, Germany
We present a temperatureindependent Monte Carlo method for
the determination of the density of states of lattice proteins
that combines the fast groundstate 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
hydrophobicpolar HP model. For a selected sample of HP
sequences we first discuss groundstate 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.
« Back...
Rugged metropolis sampling for
peptides
Bernd A. Berg, Florida State University
Metropolis simulations of allatom 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 MetEnkephalin 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.
« Back...
Strategies for MCMC acceleration
David Draper, University of California
Simulationbased MCMC methods for approximating
highdimensional 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.
« Back...
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.
« Back...
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
MetropolisHastings 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.
« Back...
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
« Back...
Simulation algorithms for potts
models
JianSheng Wang, National University of Singapore
Many of the interesting Monte Carlo simulation algorithms
are first used with the qstate Potts models. In this talk, we
first review some of the early development such as the
Sweeny’s algorithm and SwendsenWang 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 NewmanZiff method for percolation.
« Back...
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 WangLandau sampling),
will be described and sample results will be shown to
demonstrate the effectiveness of this approach.
« Back...
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.
« Back...
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.
« Back...
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 KosterlitzThouless phase transitions, disordered
systems and deterministic dynamics will be reported.
« Back...
A decision support system for
winner determination in multiobjective 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 paretooptimal solution (winner set) in a
reasonable amount of time, and (iii) robust  scalable for
large number of bids, bidders and items in the auction.
« Back...
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
WangLandau 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 twodimensional (2D)
fullyfrustrated clock models to reveal the interplay of the
magnetic ordering belonging to the KosterlitzThouless phase
transition and the chiral ordering. We also treat the 2D
antiferromagnetic threestate Potts model to investigate the
unusual scaling at low temperatures.
« Back...
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 SwendsenWang 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.
« Back...
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.
« Back...
Perfect perpetuity and GARCH
Wilfrid Kendall, University of Warwick
Report on work in progress. Joint work with Elke Thoennes
« Back...
