The course starts with an introduction to graphical probability models (or belief networks) focusing on the rules of inference in graphs. We then introduce the classic exact belief propagation algorithms (i.e the junction tree algorithm). For the second part of the course we focus on modern approximate algorithms, used for belief propagation in large or dense graphs. We will discuss application in speech and language, image processing, computational biology, and other areas. We will also show that probabilistic reasoning algorithms are a subclass of a much larger class of algorithms, which could be loosely termed "local propagation on AND-OR graphs". The connections to, for instance dynamic programming and constraint propagation will be discussed.
Prerequisites: basic notions of probability (at the level of STAT 390/391/394), basics of algorithms and complexity.
Format: One two hour lecture/discussion weekly. Typically, the instructors will start by presenting each topic, then we will progress towards an open discussion. The reading materials will be course notes plus original research and tutorial papers.
Graded: 3 credits based on mini-projects/homework and participation in class.