Probabilistic graphical models play a central role in modern statistics, machine learning, and artificial intelligence. Within these contexts, researchers and practitioners alike are often interested in modeling the conditional independencies among variables within some complex system. Graphical models address this problem via a union of probability and combinatorics: Namely, a probabilistic graphical model associates jointly distributed random variables in the system with the nodes of a graph and then encodes conditional independence relations entailed by the joint distribution in the edge structure of the graph. Consequently, the combinatorial properties of the graph come to play a critical role in our understanding of the model.

By way of the combinatorial properties of the graph in our graphical model, we gain three main advantages: (1) transparent and tractable representations of our model, (2) effective approaches to exact inference, and (3) data-driven model learning techniques. In this module, we will discuss each of these three advantages as they exist for probabilistic graphical models associated to undirected and directed acyclic graphs. For each topic we will take a close look at the role played by the combinatorial properties of the graph in helping us address these fundamental problems.

Teachers

Svante Linusson (linusson@kth.se)

Liam Solus (solus@kth.se)

Course Literature

The following set of introductory notes and recommended textbooks can be used in conjunction with this course. In the schedule below, suggested reading associated to each lecture can be found. The main books for the course will be resources (2) and (4).

1. Introductory Notes, WASP Graphical Models Course, Module 1.

2. Lauritzen, Steffen. Graphical models. Vol. 17. Clarendon Press, 1996.

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

4. Chickering, David Maxwell. "Optimal structure identification with greedy search." Journal of machine learning research 3.Nov (2002): 507-554.

Examination

Performance in the course will be assessed based on two things: (1) participants will need to earn at least 70% of the points possible over two homework assignments. The first homework assignment is due September 20 and the second homework assignment is due October 13. (2) Participation in the two day meeting on September 27-28 at KTH (or online depending on the pandemic), during which students must attend the lectures and participate in the problem sessions. Information on the two day meeting can be found in the schedule below.

Those participants that specialize in module 1 will also be required to earn at least 70% of the points possible on a third homework assignment that will be distributed to those participants toward the end of the course (date to be announced).

Homework Assignments

The following links will become active when the homework assignments are available:

Homework Assignment 1 (Due: 20 September 2021 at 23.59)

Homework Assignment 2 (Due: 24 October 2021 at 23.59)

Homework Assignment 3 (Due: 28 February 2022 at 23.59)

Your solutions set to homework 1 should be uploaded here.

Your solutions set to homework 2 should be uploaded here.

Your solutions set to homework 3 should be uploaded here.

Socializing Opportunity on 27 September at 20.00

In the schedule below, on the evening of 27 September is an event named "Socializing." Despite the pandemic and having to hold the course virtually, we know that it is important to have some time to socialize with other WASP students. So Danai Deligeorgaki and Albin Toft have created a wonder.me space where anyone who would like to catch up with friends are welcome. The link for the activity is in the schedule below. Either Danai or Albin will also be in the main zoom room for the course in case anyone is having trouble connecting to the wonder.me page. This event is just for the students, so no professors will be present.

Schedule

The following schedule specifies the dates and times of each activity associated with the course, their content, and the associated recommended reading for the lectures. The schedule also specifies important deadlines (e.g. due dates for assignments). The online lectures for the course will take place at the zoom link here:

ZOOM LINK: https://kth-se.zoom.us/j/67240814358

For the activities such as "lunch," "dinner," and "socializing," it is of course not required that participants attend. However, we will have zoom breakout rooms open at these times so that you can eat together and socialize with friends that you cannot meet with in person due to the pandemic.

In the Suggested Reading column, KF and L refer to references 3 and 2 above, respectively.

Date	Time	Teacher	Suggested Reading	Content	Notes	Deadlines
Aug 30	13.00-15.00	Svante	KF 2.2, Introductory notes	Graph theory basics	Slides GraphTheory zoom chat	Homework Set 1 handed out
Sept 6	15.00-17.00	Liam	KF 1.1, 1.2, 2.1	What are graphical models? Probability basics and first examples	notes and zoom chat
Sept 20						Homework Set 1 due
Sept 27	13.00-14.00	Liam	L 3.1, 3.2.1	Representation: Undirected Graphical Models and the Hammersley-Clifford Theorem	notes
Sept 27	14.00-15.00			Practice Session	practice-1 solutions-1
Sept 27	15.00-16.00	Svante	L 3.2.2	Representation: DAG models, and the Directed Factorization Theorem	notes2
Sept 27	16.00-17.00			Practice Session	practice-2 Solutions-2
Sept 27	17.00-18.00	Svante	KF 3.3.4	Learning: Markov equivalence	notes3
Sept 27	18.00-19.00			Practice Session	practice-3 Solutions-3
Sept 27	19.00-20.00			Dinner
Sept 27	20.00-23.59			Socializing	wonder.me link
Sept 28	9.00-10.00	Liam	KF 18.1, 18.2, 18.3, Chickering paper	Learning: Constraint-based and greedy approaches to learning DAG representations from data	notes
Sept 28	10.00-11.00			Practice Session	practice-4 solutions-4
Sept 28	11.00-12.00	Liam	KF 9	Exact Inference: Variable Elimination, Complexity and Tree-width	notes
Sept 28	12.00-13.00			Lunch
Sept 28	13.00-14.00			Practice Session	practice-5 solutions-5
Sept 28	14.00-15.00	Svante	KF 10	Exact Inference: The Clique-tree Algorithm	notes
Sept 28	15.00-16.00			Practice Session	practice-6 solutions-6
Sept 28	16.00			Farewell!
Sept 29						Homework set 2 handed out
Oct 13						Homework Set 2 due
						Homework Set 3 handed out
						Homework Set 3 due