Transcript Document

Spatial decay of correlations and efficient
methods for computing partition functions.
David Gamarnik
Joint work with
Antar Bandyopadhyay (U of Chalmers),
Dmitriy Rogozhnikov-Katz (MIT)
June, 2006
Talk Outline
• Partition functions. Where do we see them ?
• Computing partition functions. Monte Carlo method.
• Correlation decay.
• Our results: computation tree, correlation decay and
• Deterministic algorithm for approximate computation
of partition functions for matchings and colorings.
• Structural results and large deviations.
• Conclusions
Partition functions - feature in
• statistical mechanics
Gibbs measure and Ising models
• computer science and combinatorics
counting problems
• queueing theory
product form loss networks
• electrical engineering
coding theory
• statistics
bayesian networks
Queueing Example: loss system with shared resources
• Calls arrive as
and request communication link
• Call is accepted only if no other link attached to
• Unaccepted call is lost
• Call duration is
is occupied
• At any moment the set of occupied links is a matching
• The steady-state distribution is product form:
- partition function.
Example II: multicasting in a communication network
• Calls arrive as
and occupy a node
• Call is accepted only if no neighbor
• Unaccepted call is lost
• Call duration is
is occupied
• At any moment the set of occupied nodes is an independent set
• The steady-state distribution is product form:
- partition function.
Example III: multicasting with many frequencies
• Calls arrive as
and occupy a node
• Call is accepted only if no neighbor
• Unaccepted call is lost
• Call duration is
and use frequency
is occupied and uses the same fr.
• At any moment the set of occupied nodes is a partial coloring
• The steady-state distribution is product form:
- partition function.
From queueing to statistical physics
• Communication (matching) problem with
- Gibbs distribution on Ising type models.
Important object in stat mechanics.
- inverse temperature
- Monomer-dimer model.
From statistical physics to computer science
• Matching problem with
total number of matchings in the graph (counting)
Can we compute partition function?...
… easily when the underlying graph is a tree.
Example (independent sets)
This leads to
Theorem. Spitzer [75], Zachary [83,85], Kelly [85]. In
-ary tree
Is independent from the boundary condition (correlation decay) if and only if
Implication: if the graph is locally-tree like,
then computing marginals is possible in the
regime
Ramanan, Sengupta, Zeidins, Mitra [2002]
Related work on unicasting and multicasting
on trees
Computing partition function in general
• Valiant [1979] -- #P complexity class. Exact counting is hard for most of the
counting problems (matchings, independent sets, colorings, etc. )
• Focus – approximate counting.
Our contribution: - use of correlation decay for
- Deterministic (non-simulation based) algorithms for computing approximately
partition functions for
• Matchings in low degree graphs
• Colorings in low degree graphs
- Structural properties of partition functions in special classes of graphs
Existing approaches for computing partition function
• Main approximation method: Markov Chain Monte Carlo (MCMC)
• The MCMC is based on
- computing the marginal distribution
via simulation.
- reducing partition function to marginals (cavity method).
Jerrum, Valiant & Vazirani [86]
• Technical challenge: establishing rapid mixing
Computing partition functions using MCMC
Jerrum [95].
Coloring
Vigoda [2000]. Coloring
Coloring
Jerrum & Sinclair [89]
Matchings
Dyer, Frieze & Kannan [91]
Volume of a convex body.
Jerrum, Sinclair & Vigoda [2004].
Permanents
(Temporal) Decay of correlations in Markov chains
A Markov chain
with transition matrix
decay of correlation (mixes)
if and only if it is aperiodic
(Spatial) Decay of correlations
Same thing, but time
is replaced by a “spatial” distance
satisfies
Correlation Decay
A sequence of spatially (graph) related random variables
exhibits a decay of correlation (long-range independence),
if when
is large
Principle motivation - statistical phyisics. Uniqueness of Gibbs measures on
infinite lattices, Dobrushin [60s].
What is known about correlation decay ?
Spitzer [75], Zachary [83,85], Kelly [85].
Independent
sets
-ary tree
J. van den Berg [98]
Matchings
Goldberg, Martin & Paterson [05].
Coloring.
General graphs
Jonasson [01].
Coloring.
Regular trees
Link between Correlation Decay and rapid mixing of MC:
•
•
CD implies rapid mixing in subexp. growing graphs.
Converse not true Kenyon, Mossel & Peres [01].
Our results:
Theorem I. There exists a deterministic algorithm for computing
approximately the partition function corresponding to matchings in
graphs with constant degree (deterministic FPTAS), for arbitrary
Related work: Weitz [2005]. Self-avoiding walk based algorithm for counting
independent sets when
Algorithm and proof:
Step I. Reduce computing partition function to computing marginals (cavity
method)
Thus computing marginals
implies computing the partition function
Step II. Cavity recursion
Step II. Cavity recursion
Step II. Cavity recursion
Algorithm: repeat the recursion
times.
- Computation tree
Initialize
Compute
at the bottom arbitrarily.
recursively.
Proposition. The computation tree
correlation property
Proof: look at the recursion function:
Introduce change of variables:
satisfies the decay of
Mean Value Theorem:
- contraction
Theorem II. There exists a deterministic algorithm for computing
approximately the number of list colorings in triangle-free graphs when
the size of each list
is constant and
for all nodes
Cavity recursion
Cavity recursion
x
x
x
Cavity recursion
x
x
x
We establish correlation decay for this recursion
Why can’t we use conventional decay of correlation directly for counting by computing
marginals
locally for small (constant)
?
Problem:
We need accuracy
in order to have accuracy
But:
Structural results
The decay of correlation property implies the following large deviations results:
Theorem III. The partition function of independent sets in every r-regular locally treelike graphs satisfies
when
Queueing/large deviations interpretation
1. In a multicasting model (independent sets) the probability that nobody is
transmitting a signal is
2. The probability that the set of active nodes is
is given as
Structural results
Theorem IV. The partition function of the number of q-colorings in every r-regular
graph with large girth satisfies
These results are not “provable” using MCMC technique
Note: removing a node when computing marginals destroys regularity
A fix comes from a rewiring trick Mezard-Parisi [05].
Lemma. The rewiring operation can be performed on pairs of nodes without creating
small cycles.
Final thoughts and goals
•
Queueing and stationarity.
Consider a queueing version of the “matching” problem. Assume FIFO.
Does the loss of stationarity occur before or after onset of long-range dependence?
Final thoughts and goals
•
Create an implementable version of our algorithm (aka Belief Propagation). Our
algorithm is only nominally efficient.
•
Combining algorithm with importance sampling to handle large degree
instances.
•
Other counting problems: permanent, volume of a polyhedron.
•
What other structures have the underlying computation tree satisfy the
correlation decay property? Markov random fields?