CSE 471/598 Intro to AI (Kambhampati)

Homework 4 Solutions (Fall 2007


Question 1 [Short answer questions:

  1. [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

  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 Springfield nuclear power plant (where Homer Simpson is gainfully employed). Here is our understanding of the domain (this is all official based on my conversations with Bart). The presence of inferior plutonium or low quality heavy water (D20) in the plant reactor leads to a core melt-down in the reactor. When core-meltdown occurs, it tends to irradiate the employees (such as Homer) causing them to glow in the dark. Core-meltdown also tends to shutoff the power grid which in turn causes the slurpees in Apu's convenience store (called Squishees as Kwikee Mart) to melt and get watery.

Here are a bunch of probabilities I got from the Springfield Statistics Beureau: If inferior plutonium alone is present, core-meltdown occurs with probability 0.3; If low quality heavy water alone is present, the core-meltdown occurs with probability 0.3. If both inferior plutonium and low-quality heavy water are present, then the core-meltdown occurs with probability 0.7. Even under completely normal conditions, core-meltdown can occur with probability 0.01. Core-meltdown leads to glowing-in-the-dark employees with probability 0.5. What with lax quality control over at Springfield plant, even under normal circumstances, Homer and his buddies tend to glow in the dark with probability 0.05. Core-meltdown causes slurpee liquification with 0.9, and over at Apu's slurpees tend to get watery even without a core-meltdown with probability 0.1. Finally, the probability that Springfield plant gets inferior-quality plutonium is 0.3 and that it gets low-quality heavy water is 0.4 (you know that wacky Burns--he is always trying to buy cheap stuff and make more bucks).

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:

    1. Independence of inferior-quality plutonium and low-quality heavy water in Springfield nuclear plant

Given no evidence at all, they are independent of each other.

    1. Independence of inferior-quality plutonium and low-quality heavy water in Springfield nuclear plant, given watery slurpees over at Apu's.

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)

    1. Independence of low-quality heavy-water and wateryness of slurpees at Apu's, given core-meltdown

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 Springfield will have a merry season devoid of any untoward incidents. What is the probability that this is going to be the case? (That is, what is the probability that there is no inferior-grade plutonium in the plant, and there is no low-grade heavy water in the plant, and there is no core-meltdown, and Homer ain't glowing in the dark, and Apu's slurpees are not watery).


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 Springfield)


Part E.[8pt]

***Here is the answer for the version specified in the homework you did


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




= .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)


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|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).