2012 – Graphical models and inference

Organizer: Nicholas Ruozzi
Office: INR 136
Phone: 37551
Email: [email protected]

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