CSE458 Bayesian Networks -- Exercise Sheet 1

www.csse.monash.edu.au/courseware/cse458/Ex1.html

Part 1: Probabilities and Bayes' Rule

1. Prove the Chain Rule Corollary:

   P(A|C) = P(A|B,C)P(B|C) + P(A|not B,C)P(not B|C).

2. There are five containers of milk on a shelf; unbeknownst to you, two of them have passed their use-by date. You grab two at random. What's the probability that neither have passed their use-by date? Suppose someone else has got in just ahead of you, taking one container, after examining the dates. What's the probability that the two you take after that are ahead of their use-by dates?

3. Suppose 20\% of Australians have been born overseas and that 10\% of those have been born in the Mideast. What percentage of Australians were born in the Mideast?

4. (From D. Kahneman & A. Tversky (1982) "Evidential Impact of Base Rates" in D. Kahneman, P. Slovic & A. Tversky (eds) Judgement Under Uncertainty, Cambridge.)

   You are a witness of a night-time hit-and-run accident involving a taxi in Athens. All taxis in Athens are blue or green. You swear, under oath, that the taxi was blue. Extensive testing shows that under the dim lighting conditions, discrimination between blue and green is 75% reliable. Is it possible to calculate the most likely colour for the taxi? (Hint: distinguish between the proposition that the taxi blue and the proposition that it appears blue.) What now, given that 9 out of 10 Athenian taxis are green?

5. Suppose that a doctor performs a test to determine if one of her patients is pregnant. The test gives either a positive or negative result. Most of the time the test is quite accurate: only 1 positive result in 100 is incorrect and only 1 negative result in 1000 is incorrect. Given that the doctor has found that about 70% of women who come to her for pregnancy tests are in fact pregnant, use Bayes' Rule to calculate the probability a woman the doctor sees is pregnant given that the pregnancy test gives a positive result.

6. A bookie offers you a ticket for \$5.00 which pays \$6.00 if Essendon beats Richmond and nothing otherwise. What are the odds being offered? To what probability of Essendon winning does that correspond?

7. You consider the probability that a coin is double-headed to be 0.01 (call this option $h'$); if it isn't double-headed, then it's a fair coin (call this option $h$). You consider the prior probability of bias (i.e., its being double-headed) to be 0.01. For whatever reason, you can only test the coin by flipping it and examining the coin (i.e., you can't simply examine both sides of the coin). In the worst case, how many tosses do you need before having a posterior probability for either $h$ or $h'$ that is greater than 0.99? (I.e., what's the maximum number of tosses until that happens.)

8. You are given two articles on the subject of global warming. One has been published on the Internet in December, 2000. The other is a student paper turned in in Semester 1, 2001. There is a substantial overlap in content, but that is to be expected since the assignment resulting in the student paper concerns the same issue as the Internet article. You consider the probability that the student paper is a case of plagiarism to be about 0.05 initially. To check, however, you decide to run a word profile program over the two papers. This program reports that the probability that the word profiles from the two documents come from unrelated papers is 0.0001. What should your posterior probability be? Show your reasoning.

Part 2: Bayesian Networks: Syntax and Semantics

1. Orville the Juggler

Orville, the robot juggler, drops balls quite often when its battery is low. In previous trials, it has been determined that the probability that it will drop a ball when its battery is low is 0.9. On the other hand when its battery is not low, the probability that it drops a ball is only 0.01. The battery was recharged not so long ago, so there is only a 5% chance that the battery is low. A robot observor, with a somewhat unreliable vision system, reports on whether or not Orville has dropped the ball. This question involves constructing a belief network, containing only Boolean variables, to represent and draw inferences about whether the battery is low depending on how well Orville is juggling.

(a) Draw a belief network to represent the problem. Label the network nodes and indicate clearly the direction of the arcs between the nodes.

(b) Write down the probability tables showing where the information on how Orville's success is related to the battery level, and the robot observer's accuracy, are encoded in the network.

(c) Suppose the robot observer reports that Orville has dropped the ball. What effect does this have on your belief that the battery is low. What type of reasoning is being done?


2. Conditional Independence

Consider the following belief network for another medical diagnosis example, where B=Bronchitis, S=Smoker, C=Cough, X=Positive X-ray and L=Lung cancer. Suppose that the prior for a patient being a smoker is 0.25, and the prior for the patient having bronchitis (during winter in Melbourne!) is 0.05.
 



List the pairs of nodes that are conditionally independent in the following situations:

(a) There is no evidence for any of the nodes.
(b) The cancer node is set to true (and there is no other evidence).
(c) The smoker node is set to true (and there is no other evidence).
(d) The cough node is set to true (and there is no other evidence).


3. Variable ordering

(a) What variable ordering(s) would have been used to produce the above network using the network construction algorithm described in lectures (Lecture 2, slide 10)?

(b) Given different variable orderings, what network structure would result from this algorithm?


4. D-separation.

   (a) Find all the sets of nodes that d-separate X and Y in the graph below (not including either X or Y in such sets).

   

   (b) Try to come up with a real-world scenario that might be modelled with such a network structure.