CSE 471/598 Intro to AI
(Kambhampati)
Homework 4 Solutions (Fall 2007
Question 1 [Short answer questions:
- [3pt] In
class, we said that bayesian inference can be
seen as a general case of the propositional inference. This means that
propositional inference should be subsumed by bayesian
inference. Suppose we know that A => B, and
that B is not true. We know from the modus tollens
inference that A is not true. Show that this also follows from bayesian inference. (Hint: We can model the
propositional implication A =>B as P(B|A) = 1)
Modus tollens
shows that A=>B and ~B entails ~A
A=>B is P(B|A) = 1 ~B is
P(B) = 0
We want to compute P(A/~B). Using bayes rule
It is P(~B/A) * P(A)/P(~B)
Since P(B/A) = 1 P(~B/A) = 1-1=0
So the whole expression becomes 0. Thus P(A|~B)
= 0 or P(~A|~B) = 1
- [4] Given n boolean
random variables, we know that explicitly specifying their joint
probability distribution takes (2n - 1) probabilities. By
exhibiting their inter-relationships in the form of a bayesian
network, we can often get by with specification of fewer (conditional
probability) numbers. What is the MAXIMUM number of probabilities that
might bSe needed in an n-variable bayes net? How will the net look like in that case?
What is the MINIMUM number of probabilities that might be needed in an
n-variable bayes net? What will the structure of
network look like in that case? (*Note:
The homework that I gave had a typo: instead of 2n-1, it says 2n-1
)
The basic idea is that if you are constructing the bayes network by introducing the nodes one by one (as
described in the class and the textbook), in the worst case the jth node will have incoming arcs from nodes 1 … j-1—giving
rise to a complete directed acyclic graph. In the best case the jth node will not have any incoming arcs—giving rise to a
disconnected graph of n components and n vertices.
Question V 23pt] We
have decided to use the bayes-network technology to
model the
Here are a bunch of probabilities I got from the
Part A:[5pt] We want to
represent all his knowledge conveniently as a nice little bayes
network. Show the configuration of the network along with the requisite
conditional probabilities.
IP=Inferior plutonium. LH=Low quality heavy
water. CM=Core meltdown. GD=Glow in the dark employees. SL= Slurpee
liquefaction.
Part B.[4pt] Given your
network above, which of the following (conditional) independences hold? Briefly
justify your answer in each case:
Given no
evidence at all, they are independent of each other.
Using
D-SEP, we can see that once SL is given,
IP and LH are not independent (the "common-effect" case; since neither CM nor any of its
descendants can be in the evidence for IP and LH to be independent)
Using D-Sep again, LH is indepedent of SL given
CM (since the only path from LH to SL goes through CM, and
it is an inter-causal path, and it gets blocked once CM is
known).
Another way of seeing this is that CM is the markov blanket of SL, and
so given CM, SL is independent of everything else.
Part C. [3pt] Consider the following
probabilities: p1: Probability that low-quality heavy water is present, p2:
probability that low-quality heavy water is present, given that core-meltdown
has occurred, p3: probability that low-quality heavy water is present given
that core-meltdown occurred and we know that inferior-quality plutonium is
present. Given the network above, what would be the relative ordering of these probailities (Note: I don't need the exact numbers. I am
just looking for a statement such as "pi less than or equal to pj and pj is less than or equal
to pk"). Briefly explain your reasoning. P2 >= P1 (because
core meltdown could have been caused by low quality heavy water) P3 <= P2 (because
once we know that inferior plutonium is present, that is sufficient to explain
the core melt down and thus our belief in low quality heavy water reduces) Part D.[3pt] It is afterall the holiday season and we really would like to
make sure that P(~IP & ~LH & ~CM & ~GD & ~SL) = P(~SL/~CM)*
P(~GD/~CM) * P(~CM/~IP,~LH) * P(~IP) * P(~LH) (Using the conditional independences
inherent in the network, and the chain rule of joint probability) P(~SL/~CM) = 1 P(SL/~CM) = 1 - .1 = .9 (from the CPT for SL) P(~GD/~CM) = 1-.05= .95 P(~CM/~IP,~LH) = 1 P(CM/~IP,~LH) = 1 - .01 = .99 P(~IP) = 1-.3 = .7 P(~LH) = 1-.4 = .6 So, P(~IP
& ~LH & ~CM & ~GD & ~SL) = .9 * .95 * .99 * .7 * .6 = .355 (So there is a 35% chance that nothing will
go wrong in Part E.[8pt] . Part E.[8pt] [[The
older version]]What is the numerical probability that Homer glows in the dark
and there is low-quality heavy water in the plant and there is inferior-quality
plutonium in the plant, given that we know that core-meltdown has occurred? P(GD,LH,IP|CM) is what
we want. I will do it by two methods. Method
1. Enumeration method P(GD,LH,IP|CM) = P(GD,LH,IP,CM)/ P(CM) P(GD,LH,IP,CM) =
P(GD,LH,IP,CM,SL) + P(GD,LH,IP,CM,~SL) = .3*.4*.7*.5*.9 + .3*.4*.7*.5*.1 = .042 We
need P(CM). We can compute it by conditioning on IP
and LH
P(CM) = P(CM/IP,LH)*P(IP,LH)+P(CM/IP,~LH)*P(IP,~LH) + P(CM|~IP,LH) *
P(~IP,LH) +P(CM/~IP,~LH)*P(~IP,~LH) Noting
that P(IP,LH) = P(IP/LH)* P(LH) = P(IP) * P(LH), and
using the CPTs
= .7*.3*.4 + .3*.3*.6 + .3*.7*.4+ .01*.7*.6 = .2262 So P(GD,LH,IP|CM) = .042/.2262 = 0.1856 (notice that trying
to avoid computing P(CM) by normalization method here would need us to compute P(~(GD,LH,IP)|CM) which is P(~GDV~LHV~IP | CM) and computing
this will be too messy) Method 2. Easy (for humans) method--uses bayes
rule P(GD,LH,IP|CM) = P(GD|LH,IP,CM)*P(LH,IP|CM) = P(GD|CM) * P(LH,IP|CM)
P(GD|LH,IP,CM) = P(GD|CM) (by conditional independence of GD
given CM) = .5 P(LH,IP|CM) = P(CM|LH,IP)*P(LH,IP)/P(CM) (by bayes rule) = .7 *
.3 *.4 / .2262 (noting that P(CM),
from the method 1 computation, is .2262) = .371352 P(GD,LH,IP|CM) = .5 * .371352 = 0.1856 (Same answer).
***Here is
the answer for the version specified in the homework you did