Information theory, inference, and learning algorithms

Vorlesung mit Übung (4 + 2 SWS)

Author

Tiago P. Peixoto <peixoto@c3s.uni-frankfurt.de>

Course description

This course presents a unified treatment of information theory and statistical inference, highlighting their shared foundations and complementary perspectives. Emphasis is placed on modern developments and interdisciplinary connections, particularly with statistical physics and theoretical computer science. Core topics include entropy and information measures, the maximum entropy principle, data compression and channel coding, Kolmogorov complexity, and the minimum description length principle. The course then turns to probabilistic graphical models and inference algorithms, including belief propagation and Monte Carlo sampling, and to the statistical mechanics of learning, where phase transitions and statistical–computational gaps reveal the limits of inference in high dimensions. It also explores the physical nature of information, including the thermodynamic cost of computation and the generation of information in chaotic dynamics. The course concludes with applications of these ideas in biology, linguistics, and the social sciences.

By the end of the course, students will be able to apply core concepts of information theory, such as entropy, mutual information, and relative entropy, to problems in statistical inference and learning. They will formulate inference problems within an information-theoretic and Bayesian framework, analyze data compression and communication schemes in light of fundamental limits, and model complex systems using probabilistic graphical models and inference algorithms such as belief propagation and Markov chain Monte Carlo. Students will also understand how ideas from statistical physics, such as free energy, entropy–energy tradeoffs, and phase transitions, illuminate the limits of inference and the emergence of computational hardness in high-dimensional systems. Finally, they will be able to recognize and critically assess information-theoretic reasoning in the physical, biological, linguistic, and social sciences.

Parameters

Time: Thu, 14:00 s.t. to 18:00 (weekly lectures)1, Mon, 10:00 to 12:00 (biweekly tutorials)
Location: Robert-Mayer-Str. 11-15, SR 307 (lectures), SR 11 (tutorials)
Language: English
Evaluation: Final oral exam
Course catalog entry: QIS link
Lecture notes and slides: https://skewed.de/lab/lectures/infoinf/

1 Lectures are comprised of a 3 hour session, and an optional 45 minutes tutorial consultation.

Schedule

  1. Information, entropy, mutual information
  2. The maximum entropy principle, exponential families, and the entropy of physical systems
  3. Source coding and data compression
  4. Noisy channels and error-correcting codes
  5. Inference is compression: Bayesian statistics and the minimum description length principle
  6. Kolmogorov complexity
  7. “No free lunch” theorems and meta-induction
  8. Graphical models, belief networks, causality
  9. Statistical mechanics of learning: phase transitions, statistical–computational gaps
  10. Thermodynamics of information and computation
  11. Monte Carlo sampling
  12. Information theory in dynamical systems and chaos
  13. Information theory in biology
  14. Information theory in language and linguistics
  15. Information theory in the social sciences