[
CogSci Summaries home  UP

email
]
http://www.jimdavies.org/summaries/
Probabilisitc Reasoning Systems, Chapter 15: Artificial Intelligence:
A Modern Approach.
@InBook{,
author = {Stuart Russell and Peter Norvig},
title = {Artificial Intelligence:
A Modern Approach},
}
Author of the summary: Yaxin Liu, 1999, yxliu@cc.gatech.edu
Cite this paper for:
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_iparent(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

Directiondependent seperation (dseperation)

If E dseperates X and Y then X and
Y are c.i. given E

E dseperates 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(QueryEvidence)
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 singlyconnected 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

NPhard

Clustering methods

Combine nodes into meganodes, calculate jointCPT, 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

Lymphnode diseases: competing experts
Other approaches to uncertain reasoning

Default reasoning: default logic (Reiter), nonmonotonic logic (McDermott,
Doyle), circumscription (McCarthy)

Rulebased 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

Truthfunctionality: 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: DempsterShafer 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:
Back to the Cognitive Science Summaries homepage
Cognitive Science Summaries Webmaster:
JimDavies (jim@jimdavies.org)
Last modified: Thu Apr 15 11:07:19 EDT 1999