Transcript Document

Applications of Extended
Ensemble Monte Carlo
Yukito IBA
The Institute of Statistical
Mathematics, Tokyo, Japan
Extended Ensemble MCMC
A Generic Name which indicates:
Parallel Tempering,
Simulated Tempering,
Multicanonical Sampling,
Wang-Landau, …
Umbrella Sampling Valleau and Torrie
1970s
Contents
1. Basic Algorithms
Parallel Tempering .vs Multicanonical
2. Exact Calculation with soft Constraints
Lattice Protein / Counting Tables
3. Rare Events and Large Deviations
Communication Channels
Chaotic Dynamical Systems
Basic Algorithms
Parallel Tempering
Multicanonical Monte Carlo
References in physics
• Iba (2001) Extended Ensemble Monte Carlo
Int. J. Mod. Phys. C12 p.623.
A draft version will be found at
http://arxiv.org/abs/cond-mat/0012323
• Landau and Binder (2005)
A Guide to Monte Carlo Simulations in Statistical Physics
(2nd ed. , Cambridge)
• A number of preprints will be found in
Los Alamos Arxiv on the web.
# This slide is added after the talk
Slow mixing by multimodal dist.
× ×
×
Bridging
fast mixing
high temperature
slow mixing
low temperature
Path Sampling
1.Facilitate Mixing
2.Calculate Normalizing
Constant (“free energy”)
“Path Sampling”
Gelman and Meng (1998)
stress 2. but 1. is also important
In Physics: from 2. to 1.
1970s  1990s
Parallel Tempering
a.k.a. Replica Exchange MC
Metropolis Coupled MCMC
Geyer (1991), Kimura and Taki (1991)
Hukushima and Nemoto (1996)
Iba(1993, in Japanese)
Simulate Many “Replica”s in Parallel
MCMC in a Product Space
Examples
Gibbs Distributions with different
temperatures
Any Family parameterized by
a hyperparameter
Exchange of Replicas
K=4
Accept/Reject Exchange
Calculate Metropolis Ratio
Generate a Uniform Random Number
in [0,1) and accept exchange
iff
Detailed Balance in Extended Space
Combined Distribution
Multicanonical Monte Carlo
Berg et al. (1991,1992)
sufficient statistics
Exponential Family
sufficient statistics
Energy
not Expectation
Density of States
The number of
which satisfy
Multicanonical Sampling
Weight and Marginal Distribution
Original (Gibbs)
Multicanonical
Random
flat marginal distribution
Scanning broad range of E
Reweighting
Formally, for arbitrary
Practically,
it holds.
is required,
else the variance diverges in a large system.
Q. How can we do without knowledge
on D(E)
Ans．
Estimate D(E) in the preliminary runs
Simplest Method : Entropic Sampling
k th simulation
in
Estimation of Density of States
(Ising Model on a random net)
k=1
2
3
4
5
10
11
14
k=15
30000 MCS
Estimation of D(E)
• Histogram
Entropic Sampling
• Piecewise Linear
Original
Multicanonical
• Fitting, Kernel Density Estimation ..
• Wang-Landau
• Flat Histogram
Continuous Cases
D(E)dE : Non-trivial Task
Parallel Tempering / Multicanonical
parallel tempering combined distribution
simulated tempering mixture distribution
to approximate
Potts model (2-dim, q=10 states)
disordered
ordered
Phase Coexistence/ 1st order transition
parameter (Inverse Temperature)
changes
sufficient statistics (Energy)
jumps
water and ice
coexists
Potts model (2-dim, q=10 states)
disordered
bridging by multicanoncal construction
ordered
Comparison
@ Simple Liquids , Potts Models ..
Multicanonical seems better than Parallel Tempering
@ But, for more difficult cases ?
ex. Ising Model with three spin Interaction
Soft Constraints
Lattice Protein
Counting Tables
The results on Lattice Protein are taken from joint works
with G Chikenji (Nagoya Univ) and Macoto Kikuchi (Osaka Univ)
Some examples are also taken from the other works
by Kikuchi and coworkers.
Lattice Protein Model
Motivation
Simplest Models of Protein
Lattice Protein :
Prototype of “Protein-like molecules”
Ising Model :
Prototype of “Magnets”
Lattice Protein (2-dim HP)
sequence of
and
FIXED
corresponds to 2-types of amino acids (H and P)
conformation of chain
STOCHASTIC VARIABLE
SELF AVOIDING
(SELF OVERLAP is not allowed)
IMPORTANT!
Energy (HP model)
the energy of conformation x is defined as
E(X)=
- the number of
in x
Examples
E= -1
E=0
Here we do not count the pairs neighboring on the chain
but it is not essential because the difference is const.
MCMC
Slow Mixing
Even Non-Ergodicity with local moves
Bastolla et al. (1998)
Proteins 32 pp. 52-66
Chikenji et al. (1999)
Phys. Rev. Lett. 83 pp.1886-1889
Multicanonical
Multicanonical w.r.t. E only
NOT SUFFUCIENT
Self-Avoiding condition is essential
Soft Constraint
Self-Avoiding condition is essential
Soft Constraint
is the number of
monomers that occupy the site i
Multi Self-Overlap Sampling
Multi Self-Overlap Ensemble
Bivariate Density of States
in the (E,V) plane
Samples with
are used for the calculation
of the averages
EXACT !!
V
(self-overlap)
E
Generation of Paths
by softening of constraints
E
V=0
large V
Comparison with multicanonical
with hard self-avoiding constraint
switching
between
three groups of
minimum energy
states
of a sequence
conventional
(hard constraint)
proposed
(soft constraint)
optimization
optimization (polymer pairs)
Nakanishi and Kikuchi (2006)
J.Phys.Soc.Jpn. 75 pp.064803 / q-bio/0603024
double peaks
An Advantage of
the method
is that it can use
for the sampling
at any temperature
as well as
optimization
3-dim
Yue and Dill (1995)
Proc. Nat. Acad. Sci. 92 pp.146-150
Another Sequence
Chikenji and Kikuchi (2000)
Proc. Nat. Acad. Sci 97
pp.14273 - 14277
non monotonic change
of the structure
Related Works
Self-Avoiding Walk without interaction / Univariate Extension
Vorontsov-Velyaminov et al. :
J.Phys.Chem.,100,1153-1158 (1996)
Lattice Protein but not exact / Soft-Constraint without control
Shakhnovich et al.
Physical Review Letters 67 1665 (1991)
Continuous homopolymer -- Relax “core”
Liu and Berne
J Chem Phys 99 6071 (1993)
See References in
Extended Ensemble Monte Carlo, Int J Phys C 12 623-656 (2001)
but esp. for continuous cases,
there seems more in these five years
Counting Tables
Pinn et al. (1998)
Counting Magic Squares
Soft Constraints
+
Parallel Tempering
４
９
２
３
５
７
８
１
６
Sampling by MCMC
Multiple Maxima
Parallel Tempering
Normalization Constant
calculated by Path sampling
(thermodynamic integration)
Latin square (3x3)
For each column, any given number appears once and only once
For each raw, any given number appears once and only once
Latin square (26x26)
# This sample is taken from the web.
Counting Latin Squares
• 6
410000 MCS x 27 replicas
• 10
510000 MCS x 49 replicas
• 11
510000 MCS x 49 replicas
other 3 trials
Counting Tables
Soft Constraints + Extended Ensemble MC
“Quick and Dirty” ways of calculating the
number of tables that satisfy given constraints.
It may not be optimal for a special case,
but no case-by-case tricks, no mathematics,
and no brain is required.
Rare Events and Large Deviations
Communication Channels #1
Chaotic Dynamical Systems #2
# 1 Part of joint works with
Koji Hukushima (Tokyo Univ).
# 2 Part of joint works with
Tatsuo Yanagita (Hokkaido Univ).
(The result shown here is mostly due to him )
Applications of MCMC
Statistical Physics (1953 ~ )
Statistical Inference (1970s,1980s, 1990~)
Solution to any problem on
sampling & counting
estimation of large deviation
generation of rare events
Noisy Communication Channel
prior
decode
by Viterbi, loopy BP,
MCMC
encoded & degraded
distance
(bit errors)
Distribution of Bit Errors
Kronecker delta
tails of the distribution is not easy to estimate
Introduction of MCMC
NOT sampling from the posterior
Sampling noise in channels by the MCMC
Given an error-correcting code
Some patterns of noise are very harmful
difficult to correct
Some patterns of noise are safe
easy to correct
Multicanonical Strategy
MCMC sampling of
and
Broad distribution of
 Broad distribution of distance
Multicanonical Sampling
MCMC Sampling
with the weight
exactly what we want,
but can be ..
and
Estimated by the iteration
of preliminary runs
flat marginal distribution
Enable efficient calculation
of the tails of the distribution
(large deviation)
Scanning broad range of bit errors
Example
Convolutional Code
Viterbi decoding
Binary Symmetric Channel
Fix the number of noise (flipped bits)
Simplification
In this case
is independent of
Set
Binary Symmetric Channel
Fix the number of noise (flipped bits)
sum over the possible
positions of the noise
Simulation
difficult to
calculate by simple
sampling
the number of bit errors
Correlated Channels
It will be useful for the study of errorcorrecting code in a correlated channel.
Without assuming models of correlation
in the channel we can sample relevant
correlation patterns.
Rare events in Dynamical Systems
Deterministic Chaos
Doll et al. (1994), Kurchan et al. (2005)
Sasa, Hayashi, Kawasaki .. (2005 ~)
Stagger and Step Method Sweet, Nusse, and Yorke (2001)
(Mostly) Stochastic Dynamics
Chandler Group
Frenkel et al.
and more …
Transition Path Sampling
Sampling Initial Condition
Sampling initial condition of
Chaotic dynamical systems
Rare Events
Double Pendulum
Unstable fixed points
control
and stop the pendulum
one of the three positions
energy dissipation
(friction) is assumed
i.e., no time reversal sym.
Definition of artificial “energy”
stop
= zero velocity
stopping position
T is max time
penalty to
long time
Metropolis step
Perturb Initial State
Evaluate “Energy”
Integrate Equation of Motion
and
Simulate Trajectory
Reject or Accept
for given T
 Parallel Tempering
An animation by Yanagita is shown in the talk,
but might not be seen on the web.
Summary
Extended Ensemble + Soft Constraint
strategy gives simple solutions to a
number of difficult problems
The use of MCMC should not be restricted
to the standard ones in Physics and
Bayesian Statistics.
To explore new applications of MCMC
extended ensemble MC will play an
essential role.
END