Stochastic Systems Group  

Statistical Physics of Algorithms (or Belief Propagation and Beyond)
Michael (Misha) Chertkov
Theory Division, Los Alamos National Laboratory
Day 
Monday 
Wednesday 
Thursday 
Date 
Sep 29 
Oct 1 
Oct 2 
Oct 27 
Oct 29 
Oct 30 

Room 
32141 
32141 
32D463 
Time 
45pm 
Syllabus:
There has been an explosion of interest in the past decade to
statistical problems related to computer science and information
processing, such as new decoding paradigms for highvolume
communication and storage, problems in search and counting through a
huge set of combinatorial constraints, etc. Novel ideas in analysis of
complexity and development of approximate but systematically improvable
algorithms are required for the hard statistical problems. Since the
central task of statistical physics is to describe how complex behavior
emerges from interaction of large number of basic elements, its tools
and concepts are proven valuable in the emerging disciplines.
This minicourse offers an overview of the work by the author and
collaborators on analysis and design of efficient algorithms for hard
computational problems.
List of subjects includes
*
Statistical Inference (Data Restoration), Combinatorial Optimization
and Counting. What is easy (shortest path, dynamical programming,
calculations on a tree) and what is difficult (KSAT, spinglasses,
decoding of graphical codes).
* Graphical Models. Ground State and Partition Function. Belief
Propagation, Mean Field and Bethe Free Energy Approximation. Linear
Programming and Belief Propagation.
*
Belief Propagation and Loop Calculus. Binary case. Graphic and
Variational Formulations. Selfavoiding tree (Weitz method). Loop
Tower = Extension of Loop Calculus to qary alphabet.
* Inference on Planar Graphs: FisherKastelyanBarahona approach.
Loop Calculus for Planar Models. Pfaffians as Grassman Integrals.
*
Loop Caculus for Gaussian Graphical Model (continious alphabet).
Graphical Gauge Theories. MonomerDimer Model and Determinants.
* Example of Synthesis: BP and Beyond for particle tracking. Loop Series as a Cauchi Integral.
References:
1.
Loop Calculus in Statistical Physics and Information Science, Phys.
Rev. E 73, 065102(R) (2006), condmat/0601487, coauthor: Vladimir
Chernyak.
2. Loop series for discrete statistical models on graphs, condmat/0603189, JSTAT/2006/P06009, coauthor: Vladimir Chernyak.
3. Loop Calculus and Belief Propagation for qary Alphabet: Loop
Tower, Proceedings of ISIT 2007, June 2007, Nice, cs.IT/0701086,
coauthor: Vladimir Chernyak.
4. Exactness of Belief Propagation for Some Graphical Models with Loops, submitted to JSTAT, http://arxiv.org/abs/0801.0341
5. Belief Propagation and Loop Series on Planar Graphs, JSTAT/2008/P05003, http://arxiv.org/abs/0802.3950
6. Belief Propagation and Beyond for Particle Tracking, submitted
to Proceeding of NIPS 2008, arXiv: 0806.1199, coauthors: L. Kroc, M.
Vergassola
7. Fermions and Loops on Graphs. I. Loop Calculus for Determinant, preprint Aug 2008, http://arxiv.org/abs/0809.3479, coauthor: V. Chernyak.
8. Fermions and Loops on Graphs. II. MonomerDimer Model as Series of Determinants, preprint Aug 2008, http://arxiv.org/abs/0809.3481, coauthor: V. Chernyak.
Problems with this site should be emailed to jonesb@mit.edu