CSE443 Reasoning Under Uncertainty (2nd Semester 2001)

Lecturers: Dr. Ann Nicholson and Dr. Kevin Korb

Lectures: Wednesday 10.00-12.00 S11, Friday 11.00am-1.00pm S11 (1st 4 weeks of semester ONLY).

Ann Nicholson's office hours: Wednesday 1.00-2.00pm or by appointment

Kevin Korb's office hours: Monday 4.00-5.00pm, Tuesday 2.00-3.00pm, Wednesday 3.00-4.00pm or by appointment.


News of the week

4/11/01: Marks for Assignment 3 are now available. 21/10/01: Marks for Assignments 1 and 2 now available.

2/10/01: Assignment 4 is now available. The methods required to be implemented will be explained only on Friday (5/10) however. 26/9/01: The tentative new schedule for the last 4 weeks of semester is:

  1. Week 11: L10 Linear Causal Models (Wed); L11 CI Learning (Fri); Ass 4 out (Fri).
  2. Week 12: L12 Parameter Learning (Fri).
  3. Week 13: L13 Metric Learning (Wed); L14 Search and Evaluation (Fri); Ass 4 due (Fri).
  4. Week 14: Final exam (Wed)
Old News of the week.


Subject Outline

CSE 443 is an overview of work done in the Artificial Intelligence community in the area of reasoning under uncertainty.

Part I (Ann Nicholson): This part of the course will focus on two representations for modelling and reasoning under uncertainty: Bayesian (or Belief) networks and Markov Decision Processes. Bayesian networks have rapidly become one of the leading technologies for applying AI to real world problems. This follows the work of Pearl, Lauritzen, and others in the late 1980s showing that Bayesian reasoning in practice could be tractable (although in principle it is NP-hard). We begin with a brief examination of the philosophy of Bayesianism, motivating the use of probabilities in decision making, agent modeling and data analysis, and contrasting Bayesian methods with certainty factors, fuzzy logic and the Dempster-Shafer calculus. We introduce Bayesian networks, their inference techniques and approximation methods. We look at an extension to Bayesian networks, called decision networks, which support decision making. Several BN software packages will be introduced and used throughout the course. We will look at the general problem of "knowledge engineering" of Bayesian networks, and consider practical issues of eliciting domain knowledge from experts. These issues will be illustrated with through the use of several real-world case studies, including Bayesian poker, seabreeze prediction and an intelligent tutoring system for decimal misconceptions. This part of the course will conclude with a brief look at another representation of uncertainty, Markov Decision Processes, together with basic dynamic programming solution methods

Part II (Kevin Korb): There are many difficulties with constructing AI models (such as BNs or MDPs) using human domain knowledge, including lack of human domain expertise, difficulties in elicting causal structure and inconsistent probabilities. This has led to a strong interest in automating the learning of such models from statistical data, which is the focus of the second part of the course. We will start with an introduction to machine learning concepts, including Bayesian confirmation theory, and their application to classifier systems and MDPs with reinforcement learning. We with then examine paremeter learning in the context of Bayesian net parameterization. These techniques allow much of the difficult part of knowledge engineering with Bayesian nets to be automated, but leaves the problem of sorting out Bayesian net structure untouched, so we will continue with Bayesian net structure learning. Some of the techniques have been around for a century; we will look briefly at the tradition of structural equation modeling and causal modeling in the social sciences. Then we examine very recently developed Bayesian, MDL and MML methods for learning causal structure


Prerequisites

It is preferable that you have done CSE3309 Artificial Intelligence (or equivalent) but students can take the subject without this prerequisite. The introductory material on Bayesian networks covered in that subject will be reviewed quickly in CSE443. CSE423 Learning and Prediction is not a prerequisite (though it may be an advantage); introductory material on methods such as MML and MDL will be covered in this course.


Lecture Overheads (Ann Nicholson)

(Note that Ann Nicholson will allocate some class time each week to a tutorial style class, including answering questions about the assignments and the exercises.)

Lecture Overheads (Kevin Korb)


Assessment


Exercises

Homework exercises will be handed out for each topic. It is recommended that students attempt these problems before the next class, as they will assist in developing student understanding of the material. Also, some of the questions in the final exam will be similar to the homework exercises.



Readings for lectures

Lecture 1
  1. Russell & Norvig (1995), Artificial Intelligence: A Modern Approach, Prentice Hall. Chapter 14, 15.6

Lecture 2

  1. Russell & Norvig (1995), Artificial Intelligence: A Modern Approach, Prentice Hall. 15.1-15.2.
  2. E. Charniak (1991), Bayesian Networks Without Tears, Artificial Intelligence Magazine, pp. 50-63, Vol 12.
  3. P. Haddaway (1999). An Overview of Some Recent Developments in Bayesian Problem-Solving Techniques. Artificial Intelligence Magazine, Vol 20, No. 2, pages 11-19.
Lecture 3
  1. Russell & Norvig (1995), Artificial Intelligence: A Modern Approach, Prentice Hall. Chapter 15.3-15.4.
  2. Dean, T.L., Allen, J. and Aloimonons, J. (1994) Artificial Intelligence: Theory and Practice, Benjamin/Cummings. pages 368-389 (Section 8.3)
  3. D. D'Ambrosio (1999) ``Inference in Bayesian Networks". Artificial Intelligence Magazine, Vol 20, No. 2, pages 21-36.

Lecture 4

  1. Russell & Norvig (1995), Artificial Intelligence: A Modern Approach, Prentice Hall. Chapter 16.
  2. M. Henrion, J.S. Breese and E.J. Horvitz (1991). Decision Analysis and Expert Systems. Artificial Intelligence Magazine, pp. 64-91, Vol 12.

Lecture 5

  1. M.J. Druzsdel & L.C. van der Gaag (Eds.) (2000) "Building probabilistic networks: Where do the numbers come from?" Special Section IEEE Trans. on Knowledge and Data Engineering, 12(4), pp 481-528.
  2. Russell & Norvig (1995), Artificial Intelligence: A Modern Approach, Prentice Hall. 15.5, 16.7.

Lecture 6

  1. R.J. Kennett, K.B. Korb, A.E. Nicholson (2001). "Seabreeze Prediction Using Bayesian Networks", In PAKDD'01 -- Proceedings of the Fourth Pacific-Asia Conference on Knowledge Discovery and Data Mining, Hong Kong, pages 148-153.
  2. A.E. Nicholson, T. Boneh, T. Wilkin, K. Stacey, L. Sonenberg, V. Steinle (2001). "A Case Study in Knowledge Discovery and Elicitation in an Intelligent Tutoring Application", To appear in UAI2001.
  3. K.B. Korb, A.E. Nicholson and N. Jitnah (1999). "Bayesian Poker". In UAI99 -- Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence, pages 343-350.
  4. J. Carlton "Bayesian Poker", Honours thesis, 2000.

Lecture 7

  1. Sutton, R.S. and Barto, A.G.  (1998) Reinforcement Learning, MIT Press. Chapter 1, Chapter 3.
  2. Russell & Norvig (1995), Artificial Intelligence: A Modern Approach, Prentice Hall. 17.1

Lecture 8

  1. Sutton, R.S. and Barto, A.G.  (1998) Reinforcement Learning, MIT Press. Chapter 4.
  2. Russell & Norvig (1995), Artificial Intelligence: A Modern Approach, Prentice Hall. 17.2-17.3

Lecture 9

  1. Russell & Norvig (1995), Artificial Intelligence: A Modern Approach, Prentice Hall.

Lecture 10

  1. S. Wright (1934). The method of path coefficients. Annals of Mathematical Statistics, 5, 161-215.

Lecture 11

  1. D.M. Chickering (1995). A transformational characterization of equivalent Bayesian networks structures. Eleventh Conference on Uncertainty in AI, pp. 87-98.
  2. P. Spirtes, C. Glymour and R. Scheines (1990). Causality from probability. In J.E. Tiles, G.T. McKee and G.C. Dean (Eds.) Evolving knowledge in natural science and artificial intelligence. Pitman.
  3. T. Verma and J. Pearl (1991). Equivalence and synthesis of causal models. Sixth Conference onUncertainty in AI, pp. 255-268.

Lecture 12 - 14: TBD

Interesting WWW Pages

Bayesian Network Software

Bayesian Network Web Resources


Syllabus

Week (Date)
Wednesday
10-12noon S11
Friday
11-1pm S11
Assignment
1 (16/7)
L1 Intro to CSE443/Bayesian AI
L2 Intro to Bayesian Networks
Ass. 1, Ass. 2 Out 19/7
2 (23/7)
L3 Inference in Bayesian Networks
L4 Decision Networks
 
3 (30/7)
L5 BN Knowledge Engineering
L6 BN Case Studies
 Ass. 1 In 3/8
4 (6/8)
L7 Intro to MDPs
L8 Dynamic Programming
Ass 2 In 10/8.
Ass. 3 Out 9/8
5 (13/8)
L9 Intro to ML; Bayesian conf theory
   
6 (20/8)
L10 Reinforcement learning; linear models
   
7 (27/8)
No Class
 
Ass. 3 In 31/8
8 (3/9)
No Class
   
9 (10/9)
No Class
   
10 (17/9)
L11 Parameter learning
 
 Ass. 4 Out 19/9
 
MIDSEMESTER BREAK
11 (1/10)
L12 CI learning
   
12 (8/10)
L13 Bayesian, MDL, MML learners
 
 Ass. 4 In 12/10
13 (15/10)
L14 Search methods; evaluation of BN learners
   
14 (22/10)
Exam
   

Ann Nicholson Last Updated Monash July 16 2001