Caricamento in corso...
Introduction to belief propagation
01ROOKG
A.A. 2024/25
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
Context
| SSD | CFU | Activities | Area context | *** N/A *** |
|---|
La belief propagation è un algoritmo iterativo molto potente (di tipo message-passing), usato per trattare svariati problemi di inferenza statistica e ottimizzazione combinatoria (decodifica di codici correttori, allocazione di risorse, clustering di dati, eccetera). Il corso si propone di discutere i concetti all'origine della belief propagation utilizzando un approccio fisico, ovvero presentando il metodo come un algoritmo per il calcolo approssimato di marginali della distribuzione di Boltzmann per un dato tipo di sistema termodinamico, sfruttando opportune analogie formali. Vengono presentati in effetti due diversi approcci (che si mostrano essere equivalenti), l'uno di tipo variazionale e l'altro di tipo autoconsistente (quest'ultimo noto anche come metodo delle cavità).
Viene anche trattata in qualche dettaglio una delle applicazioni di cui sopra, a seconda del maggiore interesse degli studenti frequentanti.
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.
Il corso non necessita di nozioni preliminari specifiche e può pertanto essere considerato come self-contained.
Può essere utile una conoscenza di principi base di fisica statistica.
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. Richiami di meccanica statistica. Analogie formali con i problemi di inferenza.
2. L’antica “belief propagation”: approssimazione di Bethe-Peierls e approssimazione quasi-chimica.
3. Approccio autoconsistente e relazione con il metodo delle cavità.
4. Approccio variazionale e relazione con il metodo variazionale a cluster.
5. Esempi di applicazione: inferenza statistica e ottimizzazione combinatoria.
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.
In presenza
On site
Presentazione orale
Oral presentation
P.D.1-1 - Novembre
P.D.1-1 - November
Il calendario delle lezioni sarà concordato con gli studenti iscritti, che riceveranno informazioni dettagliate via mail e sulla pagina del corso (sezione avvisi).
The lecture schedule will be arranged with the enrolled students, who will receive detailed information via email and on the course page (notices section).