2012 – Graphical models and inference

Organizer: Nicholas Ruozzi
Office: INR 136
Phone: 37551
Email: nicholas.ruozzi@epfl.ch

Meetings: Fridays 4:15pm – 5:30pm in room INR 113


The objective of the reading group is to understand the recent results in the study of graphical models and approximate inference. No background in graphical models or message passing is required.

A tentative list of topics includes:

  • Factor graphs and message passing as dynamic programming on a tree
  • Message passing (belief propagation, max-product, min-sum): admissibility, consistency, and computation trees
  • Message passing for the maximum weight matching problem
  • Message passing for optimization: MAP LP and reparameterizations
  • Graph covers and pseudocodewords
  • Convergent and correct message passing: TRMP, MPLP, etc.
  • Variational approximations and belief propagation
  • Variational approximations: zero temperature limits of BP and generalized belief propagation
  • Convex entropy approximations and convergent message passing: TRBP and others
  • Graph covers and the Bethe partition function
  • Loop Expansions



speaker   date   topic   references
Nicholas Ruozzi   April 13   Introduction to Graphical Models and Inference   Notes For more background and examples, see sections 1-3 of Understanding Belief Propagation and Its Generalizations
Amin Karbasi   April 20   Message Passing and Maximum Weight Matchings   Belief Propagation and LP relaxation for Weighted Matching in General Graphs
Masoud Alipour   April 27   Correctness of Max-Product on Graphs Containing a Single Cycle   Tree consistency and bounds on the performance of the max-product algorithm and its generalizations
Andrei Giurgiu   May 4   MAP LP and Lagrangian Duality   MAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming
Nicholas Ruozzi   May 18   Tree-Reweighted Message Passing   MAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming
Nicholas Ruozzi   May 25   Graph Covers and Pseudocodewords   Graph-Cover Decoding and Finite-Length Analysis of Message-Passing Iterative Decoding of LDPC Codes
Amin Karbasi   June 8   Variational Approximations   Constructing Free Energy Approximations and Generalized Belief Propagation Algorithms
Igor Malinovic   June 15   Convergent Sum-Product Algorithms   Convergent message passing algorithms – a unifying view