PORTALE DELLA DIDATTICA

PORTALE DELLA DIDATTICA

PORTALE DELLA DIDATTICA

Elenco notifiche



Introduction to belief propagation

01ROOKG

A.A. 2021/22

Course Language

Inglese

Degree programme(s)

Doctorate Research in Fisica - Torino

Course structure
Teaching Hours
Lezioni 10
Lecturers
Teacher Status SSD h.Les h.Ex h.Lab h.Tut Years teaching
Pretti Marco Docente esterno e/o collaboratore   10 0 0 0 5
Co-lectures
Espandi

Context
SSD CFU Activities Area context
*** N/A ***    
Belief propagation is a very powerful iterative algorithm (of the message-passing type), used for solving several statistical inference and combinatorial optimization problems (decoding of error-correcting codes, resourse allocation, data clustering, etcetera). The course aims at discussing the basic concepts of belief propagation, making use of a physical approach, that is, presenting the method as an algorithm for approximate computation of marginals of the Boltzmann distribution for a given kind of thermodynamic system, exploiting suitable formal analogies. Indeed two different approaches (which turn out to be equivalent) are presented, a variational one and a self-consistent one (the latter also known as cavity method). One of the aforementioned applications is also treated in some detail, according to main interests of students attending the course.
The course does not require specific preliminary notions, so that it can be considered as self-contained. Some previous knowledge of basic statistical physics principles may be of use.
1. Recaps of statistical mechanics. Formal analogies with inference problems. 2. Old “belief propagation”: Bethe-Peierls approximation and quasi-chemical approximation. 3. Self-consistent approach and relationships with the cavity method. 4. Variational approach and relationships with the cluster-variational method. 5. Examples of application: statistical inference and combinatorial optimization.
On site
Oral presentation
P.D.2-2 - October
The course period may vary, subject to agreement with the students enrolled.