Probabilistic Graphical Models

CS 688, Spring 2016, UMass Amherst CS

Instructor: Brendan O’Connor, brenocon AT cs.umass.edu

Lecture: MW 2:30-3:45, Engineering Laboratory, room 304

TA: Tao Sun, taosun AT cs.umass.edu

See the Moodle and Piazza sites for this course.

Course description

Probabilistic graphical models are an intuitive visual language for describing the structure of joint probability distributions using graphs. They enable the compact representation and manipulation of exponentially large probability distributions, which allows them to efficiently manage the uncertainty and partial observability that commonly occur in real-world problems. As a result, graphical models have become invaluable tools in a wide range of areas from computer vision and sensor networks to natural language processing and computational biology.

The aim of this course is to develop the knowledge and skills necessary to effectively design, implement and apply these models to solve real problems. The course will cover (a) Bayesian and Markov (MRF) networks; (b) exact and approximate inference methods; (c) estimation of both the parameters and structure of graphical models. Students entering the class should have good programming skills and knowledge of algorithms. Undergraduate-level knowledge of probability and statistics is recommended.

This course emphasizes the versatile compositionality of PGMs’ core building blocks—intuitive representations and algorithms which can be combined to derive a huge variety of models and inference/learning procedures. Probabilistic graphical models unify a very broad range of statistical and machine learning methods, and allow the invention of new ones too. These concepts are essential for advanced work in machine learning, artificial intelligence, and statistical modeling.

An approximate list of topics (subject to change):

Introduction and Probability Theory
Bayesian Networks
KL Divergence and Learning in Bayesian Networks
Markov Random Fields
Inference in Markov Random Fields
Exact Inference by Message Passing
Sum-Product Implementation and Learning Markov Random Fields
Markov Random Fields and Bayesian Networks
Particle Respresentations and Monte Carlo Integration
Markov Chains and MCMC Methods
Metropolis Hastings Algorithm
MCMC and Learning
Variational Inference
Variational Learning
Loopy Belief Propagation
Factor Graphs
Bayesian Inference

Textbook: Kevin Murphy (2012), “Machine Learning: a Probabilistic Perspective.” (book website).

Who should take this course?: This is a PhD-level course that is designed for students who want depth in statistical machine learning. It may also be useful for related areas such as probabilistic inference in intelligent systems. This course focuses on mathematical formalisms, algorithms, and models. If you haven’t taken a course in machine learning, artificial intelligence, or statistical modeling before (e.g. CS 589, CS 689, CS 383, CS 683, STAT 597*, STAT 697*, etc.), the motivation for this course may not be as clear.

Retrospective Syllabus

Schedule of topics we actually covered:

In the readings, texts refer to

Kevin Murphy (2012), “Machine Learning: a Probabilistic Perspective.” (book website; the main probabilistic ML text these days)
David MacKay (2003), “Information Theory, Inference, and Learning Algorithms.” (book website, free online; it’s idiosyncratic but brilliant)
David Barber (2012), “Bayesian Reasoning and Machine Learning” (book website, free online; I haven’t read too much but it looks good and some people really like it.)

[Lec1] W 1/20: Intro and Probability

(suggested) MacKay 2.1-2.3, Murphy 2.1-2.3

[Lec2] M 1/25: Bayesian Networks

Murphy 10.1-10.3, 10.5.
Pearl: d-separation without tears
(suggested) Barber Ch. 3
HW1 will be posted. Due 2/1 2/8.

[Lec3] W 1/27: Maximum Likelihood in BNs

Murphy 10.4
Murphy 3.1-3.4, though we will use only parts of it. (related: these other notes by Murphy on binomial/multinomials)

[Lec3’] M 2/1: BN learning, continued

[Lec4] W 2/3: MRFs

Murphy 19.1-19.4.1
(suggested) Kindermann&Snell 1980 on MRFs: an awesome book from the typewriter manuscript era

[Lec5] M 2/8: MRF inference

HW1 due today
Murphy 19.6-19.6.1 (suggested: 19.6.2)

[Lec6] W 2/10: MRF learning and message-passing

(CRF learning) Murphy 19.5.1
(BP) Murphy 20.3, 20.2, optionally 17.4

[Lec7] T 2/16: Message passing

(no class on Monday! class is on Tuesday, a Monday-schedule-day)
Murphy 20.4 (junction trees a.k.a. clique trees)
actually, Barber chapter 6 looks like a better treatment

[Lec8] W 2/17: Message passing wrap-up

M 2/22: Recitation

[Lec8.5] W 2/24: Numerical optimization

[Lec9] W 2/24: Monte Carlo methods

HW2a new due date - start of lecture
Murphy 23.1-23.3, 24.1-24.2

[Lec10] M 2/29: Markov Chain Monte Carlo (1)

Topics: Non-MC Monte Carlo, Gibbs sampling
Murphy 24.1-24.3
(suggested) Barber 27.1-27.4

[Lec11] W 3/2: Markov Chain Monte Carlo (2)

Topics: Detailed balance, Gibbs sampling, start Metropolis-Hastings
Murphy 24.4

[Lec12] M 3/7: Markov Chain Monte Carlo (3)

(hw2b is due)
Topics: Metropolis-Hastings and friends
Reading: Brendan’s blogpost on MH/opt algorithms
Reading: indep_mh_gibbs.pdf (another note, in Resources section)

[Lec13] W 3/9: Markov Chain Monte Carlo (4)

Topics: Diagnostics, debugging, & other practicalities

[Lec14] M 3/21: Latent Variable Models with Gibbs Sampling

Murphy 3.1-3.4: Dirichlet-Multinomial conjugacy

[Lec15] W 3/23: The EM Algorithm

Murphy ch. 11, esp 11.3-11.4
Dawid and Skene 1979 (on Resources page or find on web)

[Lec16] M 3/28: EM and Gaussian mixtures

[Lec17] W 3/30: Variational inference (I)

Lagrangians for multinomial MLE: Ch. 3
Suggested reading: Klein ????, Lagrange Multipliers without Permanent Scarring
David Blei’s 2011 notes on variational inference: everything before exponential families section
Variational inference: Murphy ch. 21

[Lec18] M 4/4: Variational inference (II)

[Lec19] W 4/6: Topic models

Asuncion et al. 2009: Smoothing and inference in topic models
Optional: Papers on David Mimno’s seminar reading list
Optional: Murphy 27.1-27.4

[Lec20] M 4/11: Regression models (I)

Martin and Quinn (2002), Dynamic Ideal Point Estimation via Markov Chain Monte Carlo for the U.S. Supreme Court, 1953-1999.

You do not need to read in depth about the dynamic model inference.
See also the website.
Current events example of the Martin-Quinn scores: this page, especially the 2nd graph.

Murphy 7.6 (see 7.1-7.5 if you aren’t familiar with linear & ridge regression)
Murphy 9.4.1, 9.4.2 (on probit regression)
Reference: Murphy 4.1-4.4 (on Gaussians)
Suggested: MacKay 2006, The Humble Gaussian Distribution (lots of intuitions about multivariate Gaussians)
Suggested: Do 2008 notes on multivariate Gaussians

[Lec21] W 4/13: Regression models (II)

Cook et al. 2007, Validation of Software for Bayesian Models using Posterior Quantiles
For fun: a recent Cosma Shalizi blogpost complaining about Bayesian uncertainty. The Cook et al. paper concerns the arguably unusual case where Bayesian inference exactly aligns with frequentist statistics. Which works when you set it up that way. Real world is different.

[Lec22] W 4/20: Non-parametric Bayes

Murphy ch 25.12. Dirichlet process mixture models
Suggested: Paisley, notes on DP for Enigneers

[Lec23] M 4/25: Non-probabilistic graphical models

Reading: LeCun 2006, Energy-Based Learning
Suggested: Ratliff et al. 2007, (Online) Subgradient Methods for Structured Prediction
Suggested: Schmid 2009, Note on Structural Extensions of SVMs

[Lec24] W 4/27: Review