Transcript Exploring the connection between sampling problems in Bayesian

Exploring the connection
between sampling problems
in Bayesian inference and
statistical mechanics
Andrew Pohorille
NASA-Ames Research Center
Outline
• Enhanced sampling of pdfs
flat histograms
multicanonical method
Wang-Landau
transition probability method
parallel tempering
• Dynamical systems
• Stochastic kinetics
Enhanced sampling
techniques
Preliminaries
define: variables x, , N
a function U(x,,N)
a probability:
marginalize x
energies are
Boltzmann-distributed
 = 1/kT
partition function Q(x,,N)
define “free energy” or “thermodynamic potential”
The problem:
What to do if
is difficult to estimate because we can’t
get sufficient statistics for all of interest.
Flat histogram approach
pdf sampled uniformly for all , N
weight

Example:
original pdf
weighted pdf
marginalization
“canonical”
partition function
1. get 
2. get Q
General MC sampling scheme
insertion
deletion
adjust weights
free energy
insertion
deletion
adjust free energy
Multicanonical method
normalization of 
bin count
shift
Berg and Neuhaus, Phys. Rev. Lett. 68, 9 (1992)
The algorithm
• Start with any weights (e.g. 1(N) = 0)
• Perform a short simulation and measure
P(N; 1) as histogram
• Update weights according to
or better
• Iterate until P(N; 1) is flat
Typical example
Wang-Landau sampling
Example: estimate entropies for (discrete) states
entropy
acceptance criterion
update constant
Wang and Landau, Phys. Rev. Lett. 86, 2050 (2001),
Phys. Rev. E 64, 056101 (2001)
The algorithm
• Set entropies of all states to zero; set initial g
• Accept/reject according to the criterion:
• Always update the entropy estimate for the
end state
• When the pdf is flat reduce g
Transition probability method
J
I
i
j
K
Wang, Tay, Swendsen, Phys. Rev. Lett., 82 476 (1999)
Fitzgerald et al. J. Stat. Phys. 98, 321 (1999)
detailed balance
macroscopic
detailed balance
Parallel tempering
Dynamical systems
Assumption -ergodicity
The idea: the system evolves according to
equations of motion (possibly Hamiltonian)
 we need to assign masses to variables
Advantages
• No need to design sampling techniques
• Specialized methods for efficient
sampling are available (Laio-Parrinello,
Adaptive Biasing Force)
Disadvantages
• No probabilistic sampling
• Possibly complications with assignment
of masses
Two formulations:
• Hamiltonian
• Lagrangian
Numerical, iterative solution of
equations of motion (a trajectory)
Assignment of masses
Energy equipartition needs to be
addressed
• Masses too large - slow motions
• Masses too small - difficult integration of
equations of motion
• Large separation of masses - adiabatic
separation
Thermostats are available
Lagrangian - e.g. Nose-Hoover
Hamiltonian - Leimkuhler
Adaptive Biasing Force
force
A =
b


∂H()/∂  d *

a
*
Darve and Pohorile, J. Chem. Phys. 115:9169-9183 (2001).
A
Summary
• A variety of techniques are available to
sample efficiently rarely visited states.
• Adaptive methods are based on modifying
sampling while building the solution.
• One can construct dynamical systems to seek
the solution and efficient adaptive techniques
are available. But one needs to do it carefully.
Stochastic kinetics
The problem
•
•
•
•
{Xi} objects, i = 1,…N
ni copies of each objects
undergo r transformations
With rates {k},  = 1,…r
Assumptions
• {k} are constant
• The process is Markovian (well-stirred
reactor)
Example
7 objects
5 transformations
Deterministic solution
kinetics (differential equations)
concentrations
steady state (algebraic equations)
Works well for large {ni} (fluctuations suppressed)
A statistical alternative
generate trajectories
• which reaction occurs next?
• when does it occur?
next reaction
is  at time 
next reaction is 
at any time
any reaction at time 
Direct method - Algorithm
• Initialization
• Calculate the propensities {ai}
• Choose  (r.n.)
• Choose  (r.n.)
• Update no. of molecules and reset tt+ 
• Go to step 2
Gillespie, J. Chem. Phys. 81, 2340 (1977)
First reaction method -Algorithm
• Initialization
• Calculate the propensities {ai}
• For each  generate  according to (r.n.)
•
•
•
•
Choose reaction for which is  the shortest
Set = 
Update no. of molecules and reset tt+ 
Go to step 2
Gillespie, J. Chem. Phys. 81, 2340 (1977)
Next reaction method
Complexity - O(log r)
Gibson and Bruck,
J. Phys. Chem. A 104
1876 (2000)
Extensions
•
•
•
•
k = k(t) (GB)
Non-Markovian processes (GB)
Stiff reactions (Eric van den Eijden)
Enzymatic reactions (A.P.)