Homework 4

CSE 471/598

Due Date: 29^th November, 2001.

(On Planning, Logic, Probabilistic Logic,learning)

[Or the Homework of Magellan, Simpsons, and Seinfeld]

Planning

Qn I. Consider the following "artificial" planning domain, which contains

the (artificial) operators described below:

operator O1

prec: P

Eff: R, ~S

operator O2

prec: Q

Eff: S

operator O3

prec: P

Eff: M

operator O4

prec: R,S

Eff: P,Q,R,S

operator O5

prec: M, R

Eff: P

The initial state is {P,Q} and the desired goals are {P,Q,R,S}

1.  Show the first level of the search space of  a progression planner .

2.  Show the first level of the search space of a regression planner

3. Draw the planning graph for this problem until it levels off. You

   should show the propagated mutex relations. (This problem is small

   enough that you can actually draw the graph to level of fairly

   easily).

4.  Use the planning graph to estimate the costs of each of

   the states in part 2 above.

5.  Convert the final level planning graph into a CSP problem. That is

    describe all the variables, their domains, and the

    constraints. See if you can write down a solution (without

    actually solving it--since this problem is small enough, you know

    the solution and you can see how it is manifested as a solution to

    the CSP).

Logic:

Qn II

. A small question from a previous  year's midterm

You are given the following two facts:

1. If Rao is happy, then Rao is smiling.

2. Rao is smiling.

You want to infer from these facts that Rao is happy. Check, using

truth-table method, whether this inference is sound. Show the truth

table you constructed and the reasoning you used to decide soundess.

ii. Convert the following sentence into clausal form.

         (A V B) => C

iii.  Suppose you also know that B is true. Use resolution inference

rule to show that C is true.

Qn III. Another question from a take-home exam. The following question tells us how

"commonsense" knowledge is very important in doing even simple

inferences. You are told the following:

"EXPLORER MAGELLAN WENT AROUND THE WORLD THREE TIMES. ON ONE OF THESE TRIPS, HE DIED."

You are asked to figure out which of the trips magellan died. You want

to use a resolution theorem prover to prove that he died on trip 3.

3.1.[5] Write the given sentences, and the goal in prepositional form

(You can use hyphenated propositions such as died-on-trip1, round-the-world-trip1 etc. You can also shorten the proposition names as you please—as long as

you give a glossary of the intended meanings of the propositions)

3.2.[5] Write in English, all other common-sense knowledge that you used

     in addition to the above to figure out the answer yourself.

3.3.[5] Write all the sentences in 3.3 into prepositional logic

3.4.[10]  Now provide a resolution refutation trace that shows the

     answer. (I will give partial credit for proof sketches).

3.6.[2] Could this problem have been solved with Generalized modus ponens based solver?

Probabilistic Reasoning

Qn IV:

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

[4] Given n boolean random variables, we know that explicitly specifying their joint probability distribution takes 2^n-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 be 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?

Qn 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 (D₂0) 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.

Part B.[4pt] Given your network above, which of the following (conditional) independences hold? Briefly justify your answer in each case:

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

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

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

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.

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

Part E.[8pt] I am changing this question to make it more in line with the material we actually did on Nov 16^t.

We just found that there the slurpees at Apus’s place have liquefied. We also found out, from reliable sources, that the batch of heavy water they are using at the reactor is INDEED low quality one. Compute the probability distribution on Homer glowing in the dark. Use the enumeration method—as discussed on Friday’s class—to compute this probability (notice that this involves marginalization and normalization). [If you want to be sure, You can check your answer by plugging this network in the bayesnet tool and doing the query).

(previously, it was “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? “—I would request that you do the new version)

Part F. [***Bayes Net Mini-Project**] (there is no part f. Instead, you have the project 4

Learning:

Note: I may decide to make all or part of this problem optional if the relevant material has not been discussed in the class by the homework deadline

Problem VI. [30pt] George Costanza wants to throw a party and he wants it to be a success. Over the years he has thrown a fair number of parties, and some have been successful and some have been unsuccessful. He typically calls some subset of Seinfeld, Newman and Kramer. Here is the data about the past parties--described in terms of who turned up at the party and whether the party was a success.

	Seinfeld invited	Newman invited	Kramer invited	Good Party
Party1	N	N	N	N
Party2	N	N	Y	N
Party3	N	Y	N	Y
Party4	N	Y	Y	Y
Party5	Y	N	N	Y
Party6	Y	N	Y	Y
Party7	Y	Y	N	N
Party8	Y	Y	Y	N

Part A.[3pt] We want to help George out by using decision trees to learn the pattern behind successful parties, so that George can then use the learned decision tree to predict whether or not a new party he is trying to throw will be a success. Since this is a small-enough example, YOU should be able to see the pattern in the data. Can you express the pattern in terms of a compact decision tree? (If you are completely lost on this part, you can ask me for a hint at the expense of some points; so you can continue with the rest of the sub-parts)

Part B.[6pt] Suppose you want to go with the automated decision-tree construction algorithm (which uses the information value of splitting on each attribute). Show the information values of splitting on each attribute, and show which attribute will be selected at the first level. Assume that if two attributes have the same information value, you will split the tie using the alphabetical ordering (this should be a reasonable assumption since decision trees don't care how you choose among equally valued attributes).

Part C.[3] Do you think the tree that you will ultimately get by continuing to refine the partial tree in Part B will be better or worse than the tree that you wrote in Part A? If it is worse, is it theoretically consistent that you could do better than the automated information-theoretic method for constructing decision trees? (You don't need to show any explicit information value calculations here).

Part D.[4] Consider the super-attribute "Seinfeld-Newman", which in essence is the result of merging the seinfeld and newman attributes. This super attribute takes four values: YY, YN, NY, NN. Compute the information value of this super-attribute, and compare it to the attribute information values in Part B. If you had a chance of considering this super attribute along with the other attributes, which would you have chosen to split on at the first level?

Part E.[4] Does the answer to Part D suggest you a way of always getting optimal decision trees? If so, what is the computational cost of this method relative to the standard method (that you used in Part B)?

Part F.[4] Now, George is gettin' upset at all this dilly-dallying with the decision trees, and would like to switch over to neural networks for finding pattern in his successful parties. What is the minimum number of layers of threshold units that he would need in his neural network so he can converge and learn the pattern behind his successful parties? Explain how you reached your answer.

Part G.[6] Show an actual neural network (with weights and thresholds) that represents the concept. Assume that the inputs are going to be 1 (for Y) and 0 (for N). We want the output to be 1 (for successful party) and 0 (for unsuccessful party). I am not asking you to learn a network using the gradient descent method. I am asking you to show one directly. (hint 1: Use your answer to part A). (Hint 2: You might want to consult figure 19.6 in page 570 of the textbook in doing this problem.)

General Qusetion: [[Extra Credit. But Highly Recommended]]

Problem VII. Watch the PBS program 2001: HAL’s Legacy on PBS (Channel 8). Original broadcast Tuesday, November 27^th- 9pm, and on the same day at midnight (repeated).

Write a paragraph summarizing your impressions on the program vis a vis where AI was expected to get, and where it got.