Probabilistic Inference
AIMA 12.5; AIMA 12.7
CMPSC 442
Week 7, Meeting 20, Three Segments
Outline
● Discrete Random Variables
● Bayes’ Rule and its Uses
● Probabilistic Inference in Wumpus World
2Outline, Wk 7, Mtg 20
Probabilistic Inference
AIMA 12.5; AIMA 12.7
CMPSC 442
Week 7, Meeting 20, Segment 1 of 3: Discrete versus
Continuous Random Variables
Example of a Discrete Random Variable
● Sample space of 5 coin flips (|Ω| = 2n = 32)
○ Ω = {HHHHH, HHHHT, . . ., TTTTT}
○ X(ω) = number of heads in a given flip
○ Y(ω) = Boolean for whether H appears in ω
● Random variables have probability distributions
○ P(X=0) = 1/32, P(X=1) = 5/32, P(X=2) = 10/32, . . .
○ P(Y=0) = 1/32, P(Y=1) = 31/32, . . .
4Discrete Random Variables
Definition of Random Variable
● In the probability space (Ω, Ρ):
○ Ω is a sample space (set of all outcomes)
○ Ρ is the probability measure
● Random variables are functions
● Given some probability space (Ω, Ρ), a random variable X: Ω →R is a function
defined from the probability space to the real line
● In other words, Ρ attaches probabilities to events, which are subsets of Ω
5
Probability Space
Discrete Random Variables
Definition of Random Variable
● Random variables take on values in an
experiment, e.g., a set of measurements
● Formally, probability distribution of a
random variable X is such that
6
Probability Space
Discrete Random Variables
PMF, PDF, CDF
● Probability Mass Function (PMF): for a discrete random variable, the
probability of each value
● Probability Density Function (PDF): for a continuous random variable,
the probability for the value to be within some range
● Cumulative Distribution Function (CDF): for a continuous random
variable, the probability of having a value ≤ n
7Discrete Random Variables
Example PMF
● Experiment: roll 2 dice
○ Ω = {(1,1), (1,2), … , (6,6)}
○ X = their sum
○ X(ω)=X((d1, d2 ))=d1+d2
8Discrete Random Variables
Binomial Distribution: x Successes in y Trials
● Experiment: n repeated trials where each trial has one of two
outcomes, success or failure (Bernouilli trials)
● P (probability of success) is the same on every trial
● Trials are independent
● x = number of successful trials out of n
● Binomial Probability Mass Function
9Discrete Random Variables
Probabilistic Inference
AIMA 12.5; AIMA 12.7
CMPSC 442
Week 7, Meeting 20, Segment 2 of 3: Bayes’ Rule
Deriving Bayes’ Rule
11Bayes’ Rule
Generalizing Bayes’ Rule
● Conditionalize Bayes’ rule on background evidence e
● The evidence e can stand for the set of other variables in a joint
probability distribution besides X and Y
12
Reasoning about Cause and Effect
● Bayes’ Rule provides a way to reason from causes to effects
● Note that normalization of probabilities to sum to one means only two
kinds of knowledge are needed
○ Prior probability of the cause P(c)
○ Likelihood of the effect given the cause P(e|c)
13
Causal Reasoning in Medicine
● Probability of a stiff neck (s) conditioned on meningitis (m) is high
● Prior probability of meningitis is very low
● Prior probability of a stiff neck >> than prior probability of meningitis
● Probability of patients with stiff necks having meningitis is very low
14
Combining Evidence (Mtg 19, slide 28)
● Bayes’ rule can be used to condition on multiple pieces of evidence
from a joint probability distribution
○ P(Cavity|toothache ∧ catch) = α〈0.108, 0.016〉 ≈ 〈0.871, 0.129〉
● Does not scale well: for n variables that can be true or false, O(2n)
● Conditional independence can help, e.g., catch is irrelevant
15
● Assume Toothache,Catch are conditionally independent, given Cavity
● Use conditional independence to compute the probability of Cavity
Example of Conditional Independence
16
Reduction in Complexity
● Given n random variables that are all conditionally independent on a
single causal variable, probabilistic inference goes from O(2n) to O(n)
● Basis for naïve bayes
● Allows probabilistic inference to scale to many variables
● Conditional independence is very common, in contrast to full
independence, which is not
17
Probabilistic Inference
AIMA 12.5; AIMA 12.7
CMPSC 442
Week 7, Meeting 20, Segment 3 of 3: Probabilistic Inference
in Wumpus World
Probabilistic Agent in Wumpus World
● Facts
○ ¬B
1,1
; B
1,2
; B
2,1
;
¬P
1,1
; ¬P
1,2
; ¬P
2,1
○ P
1,3
⋁ P
2,2
⋁ P
3,1
● Are any non-visited cells safer than others?
○ P
1,3
, P
3,1
safer than P
2,2
19
● Non-probabilistic agent has no way to believe P
2,2
more strongly
● Probabilistic agent can conclude that (P(P
1,3
) < P(P 2.2 )) ∧ (P(P 1,3 ) = P(P 3.1 )) Probabilistic Wumpus World Probabilistic KB ● Observations: ¬B 1,1 , B 2,1 , B 1,2 ● One boolean variable for presence of pit in each square: P 1,1 , P 1,2 , . . . P 2,1 , . . . P 4,4 ● ∀x pit(x) ∧ x ≠ [1,1] ⇒ P(pit(x))= 0.2 20Probabilistic Wumpus WorldProbabilistic Wumpus World What We Know ● Breezes are conditioned on pits. Product rule gives: ● Probability of a boolean event = P(true) x P(false) (Bernouilli trial) ● Probability of n pits (Binomial Distribution; slide 9): 21Probabilistic Wumpus World Query Conditioned on Evidence and Uknown ● Query: (slide 30, Mtg 19) ● Let P 1,3 be the query (X) and let e= b, known where b= ¬B 1,1 ∧ B 2,1 ∧ B 1,2 and known = ¬P 1,1 ∧ ¬P 1,2 ∧ ¬P 2,1 , and let y = unknown ● Summing over all combinations of P i,j and ¬P i,j for 12 unknown squares (16 - 3 known - 1 query) is 212 ● But, only the adjacent unknown squares matter 22Probabilistic Wumpus World Partition the Unknown into the Frontier and Other ● Unknown = Frontier ∪ Other ● Observed breezes are conditionally independent of Other, given Query, Known, and Frontier 23Probabilistic Wumpus World ● Inference ○ Divide up the evidence, then apply conditional independence Inference Steps 24Probabilistic Wumpus World More Inference Steps 25Probabilistic Wumpus World Motivation for Final Step ● Reduced summation over 212 combinations of unknown to summation of frontier over four terms: P 1,3 , and the three terms in known ● Reliance on independence and conditional independence reduces the number of relevant cases to consider, relative to the full joint probability distribution 26Probabilistic Wumpus World Logically Possible Combinations ● Two possibilities for P 1,3 ○ P(P 1,3 ) = 0.2 ○ P(¬P 1,3 ) = 0.8 ● Assuming: P 1,3 ∧ ¬B 1,1 ∧ B 1,2 ∧B 2,1 ○ 3 possibilities: (P 2,2 ∧ P 3,1 ) ∨ (¬P 2,2 ∧ P 3,1 ) ∨ (P 2,2 ∧ ¬P 3,1 ) ● Assuming: ¬ P 1,3 ∧ ¬B 1,1 ∧ B 1,2 ∧B 2,1 ○ 2 possibilities (P 2,2 ∧ P 3,1 ) ∨ (P 2,2 ∧ ¬P 3,1 ) 27Probabilistic Wumpus World Plugging in the Values ● P(P 1,3 ) ≈ 0.31, and by symmetry, P(P 3,1 ) ≈ 0.31 ● By calculation using the same approach, P(P 2,2 ) ≈ 0.86 ● Rational agent should move to P 1,3 or P 3,1 28Probabilistic Wumpus World Summary ● 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. ● A wumpus-world agent can calculate probabilities for unobserved aspects of the world, thereby improving on the decisions of a purely logical agent. Conditional independence makes these calculations tractable. ● 29Summary, Wk 7, Mtg 20