CS 8803 PGM
Introduction to Probabilistic Graphical Models

Spring 2007
Klaus 1447
MW 3:00 - 4:00

Grading        Syllabus        Projects

This course provides an introduction to the theory, algorithms, and applications of probabilistic graphical models. These models represent the joint distribution of a set of random variables as a factorization over a graph. They include Bayesian networks, Markov random fields, and Hidden Markov models as special cases. Topics include representation, inference, parameter and structure learning, variational inference, belief propagation, and causality. The development will be motivated by applications in computer vision and speech, decision support, and bioinformatics.

Instructor

Jim Rehg
Email: rehg@cc.gatech.edu
Office: TSRB 230B
Office hours: After class or by appointment
Phone: 404-894-9105 (email preferred)

Prerequisites

Familiarity with probability, statistics, and linear algebra is essential. Familiarity with Matlab will be helpful for some of the assignments. For CS students, CS 8803 Mathematics for Computational Perception provides a satisfactory background for this class. Please contact me if you have questions.

Text

Draft chapters will be handed out in class from the following unpublished books:

• Bayesian Networks and Beyond by Daphne Koller and Nir Friedman
• An Introduction to Probabilistic Graphical Models by Michael I. Jordan

Students wishing to purchase a textbook should consider:

• Probabilistic Networks and Expert Systems by Cowell, Dawid, Lauritzen, and Spiegelhalter, Springer 1999.
  Clear and precise treatment of representation and exact inference methods.
• Learning in Graphical Models by M. Jordan (editor), MIT Press, 1999.
  An excellent collection of papers on graphical models, including topics such as variational inference.
• Bayesian Networks and Decision Graphs by Finn V. Jensen, Springer, 2001.
  Good overview of Bayesian networks at an introductory level.

Organization

Grades will be assessed as follows:

A single homework problem will be given at the end of most lectures. Homework write-ups will be collected at the start of the following class, and the solution will be provided in-class. My intent is to encourage you to keep up with the material and attend the lectures. Collaboration on the homework is encouraged at the "white board interaction" level. That is, share ideas and technical conversation, but do your own detailed derivations, write your own code, etc. Some assignments may require you to use Matlab.

There is a take-home midterm and a final project. Instead of a final exam, we will have oral presentations of final project reports during the final exam period. You are encouraged to do a final project which is related to your research interests. Project proposals will be due shortly after the midterm. Depending on the number of enrolled students, I may require you to work in groups of two or more for the final project.

No late submissions of homework will be accepted. There will be a sufficient number of problems that missing a few due to absences will not significantly affect your grade. Undergraduate and graduate students will be graded in an identical  manner in this course.

Syllabus

1. Introduction
2. Bayesian network
   • Examples (HMM, diagnostic system, etc.)
   • Separation and independence
   • Markov properties and minimalism
3. Markov network
   • Examples (Boltzmann machine, Markov random field, etc.)
   • Cliques and potentials
   • Markov properties
4. Exact inference
   • Complexity
   • Bucket elimination
   • Junction tree 
   • Belief propagation (message passing)
   • Application to HMM
   • Sum- and Max-product algorithms 
5. Parameter learning
   • Exponential family
   • Bayesian learning
   • Expectation-Maximization (EM)
6. Approximate inference
   • Convexity
   • Mean field approach
   • Structured variational method
   • Loopy belief propagation
   • Characterization of solution spaces
   • Sampling methods
7. Structure learning and causality

Problem Sets

• PS1, Code you will need: BNT_example_soln.m, poker.m, Poker page, showCPT.m (Due Mon Feb 19 in class)

Resources

Overview

• Overview of Graphical Models by Michael Jordan
• Kevin Murphy's introduction to graphical models and on-line tutorial. Also see his Fall 04 class, which I have found to be very helpful in preparing this class.

Applications

• See my introduction in a recent special issue of PAMI on graphical models in vision, as well as the contributed papers.

Help with Matlab

• Kevin Murphy's Matlab Tips
• Ben's Matlab tutorial

Final Projects

Schedule

• TBD

Possible Projects

• Your own project or I can suggest something