CSCE 582 {=STAT 582} Bayesian Networks and Decision Graphs

Prerequisites: CSCE 350 (formerly CSCI 220) (Data Structures and Algorithms) and STAT 509 (Statistics for Engineers)

Bulletin Description: Bayesian Networks and Decision Graphs. {=STAT 582} (3) (Prereq: CSCE 350 and STAT 509) Normative approaches to uncertainty in Artificial Intelligence. Probabilistic and causal modeling with Bayesian networks and influence diagrams. Applications in decision analysis and support. Algorithms for probability update in graphical models.

Meeting Time: TTh 0930-1100
Instructor: Marco Valtorta
Office: Swearingen 3A55, 777-4641
Office Hours: MWF 0900-1000 or by previous appointment,
Teaching Assistant: Hong (Sharon) Xi, Office TBD, Phone TBD,, Office Hours TBD or by appointment set up by email.

The goals of this course are:

The course is foundational. It concentrates on modeling and use of decision analysis principles. Algorithms for belief updating (especially variable elimination and Jensen's version of the Lauritzen-Spiegelhalter algorithm, but also stochastic simulation) are discussed to some depth, but advanced topics on algorithmic issues are left out. It is my hope that a student who successfully completes this course will both be able to use decision analytic tools such as Hugin well and be well prepared for advanced graduate courses in, e.g., data mining.

The material in this course is very new. It is not very difficult, but it is likely that you have never seen anything quite like this in your academic career. Therefore, it is very important that you do the homework as it is assigned. Homework is due at the beginning of class. Homework submitted after the beginning of class but before the beginning of the next class is assessed a 20% penalty. Homework submitted after that but before the beginning of the next class is assessed an additional 10% penalty per day. A grade of zero is assigned to homework that is more than a week late. It is essential for your understanding of the subject matter that you do the homework on your own. Undoubtedly, you can find solutions to some of the exercises on the web or elsewhere. If you find the solution to some exercise in the literature, please indicate clearly the source (book, article, conference paper, web site) you consulted. I will then discuss with you the situation. I will not penalize you (and may even commend you for your scholarship), but I will make sure that you understand the concepts involved in the assigned exercise. Since some of the homework involves drawing graphs, you may find it easier to turn in handwritten homework. This is acceptable, but you may be penalized for homework that is not clearly and neatly written.

Honor code violations will be followed up as required by the Academic Responsibility section of "Carolina Community: USC Student Handbook and Policy Guide." (You may want to review this document. In particular note that the instructor's discretion is quite limited in cases involving academic dishonesty.) Honor code violations will impact your grade negatively.

Students are expected to be aware of the university policy on use of computing resources, including the Student Guidelines for Responsible Computing, as well as the college and departmental policies on proper use of computing resources. Every instance of a suspected violation will be reported.

NOTES ABOUT FINAL EXAM: (1) Final exam will be cumulative (2) Graduate student presentations will not be a part of the exam (3) Textbook materials to be subject of the exam are: chapters 1 and 2 (all), Section 3.1, Sections 4.1, 4.2, and 4.3, Section 5.7. (4) Other topics that are subjects of the exam include: the stratum method for constructing Bayesian networks (start by choosing an order of the variables,...).

Suggestions for the final.

I was asked to post a solution to problem 3 in the final exam actually give on December 11, 2003. Here is Finn V. Jensen's solution, as a Hugin .net file. This is not the only solution possible. In fact, it is arguable whether the link from Pot to Cup is warranted by the story. It makes the network more interesting, but it just does not seem to follow from the story: after all, I often dring coffee in a tea cup! The use of the constraint node to represent the constraing between pieces of cutlery is the obvious solution, and it requires entering as evidence that the constraint is present. Some of the students used this approach; others linked Cut1 to Cut2: this also seems to work, and it does not require entering additional evidence.

NOTE: EXTRA CREDIT ASSIGNMENT (STOCHASTIC SIMULATION) WILL BE ACCEPTED UNITIL MIDNIGHT ON FRIDAY, December 5. Please use the dropbox labeled PR6 to submit the extra credit assignement. Update: Extra Credit Assignment will be accepted late with penalty.

Grading Policy

Syllabus and Required Text

Lecture Log

Lecture Notes

Homework grading policy, per assignment

Links for the semester programming assignment

Useful Links (to be constructed)

Some sample questions for Midterm 1 (in postscript)

Graduate Student Presentations