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

August 20 (Mon), 2010 HW1 assigned: exercises 1.7, 1.11, 1.12, due date to be determined, but not earlier than Friday, August 27. 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." Examples of plausible reasoning and causal graphs: icy roads.

August 23 (Mon), 2010 More examples of plausible reasoning and causal graphs: wet grass, earthquake. Reasoning in the evidential and causal direction. Intercausal reasoning and explaining away. Serial, diverging, and converging connections. 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.

August 25 (Wed), 2010 HW1 due no earlier than next Monday. Note corrected exercise numbers: 1.7, 1.11, 1.12. Uncertain reasoning is non-compositional. 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. Presentation of the classical approach, including sketch of the proof of the three properties that are the axioms of Kolmogorov. Brief presentation of the frequentist approach. 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 [to be provided] and on the slides. "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).

August, 27 (Fri), 2010 HW1 assigned with changes: exercises 1.7, 1.11, 1.12, 1.13 [J07], due September 1, 2010 (Wednesday). The fundamental rule, Bayes theorem, conditional independence, factorization, variables and their states (values) partition the outcome space, probability of variables, probability tables, marginalization. Potentials. Independence for variables. Conditional independence is symmetric. (Bernardo Quibiana shows the latter in class.)

August, 30 (Mon), 2010 Review of causal networks: the car start example. Neapolitan's definition of Bayesian network [Neapolitan, 1990; in ppt Intro slides]. Comments on the alternative definition of BN used in [J07]. The visit to Asia example.

September 1 (Wed), 2010 HW2 assigned, with due date to be determined: exercises 2.1, 2.4, 2.5, 2.6, 2.7, 2.8, 2.9, 2.10. HW1 collected and correction given in class.

September 3 (Fri), 2010 HW2 is due on Friday, September 10. The Chain rule for Bayesian networks. Chapter 2 completed, except for variable elimination.

September 8 (Wed), 2010 Belief Assessment, Most Probable Explanation (MPE), and Maximum A Posteriori Hypothesis (MAP). Variable elimination (in the bucket elimination format), with the visit to Asia Example.

September 10 (Fri), 2010 Video camera failed (batteries ran out). HW2 collected and corrected. Numbers for the visit to Asia example of bucket elimination.

September 13 (Mon), 2010 HW1 returned. Section 3.1 [J07]: Catching the structure.

September 15 (Wed), 2010 The stratum method for constructing Bayesian networks (from independence information derived from qualitative descriptions), with a detailed example (Alarm, Burglary, Earthquake, MaryCalls, JohnCalls) from [Russell and Norvig 2003 after Pearl] with different orders of variables.

September 17 (Fri), 2010 I forgot the video camera! Sorry! HW3 assigned, due 2010-09-24 (Fri): Install Hugin on your computer. (See blackboard for details.) Do exercises 3.3, 3,5, 3.6, 3.8, 3.9, 3.10, all from [J07] [Due date later changed to 2010-09-29]. Determining the conditional probabilities (or: Where do the numbers come from?): Section 3.2 through 3.2.3 [J07].

September 20 (Mon), 2010 MT1 (Midterm exam) will be on Monday, September 27. Determining the conditional probabilities: Section 3.2 through 3.2.5 [J07].

September 22 (Wed), 2010 HW3 is now due on Wednesday, September 29. More modeling methods: noisy OR, divorcing, undirected relations, with examples.

September 24 (Fri), 2010 Causality and Bayesian networks. Excision semantics. Intervention variables and non-crisp intervention. Examples: Mary, John, Alarm, Earthquake, Burglary; Cold and Hay Fever.

September 27 (Mon), 2010 MT1.

September 29 (Wed), 2010 HW3 is now due Friday, October 1. MT1 returned and corrected. Coins and bells example from MT1 in Spring 2009 discussed in class, using Hugin. See lecture notes entry.

October 1 (Fri), 2010 HW3 collected. HW4 assigned: Exercises 3.11, 3.12, 3.13, 3.14 (use the numbers on the slides for ch.3 [J07], *not* the numbers in [J07]!), and 3.15 [J07], due 2010-10-13. HW5 assigned: Exercises 3.16 (use Hugin for this!), 3.19, 3.20, 3.21, 3.26, 3.27, and 3.28 (note: most of this is a paper-and-pencil exercise) [J07] due 2010-10-20. Graduate student presentations assigned. There will be three presentations by teams of two students each. See presentation page on the course web site for links to the papers and some other details. Each student team must turn in the presentation slides (ppt, preferred, or pdf) and a one-page summary of the paper. HW3 corrected, through exercise 3.9. There will be no classes until Monday, October 11, 2010. Work on homework and presentations!

October 11 (Mon), 2010 Presentation by Simin and Smith, with discussion. On Wednesday, we will have a two-class period lesson; the first hour will consist of two graduate student presentations. The second hour will be related to the AIM workshop on parameter identification in graphical models that I recently attended.

October 13 (Wed), 2010 HW4 due date moved to Monday, October 18. Presentation by Parsons and Tarter, with discussion. Discussion of the HW3 exercises, in detail. Second hour: presentation of the first part of my AIM workshop talk on identifiability in causal Bayesian networks and the do-calculus.

October 18 (Mon), 2010 HW4 collected. HW5 due date changed to Monday, October 25. Presentation (on Vomlel and his students' work on assessing skills in the arithmetic of fractions) by Quibiana and Roy Chowdhury started. Discussion of entropy as a measure of ignorance (a kind of uncertainty).

October 20 (Wed), 2010 Presentation by Quibiana and Roy Chowdhury continued. Long detour on entropy, decision-theoretic troubleshooting, myopic test selection.

October 22 (Fri), 2010 Presentation by Quibiana and Roy Chowdhury completed. Detours on learning BNs with score-based and structure-based approaches.

October 25 (Mon), 2010 Discussion of the complexity of several related problems: PIBNET, PIBNETD, and D-PR. Discussion of exercise 3.27 [J07].

October 27 (Wed), 2010 Discussion of exercises 3.28 (completed) and 3.26 (not completed) [J07].

October 29 (Fri), 2010 Belief Updating in Bayesian Networks (Ch. 4 [J07]) started. Video from Spring 2009 was used.

November 1 (Mon), 2010 Belief updating through Section 4.2 and definition 4.4; video from Spring 2009 was used.

November 3 (Wed), 2010 Belief updating through Theorem 4.3, with examples; video from Spring 2009 was used.

November 5 (Fri), 2010 Jensen and Jensen's UAI 1994 result: a spanning tree of a join graph is a join tree if and only if it is a maximal spanning tree of a join graph.

November 8 (Mon), 2010 Review of how to construct join trees of trinangulated graph. Separators. Junction trees. Messages. Distribute and collect evidence. Statement of the main theorem: Theorem 4.5 part 1 [J07].

November 10 (Wed), 2010 Conclusion of sections on propagation in junction trees: triangulation with some heuristics. Brief discussion of lazy propagation, using definition of marginalization from Madsen, which is a notational variant of Definition 4.1 (Elimination) in [J07].

November 12 (Fri), 2010 Approximate belief updata: stochastic simulation, likelihood weighting, Gibbs sampling (parts of 4.8 [J07]). Some slides from Thomas Nielsen are in blackboard.

November 15 (Mon), 2010 Graphical Languages for Specification of Decision Problems (Ch.9 [J07]): Introduction (test decisions, action decisions, causality), One-Shot Decision Problems, Utililies, including the management of effort example, instrumental rationality, and Allais' paradox.

November 17 (Wed), 2010 Decision Trees (9.3 [J07]).

November 19 (Fri), 2010 Influence diagrams: basics (from 9.4 [J07]), Apple Jack example from Kjaerulff and Madsen, worked out in Hugin. I note that Hugin uses LIMIDs instead of plain IDs.

November 22 (Mon), 2010 Influence diagrams: the pig breeding example by Madsen and Kjaerulff. Solving influence diagrams: description of approach by conversion to symmetric (full, complete) decision trees. Policy; strategy. The relevant past.

November 29 (Mon), 2010 HW6 assigned: Exercises 9.11 (both parts) and 9.12 (part (i) only) [J07]. The oil wildcatter example in detail, represented and solved both as an influence diagram and as a decision tree.

December 1 (Wed), 2010 The used car buyer example in detail, represented as a decision tree. Test decisions in influence diagrams (first part of section 9.5 [J07]). Solutions to influence diagrams (section 10.1 [J07]) started.

December 3 (Fri), 2010 HW6 collected. Solutions to influence diagrams; variable elimination and strong junction trees (ch. 10 [J07] through p.358). Student evaluations.