Statistical Physics of Algorithms
MIT -- Special Lecture Series on
Statistical Physics of Algorithms (or Belief Propagation and Beyond)
Michael (Misha) Chertkov (Theory Division, Los Alamos National Laboratory)
Time: 4-5pm
Date and Room:
Sep 29 Mon 32-141
Oct 01 Wed 32-141
Oct 02 Thur 36-156 (room change: 32-D463 (Star Room))
Oct 27 Mon 32-141
Oct 29 Wed 32-141
Oct 30 Thur 36-156 (room change: 32-D463 (Star Room))
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 high-volume 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 mini-course 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 (K-SAT, spin-glasses, 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. Self-avoiding tree (Weitz method). Loop Tower = Extension of Loop Calculus to q-ary alphabet.
* Inference on Planar Graphs: Fisher-Kastelyan-Barahona approach. Loop Calculus for Planar Models. Pfaffians as Grassman Integrals.
* Loop Caculus for Gaussian Graphical Model (continious alphabet). Graphical Gauge Theories. Monomer-Dimer 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), cond-mat/0601487, co-author: Vladimir Chernyak.
2. Loop series for discrete statistical models on graphs, cond-mat/0603189, JSTAT/2006/P06009, co-author: Vladimir Chernyak.
3. Loop Calculus and Belief Propagation for q-ary Alphabet: Loop Tower, Proceedings of ISIT 2007, June 2007, Nice, cs.IT/0701086, co-author: 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, co-authors: V. Chernyak, R. Teodorescu.
6. Belief Propagation and Beyond for Particle Tracking, submitted to Proceeding of NIPS 2008, arXiv: 0806.1199, co-authors: L. Kroc, M. Vergassola
7. Fermions and Loops on Graphs. I. Loop Calculus for Determinant, preprint Aug 2008, co-author: V. Chernyak.
8. Fermions and Loops on Graphs. II. Monomer-Dimer Model as Series of Determinants, preprint Aug 2008, co-author: V. Chernyak.
Statistical Physics of Algorithms (or Belief Propagation and Beyond)
Michael (Misha) Chertkov (Theory Division, Los Alamos National Laboratory)
Time: 4-5pm
Date and Room:
Sep 29 Mon 32-141
Oct 01 Wed 32-141
Oct 02 Thur 36-156 (room change: 32-D463 (Star Room))
Oct 27 Mon 32-141
Oct 29 Wed 32-141
Oct 30 Thur 36-156 (room change: 32-D463 (Star Room))
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 high-volume 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 mini-course 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 (K-SAT, spin-glasses, 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. Self-avoiding tree (Weitz method). Loop Tower = Extension of Loop Calculus to q-ary alphabet.
* Inference on Planar Graphs: Fisher-Kastelyan-Barahona approach. Loop Calculus for Planar Models. Pfaffians as Grassman Integrals.
* Loop Caculus for Gaussian Graphical Model (continious alphabet). Graphical Gauge Theories. Monomer-Dimer 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), cond-mat/0601487, co-author: Vladimir Chernyak.
2. Loop series for discrete statistical models on graphs, cond-mat/0603189, JSTAT/2006/P06009, co-author: Vladimir Chernyak.
3. Loop Calculus and Belief Propagation for q-ary Alphabet: Loop Tower, Proceedings of ISIT 2007, June 2007, Nice, cs.IT/0701086, co-author: 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, co-authors: V. Chernyak, R. Teodorescu.
6. Belief Propagation and Beyond for Particle Tracking, submitted to Proceeding of NIPS 2008, arXiv: 0806.1199, co-authors: L. Kroc, M. Vergassola
7. Fermions and Loops on Graphs. I. Loop Calculus for Determinant, preprint Aug 2008, co-author: V. Chernyak.
8. Fermions and Loops on Graphs. II. Monomer-Dimer Model as Series of Determinants, preprint Aug 2008, co-author: V. Chernyak.