Topics in AI, Graphical Models

Winter Term 2, 2018 (CPSC 532R)

Administrative

  • Class: Tuesdays and Thursdays 3:30-5pm, Hugh Dempster Pavilion (DMP) 101
  • Office hours: Fridays 4-5pm
  • TA: Amin Aghaee

Course Description

Graphical models are powerful probabilistic modeling tools. They can model the complex behavior of a large system of interacting variables through local relations specified using a graph. These probabilistic models represent the conditional dependencies between a subsets of variables in a compressed and elegant form. The framework of graphical models has achieved a remarkable success across a variety of domains, from near-optimal codes for communication to the state-of-the-art in combinatorial optimization; these models are widely used in bioinformatics, robotics, vision, natural language processing and machine learning. In this course, after introducing different families of graphical models and their modeling assumptions, we review exact and approximate inference including deterministic optimization-based and stochastic sampling-based methods. We also discuss various approaches to learning of the model from the data.

Prerequisites:

Basic familiarity with probability theory and algorithm design is required. You need experience programming with Python/Numpy for the assignments. Background in AI CPSC522, CPSC502 and in particular machine learning CPSC340, CPSC540 is highly recommended.

Main textbook:

Koller, Daphne, and Nir Friedman. Probabilistic graphical models: principles and techniques. MIT press, 2009.

Further readings:

  • Wainwright, Martin J., and Michael I. Jordan. Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning, 2008
  • Murphy, Kevin P. Machine learning: a probabilistic perspective. MIT press, 2012.
  • Barber, David. Bayesian reasoning and machine learning. Cambridge University Press, 2012.

Syllabus + Slides

Representation

  • Syllabus, review of the probability theory (slides, chapters 2)
  • Bayesian Networks (slides, chapter 3)
  • Markov Networks (slides ) and
  • The relationship between directed and undirected models (slides, chapter 4)
  • Local and Conditional Probability Models (slides, chapter 5)
  • Gaussian Network Models (slides, chapter 6)

Inference

  • Complexity of Inference and Variable Elimination ( slides, chapter 7)
  • Junction Trees and Belief Propagation (slides, chapter 10)
  • Variational Inference (chapters 8, 11, 13)
    • Exponential Family and Variational Inference (slides)
    • Loopy Belief Propagation and Bethe Free Energy (slides)
    • Naive Mean-Field (slides)
  • Maximum a Posteriori Inference (slides, chapter 13)
  • Sampling Based Inference (chapter 12)
    • Monte Carlo Inference in Graphical Models (slides)
    • Markov Chain Monte Carlo (slides)

Learning

  • Overview: Objectives in Learning (slides, chapter 16)
  • Maximum likelihood and Bayesian Estimation in Directed Models (slides, chapter 17)
  • Parameter-Learning in Undirected Models (slides, chapter 20)
  • Learning with Partial Observations (slides, chapters 19)

Grading and Course Material

Assignments and optional/alternative readings are available on Canvas. Grading is based on

  • Homework Assignments (50%)
  • Course Project (35%)
  • Exam (15%)