AAAI-08 / LION 3   Tutorial Satisfied by Message Passing: Probabilistic Techniques for Combinatorial Problems Lukas Kroc, Ashish Sabharwal, and Bart Selman [ Information | Slides | Description | Syllabus | Speakers ]

The goal of this tutorial is to discuss the basics of and the state of the art in applying message passing techniques to solve difficult combinatorial problems. Some of these attempts, specifically the survey propagation algorithm for random k-SAT and k-coloring, have seen astonishingly successful, and have also shed light into the solution space structure of such problems. This is a promising and relatively new area at the intersection of combinatorial and probabilistic reasoning, whose understanding can be extremely beneficial for AI researchers.

General Information

Tutorial Material

Download: tutorial slides (ppt, pdf), 4-per-page handouts pdf

Printed handouts of these slides will also be available at the time of the tutorial for all registered participants.

Description

Pushing the boundary of practical solvability of certain combinatorial problems, such as Boolean satisfiability (SAT) or graph coloring, has far reaching practical consequences. This tutorial will introduce an exciting and relatively new algorithm for such problems called survey propagation. Stemming from physics research, survey propagation is so far the only known approach successful at solving hard random SAT problems with one million variables in a few minutes on a desktop computer, performance which is clearly beyond the reach of mainstream SAT solvers. The key of survey propagation's success lies in its ability to quickly compute an approximate solution of a related problem using a message passing process, and use that to solve the original task.

The tutorial, after covering the necessary background in message passing algorithms, will discuss various research aspects of SP. How can one understand survey propagation using the "usual language" of computer science? How does it relate to the known concept of belief propagation? Is it possible to extend the success of survey propagation to problems beyond random SAT? We will present the state of the art in understanding of survey propagation, as well as provide a step-by-step introduction to the subject.

Prerequisite Knowledge: This tutorial will be accessible to anyone with a basic understanding of Boolean formulas, probabilities, and combinatorial arguments. Familiarity with standard algorithm for SAT and graph coloring will not be necessary. No prior knowledge of message passing algorithms or belief propagation like techniques will be assumed.

Syllabus (tentative)

1. Introduction
   • Constraint satisfaction problems (CSPs), in particular SAT and Coloring
   • Random ensembles, satisfiability threshold
   • Traditional approaches: DPLL, local search
   • Probabilistic approaches: decimation, reinforcement

2. Probabilistic inference using message passing
   • Factor graph representation
   • Inference using Belief Propagation (BP)
   • BP inspired decimation

3. Survey propagation (SP)
   • Insights from statistical physics
   • Decimation by reasoning about clusters

4. Clusters of solutions
   • Cluster label, cover
   • Cluster filling
   • Cluster as a fixed point of BP
   • Combinatorial properties of cluster representations

5. Probabilistic inference for clusters
   • BP for covers
   • BP for Z_(-1)
   • BP for BP fixed points: origin of SP

6. Advanced topics
   • Clustering in solution spaces of random problems
   • The phase transitions zoo
   • Solution counting using BP for structured problems

Speaker Bio

Lukas Kroc is a Ph.D. student in computer science at Cornell University, under the supervision of Professor Bart Selman. His research interests lie in the field of artificial intelligence, especially using techniques from probabilistic reasoning to solve combinatorial problems, such as SAT or model counting.

Ashish Sabharwal is a postdoctoral associate in computer science at Cornell University. He received his Ph.D. from the University of Washington in 2005. He has (co-)authored over 30 publications and surveys, including two best paper awards and four nominations. His research interests include artificial intelligence, automated reasoning (SAT, CSP, QBF), planning, probabilistic inference, complexity, and algorithms.

Bart Selman is a professor of computer science at Cornell University. He was previously at AT&T Bell Laboratories. His research interests include reasoning, planning, knowledge representation, and connections to statistical physics. He has (co)-authored over 100 publications, including six best paper awards. He has received the Cornell Miles Excellence in Teaching Award, the Cornell Outstanding Educator Award, an NSF Career Award, and a Sloan Research Fellowship. He is a Fellow of AAAI and of AAAS.

Acknowledgments: This tutorial was funded in part by NSF Award 0713499 (RI: Extending the Reach of SAT Technology --- Quantification, Counting, and Sampling) and NSF EMT Award 0829861 (Collaborative Research: Harnessing Statistical Physics for Computing and Communication).