Probabilistic Graphical Models
Spring 2013
Overview A graphical model is a probabilistic model, where the
conditional dependencies between the random variables are
specified via a graph. Graphical models provide a flexible
framework for modeling large collections of variables with
complex interactions, as evidenced by their wide domain of
application, including for example machine learning,
computer vision, speech and computational biology. This
course will provide a comprehensive survey of learning and
inference methods in graphical models. 

General information Lecture: Thursday 5:006:50pm
Office hours: Wednesday 45pm and by
appointment. Location:
715 Broadway, 12th floor, Room 1204 Grading: problem sets (65%) + exam (30%)
+ participation (5%). Problem Set
policy Book (required):
Probabilistic Graphical
Models: Principles and Techniques by Daphne Koller
and Nir Friedman, MIT Press (2009). Mailing list: To subscribe to the class list, follow instructions here. 
Schedule
Week  Date  Topic  Readings  Assignments 
1  Jan 31  Introduction, Bayesian networks [Slides] 
Chapters 13, Appendix A How to write a spelling corrector (optional) 

2  Feb 7 
Undirected graphical models [Slides] 
Chapter 4 (except for 4.5 & 4.6) Introduction to Probabilistic Topic Models (optional) 

3 
Feb 14 
Conditional random fields [Slides] 
Sections 4.5 & 4.6 An Introduction to Conditional Random Fields (section 2) Original paper introducing CRFs (optional) 

4 
Feb 21 
Exact inference
[Slides] Variable elimination 
Sections 99.4, 9.6.1, 9.79.8 

5 
Feb 28 
Exact inference (continued)
[Slides] [Notes from blackboard] Treewidth, Belief Propagation 
Chapter 10, Sections 13.113.3 

6 
March 7 
Dual decomposition
[Slides] Linear programming relaxations 
Sections 13.513.9 Introduction to Dual Decomposition for Inference Derivation relating dual decomposition & LP relaxations 

7 
March 14 (no class March 21, Spring break) 
Variational inference
[Slides] 
Chapter 8, Sections 11.111.3.1, Box 11.B,11.C, Sections 11.3.611.3.7.2 

8 
March 28 
Variational inference (continued)
[Slides] Meanfield approximation 
Section 11.511.7 Graphical models, exponential families, and variational inference (optional) 

9 
April 4 
MonteCarlo methods for inference
[Slides] 
Sections 12.112.3, 12.7 

10  April 11 
Learning (Bayesian networks)
[Slides] 
Chapter 16. Sections 17.117.2.3, 17.7, 18.118.3.5 

11  April 18  Learning (Markov networks) [Slides] 
Chapter 20 (except for 20.7) Notes on pseudolikelihood An Introduction to Conditional Random Fields (section 4) Recent paper on approximate maximum entropy learning in MRFs (optional) 

12  Tuesday, April 23 (Special time/location!) 7:10pm in WWH 317 
Learning (structured prediction) [Slides] 
Original paper introducing structured perceptron (optional) CuttingPlane Training of Structural SVMs (optional) BlockCoordinate FrankWolfe Optimization for Structural SVMs (optional) 

13  May 2 
Learning (unobserved data, EM) [Slides 1, Slides 2] 
Sections 19.1, 19.2 The Expectation Maximization Algorithm: A short tutorial Latent Dirichlet Allocation (sections A.3, A.4) 

14  May 9 
Advanced topics in learning 


15 
May 16 
Final exam
(in class) 
Reference materials

PrerequisitesThis is a graduatelevel course. Students must have already taken an introductory course on machine learning, such as:

Problem
Set policy I expect you to try solving each problem set on your own. However, when being stuck on a problem, I encourage you to collaborate with other students in the class, subject to the following rules:
