EE512 - Graphical Models - Fall Quarter 2009

Last updated: $Id: index.html,v 1.42 2009/12/18 07:16:48 bilmes Exp $

Instructor:

Prof. Jeff A. Bilmes --- Email me
Office: 418 EE/CS Bldg., +1 206 221 5236
Office hours: Mondays 11:00am-12:00pm, EEB-418

Announcements

Information

Course Format: Four hours of lecture per week (TTh 1:30-3:20 EEB-054) per week.

Description: This course will serve as a thorough overview of graphical models including Bayesian networks, undirected graphical models, and factor graphs.

  1. Introduction and background to statistical inference. Independence, conditional independence, and factorization properties. Axioms of independence and independence systems. Consequences of independence in computations. Families of models and their characterization and operations on families.
  2. Undirected graphical models, their families and semantics. corresponding conditional independence properties. Markov properties on undirected graphs, factorization, Hammersley-Clifford theorems, inclusion-exclusion, Markov Random fields, Gibbs distributions, Boltzman distributions, multi-variate Gaussians as undirected models. Static (non-dynamic) conditional random fields, and graphs for representing conditional distributions in general.
  3. Chordal Graph Theory: moralization; triangulated, decomposable, and intersection graphs, $k$-trees, hyper-graphs. Tree-width and path-width parameters of a graph. Graph separators and their crossings. Relational data-base systems and joins, and phylogenetic tree construction.
  4. Factor graphs, their families and semantics. Corresponding properties and algorithms
  5. directed graphical models and Bayesian networks and their families, properties, factorization and conditional independence (e.g., d-separation). Markov properties for directed models. Markov property equivalences.
  6. Directed models: linear Gaussian models, mixture models, factor analysis, probabilistic decision trees, multivariate Gaussians as directed graphical models.
  7. Exact Probabilistic Inference: inference on trees, junction trees, belief propagation in its various forms (including Pearl's formulation, Hugin, Shafer-Shenoy, Bucket-elimination, etc.); join-trees and data-structures; optimal triangulations. The elimination family of algorithms. Generalized distributed law (GDL). Relation to dynamic programming. Generality (such as Viterbi, MPE, the fast Fourier transform). NP hardness results, and NP hardness results for finding the best form.
  8. Inference as search: Search-based approaches to inference and how it relates to junction trees, message passing, and BP. Results from the constraint satisfaction (CSP) and SAT literatures, constraint solvers, and heuristics used in these domains. Cutset and recursive conditioning, comparison with elimination. Branch-and-bound.
  9. Approximate Probabilistic Inference: loopy belief propagation (BP), expectation propagation (EP), generalized belief propagation (GBP), cluster GBP, comparisons with mean-field and variational approaches, structured mean-field, statistical physics, Bethe and Kikuchi free-energies, fixed points, recent theoretical results and open questions.
  10. sampling approaches to inference, such as MCMC and particle algorithms (such as Rao-Blackwellized particle filtering). Pruning based approaches to inference. How the above approximate inference procedures relate
  11. Learning graphical models: learning Bayesian networks, hardness results for learning networks in the maximum likelihood sense, learning in the PAC (probably approximately correct) framework, EM for parameter and structure learning, alternating minimization, discriminative parameter and structure learning, conditional (CRF) training vs. discriminative training methods (discriminative objective functions), other learning methods. Information theory and graphical models.
  12. Models in practice: Real-world static graphs. turbo-coding, low-density parity check codes, other codes on graphs, belief propagation algorithms on these graphs. Practical issues such as data structures and algorithms useful for performing inference.

Note that Fall 2009 will concentrate on static graphical models, while in Winter 2009, there will be a new course (EE599) offered Winter 2010 on dynamic graphical models (which includes Hidden Markov models, dynamic Bayesian networks, conditional random fields, Kalman filtering, linear dynamic systems, and dynamic graphical models).

Prerequisites: basic probability, statistics, and random processes (e.g., EE505 or a Stat 5xx class or consent of the instructor). Knowledge of matlab. The course is open to students in all UW departments. If you are in doubt about taking this course, please

Texts: We will mainly use written material that will be made available on the web page, as well as other printed and online material. Please take a look at the web page for more information. This will include a text entitled "An Introduction to Graphical Models", by Mike Jordan. We will also use a recent text by Daphne Koller and Nir Friedman.

Grades and Assignments: Grades will be based on a combination of a final project (35%), homeworks (35%), and the take home midterm exam (30%). There will be a new homework assignment due about every 1-2n weeks (for a total of about 4-5 homeworks).

Final project: The final project will consist of a 4-page paper (conference style) and a 10 minute final project presentation. The project must involve using or dealing mathematically with graphical models in some way or another. For their application to data, there are a number of software tools (such as BNT or GMTK) which can be used for this purpose, or you may wish to develop your own system. Projects can be done in groups of no more than two people (i.e., projects may be either 1 or two people, but no more).

Homework

There will be 4-5 homeworks for the quarter. Each will be due about one week after it is assigned. You can either hand the homework to me in person, or email me the PDF version.
  1. Problem set 1 Due Friday, 10/30 5:00pm by sending PDF to me by email.

Lecture Slides

Lecture slides will be made available as they are being prepared --- they will probably appear here right before a given lecture, and they will be in PDF format (original source is latex). You might also find it useful to look at slides from the lectures the previous time this course was offered, although this year these slides are beeing completely revised, to account for new material that is being given this year.
  1. Lecture 1 from 10/1/09. (last updated 10/4)
  2. Lecture 2 from 10/6/09. (last updated 10/7)
  3. Lecture 3 from 10/8/09. (last updated 10/13)
  4. Lecture 4 from 10/13/09. (last updated 10/14)
  5. Lecture 5 from 10/15/09. (last updated 10/15)
  6. Lecture 6 from 10/20/09. (last updated 10/21)
  7. Lecture 7 from 10/22/09. (last updated 10/22)
  8. Lecture 8 from 10/27/09. (last updated 10/28)
  9. Lecture 9 from 10/29/09. (last updated 11/04)
  10. Lecture 10 from 11/03/09. (last updated 11/03)
  11. Lecture 11 from 11/05/09. (last updated 11/09)
  12. Lecture 12 from 11/10/09. (last updated 11/11)
  13. Lecture 13 from 11/12/09. (last updated 11/17)
  14. Lecture 14 from 11/17/09. (last updated 11/17)
  15. Lecture 15 from 11/19/09. (last updated 11/22)
  16. Lecture 16 from 11/24/09. (last updated 11/24)
  17. Lecture 17 from 12/01/09. (last updated 12/01)
  18. Lecture 18 from 12/03/09. (last updated 12/04)

Discussion Board

You can post questions, discussion topics, or general information at this link.

Books and Links

There are many books available that discuss the material that we are covering in this course. A few of the ones that I use regularly, and a few other web links that I think are useful, are included below.

Important Dates

Go to my home page Email me