CSCE 582 {=STAT 582} (Fall 2003): Lecture Log

August 21 (Thu), 2003 Introduction to the Course: Goals and Topics to Be Covered. The bulletin description, explained: "582 -- 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." Questionnaire, wich discussion. Examples of plausible reasoning and causal graphs: icy roads.

August 26 (Tue), 2003 Examples of plausible reasoning and causal graphs: wet grass, car start, earthquake. Reasoning in the evidential and causal direction. Intercausal reasoning and explaining away. Uncertain reasoning is non-functional. Serial, diverging, and converging connections. Paths as sequesnces of nodes or of edges. Paths vs. walks, paths, simple paths. Chains.

August 28 (Thu), 2003 Homework 1 (HW1) assigned, due Tuesday, September 2: Exercises 1.1, 1.2, 1.3, 1.4. Definition of d-separation, with several examples. Complexity of checking d-separation using the naive algorithm based on the definition: list all chains, check every connection on each chain. Lower bound on the worst case is the number of paths between two nodes in a DAG. There are (n-2)! paths between two nodes in a DAG in the worst case. (There are c exp (n/c) paths in a staged network, a special case of DAG, in the worst case; the worst value for c is 3.) This motivates the search for more efficient algorithms for checking d-separation. There are several of them. One of them is Bayes-ball [Shachter, 1998]. Basic Bayes-ball rules.

September 2 (Tue), 2003 HW1 collected. Detailed discussion of Bayes-ball algorithm. Powepoint presentation used is linked to course web site. Two point of extra credit will be given for correctness proof, if done within a week.

September 4 (Thu), 2003 Probability. The three axioms of Kolmogorov [1950]. Outcome space, event space, probability measure. Three historically important interpretations in which the axioms of Kolmogorov are true (i.e., three models of them): classical, frequentist, and subjective. Detailed presentation of the classical approach, including proof of the three properties that are the axioms of Kolmogorov. Brief presentation of the frequentist approach. Even briefer presentation of the subjective approach.

September 9 (Tue), 2003 HW1 returned. Guest lecture by Professor Juan E. Vargas: "Information as a Measure." Notes from the lecture are posted under "Lecture Notes" on the course web site.

September 11 (Thu), 2003 Handout: Ch. 2 of Neapolitan's 1990 book on the foundations of probability. Continuation of the lecture of September 4. Subjective probability defined from betting behavior: "[De Finetti] defines the probability P(E) of an event E as the fraction of a whole unit value which one would feel is the fair amount to exchange for the promise that one would receive a whole unit of value if E turns out to be true and zero units if E turns out to be false" [Neapolitan, 1990, p.56]. Similarly, subjective probability could be defined using the equivalent urn model. The probability P(E) of an event E is the fraction of red balls in an urn containing red and brown balls such that one would feel indifferent between the statement "E will occur" and "a red ball would be extracted from the urn." (I believe that this definition is due to D.V. Lindley.) Kolmogorov's axioms and the "definition" of conditional probability can be derived from the definition of subjective probability and the assumption of coherence in (betting) behavior, as explained on pp.56-58 of the handout. "Definition" of conditional probability derived in the classical approach (Theorem 2.2), with the assumption that equiprobable outcomes remain equiprobable in a new state of knowledge. Definition of conditional probability as an additional axiom of probability, which is true in the three major models of probability (classical, frequentist, subjective). Bayes theorem (Bayes law, the inversion formula).

September 16 (Tue), 2003 Several questions answered on Neapolitan handout. The theorem of total probability (case analysis). Definition of Bayesian networks [Neapolitan, 1990]. The visit to Asia example. The chain rule for Bayesian network: statement and example using "icy roads."

September 18 (Thu), 2003 HW2 reassigned and (finally!) due on Tuesday, September 23: exercises 1.5, 1.6, 1.7. Marginalization (a.k.a. projection, in this course). Computations with conditional probability tables, using the icy roads example. Proof of the chain rule. Bayesian networks admit d-separation. Several questions answered.

September 23 (Tue), 2003 Midterm will be in one week. Evidence. P(V,e). P(V|e). Normalization.

September 25 (Thu), 2003 Midterm exam will be on Tuesday, September 30. HW3 assigned, due on Tuesday, September 30: exercises 1.8, 1.9, 1.10. The variable elimination (Dechter's "bucket elimination" variant) algorithm for computation of posterior probabilities ("belief assessment"), with detailed example using "Visit to Asia."

September 30 (Tue), 2003 Midterm (MT1). HW3 collected.

October 2 (Thu), 2003 MT1 returned. Introduction to Hugin. Hypothesis variables. Infected milk, one-day and seven-day versions.

October 7 (Thu), 2003 HW4 (exercises 1.11, 1.12, 1.13, 1.14, 1.15) is due on Thursday; use departmental dropbox for submissions. Milk test example, hidden Markov models. Many good questions.

October 9 (Thu), 2003 HW2 and HW3 returned. Students who answered question 1.9 by just giving the final answer should resubmit their work. HW5 (exercises 2.1-2.5) due Thursday, October 16. Cold and angina. Independence relations in that model. Bipartite graph models (hypotheses, observations) and their limitations. Diagnostic bipartite graph models (diseases and symptoms) and their limitations. Quadriparite graph models (setting factors, diseases, pathophysiological states, and symptoms). Family-out. Many good questions.

October 16 (Thu), 2003 HW5 deadline extended to Tuesday, October 21. Simple (naive, idiot) Bayes. Odds-likelihood formulation of simple Bayes, with derivation of formula: posterior odds = prior odds times likelihood(s). Poker example. Pearl's coins and bells example: non-causally interpretable Bayesian networks, faithfulness, stability.

October 21 (Tue), 2003 Much discussion of the coins and bells example, in full detail, with Q&A.

October 23 (Thu), 2003 HW6: Exercise 1.15, due Tuesday, October 28. (HW6 is only for students who have not turned in Exercise 1.15 as part of HW4 or want to resubmit that exercise. Submit using departmental dropbox should be used.) HW7: Exercises 2.6, 2.7, 2.8, 2.9, due Thursday, October 30. Submit using departmental dropbox. The stratum method for constructing Bayesian networks (from independence information derived from qualitative descriptions). The intervention-based notion of causality, again. The telescopes example. The Monty Hall puzzle. Bayesian net to represent it, with full numerical specification. Much good discussion involving students.

October 28 (Tue), 2003 HW7 changed: exercises 2.6, 2.7, 2.8 only (not 2.9), due Thursday, October 30. Submit using departmental dropbox. Assessment of prior and conditional probabilities: infected milk examples, statistics for reliability of information sources (after Vomlel): true positives, etc. Stud farm example.

October 30 (Thu), 2003 Detailed discussion of issues related to questions 2.6 and 2.7, with good Q&A. The transmission of symbol strings example (section 2.2.4). Introduction to independence of causal influence, with Dog_out | Family_out, Bowel_problems example.

November 4 (Tue), 2003 HW8 assigned: exercise 2.9. Independence of causal influence and noisy-OR: the Family-out example, with and without leak (background) probability. Representation of relations in Bayesian networks.

November 6 (Thu), 2003 MT1 will be on Tuesday, November 11. HW9 assigned: exercise 2.18, due Tuesday, 11/11 PR3 assigned: exercise 2.10, due Thursday, 11/13 PR4 assigned: exercise 2.22, due Tuesday, 11/18 Semester programming assignment (PR5) assigned, due Thursday, 11/20. Chapter 2 concluded, with an overview of the remaining topics, and a discussion of the tree-structured representation of CPTs. NSDP.

November 11 (Tue), 2003 MT2 (proctored by Ravi Katpelly)

November 13 (Thu), 2003 Presentation by Hing Xi and Jingshan Huang of paper by Y. Xiang and V. Lesser: "On the Role of Multiply Sectioned Bayesian Networks to Cooperative Multiagent Systems." (Local copy and PowerPoint linked to web site.)

November 18 (Tue), 2003 Programming assignment (PR5) due date changed to Tuesday, November 25. Correction of MT2 (returned). Discussion of exercise 2.22 (due today): review of conflict index and sensitivity analysis. Discussion of programming assignment.

November 20 (Thu), 2003 Stochastic simulation: forward sampling and evidence-based sampling (Gibbs sampling). Hypothesis-based influence diagrams (a.k.a. decision graphs). Utilities and decisions (actions). Cow pregnancy example.

November 25 (Tue), 2003 PR5 due date changed to Tuesday, December 2. Extra credit assignment (5% of total grade): add stochastic simulation to PR5. Value of information: Section 4.3.1 completed.

December 2 (Tue), 2003 Graduate Student Presentations.

December 6 (Tue), 2003 Graduate Student Presentations. Presentations are linked to the web site. End of course.