Chapter 9
Representing Uncertainty

Predicate logic:

So far we have used complete, consistent, and unchanging (monotonic) models of the world.

Reasoning involves manipulating a set of beliefs a belief system often incomplete and/or inconsistent

...

* Godel's Incompleteness Theorem:

All consistent axiomatic formulations of number theory include undecidable propositions

Logics:

• nonmonotonic - allows deletion of statements
• probabilistic reasoning - likelihoods
• fuzzy logic - Zadeh - continuity (time and space)

Most dogs have tails

Most people like flowers

Probability Theory

When to use probabilistic reasoning:

• the relevant world is random
• the relevant world is not random given enough data - but one does not have access to all the data (e.g. diagnosis/therapy)

• the world 'appears' to be random only because we have not described it at the right level

pattern recognition

• a random collection of dots vs
• features

i.e., if we have 'exact' knowledge, use it

Bayes

Bayesian statistics: A statistical theory of evidence

event A :    P(A)

event B :     P(B)

if A and B are independent P(A and B)

P(A and B) = P(A) * P(B)

Rating moves in a game (using probabilities)

	Score  = Sum  P(i)  * rating(i)

                i= 1 to # of possible outcomes

Bayes Theorem: (used often for diagnosis)

P(Hi | E) = probability that hypothesis Hi is true given evidence E

P(E | Hi) = probability that one will observe E given Hi

P(Hi) = a priori probability

( in the absence of evidence - "priors")

if n = number of possibilities

P(Hi|E) = P(E|Hi) * P(Hi) /  Sum P(E|Hn) * P(Hn)
                            n=1

(notice complete set of hypothesis needed)

(it is often difficult to collect all the a priori conditional and joint probabilities required... also to maintain and modify the DB (read page 168-169))

in a complex world, n may be very large and as new evidence (E) is given, the prior body of evidence (e) changes.

P(H|E, e) = P(H|E) * P(e|E,H) / P(e|E)

let us look at an example

Dealing with a Deterministic World and a lack of information

• a priori probabilities ... available?
• normative ("true") vs. descriptive (what use)

(e.g. rule-based systems - use first rule that matches)

thus the ordering of rules provides some degree of likelihood of use

(e.g. static evaluation function)

rather than one global combination, divide the process of making decisions into smaller steps - at each of which we combine a few pieces of evidence

intermediate conclusions used to form later conclusions

(Samuels ... MDX ... -> objects)

Structured Matching

(frame of discernment) (e.g., Jackson: 402, 411)

Probabilistic Rule-Based Systems

certainty factors ...Mycin [-1,1] (page 170-175)

uses an approximation of Dempster-Shafer ... belief functions and plausibility: Chapter 21, page 402 - 406

Certainty factors are composite numbers, used to:

* guide the program in its reasoning

* cause the current goal to be deemed unpromising and pruned from the search space (between -.2, +.2)

* rank hypotheses after all the evidence has been considered

Vagueness and possibility

Fuzzy Logic

Page 175-178 overheads

Questions?

• How much is problem solving guided by probabilities and how much is driven by organization?
• How should probabilities be interpreted?
• How can they be combined with each other?
• How can separate events that are not independent of each other be handled properly so that essentially the same evidence will not count more than once?
Advice:
• avoid statistical representations if not necessary or important
• perform manipulations in small increments
• output never more accurate than input
Tversky & Kahneman paper