King’s College London
This paper is part of an examination of the College counting towards the award of a degree. Examinations are governed by the College Regulations under the authority of the Academic Board.
Degree Programmes
Module Code Module Title Examination Period
BSc, MSci
6CCS3AIN
Artificial Intelligence January 2018 (Period 1)
Time Allowed Rubric
Calculators Notes
Two hours
ANSWER ALL QUESTIONS. ANSWER EACH QUESTION ON A NEW PAGE OF YOUR ANSWER BOOK AND WRITE ITS NUMBER IN THE SPACE PROVIDED. Calculators may be used. The following models are permit- ted: Casio fx83 / Casio fx85.
Books, notes or other written material may not be brought into this examination
PLEASE DO NOT REMOVE THIS PAPER FROM THE EXAMINATION ROOM
2018 King’s College London
January 2018 6CCS3AIN
1. Travel on railways in the UK can be described using three binary random variables: Late, whether the train will be late; Crowded, whether or not the train will be crowded; and Hot, whether or not the train will be too hot. The following joint probability distribution captures the relationship between the three variables:
crowded hot 0.168 ¬ hot 0.042
crowded 0.336 0.084
¬ crowded 0.028 0.252
late
¬ crowded
0.009 0.081
¬ late
Using this information, compute the following probabilities, making sure you show your working:
a. P(late)
b. P(Hot|crowded)
[2 marks]
[3 marks]
Page 2
SEE NEXT PAGE
January 2018 6CCS3AIN
2. Imagine you are part of a government ethics committee whose role is to develop legislation that will govern the development and use of self-driving cars. Identify two issues that you think the ethics committee should consider, explaining why those issues are relevant to the development and use of self- driving cars.
[5 marks]
Page 3
SEE NEXT PAGE
January 2018 6CCS3AIN
3. Think of an example of an intelligent agent (this can be from the fictional or from the real world).
a. Write a few lines to describe this example and say: i. what kind of sensors it uses;
ii. what actions it can carry out; iii. what environment it operates in.
b. Making sure you provide the reasons for your answers, classify the envi- ronment your agent operates in according to whether it is:
i. episodic or sequential; ii. static or dynamic.
[2 marks] [2 marks]
Page 4
SEE NEXT PAGE
[1 marks]
January 2018 6CCS3AIN
4. You are constructing a Bayesian network model encoding medical informa- tion about three variables: Stroke, Hypertension and Smoking.
a. You learn that Hypertension and Smoking are both causes of Stroke. Draw a Bayesian network which relates Stroke, Hypertension and Smok- ing.
b. Given the conditional probabilities:
and
P(Hypertension) true
false
P(Stroke = true | Hypertension) 0.6
0.1
P(Smoking) true false
P(Stroke = true | Smoking) 0.7
0.05
[4 marks]
Use a Noisy-Or model to compute P(stroke| hypertension, smoking).
[6 marks]
Page 5
SEE NEXT PAGE
January 2018 6CCS3AIN
5. a. Let ⟨S,R⟩ be an abstract argumentation framework.
i. What does it mean if a set of arguments T ⊆ S is admissible?
[2 marks]
b. Consider the abstract argumentation framework ⟨S,R⟩ where:
• S = {a1,a2,a3,a4,a5} and
• R = {(a2, a1), (a3, a2), (a3, a4), (a3, a5), (a4, a2), (a5, a3)}.
i. Draw the graph that represents ⟨S,R⟩.
ii. Write down all the conflict-free subsets of S.
iii. Write down all the admissible subsets of S. iv. Write down all the preferred extensions of S.
[2 marks] [2 marks] [2 marks] [2 marks]
Page 6
SEE NEXT PAGE
January 2018 6CCS3AIN
6. You are working on a project that involves programming a robot, and sud- denly, in the middle of running your code, the robot stops working. You charged the battery not long ago, so the prior probability that the battery has run flat is 0.01 (the battery is new, so it is pretty reliable). You also know that the if the battery is flat, the probability that the robot would fail in exactly the way it just did is 0.99. You also know that there are a few other things that would cause the robot to fail, so the probability of it failing if the battery is not flat is 0.1.
a. What is the probability that the battery is flat?
[8 marks]
b. Comment on your answer to (a) in comparison to the prior probability of the battery being flat.
[2 marks]
Page 7
SEE NEXT PAGE
January 2018 6CCS3AIN
7. You are travelling and have some time to kill at the aiport. There are three things you could spend your time doing:
• You could have a coffee.
This has a probability of 0.8 of giving you time to relax with a tasty beverage, and a utility of 10. It also has a probability of 0.2 of providing you with a nasty cup from over-roasted beans that has a utility of −5.
• You could shop for clothes.
This has a probability of 0.1 that you will find a great outfit at a good
price, utility 20. However, it has a probability of 0.9 that you end up wasting money on over-priced junk, utility −10.
• You could have a bite to eat.
This has a probability of 0.8 that you find something rather mediocre that prevents you from being too hungry during your flight, utility 2, and a probability of 0.2 that you find something filling and tasty, utility 5.
a. What should you do if you take the principle of maximum expected utility to be your decision criterion?
[6 marks]
b. Write down the name of another decision criterion and explain what action that criterion would pick.
[4 marks]
Page 8
SEE NEXT PAGE
January 2018 6CCS3AIN
8. The Bayesian network below captures the knowledge about my working habits. Working hard (W) means that I tend to miss lunch (M), and missing lunch means that I am so hungry by 4pm that I can no longer work (H):
WMH
P(W=true) = 0.8, and the conditional probability tables for this network are as follows:
P(M=true|W) true 0.9
false 0.5
M P(H=true|M) true 0.7
false 0.3
Calculate an approximation to P(M=true|H=false) using importance sam- pling on the network. Carry out two iterations of the importance sampling approach in your answer, and use the following sequence of random numbers drawn from a uniform distribution between 0 and 1 to create the necessary samples:
0.42, 0.95, 0.75, 0.31, 0.16, 0.23
Page 9
SEE NEXT PAGE
[10 marks]
January 2018 6CCS3AIN
9. An agent is performing reinforcement learning in the environment below:
3 2 1
The agent may make the non-deterministic actions: up (U), down (D), left (L) and right (R). The cost of every action is 0.05. During learning, the agent makes three runs through the environment from (1, 1):
(1,1) → (1,2) → (1,3) → (2,3) → (1,3) → (2,3) → (3,3) (1,1) → (2,1) → (3,1)
(1,1) → (1,2) → (1,1) → (1,2) → (1,3) → (2,3) → (3,3)
a. Using direct utility estimation, show how the utility of U(1,1) changes after each of these three runs.
+1
−1
123
b. Explain one problem with direct utility estimation.
[6 marks]
[4 marks]
Page 10
SEE NEXT PAGE
January 2018
10. Consider the following normal form game:
LR U43
21 D02 52
6CCS3AIN
a. Identify any pure strategy Nash equilibria, exlaining why they are equi- librium solutions.
[4 marks]
b. Explain which outcome(s) of the game maximise social welfare.
[4 marks]
c. In general, what is the relationship between the Nash equilibria of a game and the outcomes that maximise social welfare?
[2 marks]
Page 11
SEE NEXT PAGE
January 2018 6CCS3AIN
11. a. Write down Bellman’s equation.
[3 marks]
b. The following is a very simple world in which an agent operates: north
+1
−1
3 2 1
The shaded square represents an obstacle. The reward for being in each state is −0.05 except for the states where the rewards are given in the figure. The agent can move north, south, east and west. The world is non-deterministic: when the agent makes a move, there is a probability of 0.9 that the move succeeds, and a probability of 0.1 that the agent does not move. All attempts to move into obstacles or into the boundaries of the world fail so that the agent will not move. Explain how value iteration can be used to establish the value of (1, 1). Take the discount factor to be 1.
12
3
c. Explain how policy iteration could be applied in this case.
[8 marks]
[4 marks]
Page 12
FINAL PAGE