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

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)

Subject Outline

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

• CSSE subject page: http://www.csse.monash.edu.au/hons/2001/443.html
• Detailed subject information (including lecture overheads):
  http://www.csse.monash.edu.au/ annn/443/443.html.

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

Lecture Overheads (Ann Nicholson)

• Lecture 1 Introduction to Bayesian AI
• Lecture 2 Introduction to Bayesian Networks
• Lecture 3 Inference in Bayesian Networks
• Lecture 4 Decision Networks
• Lecture 5 BN Knowledge Engineering
• Lecture 6 BN Case Studies
• Lectures 7,8 Intro to MDPs, Dynamic Programming

Lecture Overheads (Kevin Korb)

• Lecture 9 Intro to Machine Learning and Bayesian Confirmation Theory
• Lecture 10 Linear Causal Models
• Lecture 11 Conditional Independence Learning
• Lecture 12 Parameter learning
• Lecture 13 Metric Learning: Bayesian, MDL, MML
• Lecture 14 Search and the Evaluation of BN Learners

Assessment

• Assignment 1 (20%): Building an oracle for D-separation. 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)
  • LearningEg.dne
  • Cancer_Neapolitan.dnet
  • ALARM.dnet
• 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

• Exercise sheet 1 (Probability) Solutions
• Exercise sheet 2 (BN syntax and semantics) Solutions
• Exercise sheet 3 (BN inference)
• Exercise sheet 4 (Decision making)
• Exercise sheet 5 (MDPs and Dynamic Programming)
• More exercise sheets (for KK material) will be added later.

Readings for lectures

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.

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

• Netica
• Hugin
• Analytica
• JavaBayes
• Bayesware
• Genie
• BN Power Constructor
• WinMine Tookkit

Bayesian Network Web Resources

• Russell Greiner's Bayesian Belief Network site
• Nir Friedman's Bayesian Network Repository
• Kevin Murphy's BN site

Syllabus