Probabilisitc Reasoning Systems, Chapter 15: Artificial Intelligence: A Modern Approach.

Author of the summary: Yaxin Liu, 1999, yxliu@cc.gatech.edu

Cite this paper for:

• Bayes network

SUMMARY:

Representing knowledge in an uncertain domain, Bayes nets

• Random variables are nodes
• Directed links between pair of nodes: parent directly influence child
• Each node has a CPT (conditional probability table), with all parents as given

The semantics of belief networks

• Representing the joint probability distribution

P(x_1, ... x_n) = \prod_{i=1}^{n} P(x_i|parent(x_i))
• Ordering matters a lot
• Better cause -> effect
• Representation of conditional probability tables
• Canonical distributions (some parameters suffice)
• Deterministic nodes

Conditional independence relations in belief networks

• Direction-dependent seperation (d-seperation)
• If E d-seperates X and Y then X and Y are c.i. given E
• E d-seperates X and Y if any undirected path between X and Y is blocked given E: if exists Z on the path, one of the following holds
•  Z in E, --> Z -->
•  Z in E, <-- Z -->
•  Neither Z in E, nor descendent of Z in E, --> Z <--

Inference in belief networks

• Belief update: P(Query|Evidence)

The nature of probabilistic inferences

• Diagnostic: effects to causes
• Causal: causes to effects
• Intercausal (explain away): among causes of a common effect
• Mixed of the above

An algorithm for answering queries

• For singly-connected network or polytrees
• Use of c.i. and Bayes' rule
• Splitting evidence according to whether it is an ancenster or a descendant of the currently focused node, and do it recursively

Inferences in multiply connected belief networks

• NP-hard
• Clustering methods
• Combine nodes into meganodes, calculate joint-CPT, use polytree algorithm
• Tricky in choosing what to combine
• Still exponential in general
• Cutset conditioning methods
• Split nodes as if they are known, evaluate multiple times and combine the result (hypothetical reasoning)
• Bounded cutset conditioning: choose the most likely polytree first, until an error bound is reached
• Stochastic simulation methods (Monte Carlo)
• Sampling (naive)
• Likelihood weighting: use of CPT

Case study: the Pathfinder system

• Lymph-node diseases: competing experts

Other approaches to uncertain reasoning

• Default reasoning: default logic (Reiter), nonmonotonic logic (McDermott, Doyle), circumscription (McCarthy)
• Rule-based methods for uncertain reasoning
• Locality: if A => B, then only they two matter
• Detachment: Once an inference is found for B, how it is derived doesn't matter
• Truth-functionality: truth of complex sentences is a function of its components
• Probability doesn't have these, but they are not good at all
• Certainty factors in MYCIN
• Representing ignorance: Dempster-Shafer thoery
• Also belief theory, maintain an interval for event
• High complexity and lack of intuition in most cases
• Representing vagueness: fuzzy sets and fuzzy logic
• Fuzzy set theory and fuzzy logic are different, although related closely

Summary author's notes:

• none