**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.