CSE 473 Autumn 1998, Copyright, S. Tanimoto, Univ. of Washington 
Introduction to Artificial Intelligence (Nov 18, 1998)

"Computing with Odds and Certainty Factors"

Motivation: General Means are Needed for Propagating Certainty Information While Reasoning

Much reasoning is done with "chaining";  It should be possible to chain rule applications and maintain appropriate certainty values at the same time.
 


 

The PROSPECTOR System

The PROSPECTOR expert system was developed at SRI during the late 1970s.  It was a rule-based system that incorporated knowledge about minerals exploration.  The inference engine in PROSPECTOR employed a novel means for handling uncertain information.  The technique was based on Bayes' rule, but extended it to permit uncertainty in the evidence as well as in the rules.  PROSPECTOR also provided a useful means for representing sufficiency and necessity relationships between logical variables in the representation of a geological situation.
 


.

Taking Uncertain Evidence Into Account

Bayes' rule gives us an explicit formula for computing P(H | E) where E is known to be true with probability 1.0.  We can also apply the method to get P(H | ~E) which is in the situation where E is known to be false with probability 1.0.

We often need, however, a means to compute P(H | E) where E is given with a certain probability that is less than 1 but more than 0.
 
 


.
Probability Updating Functions for Relationships of Sufficiency, Necessity, etc.

A probabilistic version of a rule P -> Q can be thought of as a function.  The function maps a probability of P into a probability of Q.  Let us use instead of P and Q the symbols E and H for evidence and hypothesis.  Then the modus ponens expression  E  and E -> H implies H becomes in the probabilistic realm,
P(E | E') and f_{EH}:[0, 1] -> [0, 1] implies P(H | E')

Here P(E | E') represents the current probability of the evidence.
P(H | E') represents the current probability of the hypothesis, taking into account the uncertain evidence.

f_{EH} is a function relating E and H in terms of their a posteriori probabilities.
Given a value of P(E | E'),  f_{EH} returns a corresponding value of P(H | E').

If f_{EH} is the identity function, then we can say that E is necessary and sufficient for H.
However, many other shapes are possible for f_{EH}.

(see the text for examples of sufficiency-only and necessity-only updating functions).
 
 

Fuzzy Logic

Bayes' rule and its generalization with the PROSPECTOR mechanisms give us a good way to handle logical combinations analogous to modus ponens.

However, we also need ways to propagate probability or certainty values through other logical expressions such as (A ^ B),  (A V B), etc.

One approach is used when items being combined are not assumed to be independent:
P(A ^ B)  = min [ P(A), P(B) ]
P(A V B) = max[ P(A), P(B) ]

P(~A) = 1 - P(A)

Another approach is used when items being combined can be considered independent.

P(A ^ B) =  P(A) P(B)

P(A V B) = 1 - P(~A ^ ~B)
 =  1 - [ (1 - P(A)) (1 - P(B)) ]
 = P(A) + P(B) - P(A) P(B)
 


 

Last modified: November 18, 1998

Steve Tanimoto

tanimoto@cs.washington.edu