Transcript Uncertainty

Decision Making Under
Uncertainty
CSE 495
Resources:
–Russell and Norwick’s book
Some Examples
1. Suppose that you are in a TV show and you have already
earned 1’000.000 so far. Now, the presentator propose you
a gamble: he will flip a coin if the coin comes up heads you
will earn 3’000.000. But if it comes up tails you will loose
the 1’000.000. What do you decide?
2. Considerations for sitting a new airport:
•Cost
•noise pollution
•Safety
If there are two candidate sites, how to decide between them?
First Order Representation
p symptom(p,toothache)  disease(p, cavity)
p disease(p, cavity)  symptom(p,toothache)
For the “dentist in you”, which one is true?
None. A better rule could be something like:
p symptom(p,toothache)  disease(p, cavity) 
disease(p, Gumdisease) …
Problems with First Order
Representation
•Laziness: it is too much work to list antecedents and
consequents
•Theoretical Ignorance: not all known
antecedents/consequents may be known
•Practical ignorance: even if we know all the rules,
uncertainty in establishing antecedents/consequents
may still occur
Related to the knowledge-acquisition bottle neck &
Fuzzy Logic
Handling Uncertain Knowledge
•We have only a degree of belief
•Probability theory can be used to deal with degree of
belief
If the probability of an event is 1 does it mean that
the event will occur?
No. It means that we believe that will always occur
•In our example we may believe that with 0.8
probability the patient has cavities
Uncertainty and Rational Decisions
•In addition to probabilities there might be preferences
Plan 1: Take the train from NYC to NC at 7:00AM
(probability of missing a connection in WAS: 5%,
waiting time in WAS: 4 hours)
Plan 2: Take the train from NYC to NC at 10:00AM
(probability of missing a connection in WAS: 35%,
waiting time in WAS: 1 hour)
Which would you choose?
The point being that decisions are not made based only on the
probability of events
Decision Theory
•Utility theory: represents and reasons with preferences
Decision Theory = probability theory + utility theory
Suppose that taken actions update
probabilities of states/actions.
Which actions should be taken?
?
?
?
1. Calculate probabilities of current state
2. Calculate probabilities of action
3. Select actions with the highest
expected utility
Probability Distribution
•The events E1, E2, …, Ek must meet the following
conditions:
•One always occur
•No two can occur at the same time
•The probabilities p1, …, pn are numbers associated with
these events, such that 0  pi  1 and p1 + … + pn = 1
A probability distribution assigns probabilities to events
such that the two properties above holds
Expected Value
In general, let Q be a quantity that has value v1 with
probability p1, …., vk with probability pk then the
Expected value of Q is:
p1 * v1 + p2 * v2 +…+ pk * vK
Selection of a Good Attribute:
Information Gain Theory
•If the possible answers vi have probabilities p(vi), then the
information content of the actual answer is given by:
I(p(v1), p(v2), …, p(vn)) = p(v1)I(v1) + p(v2)I(v2) +…+ p(vn)I(vn)
= p(v1)log2(1/p(v1)) + p(v2) log2(1/p(v2)) +…+ p(vn) log2(1/p(vn))
•Examples:
I(1/2,1/2) = 1
Information content with the fair coin:
Information content with the totally unfair: I(1,0) = 0
Information content with the very unfair: I(1/100,99/100)
= 0.08
Uniform Distribution
A probability distribution is uniform if there are k events each
of which has probability 1/k
Examples?
Rolling a “fair” dice. The events being that the dice will
comes up on each of the dice’s faces
Probability of Two Events Taken Place
Two events are independent if the occurrence of one
doesn’t affect the occurrence of the other one.
If E1 and E2 are two independent events, then the probability
that E1 and E2 occur is p(E1)*p(E2)
If the probability of having a winning a lottery is .1, then
the probability of winning the lottery two times in a row is
.1*.1 = .01
If E1 and E2 are two independent events, then the probability
that E1 or E2 occur is p(E1) + p(E2) – (p(E1)*p(E2))
Conditional Probability
P(A  B) = P(B)P(A|B) = P(A)P(B|A)
(product rule)
P(A|B) = (P(A)P(B|A))/ P(B)
(Bayes rule)
Example: Suppose that the following is true:
•Meningitis cause stiff neck, 50% of the time = P(S|M)
•Probability of patient having meningitis is 1/50000 = P(M)
•Probability of patient having stiff neck is 1/120 = P(S)
P(M|S) = 0.0002
Axioms of Probability
1. For any event A, 0  P(A)  1 holds
2. If F can never occur then P(F) = 0 and if T always occurs
then P(T) = 1
3. P(E1 E2) = p(E1) + p(E2) – p(E1E2)
Axioms of Probability (2)
•Suppose there is a betting game between 2 persons for money.
•Suppose that person 1 has some degree of belief in an event A.
“I bet $6 that it will occur. My degree of belief is 0.4”
•Suppose that person 2 bets for or against A consistent with the
degree of belief of person 1.
“I bet $4 that it will not occur”
Theorem (Bruno de Finetti, 1931): If Person 1 sets of degrees
violating the axioms of the probability, then there is a betting
strategy for Person 2 that guarantees that Person 1 looses money