CSCE 582 {=STAT 582} (Spring 2014) Lecture Log

January 14 (Tue), 2014 Introduction to the Course: Goals and Topics to Be Covered. Examples of plausible reasoning and causal graphs: icy roads and wet grass. Reasoning in the evidential and causal direction. Intercausal reasoning and explaining away.

January 16 (Thu), 2014 HW1: Do exercise 2.8 [J07], due on Tuesday, 2014-01-21. More examples of plausible reasoning: burglary and earthquake. Definition of d-separation and d-connectedness (def. 2.1[J07]). Examples of d-separation. Definition of Markov blanket (def. 2.2 [J07]). The claim at the end of p.30 [J07] discussed including the observation that a more formal treatment will start with explicit axioms, such as the graphoid axioms, from which the claim of p.30 [J07] (based on d-separation) follows.

January 21 (Tue), 2014 HW2 assigned: exercises 2.4, 2.5, 2.6, 2.9, 2.10 [J07], due 2014-01-28. HW1 will be collected on Tuesday. Uncertain reasoning is non-compositional. The Chernobyl example. D-separation algorithm using moralized ancestral graphs.

January 23 (Thu), 2014 HW1 collected. 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 the slides. Example of Dutch Book (from [AIMA-3]). "Definition" of conditional probability derived in the classical approach, 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). The fundamental rule, Bayes theorem.

January 28 (Tue), 2014 Class canceled due to university closing due to inclement weather.

January 30 (Thu), 2014 HW3 assigned: exercises 1.11 and 1.13 [J07], due on Tuesday, February 2, 2014. HW1 returned. HW2 collected. Potentials. Independence for variables. Conditional independence is symmetric. (Multiplicative) factorizaton implies independence (under a positivity condition). Table operations are pointwise. By convention, the row of conditional probability tables are indexed by the states of the variable on the left-hand side of a conditioning bar. Neapolitan's definition of Bayesian network [Neapolitan, 1990; in ppt Intro slides]. Proof of the Chain Rule for BNs from Neapolitan's definition. The visit to Asia (chest clinic) example.

February 4 (Tue), 2014 HW4 assigned: exercises 1.7 and 1.12 [J07]. HW2 returned and corrected in class. HW3 collected.

February 6 (Thu), 2014 HW4 collected.

February 11 (Tue), 2014 HW5 assigned: exercises 2.12, 2.14, 2.16, and 1.15 [J07]. Icy roads and wet lawn examples in detail using table operations. Section 2.3.3 [J07]: definition of finding; evidence; the probability of evidence.

February 13 (Thu), 2014 Class canceled. The university if closed due to inclement weather.

February 18 (Tue), 2014 HW5 collected. The Athenian Taxi Example. Variable elimination for computing posterior marginal probabilities. The Belief Update, Most Probable Explanation and Maximum A Posteriori Hypothesis problems. Bucket elimination.

February 20 (Thu), 2014 PR1 assigned: Exercises 2.20 and 2.23 [J07], due Thursday, 2014-02-27. HW5 returned and discussed. Review of variable elimination and bucket elimination, with example using the Visit to Asia network. Example of MPE problem instance, also based on the Visit to Asia network.

February 25 (Tue), 2014 Discussion of midterm (closed book, no theorems). Pearl's coins and bells example: non-causally interpretable Bayesian networks. Chapter 3 [J07] started.

February 27 (Thu), 2014 Midterm exam.

March 4 (Tue), 2014 MT returned and discussed. 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. Review of examples from Ch.3 [J07] already presented on 2014-02-25.

March 6 (Thu), 2014 PR2 assigned: exercises 3.5, 3.6, 3.8, 3.9 [J07], due 2014-03-20. Discussion of graduate student presentations. I recommend choosing one of the four applications from Ch.11 of Korb and Nicholson's _Bayesian Artificial Intelligence_, 2nd ed. The chapter is on blackboard. Graduate students will have to also use at least one primary source. Catching the structure (section 3.1 [J07]) completed. Determining the conditional probabilities (or: Where do the numbers come from?): Section 3.2 through 3.2.1 [J07].

March 18 (Tue), 2014 Determining the conditional probabilities (or: Where do the numbers come from?): Section 3.2 completed [J07]. Noisy-Or (section 3.3.2).

March 20 (Thu), 2014 PR2 collected. PR3 assigned: exercise 3.12 [J07], due 2014-03-25 (Tuesday). PR4 assigned: exercise 3.27 [J07], due 2014-03-27 (Thursday); parts (iii) and (iv) for graduate students only.

March 25 (Tue), 2014 PR2 returned and discussed briefly. Updates to PR2 will be accepted for partial credit. PR3 was not collected; due date was changed to March 27 (Thursday). Discussion of some fine points of exercise 3.12, especially parts ii and iii. Mr. Eckstrom explains the biological basis of the model for part iii, which has to do with the fact that males only have one X chromosome, while females have two. Hugin 8.0 has been announced today; email shown; it will have support for dynamic Bayesian networks (DBN). DBNs: 3.3.7 [J07]: time slices, temporal links, repetitive temporal models, hidden Markov models, and Kalman filters. Continuous variables: 3.3.8 [J07]: (conditional) Gaussian distribution; we develop the continuous version of the "Cold or Angina?" example in Hugin. For belief updating in BNs (ch.4 [J07]), I will use the presentation from ch.4 [J95] (from the 1995 version of Finn V. Jensen's book.

March 27 (Thu), 2014 PR3 collected. Sensitivity to findings (crucial findings). Sensitivity to parameters (3.4.4). Object-oriented Bayesian networks (3.3.6). Propagation in Bayesian Networks (Ch. 4[J96], on blackboard.sc.edu), through Theorem 4.3 (invariance under absorption).

April 1 (Tue), 2014 HW6: exercise 4.3 [J96], due on Thursday, 2014-04-03. Propagation in Bayesian Networks (Ch. 4[J96], on blackboard.sc.edu), through Theorem 4.8 (local computation of posterior probability in junction trees).

April 3 (Thu), 2014 HW6 collected. Propagation in Bayesian network: propagation in Bayesian networks (Ch.4[J96]) through section 4.5. Brief discussion of: Finn V. Jensen and Frank Jensen. "Optimal Junction Trees." Proceedings of UAI-94, pp. 360-366 (available on the blackboard site.)

April 8 (Tue), 2014 Propagation in Bayesian network: propagation in Bayesian networks (Ch.4[J96]) completed, including the proofs of Theorems 4.9 and 4.10 from Appendix A (available in blackboard) and stochastic simulation (forward sampling and Gibbs sampling). I noted that the textbook also covers likelihood weichting (section 4.8.2 [J07]) and uses the term "probabilistic logic sampling" in place of forward sampling.

April 10 (Thu), 2014 Topics in ch4 [J07] ("Belief Updating in Bayesian Networks"): Barren nodes (4.5.1), Exact Propagation with Bounded Space: Recursive Conditioning (4.7.1), Loopy Belief Propagation (4.9). Chapter 9 [J07] ("Graphical Languages for Specification of Decision Problems") started: 9.1 ("One-Shot Decision Problems"), 9.2 ("Utilities") through the figure on p.287.

April 15 (Tue), 2014 PR5 assigned: exercises 9.11 and 9.12 [J07]. Chapter 9 [J07] ("Graphical Languages for Specification of Decision Problems"): 9.2 ("Utilities"), 9.3 ("Decision Trees"). Section 9.4 ("Influence Diagrams") started.

April 17 (Thu), 2014 Ch.9 ("Graphical Languages for Specification of Decision Problems") [J07] continued. More examples of decision trees (section 9.3.1). Influence diagrams: section 9.4 (including the Fishing in the North Sea example and information blocking). Asymmetric decison problems, with the Test for Fever and Aspirin example, and how to convert such problems into ones without Test Decisions. Distinction between perfect-recall (or: no-forgetting) Influence Diagrams and LIMIDs. Most people call perfect-recall IDs simply IDs. LIMIDs are the only kind of IDs now supported in Hugin (Normal) IDs were the only kind supported before version 7.0. Example of LIMID: pig breeder network with four stages (Nilsson and Lauritzen, 2000 and 2001).

April 22 (Tue), 2014 Presentations by Ashwin Patthi (on learning parameters for BNs and learning classifiers in Hugin and WEKA), and by Xiao Lin on the PC algorithm.

April 24 (Thu), 2014 Presentations by Chao Chen on Bayesian filtering, Hareesh Lingareddi on computing the MPE by bucket elimination, and Megha Gupta and Rahul Tomar (as a pair) on the application of Bayesian networks in Social Network Analysis. End of course.