CSE443 Reasoning Under Uncertainty (2nd Semester 2001)
Lectures: Wednesday 10.0012.00 S11, Friday 11.00am1.00pm S11 (1st 4
weeks of semester ONLY).
Ann Nicholson's office hours: Wednesday 1.002.00pm or by appointment
Kevin Korb's office hours: Monday 4.005.00pm, Tuesday 2.003.00pm,
Wednesday 3.004.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:
 Week 11: L10 Linear Causal Models (Wed); L11 CI Learning (Fri); Ass 4 out (Fri).
 Week 12: L12 Parameter Learning (Fri).
 Week 13: L13 Metric Learning (Wed); L14 Search and Evaluation (Fri); Ass 4 due (Fri).
 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
NPhard). 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 DempsterShafer 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 realworld 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

Assignment 1 (20%): Building an oracle for Dseparation. Due 3/8/01 (end of Week 3).

Assignment 2 (20%): Modelling with Bayesian network software. Due 10/8/01 (end of Week 4)

Assignment 3 (20%): Planning with MDPs. Due 31/8/01 (end of Week 7).

Assignment 4 (20%): BN Learning. Due 19/10/01 (end of Week 13)

Written Exam (20%): 2 hr. Wed 24 Oct, 10am  12pm.
All topics may be examined, but more focus will be given to
later topics that have not been covered in assignments.
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
 Russell & Norvig (1995), Artificial Intelligence:
A Modern Approach, Prentice Hall. Chapter 14, 15.6
Lecture 2
 Russell & Norvig (1995), Artificial Intelligence:
A Modern Approach, Prentice Hall. 15.115.2.
 E. Charniak (1991), Bayesian Networks Without Tears, Artificial
Intelligence Magazine, pp. 5063, Vol 12.
 P. Haddaway (1999). An Overview of Some Recent Developments in
Bayesian ProblemSolving Techniques. Artificial Intelligence
Magazine, Vol 20, No. 2, pages 1119.
Lecture 3
 Russell & Norvig (1995), Artificial Intelligence:
A Modern Approach, Prentice Hall. Chapter 15.315.4.

Dean, T.L., Allen, J. and Aloimonons, J. (1994) Artificial
Intelligence: Theory and Practice, Benjamin/Cummings. pages 368389
(Section 8.3)
 D. D'Ambrosio (1999) ``Inference in Bayesian Networks".
Artificial Intelligence Magazine, Vol 20, No. 2, pages 2136.
Lecture 4
 Russell & Norvig (1995), Artificial Intelligence:
A Modern Approach, Prentice Hall. Chapter 16.
 M. Henrion, J.S. Breese and E.J. Horvitz (1991). Decision Analysis and
Expert Systems. Artificial
Intelligence Magazine, pp. 6491, Vol 12.
Lecture 5
 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 481528.
 Russell & Norvig (1995), Artificial Intelligence:
A Modern Approach, Prentice Hall. 15.5, 16.7.
Lecture 6
 R.J. Kennett, K.B. Korb, A.E. Nicholson (2001).
"Seabreeze Prediction Using
Bayesian Networks", In PAKDD'01  Proceedings of the
Fourth PacificAsia Conference on Knowledge Discovery and Data
Mining, Hong Kong, pages 148153.
 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.
 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 343350.
 J. Carlton "Bayesian Poker", Honours thesis, 2000.
Lecture 7
 Sutton, R.S. and Barto, A.G. (1998) Reinforcement
Learning, MIT Press. Chapter 1, Chapter 3.
 Russell & Norvig (1995), Artificial Intelligence:
A Modern Approach, Prentice Hall. 17.1
Lecture 8
 Sutton, R.S. and Barto, A.G. (1998) Reinforcement
Learning, MIT Press. Chapter 4.
 Russell & Norvig (1995), Artificial Intelligence:
A Modern Approach, Prentice Hall. 17.217.3
Lecture 9
 Russell & Norvig (1995), Artificial Intelligence:
A Modern Approach, Prentice Hall.
Lecture 10
 S. Wright (1934). The method of path coefficients. Annals of Mathematical
Statistics, 5, 161215.
Lecture 11
 D.M. Chickering (1995). A transformational characterization of
equivalent Bayesian networks structures. Eleventh Conference on
Uncertainty in AI, pp. 8798.
 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.
 T. Verma and J. Pearl (1991). Equivalence and synthesis of causal models.
Sixth Conference onUncertainty in AI, pp. 255268.
Lecture 12  14: TBD
Interesting WWW Pages
Bayesian Network Software
Bayesian Network Web Resources
Syllabus
Week (Date)

Wednesday
1012noon S11

Friday
111pm 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