Syllabus for Probabilistic Reasoning in AI (308-526B)

Winter 2002

General Information

Location:	Leacock, Room 14.
Times:	Monday and Wednesday, 1:00-2:30pm.
Instructor:	Professor Doina Precup, School of Computer Science.
Office:	McConnell 326.
Phone:	398-6443.
Email:	dprecup@cs.mcgill.ca
Office hours:	Monday & Wednesday, 2:30-3:00; Tuesday, 2:00-3:00pm. Meetings at other times by appointment only! IMPORTANT: Email is the easiest way to reach me!
Class web page:	http://www.cs.mcgill.ca/~dprecup/courses/Winter2002/prob.html IMPORTANT: This is where class notes, announcements and homeworks are posted!
Teaching Assistant:	Will Renner Email: wrenner@acm.org Office hours: TBA

Course Description

One of the primary goals of AI is the design, control and analysis of agents or systems that behave appropriately in various circumstances. Such intelligent agents require the ability to decide how to act as circumstances vary. In turn, good decision making requires that the agent have knowledge or beliefs about its environment and its dynamics, about its own abilities to observe and change the environment, and about its own goals and preferences. In this course we will examine some of the techniques for modeling decision problems of various types and the computational methods used to solve them. We will focus mainly on probabilistic models of reasoning, and on sequential decision making.

The course is intended for advanced undergraduate students and for graduate students, and will provide an introduction to the on-going research in the field of reasoning under uncertainty, which has been very active during the last decade.

The course will cover both the theoretical basis of decision making under uncertainty, and the practical applications of these algorithms. We will cover the following topics:

The principles of Bayesian inference
Belief networks
- Syntax and semantics
- Exact and approximate inference
- Learning methods
Temporal models
- Hidden Markov Models
- Dynamic Bayes nets
- Kalman filters
Basics of utility theory
Markov Decision Processes
- Dynamic programming methods
- Monte Carlo methods
- Temporal-difference learning algorithms
- Generalization and function approximation
- Structured state and action spaces
Partially Observable Markov Decision Processes
- Exact methods
- Approximate methods

A tentative class schedule is posted on the course web page.

Prerequisites

Basic knowledge of a programming language is required. Basic knowledge of probabilities and statistics is highly recommended. Example courses at McGill providing sufficient background are 189-323 or 304-305. Some AI background is recommended, as provided, for instance by 308-424 or 304-526. If you have doubts regarding your background, please contact me to discuss it.

Reference Materials

The main textbook for the first part of the course is: Probabilistic reasoning in intelligent systems: Networks of Plausible Inference by Judea Pearl (Revised second printing, Morgan Kaufmann, 1998). The main textbook for the second part of the course is: Reinforcement learning: An introduction by Richard Sutton and Andrew G Barto (MIT Press, 1998). The full text of this book is available on-line. Since the books do not cover many new and exciting developments in the field, we will supplement them with research papers and other notes. These will be distributed in class or posted on the web page, as appropriate. The class slides will be posted on the web page.

Class Requirements

The class grade will be based on the following components:

Six problem sets - 40% total
Four programming assignments - 20% total
Two reading assignments - 10% total
Class project - 30%
Participation in class discussions - up to 5% extra credit.

Minor changes to the evaluation scheme (if any) will be announced in class by Monday, January 14 (pending in-class discussion and the estimated total enrollment).

The problem sets include questions related to the material discussed in class. The programming assignments will involve experimenting with algorithms that we discuss in class and reporting results produced by these algorithms. The ability to program in a high-level language, such as C/C++, Java, LISP, Matlab, under the UNIX operating system is assumed but the use of these languages is not mandatory. You may use any programming language, as long as you can demonstrate that your implementation is correct. We may also use programs written by other researchers, as needed

The reading assignments will involve summarizing and/or critiquing research papers in the field. You are also expected to actively participate in class discussions, and the participation is part of your grade for the reading assignment. When reading the book and other papers, always think about questions that you may have, and bring them to class.

The final project will involve choosing a topic, either from a list of suggestions that will be provided or based on your own interests. You will be required to read papers related to the topic, implement or find available implementations of the algorithms discussed, and perform experimental work comparing these algorithms. You will be required to write a report describing your topic and your findings. We may also have class project presentations, depending on the enrollment. Details on the project will be available later.

Homework Policy

Problem sets and programming assignments should be submitted in class on the day when they are due. In addition, the answers to programming problems must also be submitted electronically, using the handin system. Assignments submitted until 1:00pm on the next day will be penalized by 10 points. Assignments submitted before the next class are penalized 25 points. No credit is given for assignments submitted at a later time, unless you have a medical problem.

Reading assignments are due in class. If you cannot come to class, please contact me to make different arrangements for submitting the assignment.

All assignments are INDIVIDUAL! You may discuss the problems with your colleagues, but you must submit individual homeworks. Please acknowledge all sources you use in the homeworks (papers, code or ideas from someone else).

Prof. Doina PRECUP