August 23 (Fri), 2002 Introduction to the Course: Goals and Topics to Be Covered. Questionnaire. Historical overview of the field of Uncertainty in AI. Steffen Lauritzen and Judea Pearl. 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."
August 26 (Mon), 2002 Examples of plausible reasoning and causal graphs: ici roads, wet grass. Reasoning in the evidential and causal direction. Abduction. Intercausal reasoning ane explaining away. Uncertain reasoning is non-functional.
August 27 (Wed), 2002 Examples: Earthquake. Homework 1 (HW1) assigned, due Friday August 29: exercises 1.1 and 1.2. Paths and chains in DAGs. Blocked chains. d-separation. Examples of d-separation.
August 29 (Fri), 2002 HW1 collected. HW2 assigned: exercises 1.3, 1.4, 1.5, due on Wednesday, September 4. Brief discussion of the Chernobyl example (which will be used later in the day at 10-minute madness). 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. (Just mentioned.)
September 4 (Wed), 2002 HW3 assigned: exercises 1.6, 1.7, 1.8, due Monday, September 9. Definition of Bayesian network [Neapolitan, 1990].
September 6 (Fri), 2002 Propositional variables and their states (a.k.a. values). Conditional, joint, and marginal probabilities. Operation on probability tables. The strata method of building Bayesian networks: earthquake, burglary, alarm, Mary, and John example [Russell and Norvig 1995 after Pearl] with different orders of variables.
September 9 (Mon), 2002 HW3 collected. HW4 assigned: exercises 1.9 and 1.10, due Monday, September 16. Q&A on exercise 1.7: working with joint and conditional probability tables; checking for conditional independence. Review of the strata method for building BNs: Conclusion of example, heuristic based on causal or temporal ordering of variables. Theorem: the chain rule for Bayesian networks: statement, review of the fundamental rule; not quite completed.
September 11 (Wed), 2002 Review of topological sorting. The chain rule for BNs (decomposition theorem for BNs) proven, in full detail. Definition of family of a variable. The rule allows a reduction in number of parameters (probabilities) to be estimated and on the space needed to store a joint probability.
September 13 (Fri), 2002 Bayesian networks admit d-separation: If two (sets of) variables are dseparated in a dag D given a third set of variables, then the two sets are independent given the third in any Bayesian network whose structure is D. This theorem is stated without proof. The theorem motivates building Bayesian networks in two phases: a qualitative one, in which the structure (a dag) is built, and a quantitative phase in which the parameters (i.e., just the conditional probability tables for each variable given its parents) are assessed. Example: dyspnea ("visit to Asia"), in detail. Q&A.
September 16 (Mon), 2002 HW4 collected. HW5 assigned: complete the coins and bells example by completing the joint probability tables for the two Bayesian network structures and conditional probability tables given in class, and showing that they are identical. The converse of the "admittance" theorem does not hold. As counterexample to the converse theorem, I give Pearl's [1988] coins and bells example. Very brief introduction to Hugin (using version 5.7 lite on laptop). I recommend using 6.1 professional in the lab and 5.7 lite at home. 5.7 lite is available for download at http://ftp.cse.sc.edu/valtorta/
September 18 (Wed), 2002 HW5 collected. HW6 assigned and due Monday, September 23: exercises 1.11 and 1.12. HW7 assigned and due Wednesday, September 25: exercises 1.13, 1.14, 1.15. Hugin nets should be turned in using the dropbox, in Hugin .net format (not .hkb!). Brief demonstration of Hugin: alcohol test example. Evidence and CPTs: conditioning in the presence of evidence by normalization of a table where the entries inconsistent with the evidence are zeroed out. The probability of evidence, P(All) in Hugin. Marginalization of a factorized joint probability: the Asia example, introduction.
September 20 (Fri), 2002 HW3, HW4, HW5 returned. Marginalization of a joint probability: changing the order of summation does not change the result. Notation based on the notion of family of a variable.
September 23 (Mon), 2002 HW6 collected. HW8 assigned, due Wednesday, September 25: complete the elimination of variables for the dyspnea network. Variable elimination: algorithm schema; example using the dyspnea (Asia) network, with the following order of elimination: epsilon, tau, sigma.
September 25 (Wed), 2002 HW8 collected. Extension for HW7 given: due tomorrow at 13:15, using CSE dropbox. Variable elimination. Small example (diamond). The order of elimination does not affect the result, but it affects the complexity of computing a marginal. Better elimination orders lead to h functions that have small domains (Jacobs). Definition of interaction graph. Changes in the interaction graph depend on the order of elimination. Minimum degree heuristic (Tillman). Asia example.
September 27 (Fri), 2002 Midterm Test 1.
September 30 (Mon), 2002 MT1 and HW6 returned. Correction of MT1, with discussion of topological ordering, including Szpilrajn's (1930) theorem (in any DAG there is a node with no parents, proved), the topological sort algorithm (stated), and Knuth's linear time algorithm (linear in n+m, contrary to what I said in class!). (A good reference is section 11.4 of Kingston, Jeffrey H. _Algorithms and Data Structures: Design, Correctness and Analysis_, 2nd ed., Addison-Wesley, 1998; or section 10.4 of the first edition, 1990.) Brief discussion of HW6 also, including: why is the arrow from A to T and not viceversa?
October 2 (Wed), 2002 NSDP.
October 4 (Fri), 2002 HW8 returned. Review of variable elimination, with some Q&A. Factor trees.
October 7 (Mon), 2002 Generalization of variable elimination: NSDP, belief update, MPE. Shenoy's axioms on marginalization (projection) and combination that allow the use of variable elimination. Modeling (chapter 2) started. Example (on laptop): the BOBLO system for verification of parentage of Jersey cattle.
October 9 (Wed), 2002 HW9 assigned: exercises 2.2, 2.3, 2.4, 2.6, 2.7, due Wednesday, October 16. I ask the students to use Hugin for all exercises, including 2.2; for 2.2, they are only required to draw the graph. Modeling: hypothesis, observation, and other variables. Naive Bayes. Cow pregnancy network. Milk network: seven days, with Markov condition, with two-day memory, and with estimate of the accuracy of the test.
October 11 (Fri), 2002 Graduate student presentation: bucket elimination paper by Rina Dechter, presented by Anton Bezuglov and Hrishikesh Goradia. See link to presentations on main course web page for details (including PowerPoint slides).
October 14 (Mon), 2002 Fall break. No class.
October 16 (Wed), 2002 Examples of models: Cold or Angina, Poker. Simple Bayes: likelihood. Causality in model building; Reichenbach's principle.
October 18 (Fri), 2002 Manipulative account of causality. Doing (setting a value) versus observing. Example: the sneezing net (Verma and Pearl, 1990) is causal. The coin and bell net where bell has no parents is non-causal. When a value is set in a causal Bayesian network, a new model is created in which the links to the variable whose value is set are broken. Infected milk: how the probability values in the tables are assessed.
October 21 (Mon), 2002 HW10 assigned: 2.5, 2.8, 2.9, 2.10, due Monday, October 28. Use dropbox. Turn in nets in Hugin .net (v.5.7) format for exercises 2.5, 2.8, and 2.10. Also turn in a paper for all exercises. Family Out network. Noisy Or. Leaky Noisy Or.
October 23 (Wed), 2002 More on Noisy Or. The stud farm example.
October 25 (Fri), 2002 Transmission of symbol strings. Relations. The socks example.
October 28 (Mon), 2002 HW11 assigned, due Friday, 11-1: exercises 2.13; 3.15 in [J96]: copy of relevant pages (66, 67) given. Divorcing (2.3.3); noisy functional dependence (2.3.4); time-stamped models (2.3.5).
October 28 (Mon), 2002 Review of some biological concepts for exercise 2.10: mutation and recessive gene born by the X (female) chromosome. Brief discussion of exercise 2.8(ii). Deadline for HW10 extended to Friday. All students are invited to resubmit. Expert disagreements.
November 1 (Fri), 2002 Some discussion of the Monty Hall exercise (2.13). Presentation by Viji R. Avali and Richard E. McCraw: Kathryn Laskey and Todd Levitt. "Multisource Fusion for Probabilistic Detection and Opportunistic Assessment of Terrorist Threats." Aerosense 2002.
November 4 (Mon), 2002 Reminder of policy on using solutions to exercises found on line. Test decisions and action decisions; intevening and non-intervening actions; the importance of causality (Intro to Ch.4). Value of information: informal introduction, loosely based on: Ronald A. Howard. "Information Value Theory." _IEEE Transactions on Systems Science and Cybernetics_, 2, 1 (August 1966), pp. 22-26. Myopic hypothesis driven data request (Section 4.3.2). Example of pregnacy networks; definitions. Example based on: Finn V. Jensen and Jianming Lang. "drHugin: A System for Value of Information in Bayesian Networks." Proceedings of the 1994 International Conference on Information Processing and Management of Uncertainty in Knowledge-Based Systems. Link on main web site for course.
November 6 (Wed), 2002 Utility and tests: the oil wildcatter example (as described in [J96]).
November 8 (Fri), 2002 Oil wildcatter in great detail. More on utilities; management of effort example (4.2 in [J00]).
November 11 (Mon), 2002 Midterm 2.
November 13 (Wed), 2002 Discussion of Midterm 2. Review and explanation of the "games" ("lotteries") technique for estimation of utility. The decision version of the infected milk problem.
November 15 (Fri), 2002 Presentation of Lumiere paper (Feng Xu and Suman Pakala), with discussion.
November 18 (Mon), 2002 Hypothesis driven myopic value of information; nonutility value functions: entropy and variance (4.3.2, 4.3.3).
November 20 (Wed), 2002 HW12 assigned: exercises 3.1 and 3.2, due Monday, December 2. A little more on entropy and variance as proxies for utility in VOI computation. Convex value functions. Theorem 1 (p.120) stated, with a discussion of its import. Brief discussion of the following theorem (Theorem 5.5, p.124 of [J96]): The expected benefit of performing test T is zero if and only if the optimal action is unchanged no matter what the outcome of T. No proofs given; proofs may be found in [J96]. Non-myopic data request: example of 4.3.4. Decision trees and their solution (parts of 4.4). Symmetric and non-symmetric decision problems.
November 22 (Fri), 2002 HW13 assigned: exercises 4.7 and 4.8, due Wednesday, December 4. HW12 due date changed to Monday, December 2. Influence diagrams as a representation for symmetric decision problems. Information links and precedence links.
November 25 (Mon), 2002 Influence diagrams; policies; POMDPs. (Chapter 4 completed, except section on Troubleshooting.)
December 2 (Mon), 2002 (First lesson after Thanksgiving break.) Cluster trees for BNs. Absorption; invariance of distributed representation of P(U) under absorption.
December 4 (Wed), 2002 Class canceled due to inclement weather.
December 6 (Fri), 2002 Message passing schemes: Hugin with CollectEvidence and DistributeEvidence, Shenoy-Shafer. Local consistency after message passing. The R.I.P. and global consistency justify the need for junction trees. How to build a junction tree.