04-654   Introduction to Probabilistic Graphical Model

Location: Africa

Units: 12

Semester Offered: Fall

Course concentration

Applied machine learning

Course description

This course provides an introduction to the subject of Probabilistic Graphical Models (PGM). PGM give a unified view for a wide range of problems arising in several domains such as artificial intelligence, statistics, computer systems, computer vision, natural language processing, and computational biology, among many other fields. They provide a very flexible and powerful framework for capturing statistical dependencies in complex, multivariate data. PGM brings together probability theory and graph theory to enable efficient inference, decision-making, and learning in problems with a very large number of attributes and huge datasets. This introductory course will provide you with a strong foundation necessary for applying graphical models to complex problems.

Learning objectives

We will cover key issues including representation, efficient algorithms, inference, and statistical estimation. It starts by introducing probabilistic graphical models from the very basics and concludes by presenting the different PGM algorithms and techniques used for inference and learning with directed and undirected graphical models.

Content details 

• Module 1: Motivation and Revision

  • Motivational Examples
  • Revision Probability
  • Revision Graph Theory
Module 2: Basics of Graphical Models
  • Directed Graphs
    • Factorization
    • Markov Properties
  • Undirected Graphs
    • Factorization 
    • Markov Properties
  • Factor Graphs
Module 3: Algorithms for Probabilistic Inference on Trees
  • Elimination Algorithm
    • Basic Algorithm
    • Graphical Approach
    • Complexity
  • Message Passing Algorithms (marginals over all nodes)
    • Inference of Marginals: Sum-Product
      • Sum-Product on Trees
      • Sum-Product on Factor Trees
  • Mode Computation: Max-Product
Module 4: Inference in Graphs with Cycles: Junction Tree Framework
  • Clique Tree and Running Intersection
  • Triangulation and Junction Trees
  • Junction Tree Construction
  • Junction Tree Algorithm
Module 5: Learning Algorithms
  • Parameters Estimation (Directed and Undirected Graphs)
    • Maximum Likelihood
    • Iterative Proportional Scaling
  • Structure Learning
    • Chow-Liu Algorithm
    • Bayesian Structure Learning
Module 6: Putting it all together

Outcomes

At the end of the course, students will acquire the background knowledge and skills necessary to apply probabilistic graphical models to solve real problems.

Prerequisites

Students are expected to have an undergraduate-level background in linear algebra, multivariate calculus, probability theory, statistic, and some basic graph theory.

Faculty

Assane Gueye and Carine Mukamakuza