Main Page
From Btry4790
This is the course web page for BTRY 4790/6790 [CS 4782/6782], "Probabilistic Graphical Models" (Fall 2008).
Please check this page frequently throughout the semester. It will continually be updated with information you will need. Keep in mind that the schedules for lectures and homeworks are subject to change as the semester progresses.
Contents |
Announcements
- Solutions to homework #4 are posted (see below)
- Homework #5 has been posted. It is due 11/21.
- Information about the class project has been posted
- Solutions to homework #3 are posted (see below)
- The lecture schedule for November has been reorganized
- Project proposals are due 11/7.
Course Description
A thorough introduction to graphical models, a flexible and powerful framework for machine learning and probabilistic modeling that combines graph theory and probability theory. Covers both directed models (Bayesian networks) and undirected models, inference and parameter learning, and exact and approximate algorithms. Special cases such as hidden Markov models, tree-like Bayesian nets, and conditional random fields are discussed in detail.
General Information
- Lectures: Tues/Thurs, 11:40-12:55, Caldwell 100
- Recitations: Thurs, 2:55-4:10, Comstock B106
- Credit Hours: 4 (S/U or letter)
- Instructor: Adam Siepel, 101 Biotech
- TA: Ben Logsdon, 101 Biotech
- Office Hours: Tues, 4:30-5:30
Prerequisites
Required prerequisites are a course in probability theory (BTRY 4080 or equivalent) and a course in intermediate programming/data structures (CS 2110 or equivalent). A course in mathematical statistics (BTRY 4090 or equivalent) is recommended but not required. Students should be comfortable programming in a structured language such as Java or C++.
Resources
- Syllabus
- Questionnaire
- Information about the class project
- Notes on biased mle for variance of normal distribution [ PDF ]
- Notes from recitation #1, 9/4 [ PDF ]
- Errata from Jordan's manuscript
- Solutions to homework #1
- Homework #2 solutions: answers, graph, example source code and tree (thanks Yisong Yue); also: example source #2 (thanks Chun-Nam Yu) and example source #3 (thanks Nikos Karampatziakis)
- Homework #3 solutions: key part 1, key part 2, graphs, example source code (thanks to Chun-Nam Yu)
- Review article on CRFs by Sutton and McCallum. See also the original paper by Lafferty et al. and many other papers on Andrew McCallum's web page.
- Homework #4 solutions: key part 1, key part 2, graph #1, graph #2, example source code (thanks to Benyah Shaparenko)
- Papers by Yedidia, Freeman, and Weiss on connections between belief propagation and variational inference: Bethe free energy, Kikuchi approximations, and belief propagation algorithms, Understanding Belief Propagation and its Generalizations
- Solutions to homework #5 (thanks to Chun-Nam Yu)
Books
- Primary textbook:
- Bishop CM, Pattern Recognition and Machine Learning, Springer, 2006.
- Supplementary readings:
- Jordan MI, An Introduction to Probabilistic Graphical Models, in preparation
- Recommended reference books:
- Casella G, Berger RL, Statistical Inference. Duxbury Press, 2001.
- Gelman A, Carlin JB, Stern HS, Rubin DB, Bayesian Data Analysis. Chapman & Hall/CRC, 2004.
Lecture Schedule
(Lecture slides and homework assignments are password protected.)
| Date | Readings [optional]* | Topics | Slides |
|---|---|---|---|
| Aug 28 | 8.0-8.1; Jordan & Weiss review; Kevin Murphy tutorial | Course introduction | |
| Sep 2 | 8.2; J2.0-2.1 | Conditional independence and factorization | |
| Sep 4 | 1.2-1.3; 2.1-2.3 [1.1; 1.4-1.5; 2.5] | Probability and statistics background (Ben) | |
| Sep 9 | 8.3; J2.2-2.4 [J16] | D-separation, undirected models | |
| Sep 11 | 8.4.0-8.4.2; J3 | Probabilistic inference by graph elimination | |
| Sep 16 | 8.4.3; J4 | Belief propagation / sum-product algorithm | |
| Sep 18 | 8.4.4-8.4.5; J5 | Max-product algorithm, statistical concepts | |
| Sep 23 | J5-6 [2.5; 3] | Density estimation, linear regression | |
| Sep 25 | J7 [4] | Linear classification | |
| Sep 30 | J8 [1.6; 2.4] | Exponential family, sufficiency, KL divergence | |
| Oct 2 | J9 | Learning with completely observed models | |
| Oct 7 | J10-11 [9] | Expectation maximization (EM) | |
| Oct 9 | – | More on EM | |
| Oct 14 | – | Happy Fall Break! | – |
| Oct 16 | 13.0-13.2; J12 | Hidden Markov models (HMMs) | |
| Oct 21 | – | More on HMMs and related models | |
| Oct 23 | J13-14 | Factor analysis | |
| Oct 28 | 12 | Principle component analysis | |
| Oct 30 | 13.3; J15 | Kalman filtering | |
| Nov 4 | Sutton & McCallum review; Original Lafferty et al. paper | Conditional random fields | |
| Nov 6 | 11.0-11.1 | Introduction to sampling and MCMC | |
| Nov 11 | 11.2-11.6 | More on MCMC | |
| Nov 13 | 10.0-10.5 [10.6-10.7] | Variational inference | |
| Nov 18 | – | More on variational inference | |
| Nov 20 | J17 | Junction tree algorithm | |
| Nov 25 | – | More on junction tree algorithm | |
| Nov 27 | – | Happy Thanksgiving! | – |
| Dec 2 | – | Neural networks and Boltzmann machines | |
| Dec 4 | – | Learning graph structure, structural equation models, and causality (Ben) |
*Prefix of "J" indicates Jordan's draft manuscript; other readings are from Bishop
Assignment Schedule
| Assignment | Date Assigned | Date Due | Topics | Data |
|---|---|---|---|---|
| HW#1 | Sep 6 | Sep 19 | Factorization, D-separation, graph elimination | – |
| HW#2 | Sep 20 | Oct 3 | Sum-product, max-product algorithms | column.fa multicolumn.fa tree.nh |
| HW#3 | Oct 4 | Oct 17 | Fully observed learning, expectation maximization | survey-labeled.dat survey-unlabeled.dat |
| HW#4 | Oct 18 | Oct 31 | HMMs | riverdale.dat across-the-riverdale.dat |
| Proposal | Oct 31 | Nov 7 | Detailed project proposal | – |
| HW#5 | Nov 8 | Nov 21 | Image processing and Gibbs sampling | orig.txt orig.png noisy_10.txt noisy_10.png noisy_20.txt noisy_20.png image2Text.pl text2Image.pl computeError.pl image2Text.24bit.pl |
