Introduction To Statistical Physics. Microcanonical and Canonical ensembles, thermodynamic limit. The Curie-Weiss model: phase transitions and critical phenomena, ergodicity breaking. Markov Chain Monte-Carlo: Markov processes, detailed balance condition, Metropolis-Hastings Algorithm and application to the Curie-Weiss model. Energy Based Models and Contrastive Divergence.
Intro to Graph theory. Main definitions appearing in graph theory. Random Graphs: Erdős-Renyi and random regular graph ensembles. Locally tree-like property. Percolation and Giant Component, -core, leaf removal, ODE analysis.
The Belief Propagation Algorithm. Factor Graphs. Derivation of Belief Propagation on a tree graphical model. Applications: Ising on sparse graph, graph coloring, Stochastic Block model. Algorithmic implementations. Population Dynamics algorithm.
Statistical Physics of Learning. Perceptron Models with binary and continuous weights. Teacher-Student and Storage settings. Simple geometric properties of the solution space. Concept of "self-averaging" quantity. Partition function and Gardner's volume. Replica method. Order parameters and their physical interpretation.
Statistical Physics inspired algorithms. Phase diagram for the binary perceptron. Binary Perceptron Inference: Impossible-Hard-Easy transitions. Factor graph representation of the binary perceptron and BP equations. The relaxed-BP algorithm: derivation, implementation, analysis and comparison with replica method's results.
Reference Books:
Moore, Mertens - The Nature of Computation, Oxford University Press, (2011).
Mezard, Montanari - Information, Physics, and Computation, Oxford University Press, (2009).
Engel, Van den Broeck - Statistical Mechanics of Learning, Cambridge University Press, (2001).
Additional Lecture Notes:
Python notebooks will be also provided during the course.
8 points out of 30 of the final grade come from individual assignments. The students will be required to derive and implement in a specific setting the generic algorithms discussed during the course.
The rest of the points come from an oral exam. Understanding of all the topics covered in the course will be evaluated. Besides verbally answering questions, students will be asked to reproduce part of calculations seen during the course using pen and paper or a whiteboard.