Artificial Intelligence: A Modern
Approach
Fourth Edition
Chapter 12
Quantifying Uncertainty
1
Copyright © 2021 Pearson Education, Inc. All Rights Reserved
Outline
Acting Under Uncertainty
Basic Probability Notation
Inference Using Full Joint Distributions
Independence
Bayes' Rule and Its Use
Naive Bayes Models
The Wumpus World Revisited
© 2021 Pearson Education Ltd. Chapter 12 2
Acting Under Uncertainty
• Real world problems contain uncertainties due to:
• partial observability,
• nondeterminism, or
• dynamism, etc.
• Example of dental diagnosis using propositional logic
Toothache ⇒ Cavity.
• However inaccurate, not all patients with toothaches have cavities
Toothache ⇒ Cavity ∨ GumProblem ∨ BacterialInfection...
• To make the rule true, we need to add an almost unlimited list of possible problems.
• The only way to fix the rule is to make it logically exhaustive
© 2021 Pearson Education Ltd. Chapter 12 3
Acting Under Uncertainty
• An agent strives to choose the right thing to do—the rational decision—depends
on both the relative importance of various goals and the likelihood that, and
degree to which, they will be achieved.
• Large domains such as medical diagnosis fail due to three main reasons:
• Laziness: It is too much work to list the complete set of antecedents or
consequents needed to ensure an exceptionless rule
• Theoretical ignorance: Medical science has no complete theory for the
domain
• Practical ignorance: Even if we know all the rules, we might be uncertain
about a particular patient because not all the necessary tests have been (or
can be) run.
• An agent only has a degree of belief in the relevant sentences.
© 2021 Pearson Education Ltd. Chapter 12 4
Acting Under Uncertainty
• Probability theory
• tool to deal with degrees of belief of relevant sentences
• summarizes the uncertainty that comes from our laziness and ignorance
• Uncertainty and rational decisions
• An requires preference among different possible outcomes of various
plans
• Utility Theory: the quality of the outcome being useful
• Every state has a degree of usefulness/utility
• Higher utility is preferred
• Decision Theory: Preferences (Utility Theory) combined with probabilities
• Decision theory = probability theory + utility theory.
• An agent is rational IFF it chooses the action that yields the highest
expected utility, averaged over all the possible outcomes of the
action.
• principle of maximum expected utility (MEU).
© 2021 Pearson Education Ltd. Chapter 12 5
Acting Under Uncertainty
• Function of a decision-theoretic agent that selects rational actions.
function DT-AGENT( percept) returns an action
persistent: belief state, probabilistic beliefs about the current state of the world
action, the agent’s action
update belief state based on action and percept
calculate outcome probabilities for actions,
given action descriptions and current belief state
select action with highest expected utility
given probabilities of outcomes and utility information
return action
© 2021 Pearson Education Ltd. Chapter 12 6
Basic Probability Notation
• For agent to represent and use probabilistic information, we need a formal language.
• Sample Space: the set of all possible worlds
• The possible worlds are mutually exclusive and exhaustive
• A fully specified probability model associates a numerical probability P(ω) with each
possible world.
• Basic axioms of probability theory: Every possible world has a probability between 0
and 1 and that the total probability of the set of possible worlds is 1:
0 ≤ P(ω) ≤ 1 for every ω and ω∈Ω
• Unconditional or Prior probability: degrees of belief in propositions in the absence of
any other information
© 2021 Pearson Education Ltd. Chapter 12 7
Basic Probability Notation
• Conditional or Posterior probability: given evidence that has happened, degree
of belief of new event
• Make use of unconditional probabilities
• Probability of a given b:
P(a|b) = P(a∧b)
P(b)
• Can also written as:
P(a∧b) = P(a|b)P(b) [product rule]
• Example of rolling fair dice, rolling doubles when the first dice is 5
P(doubles|Die1 = 5) = P(doubles∧Die1 = 5) .
P(Die1 = 5)
© 2021 Pearson Education Ltd. Chapter 12 8
Basic Probability Notation
• Factored Representation: possible world represented by a set of variable/value pairs.
• Variables in probability theory are called random variables, and their names begin
with an uppercase letter. (Total and Die1)
• Sometimes we will want to talk about the probabilities of all the possible values of a
random variable. We could write:
P(Weather = sun) = 0.6
P(Weather = rain) = 0.1
P(Weather = cloud) = 0.29
P(Weather = snow) = 0.01
• Abbreviation of this will be:
P(Weather) = (0.6, 0.1, 0.29, 0.01)
• P statement defines a probability distribution for the random variable Weather
© 2021 Pearson Education Ltd. Chapter 12 9
Joint Probability Distribution
• Distributions on multiple variables. e.g. P(Weather, Cavity) denotes the probabilities of
all combinations of the values of Weather and Cavity.
• This is a 4×2 table of probabilities called the joint probability distribution of Weather
and Cavity.
• The product rules for all possible values of Weather and Cavity can be written as a
single equation:
P(Weather, Cavity) = P(Weather | Cavity)P(Cavity)
instead of as these 4×2=8 equations:
P(W = sunny ∧ C =true) = P(W = sunny | C = true) P(C =true)
P(W = rain ∧ C =true) = P(W = rain | C = true) P(C =true)
P(W = cloudy ∧ C =true) = P(W = cloudy| C = true) P(C =true)
P(W = snow ∧ C =true) = P(W = snow | C = true) P(C =true)
P(W = sunny ∧ C =false) = P(W = sunny | C = false) P(C =false)
P(W = rain ∧ C =false) = P(W = rain | C = false) P(C =false)
P(W = cloudy ∧ C =false) = P(W = cloudy| C = false) P(C =false)
P(W = snow ∧ C =false) = P(W = snow | C = false) P(C =false)
© 2021 Pearson Education Ltd. Chapter 12 10
Inference Using Full Joint Distributions
Start with the joint distribution: the full joint distribution is a 2x2x2 table
toothache ¬toothache
catch ¬catch catch ¬catch
cavity .108 .012 .072 .008
¬cavity .016 .064 .144 .576
For any proposition φ, sum the atomic events where it is true:
P (φ) = Σ ω:ω|= φP (ω)
© 2021 Pearson Education Ltd. Chapter 11
13
Inference Using Full Joint Distributions
Start with the joint distribution:
toothache ¬toothache
catch ¬catch catch ¬catch
cavity .108 .012 .072 .008
¬cavity .016 .064 .144 .576
For any proposition φ, sum the atomic events where it is true:
P (φ) = Σ ω:ω|= φP (ω)
P (toothache) = 0.108 + 0.012 + 0.016 + 0.064 = 0.2
© 2021 Pearson Education Ltd. Chapter 12
13
Inference Using Full Joint Distributions
Start with the joint distribution:
toothache ¬toothache
catch ¬catch catch ¬catch
cavity .108 .012 .072 .008
¬cavity .016 .064 .144 .576
For any proposition φ, sum the atomic events where it is true:
P (φ) = Σ ω:ω|= φP (ω)
P (cavity∨toothache) = 0.108+0.012+0.072+0.008+0.016+0.064 = 0.28
© 2021 Pearson Education Ltd. Chapter 13
13
Inference Using Full Joint Distributions
Start with the joint distribution:
toothache ¬toothache
catch ¬catch catch ¬catch
cavity .108 .012 .072 .008
¬cavity .016 .064 .144 .576
Can also compute conditional probabilities:
P (¬cavity ∧ toothache)
P ( ¬cavity|toothache) =
P (toothache)
0.016 + 0.064
= = 0.4
0.108 + 0.012 + 0.016 + 0.064
© 2021 Pearson Education Ltd. Chapter 14
13
Inference Using Full Joint Distributions
Start with the joint distribution:
toothache ¬toothache
catch ¬catch catch ¬catch
cavity .108 .012 .072 .008
¬cavity .016 .064 .144 .576
Can also compute conditional probabilities:
P (cavity ∧ toothache)
P (cavity|toothache) =
P (toothache)
0.108 + 0.012
= = 0.6
0.108 + 0.012 + 0.016 + 0.064
© 2021 Pearson Education Ltd. Chapter 15
13
Normalization
toothache ¬toothache
catch ¬catch catch ¬catch
cavity .108 .012 .072 .008
¬cavity .016 .064 .144 .576
Denominator can be viewed as a normalization constant α
P(Cavity|toothache) = α P(Cavity, toothache)
= α [P(Cavity, toothache, catch) + P(Cavity, toothache, ¬catch)]
= α [(0.108, 0.016) + (0.012, 0.064)]
= α (0.12, 0.08) = (0.6, 0.4)
• General idea: compute distribution on query variable by fixing evidence
variables and summing over hidden variables
© 2021 Pearson Education Ltd. Chapter 16
13
Inference Using Full Joint Distributions
Let X be all the variables. Typically, we want
the posterior joint distribution of the query variables Y
given specific values e for the evidence variables E
Let the hidden variables be H = X − Y − E
Then, the required summation of joint entries is done by summing out the
hidden variables:
P (Y |E = e) = αP (Y , E = e) = αΣ hP (Y , E = e, H = h)
The terms in the summation are joint entries because Y, E, and H together
exhaust the set of random variables
Obvious problems:
1) Worst-case time complexity O(dn) where d is the largest arity
2) Space complexity O(dn) to store the joint distribution
3) How to find the numbers for O(dn) entries?
© 2021 Pearson Education Ltd. Chapter 17
13
Independence
• Two examples of factoring a large joint distribution into smaller distributions, using
absolute independence.
(a) Weather and Dental problems are independent.
(b) Coin flips are independent.
• P(a|b) = P(a) or P(b|a) = P(b) or P(a∧b) = P(a)P(b)
• One’s dental problems influence the weather thus, according to the product rule:
• P(toothache, catch, cavity, cloud) = P(cloud |toothache, catch cavity) P(toothache,
catch, cavity)
• P(cloud |toothache, catch, cavity) = P(cloud)
• P(toothache, catch, cavity, cloud) = P(cloud)P(toothache, catch, cavity)
© 2021 Pearson Education Ltd. Chapter 12 18
Bayes' Rule and Its Use
• Bayes’ rule is derived from the product rule
• P(a∧b) = P(a|b)P(b) and P(a∧b) = P(b|a)P(a) .
• Equating the two right-hand sides and dividing by P(a), we get
P(b|a) =P(a|b)P(b) .
P(a)
• Often, we perceive as evidence the effect of some unknown cause and we would like
to determine that cause. In that case, Bayes’ rule becomes
P(cause|effect) =P(effect |cause)P(cause)
P(effect)
• The conditional probability P(effect|cause) quantifies the relationship in the causal
direction, whereas P(cause|effect) describes the diagnostic direction.
© 2021 Pearson Education Ltd. Chapter 12 19
Bayes' Rule and Its Use: Example
• A doctor knows that the disease meningitis causes a patient to have a stiff neck, say,
70% of the time. The doctor also knows some unconditional facts: the prior
probability that any patient has meningitis is 1/50,000, and the prior probability that
any patient has a stiff neck is 1%. Letting s be the proposition that the patient has a
stiff neck and m be the proposition that the patient has meningitis, we have
P(s|m) = 0.7
cause: meningitis: m
P(m) = 1/50000
effect: stiff neck: s
P(s) = 0.01
P(m|s) = P(s|m)P(m) = 0.7 × 1/50000 = 0.0014 = 0.14%
P(s) 0.01
• We expect only 0.14% of patients have meningitis due to stiff neck. Notice that even
though a stiff neck is quite strongly indicated by meningitis (with probability 0.7), the
probability of meningitis in patients due to stiff necks remains small. This is because
the prior probability of stiff necks (from any cause) is much higher than the prior
probability for meningitis.
© 2021 Pearson Education Ltd. Chapter 12 20
Bayes’ Rule and conditional independence
P (Cavity | toothache ∧ catch)
= α P(toothache ∧ catch | Cavity)P(Cavity) using Bayes’ rule
= α P(toothache|Cavity)P(catch|Cavity)P(Cavity) using Conditional independence
This is an example of a naive Bayes model:
P(Cause, Effect 1 , . . . , Effect n ) = P(Cause)ΠiP(Effecti|Cause)
Cavity Cause
Toothache Catch Effect1 Effectn
Total number of parameters is linear in n
© 2021 Pearson Education Ltd. Chapter 21
13
Naïve Bayes Models
• The full joint distribution can be written as
P(Cause, Effect1 , . . . , Effectn) = P(Cause) ∏! P(Effecti |Cause)
• Such a probability distribution is called a Naive Bayes model—“naive”
because it is often used (as a simplifying assumption) in cases where the
“effect” variables are not strictly independent given the cause variable.
• Call the observed effects E=e, while the remaining effect variables Y are
unobserved
© 2021 Pearson Education Ltd. Chapter 12 22
Summary
• Probabilities express the agent’s inability to reach a definite decision regarding
the truth of a sentence.
• Decision theory combines the agent’s beliefs and desires, defining the best
action as the one that maximizes expected utility.
• Basic probability statements include prior or unconditional probabilities and
posterior or conditional probabilities over simple and complex propositions.
• The axioms of probability constrain the probabilities of logically related
propositions.
• The full joint probability distribution specifies the probability of each
complete assignment of values to random variables
• Absolute independence between subsets of random variables allows the full
joint distribution to be factored into smaller joint distributions, greatly
reducing its complexity.
• Bayes’ rule allows unknown probabilities to be computed from known
conditional probabilities, usually in the causal direction.
• Conditional independence brought about by direct causal relationships in the
domain allows the full joint distribution to be factored into smaller, conditional
distributions.
© 2021 Pearson Education Ltd. Chapter 12 29