CS 188: Artificial Intelligence

Bayes’ Nets

Instructors: Dan Klein and Pieter Abbeel --- University of California, Berkeley
[These slides were created by Dan Klein and Pieter Abbeel for CS188 Intro to AI at UC Berkeley. All CS188 materials are available at [Link]
 Probabilistic Models
 Models describe how (a portion of) the world works

 Models are always simplifications

 May not account for every variable
 May not account for all interactions between variables
 “All models are wrong; but some are useful.”
– George E. P. Box

 What do we do with probabilistic models?

 We (or our agents) need to reason about unknown
variables, given evidence
 Example: explanation (diagnostic reasoning)
 Example: prediction (causal reasoning)
 Example: value of information
Independence
 Independence
 Two variables are independent if:

 This says that their joint distribution factors into a product two
simpler distributions
 Another form:

 We write:

 Independence is a simplifying modeling assumption

 Empirical joint distributions: at best “close” to independent
 What could we assume for {Weather, Traffic, Cavity, Toothache}?
 Example: Independence?

T P
hot 0.5
cold 0.5
T W P T W P
hot sun 0.4 hot sun 0.3
hot rain 0.1 hot rain 0.2
cold sun 0.2 cold sun 0.3
cold rain 0.3 cold rain 0.2
W P
sun 0.6
rain 0.4
 Example: Independence
 N fair, independent coin flips:

H 0.5 H 0.5 H 0.5

T 0.5 T 0.5 T 0.5
 Conditional Independence
 P(Toothache, Cavity, Catch)

 If I have a cavity, the probability that the probe catches in it

doesn't depend on whether I have a toothache:
 P(+catch | +toothache, +cavity) = P(+catch | +cavity)

 The same independence holds if I don’t have a cavity:

 P(+catch | +toothache, -cavity) = P(+catch| -cavity)

 Catch is conditionally independent of Toothache given Cavity:

 P(Catch | Toothache, Cavity) = P(Catch | Cavity)

 Equivalent statements:
 P(Toothache | Catch , Cavity) = P(Toothache | Cavity)
 P(Toothache, Catch | Cavity) = P(Toothache | Cavity) P(Catch | Cavity)
 One can be derived from the other easily
 Conditional Independence
 Unconditional (absolute) independence very rare (why?)

 Conditional independence is our most basic and robust form

of knowledge about uncertain environments.

 X is conditionally independent of Y given Z

if and only if:

or, equivalently, if and only if

 Conditional Independence
 What about this domain:
 Traffic
 Umbrella
 Raining
 Conditional Independence
 What about this domain:
 Fire
 Smoke
 Alarm
 Conditional Independence and the Chain Rule
 Chain rule:

 Trivial decomposition:

 With assumption of conditional independence:

 Bayes’nets / graphical models help us express conditional independence assumptions

Bayes’Nets: Big Picture
 Bayes’ Nets: Big Picture
 Two problems with using full joint distribution tables
as our probabilistic models:
 Unless there are only a few variables, the joint is WAY too
big to represent explicitly
 Hard to learn (estimate) anything empirically about more
than a few variables at a time

 Bayes’ nets: a technique for describing complex joint

distributions (models) using simple, local
distributions (conditional probabilities)
 More properly called graphical models
 We describe how variables locally interact
 Local interactions chain together to give global, indirect
interactions
 For about 10 min, we’ll be vague about how these
interactions are specified
Example Bayes’ Net: Car
 Graphical Model Notation

 Nodes: variables (with domains)

 Can be assigned (observed) or unassigned
(unobserved)

 Arcs: interactions
 Similar to CSP constraints
 Indicate “direct influence” between variables
 Formally: encode conditional independence
(more later)

 For now: imagine that arrows mean

direct causation (in general, they don’t!)
 Example: Coin Flips
 N independent coin flips

X1 X2 Xn

 No interactions between variables: absolute independence

 Example: Traffic
 Variables:
 R: It rains
 T: There is traffic

 Model 1: independence  Model 2: rain causes traffic

R R

T T
 Why is an agent using model 2 better?
 Example: Traffic II
 Let’s build a causal graphical model!
 Variables
 T: Traffic
 R: It rains
 L: Low pressure
 D: Roof drips
 B: Ballgame
 C: Cavity
 Example: Alarm Network
 Variables
 B: Burglary
 A: Alarm goes off
 M: Mary calls
 J: John calls
 E: Earthquake!
Bayes’ Net Semantics
 Bayes’ Net Semantics
 A set of nodes, one per variable X

 A directed, acyclic graph A1 An

 A conditional distribution for each node
 A collection of distributions over X, one for each
combination of parents’ values X

 CPT: conditional probability table

 Description of a noisy “causal” process

A Bayes net = Topology (graph) + Local Conditional Probabilities

 Probabilities in BNs
 Bayes’ nets implicitly encode joint distributions
 As a product of local conditional distributions
 To see what probability a BN gives to a full assignment, multiply all the
relevant conditionals together:

 Example:
 Probabilities in BNs
 Why are we guaranteed that setting

results in a proper joint distribution?

 Chain rule (valid for all distributions):

 Assume conditional independences:

 Consequence:

 Not every BN can represent every joint distribution

 The topology enforces certain conditional independencies
 Example: Coin Flips

X1 X2 Xn

h 0.5 h 0.5 h 0.5

t 0.5 t 0.5 t 0.5

Only distributions whose variables are absolutely independent can be

represented by a Bayes’ net with no arcs.
 Example: Traffic

+r 1/4
R -r 3/4

+r +t 3/4

T -t 1/4

-r +t 1/2
-t 1/2
 Example: Alarm Network
B P(B) E P(E)

Burglary Earthqu +e 0.002

+b 0.001 ake
-b 0.999 -e 0.998

Alarm
B E A P(A|B,E)
+b +e +a 0.95
John Mary
+b +e -a 0.05
calls calls
+b -e +a 0.94
A J P(J|A) A M P(M|A) +b -e -a 0.06
+a +j 0.9 +a +m 0.7 -b +e +a 0.29
+a -j 0.1 +a -m 0.3 -b +e -a 0.71
-a +j 0.05 -a +m 0.01 -b -e +a 0.001
-a -j 0.95 -a -m 0.99 -b -e -a 0.999
 Example: Traffic
 Causal direction

+r 1/4
R -r 3/4

+r +t 3/16
+r -t 1/16
+r +t 3/4
-r +t 6/16
T -t 1/4
-r -t 6/16
-r +t 1/2
-t 1/2
 Causality?
 When Bayes’ nets reflect the true causal patterns:
 Often simpler (nodes have fewer parents)
 Often easier to think about
 Often easier to elicit from experts

 BNs need not actually be causal

 Sometimes no causal net exists over the domain
(especially if variables are missing)
 E.g. consider the variables Traffic and Drips
 End up with arrows that reflect correlation, not causation

 What do the arrows really mean?

 Topology may happen to encode causal structure
 Topology really encodes conditional independence
 Bayes’ Nets
 So far: how a Bayes’ net encodes a joint
distribution

 Next: how to answer queries about that

distribution
 Today:
 First assembled BNs using an intuitive notion of
conditional independence as causality
 Then saw that key property is conditional independence
 Main goal: answer queries about conditional
independence and influence

 After that: how to answer numerical queries

(inference)
 Bayes’ Net Representation
 A directed, acyclic graph, one node per random variable
 A conditional probability table (CPT) for each node
 A collection of distributions over X, one for each combination
of parents’ values

 Bayes’ nets implicitly encode joint distributions

 As a product of local conditional distributions
 To see what probability a BN gives to a full assignment,
multiply all the relevant conditionals together:
 Example: Alarm Network
B P(B) E P(E)

+b 0.001 Burglary Earthqk +e 0.002

-b 0.999 -e 0.998

Alarm
B E A P(A|B,E)
+b +e +a 0.95
John Mary
+b +e -a 0.05
calls calls
+b -e +a 0.94
A J P(J|A) A M P(M|A) +b -e -a 0.06
+a +j 0.9 +a +m 0.7 -b +e +a 0.29
+a -j 0.1 +a -m 0.3 -b +e -a 0.71
-a +j 0.05 -a +m 0.01 -b -e +a 0.001
-a -j 0.95 -a -m 0.99 -b -e -a 0.999
[Demo: BN Applet]
 Example: Alarm Network
B P(B) E P(E)
+b 0.001
B E +e 0.002
-b 0.999 -e 0.998

A J P(J|A)
A A M P(M|A)
B E A P(A|B,E)
+a +j 0.9 +a +m 0.7
+b +e +a 0.95
+a -j 0.1 +a -m 0.3
+b +e -a 0.05
-a +j 0.05 J M -a +m 0.01
+b -e +a 0.94
-a -j 0.95 -a -m 0.99
+b -e -a 0.06
-b +e +a 0.29
-b +e -a 0.71
-b -e +a 0.001
-b -e -a 0.999
 Example: Alarm Network
B P(B) E P(E)
+b 0.001
B E +e 0.002
-b 0.999 -e 0.998

A J P(J|A)
A A M P(M|A)
B E A P(A|B,E)
+a +j 0.9 +a +m 0.7
+b +e +a 0.95
+a -j 0.1 +a -m 0.3
+b +e -a 0.05
-a +j 0.05 J M -a +m 0.01
+b -e +a 0.94
-a -j 0.95 -a -m 0.99
+b -e -a 0.06
-b +e +a 0.29
-b +e -a 0.71
-b -e +a 0.001
-b -e -a 0.999
 Bayes’ Nets
 Representation

 Conditional Independences

 Probabilistic Inference
 Enumeration (exact, exponential complexity)

 Variable elimination (exact, worst-case exponential

complexity, often better)
 Inference is NP-complete

 Sampling (approximate)

 Learning Bayes’ Nets from Data

 Inference
 Inference: calculating some  Examples:
useful quantity from a joint  Posterior probability
probability distribution

 Most likely explanation:

 Inference by Enumeration
* Works fine with
 General case:  We want: multiple query
 Evidence variables: variables, too
 Query* variable:
 Hidden variables: All variables

 Step 1: Select the  Step 2: Sum out H to get joint  Step 3: Normalize
entries consistent of Query and evidence
with the evidence
 Inference by Enumeration in Bayes’ Net
 Given unlimited time, inference in BNs is easy
B E
 Reminder of inference by enumeration by example:

J M
 Inference by Enumeration in Bayes’ Net

P(+b|+j,+m)=P(+b,+j,+m)/P(+j,+m)

P(+b,+j,+m)

=P(+b,+e,+a,+j,+m)+P(+b,+e,-a,+j,+m)+P(+b,-e,+a,+j,+m)+P(+b,-e,-a,+j,+m)

=P(+b)P(+e)P(+a|+b,+e)P(+j|+a)P(+m|+a)+ P(+b)P(+e)P(-a|+b,+e)P(+j|-a)P(+m|-a)
+P(+b)P(-e)P(+a|+b,-e)P(+j|+a)P(+m|+a)+ P(+b)P(-e)P(-a|+b,-e)P(+j|-a)P(+m|-a)

39
 Example: Alarm Network
B P(B) E P(E)
B E A P(A|B,E)
+b 0.001
B E +e 0.002 +b +e +a 0.95
-b 0.999 -e 0.998 +b +e -a 0.05
+b -e +a 0.94
A J P(J|A)
A A M P(M|A) +b -e -a 0.06
+a +j 0.9 +a +m 0.7 -b +e +a 0.29
+a -j 0.1 +a -m 0.3 -b +e -a 0.71
-a +j 0.05 J M -a +m 0.01 -b -e +a 0.001
-a -j 0.95 -a -m 0.99 -b -e -a 0.999

=0.001X0.002X0.95X0.9X0.7+0.001X0.002X0.05X0.05X0.01
+0.001X0.998X0.94X0.9X0.7+0.001X0.998X0.06X0.05X0.01
=.000592
 Inference by Enumeration in Bayes’ Net
P(+b|+j,+m)=P(+b,+j,+m)/P(+j,+m)

P(+b,+j,+m)=.0005922

P(+j,+m)=P(+b,+j,+m)+P(-b,+j,+m)

P(-b,+j,+m)
=P(-b,+e,+a,+j,+m)+P(-b,+e,-a,+j,+m)+P(-b,-e,+a,+j,+m)+P(-b,-e,-a,+j,+m)
=.0014917
41
 Example: Alarm Network
B P(B) E P(E)
B E A P(A|B,E)
+b 0.001
B E +e 0.002 +b +e +a 0.95
-b 0.999 -e 0.998 +b +e -a 0.05
+b -e +a 0.94
A J P(J|A)
A A M P(M|A) +b -e -a 0.06
+a +j 0.9 +a +m 0.7 -b +e +a 0.29
+a -j 0.1 +a -m 0.3 -b +e -a 0.71
-a +j 0.05 J M -a +m 0.01 -b -e +a 0.001
-a -j 0.95 -a -m 0.99 -b -e -a 0.999
 Independence in Bayes Nets

Every variable in a bayes net is conditionally

independent of its non-descendents given
its parents.
Determine if the following statements are True/False:
[Link](P8|P3,P7)=Pr(P8|P7)
[Link](P3|P1,P5)=Pr(P3|P1)
[Link](P4,P2|P3)=Pr(P4|P3)Pr(P2|P3)
[Link](P5,P4|P1)=Pr(P5|P1)Pr(P4|P1)

43