Probabilistic Graphical Models, Spring 2013

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:00-6:50pm
Room: Warren Weaver Hall 312

Instructor:
David Sontag
dsontag {@ | at} cs.nyu.edu

Teaching assistant:
Li Wan
wanli {@ | at} cs.nyu.edu

Office hours: Wednesday 4-5pm and by appointment. Location: 715 Broadway, 12th floor, Room 1204
Li's office hours: Monday 5-6pm. Location: 715 Broadway, 12th floor, Room 1231

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 1-3, Appendix A How to write a spelling corrector (optional)	ps1 due Feb 7 at 5pm [Solutions]
2	Feb 7	Undirected graphical models [Slides]	Chapter 4 (except for 4.5 & 4.6) Introduction to Probabilistic Topic Models (optional)	ps2 due Feb 14 at 5pm [Solutions]
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)	ps3 due Feb 21 at 5pm [Solutions]
4	Feb 21	Exact inference [Slides] Variable elimination	Sections 9-9.4, 9.6.1, 9.7-9.8	ps4 (data) due March 11 at 5pm
5	Feb 28	Exact inference (continued) [Slides] [Notes from blackboard] Treewidth, Belief Propagation	Chapter 10, Sections 13.1-13.3
6	March 7	Dual decomposition [Slides] Linear programming relaxations	Sections 13.5-13.9 Introduction to Dual Decomposition for Inference Derivation relating dual decomposition & LP relaxations	ps5 (data) due March 28 at 3pm
7	March 14 (no class March 21, Spring break)	Variational inference [Slides]	Chapter 8, Sections 11.1-11.3.1, Box 11.B,11.C, Sections 11.3.6-11.3.7.2
8	March 28	Variational inference (continued) [Slides] Mean-field approximation	Section 11.5-11.7 Graphical models, exponential families, and variational inference (optional)
9	April 4	Monte-Carlo methods for inference [Slides]	Sections 12.1-12.3, 12.7	ps6 (data) due April 18 at 5pm [Solutions]
10	April 11	Learning (Bayesian networks) [Slides]	Chapter 16. Sections 17.1-17.2.3, 17.7, 18.1-18.3.5
11	April 18	Learning (Markov networks) [Slides]	Chapter 20 (except for 20.7) Notes on pseudo-likelihood 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) Cutting-Plane Training of Structural SVMs (optional) Block-Coordinate Frank-Wolfe Optimization for Structural SVMs (optional)	ps7 (data) due May 2 at 5pm
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)	ps8 due May 9 at 5pm [Solutions]
14	May 9	Advanced topics in learning
15	May 16	Final exam (in class)

Acknowledgements: Many thanks to the Toyota Technological Institute, Hebrew University, UC Berkeley, and Stanford University for sharing material used in slides and homeworks

Reference materials

Optional course text: Kevin Murphy, Machine Learning: a Probabilistic Perspective, MIT Press, 2012.
Machine learning books

Trevor Hastie, Rob Tibshirani, and Jerry Friedman, Elements of Statistical Learning, Second Edition, Springer, 2009. (Can be downloaded as PDF file.)
David Barber, Bayesian Reasoning and Machine Learning, Cambridge University Press, 2012. (Can be downloaded as PDF file.)

Probability

Chapter 2 of Murphy
Review notes from Stanford's machine learning class
Sam Roweis's probability review

Optimization

Convex Optimization by Stephen Boyd and Lieven Vandenberghe. (Can be downloaded as PDF file.)

Prerequisites

This is a graduate-level course. Students must have already taken an introductory course on machine learning, such as:

Statistical Natural Language Processing (GA.3033-001)
Introduction to Machine Learning (UA.0480-002)
Machine Learning and Pattern Recognition (G22.2565-001)
Foundations of Machine Learning (G22.2566-001)

In particular, students should be familiar with classification algorithms including logistic regression and support vector machines, loss functions, basic concepts in learning theory, clustering, and dimensionality reduction. Students should also have a solid understanding of basic concepts from probability (e.g., Bayes' rule, multivariate distributions, conditional independence), algorithms (e.g., dynamic programming, graphs, shortest paths, complexity), and calculus.

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:

You may discuss a problem with any student in this class, and work together on solving it. This can involve brainstorming and verbally discussing the problem, going together through possible solutions, but should not involve one student telling another a complete solution.
Once you solve the homework, you must write up your solutions on your own, without looking at other people's write-ups or giving your write-up to others.
In your solution for each problem, you must write down the names of any person with whom you discussed it. This will not affect your grade.
Do not consult solution manuals or other people's solutions from similar courses.

Late submission policy: During the semester you are allowed at most two extensions on the homework assignment. Each extension is for at most 48 hours and carries a penalty of 25% off your assignment.