ICML-2008 Tutorial: Saturday, July 5, 2008

Graphical models and variational methods: Message-passing and relaxations

Tutorial presenter: Martin Wainwright, Assistant Professor,

Department of Electrical Engineering and Computer Sciences, and
Department of Statistics,
UC Berkeley, California, USA.

  • Outline
  • Presenter's background
  • Background materials
  • Goals and summary

    Graphical models provide a flexible framework for capturing dependencies among large collections of random variables, and are by now an essential component of the statistical machine learning toolbox. Any application of graphical models involves a core set of computational challenges, centered around the problems of marginalization, mode-finding, parameter estimation, and structure estimation. Although efficiently solvable for graphs without cycles (trees) and graphs of low treewidth more generally, exact solutions to these core problems are computationally challenging for general graphical models with large numbers of nodes and/or state space sizes. Consequently, many applications of graphical models require efficient methods for computing approximate solutions to these core problems. The past decade and a half has witnessed an explosion of activity on approximate algorithms for graphical models.

    Tree-like graph Directed Compression with undirected models

    The goal of this tutorial is to provide a unifying roadmap for navigating and understanding the broad array of approximate algorithms for marginalization and learning in graphical models. This tutorial will show how a wide class of methods----including mean field theory, sum-product or belief propagation algorithms, expectation-propagation, and max-product algorithms----are all variational methods, meaning that they can be understood as algorithms for solving particular optimization problems on graphs. The perspective also forges connections to convex optimization, including linear programming and other type of conic relaxations.

    Presenter's background

    Martin J. Wainwright is an Assistant Professor at UC Berkeley, with a joint appointment between the Department of Electrical Engineering and Computer Sciences, and the Department of Statistics. His research interests include statistical machine learning, information theory, statistical signal processing, and high-dimensional statistics. He received a PhD in EECS from the Massachusetts Institute of Technology, with a thesis focusing on graphical models and variational methods, for which he was awarded the George M. Sprowls Award for outstanding doctoral dissertation. He has received several awards, including a Sloan Fellowship, an Okawa Research Fellowship, an NSF CAREER Award, and various conference paper awards. He has worked extensively on graphical models, message-passing and variational methods, given various invited talks and tutorials on the topic, and taught a graduate level
    course in the area at UC Berkeley.
    Martin Wainwright's webpage


    The tutorial will begin with a quick introduction to graphical models, before moving onto exponential families and variational formulations. Various classes of approximate inference algorithms will be derived from the variational perspective, including belief propagation, expectation-propagation, mean field, and various convex relaxations.
  • Basics of graphical models
    Directed models, undirected models, factor graphs
    Marginalization, MAP problem, parameter/structure learnin
    Exponential families and maximum entropy
    Mean parameters and global validity
  • Bethe-Kikuchi, sum-product, and expectation-propagation
    Bethe approximation and belief propagation
    Kikuchi clustering and generalization
  • Mean field methods and learning
    Naive and structured mean field
    Variational EM and Bayes
  • LP relaxations, max-product and other convex relaxations
    Basic tree-based LP relaxation
    Reweighted max-product and LP duality
    Higher-order LP relaxations
    Conic programming relaxations (SOCP, SDP etc.)
  • Tutorial slides

  • Slides (PDF)
  • Slides (2 per page) (PDF)

    Intended audience

    The literature on message-passing and variational methods can be difficult to navigate at times, since it draws on a large number of different areas (optimization, statistics, AI, physics etc.). The goal of this tutorial is provide a guide to this area, so that researchers in machine learning can better understand and implement existing methods, and also tailor variational methods to particular applications of interest. We assume a familiarity with the basic concepts of graphical models (graphs, probability distributions, conditioning, independence, Markov properties). Those in need of a refresher can consult the lecture notes and videos available on-line (see Background materials below).

    Background and auxiliary materials

    Graduate course: CS 281A/STAT 241A website

    Webcast lectures on basics of graphical models

    Previous incarnations of tutorial slides

  • Machine Learning Summer School, Taipei, August 2006
    Lectures on Graphical Models and Variational Methods.
    Introductory lecture: Part I
    Advanced topics: Part II

    Tutorial papers and book chapters

  • Graphical models and variational methods (Wainwright and Jordan, 2005): Book chapter
  • Graphical models and variational methods (Wainwright and Jordan, 2003): The "Monster" technical report