Q1. Probability (worth 15/100 marks)

1.  (worth 2 marks) There is a type of skin cancer that affects 3 in every 100 people. A company has invented a test that can diagnose this cancer using an image. The test isn’t perfect, tho; it will give a false positive (i.e. it will detect cancer when there is none) 5% of the time and a false negative (i.e. it will fail to detect a cancer that is present) 3% of the time.

If a test is positive, what is the probability the patient does not have cancer?  If a test is negative, what is the probability the patient does have cancer?

2.  (worth 3 marks) Doctors are not happy with the false positive rate of the test. The company responds by creating a new test that has a false positive rate of 6% and false negative rate of 4%. Although the test seems worse than the original, the company explains the test results are conditionally indepen- dent of one another given the condition of the user. They suggest using both tests in conjunction to

improve the false positive rate. Specifically, they suggest doctors diagnose cancer if and only if both tests are positive. Does this logic make sense? Explain.

3.  (worth 5 marks) We briefly discussed what it might mean to create an ’unbiased’ Bayesian Clas- sifier. Specifically, we said that if C is a classification, Y is a label representing ’ground truth’ and A is some ’protected attribute’ (e.g. gender or race) we might enforce Separation of classifications, making A independent of C given Y .  Alternately we might enforce Sufficiency, making A is in- dependent of Y given C.  But we can’t do both at the same time!  Show that this is true, i.e.  that enforcing both Separation and Sufficiency implies A is independent of (Y, C).

4.  (worth 5 marks) Given that X is independent of Y given Z and X is independent of W given (Y, Z). Show that X is independent of (Y, W) given Z.

Q2. Variable Elimination (worth 13/100 marks)

Birds frequently appear in the tree outside of your window in the morning and evening; these include finches, cardinals and robins.  Finches appear more frequently than robins, and robins appear more fre- quently than cardinals (the ratio is 7:4:1). The finches will sing a song when they appear 7 out of every 10 times in the morning, but never in the evening. The cardinals rarely sing songs and only in the evenings (in the evening, they sing 1 of every 10 times they appear). Robins sing once every five times they appear regardless of the time of day. Every tenth cardinal and robin will stay in the tree longer than five minutes. Every fourth finch will stay in the tree longer than five minutes.

1.  (worth 2 marks) Draw a Bayesian network that captures the information in the story above correctly and concisely. Make sure to annotate your network with conditional probability tables (CPTs).

2.  (worth 1 mark) How many parameters will be required to specify the network you have drawn? Explain.

3.  (worth 5 marks) A bird lands in the tree in the morning. What is the probability that it will stay in the tree longer than five minutes?

4.  (worth 5 marks) What is the overall probability that any given bird in your tree will sing a song?

Q3. Markov Models (worth 12/100 marks)

In the mail room of a university office, a stream of blue and yellow mail carts pass a mail sorting robot. Blue carts contain 7 domestic letters for every 3 international letters. Yellow carts contain 2 domestic letters for every 3 international letters. Blue carts are followed by blue carts 70% of the time, but 30% of the time they are followed by a yellow cart. Yellow carts are followed by yellow carts half of of the time, and the other

half of the time they are followed by a blue cart. The first cart, every morning, is yellow 9 of every 10 times.

The robot pulls a single letter from each cart as the cart passes it by.

1.  (worth 2 mark) Draw a markov model to represent the joint distribution over cart colors and the origins of letters selected by the robot.  Include a conditional probability table (CPT) with each variable in your model.

2.  (worth 5 marks) What is the probability that the first three letters selected by the robot, in order, will be: domestic, international, domestic?

3.  (worth 5 marks) What is the probability that the fourth cart will be blue if the first three letters selected, in order, are: international, international, domestic?

Q4. D-Separation and Relevance (worth 10/100 marks)

Given the Bayesian Network structure above ....

1.  (worth 1 mark) How many parameters are required to fully specify the network? Explain.

2.  (worth 3 marks) List three pairs of variables X, Y where X is independent of Y .

3.  (worth 3 marks) List three sets of variables X, Y, Z where X is independent of Z given Y .

4.  (worth 1 mark) Assume we are to calculate P (BlE, F). Which variables are relevant?

5.  (worth 2 marks) Assume we are to calculate P (BlG) using variable elimination. List the elimina- tion order you might suggest when using the min-fill heuristic to select variables, and give the size of the factors that result from each elimination.

Q5. First-order Structures and Models (worth 19/100 marks)

Consider a first-order language cmetal consisting of constant symbols o1 , o2 , o3 , a binary predicate symbol heavier than, and unary predicate symbol expensive.

Let D = ASteel, Aluminium, Titanium}.

1.  (worth 6 marks) How many cmetal -structures with domain D exist? Justify your answer.

2.  (worth 3 marks) Let Φ1 be the set consisting of the following sentences:

heavier than(o2 , o1 )

heavier than(o1 , o3 )

expensive(o1 )

expensive(o2 )

Consider a set 9 of cmetal -structures for all structures M e 9:

● The domain of M is D and

o1M  = Steel

o2M  = Aluminium

o3M  = Titanium

(Aluminium, Steel) e heavier thanM

(Steel, Titanium) e heavier thanM

(Titanium, Aluminium) e heavier thanM

Aluminium e expensiveM

Steel e expensiveM

Are all structures in 9 models of Φ 1 ? Explain why or why not.

3.  (worth 4 marks) Suppose Φ2 is the set obtained by adding the following sentence to Φ 1 VxVyVz(heavier than(x, y) ^ heavier than(y, z) → heavier than(x, z))

Are all structures in 9 models of Φ2 ? Explain why or why not.

4.  (worth 6 marks) Consider the set Φ3 that contains only the following axiom

VxVyVz(heavier than(x, y) ^ heavier than(y, z) → heavier than(x, z)) How many cmetal -structures with domain D are models of Φ3 ? Justify your answer.

Q6. Proof by Resolution (worth 31/100 marks)

Consider the following knowledge base (note that p, p1 , p2 , p3  are constant symbols, part(x, y) means x is a part of y and precedes(x, y) means x precedes y):

3c1 3c2 3c3 [component(c1 , p1 ) ^ component(c2 , p2 ) ^ component(c3 , p3 ) ^ assemble before(c1 , c2 , p) ^ assemble before(c2 , c3 , p)]

(1)

Ac1Ac2 [(component(c1 , p1 ) ^ component(c2 , p2 ) ^ assemble before(c1 , c2 , p))

→ 3c3  (component(c3 , p3 ) ^ assemble before(c1 , c3 , p) ^ assemble before(c3 , c2 , p))]   (2)

→ precedes(a1 , a2 )]                                                                                     (3)

Ac1Ac2Ac3Aa [(assemble before(c1 , c2 , a) ^ assemble before(c2 , c3 , a)) → assemble before(c1 , c3 , a)]

(4)