Servizi per la didattica
PORTALE DELLA DIDATTICA

Introduction to belief propagation

01ROOKG

A.A. 2019/20

Course Language

Inglese

Course degree

Doctorate Research in Fisica - Torino

Course structure
Teaching Hours
Lezioni 10
Teachers
Teacher Status SSD h.Les h.Ex h.Lab h.Tut Years teaching
Pretti Marco Docente esterno e/o collaboratore   10 0 0 0 4
Teaching assistant
Espandi

Context
SSD CFU Activities Area context
*** N/A ***    
Valutazione CPD /
2019/20
PERIOD: SEPTEMBER 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.
PERIOD: SEPTEMBER 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.
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-variation method. 5. Examples of application: statistical inference and combinatorial optimization.
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-variation method. 5. Examples of application: statistical inference and combinatorial optimization.
Modalità di esame:
Exam:
Gli studenti e le studentesse con disabilità o con Disturbi Specifici di Apprendimento (DSA), oltre alla segnalazione tramite procedura informatizzata, sono invitati a comunicare anche direttamente al/la docente titolare dell'insegnamento, con un preavviso non inferiore ad una settimana dall'avvio della sessione d'esame, gli strumenti compensativi concordati con l'Unità Special Needs, al fine di permettere al/la docente la declinazione più idonea in riferimento alla specifica tipologia di esame.
Exam:
In addition to the message sent by the online system, students with disabilities or Specific Learning Disorders (SLD) are invited to directly inform the professor in charge of the course about the special arrangements for the exam that have been agreed with the Special Needs Unit. The professor has to be informed at least one week before the beginning of the examination session in order to provide students with the most suitable arrangements for each specific type of exam.
Esporta Word


© Politecnico di Torino
Corso Duca degli Abruzzi, 24 - 10129 Torino, ITALY
Contatti