E0 269: Probabilistic Graphical Models (Jan-Apr 2011)

Instructor: Indrajit Bhattacharya

Schedule: T,Th 11:30-1:00 CSA - 117

Pre-requisite:

• Introduction to Probability and Statistics
• Consent of Instructor

Text/Reading:

• "Probabilistic Graphical Models: Principles and Techniques", Daphne Koller and Nir Friedman,
• Relevant papers

Grading Policy: Class Assignments, Midterm, Final Exam / Course Project, Class Participation

News

April 14: New project report deadline: 19/4 Tuesday
April 14: Final Lecture 14/4 2-4pm
April 5: Handout on Junction Tree Algorithm
Mar 31: Handout on HMMs
Mar 24: Final Project Report due April 15
Mar 24: Handout on EM and Mixture Models
Mar 22: Exam 2 graded
Mar 17: Handout on Parameter Estimation
Mar 15: Project Proposals due this week
Feb 10: Handout on Sum Product
Feb 10: Exam 1 graded
Feb 10: Handout on Variable Elimination
Jan 25: Handout on Undirected Graphical Models
Jan 20: First Mid Term Exam on Feb 1
Jan 20: Handout on Directed Graphical Models
Jan 6: First class

Tentative Syllabus

Graph types: conditional independence; directed, undirected, and factor models; algorithms for conditional independence, d-separation, Markov properties on graphs, factorization, Hammersley-Clifford theorem.
Static Models: linear Gaussian models, mixture models, factor analysis, Markov Random Fields, Gibbs distributions, static conditional random fields (CRFs), multivariate Gaussians as graphical models, Exponential family, generalized linear models
Dynamic Models: Hidden Markov Models, Kalman filtering and linear-Gaussian HMMs
Exact Inference: The elimination family of algorithms. Relation to dynamic programming, belief propagation, Junction trees, optimal triangulations. NP hardness results.
Approximate Inference: Loopy belief propagation (BP), expectation propagation (EP), Sampling (Markov Chain Monte Carlo, Metropolis Hastings, Gibbs) Particle filtering
Structure Learning: Chow Liu algorithm
Latent Dirichlet Allocation: Exchangeability, de Finetti Theorem, Inference using collapsed Gibbs sampling

Lecture Schedule

Thu 06/1: Class Introduction and Logistics
Tue 11/1: Introduction to Graphical Models

• Graphical Models, M. I. Jordan. Statistical Science (Special Issue on Bayesian Statistics), 19, 140-155, 2004
• A Brief Introduction to Graphical Models and Bayesian Networks, Kevin Murphy, 1998.

Thu 13/1: Directed Graphical Models: Factorization
Tue 18/1: Directed Graphical Models: Conditional Independence
Thu 20/1: Undirected Graphical Models: Conditional Independence
Tue 25/1: Undirected Graphical Models: Factorization
Thu 27/1: Wrapping up GM Semantics; Intro to Inference
Tue 1/2: Midterm 1
Thu 3/2: Variable Elimination: Warming up
Tue 8/2: Variable Elimination Analysis
Thu 10/2: Variable Elimination Summary; Exam Discussion
Tue 15/2: Sum Product Algorithm
Thu 17/2: Sum Product and Factor Graphs

• Factor Graphs and the Sum-Product Algorithm, Kschischang et al, 2001

Tue 22/2: MAP Inference and Max Product
Thu 24/2: Review: Density Estimation and Regression
Tue 1/3: Review: Classification and Generative Models
Thu 3/3: Review: Discriminative Models
Tue 8/3: No Class
Thu 10/3: Second Mid Term Exam
Tue 15/3: Parameter Estimation in Completely Observed Graphical Models

• Graphical Models: Parameter Learning, Zoubin Ghahramani

Thu 17/3: Mixture Models, Latent Variables, EM

• A Gentle Tutorial of the EM algorithm and its application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models, Jeff Bilmes, 1997

Tue 22/3: Exam Discussion, EM Analysis
Thu 24/3: Parameter Estimation in Partially Observed Graphical Models
Tue 29/3: Hidden Markov Model

• A Tutorial on Hidden Markov Models and. Selected Applications in Speech Recognition, Lawrence Rabiner, 1989

Thu 31/3: Junction Tree Algorithms
Tue 5/4: Sampling Algorithms for Inference
Thu 7/4: Sampling Algorithms for Inference

• Probabilistic Inference Using Markov Chain Monte Carlo Methods, Radford Neal, 1993
• An Introduction to MCMC for Machine Learning, Christophe Andrieu, Nando de Freitas, Arnaud Doucet, Michael I. Jordan, 2003

Tue 12/4: Topic Models
Thu 14/4: Topic Models

• Probabilistic latent semantic analysis, T. Hofmann, 1999
• Latent Dirichlet Allocation, D. Blei, A. Ng, M. Jordan, 2003
• Probabilistic topic models, Steyvers, M. & Griffiths, T, 2007
• Topic Models, D. Blei and J. Lafferty, 2009

Additional Reading

• Principal Component Analysis, Factor Analysis, Kalman Filtering as Graphical Models
  • Probabilistic Principal Component Analysis, Michael Tipping and Christopher Bishop, 1999.
  • Multivariate Gaussian, Factor Analysis, and EM Algorithm, Michael Jordan, 2004
  • Factor Analysis and Kalman Filtering, Michael Jordan, 2004
  • State-space Models, Michael Jordan, 2004
• Structure Learning
  • Approximating Discrete Probability Distributions with Dependence Trees, Chow and Liu, 1968
  • Learning Bayesian networks with local structure, Nir Friedman and Moises Goldszmidt, 1999
  • Being Bayesian about network structure. A Bayesian approach to structure discovery in Bayesian networks, Nir Friedman and Daphne Koller, Machine Learning, 2003
  • The Bayesian Structural EM Algorithm, Nir Friedman, 1998
• Inventing Hidden Variables
  • Theory Refinement for Bayesian Networks with Hidden Variables, Sowmya Ramachandran and Ray Mooney, 1998
• Loopy Belief Propagation and Generalized Belief Propagation
  • Loopy Belief Propagation for Approximate Inference: An. Empirical Study, Murphy, Weiss, Jordan, 1999
  • Understanding Belief Propagation and Its Generalizations, Yedidia, Freeman, Weiss, 2001
  • Tree-Based Reparameterization Framework for Analysis of Sum-Product and Related Algorithms, Wainwright, Jaakkola, Willsky, 2003
  • Constructing Free Energy Approximations and Generalized Belief Propagation Algorithms, Yedidia, Freeman, Weiss, 2005
• Variational Inference for Graphical Models
  • Tutorial on Graphical models and variational methods, Martin Wainwright, 2008
  • Graphical models, exponential families, and variational inference, Wainwright and Jordan, 2003
  • Tutorial on variational approximation methods, Tommi Jaakkola, 2000

Graphical Model Resources

• Various Graphical Model Courses
• Kevin Murphy's page
• Software and Implementations

Last modified: