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.
Examination Period Module Code Module Title
May 2021 (Period 2) 6CCS3PRE
Pattern Recognition
Format of Examination Start time
Time Allowed Instructions
Rubric
Written questions
9am BST (GMT +1)
1.5 hours
You are permitted to access any materials you wish, but this is not mandated and is not expected. You may use a calculator if you find this helpful.
ANSWER ALL QUESTIONS
The rubric for this paper must be followed and extra answers should not be submitted. For answers that are handwritten, write with blue/black ink on light coloured paper. Include the Module code, question number and student number on every page to be submitted. For an- swers that are typed, use the template provided.
Submission Deadline 10.30am
Submission Process Work must be submitted to the level 6 Informatics Assessments
KEATS page.
Your work must be submitted as a PDF file. If you have prepared some answers on computer, and some on paper (which have then been digitised), you may upload at most two PDF files – one for computer-prepared answers, one for digitised answers. Do not duplicate answers across the two PDFs – if you do this, the computer-prepared answer will be taken. You should check that your work displays correctly after it has been uploaded.
ACADEMIC HONESTY AND INTEGRITY
By submitting this assignment, I confirm that this work is entirely my own, or is the work of an assigned or permitted group, of which i am a member, with exception to any content where the works of others have been acknowledged with appropriate referencing.
I also confirm that I have read and understood the College’s Academic Honesty & Integrity Policy:
https://www.kcl.ac.uk/governancezone/assessment/academic-honesty-integrity
2021 King’s College London
May 2021 6CCS3ML1 and 6CCS3PRE
1.
You are going on a hiking trip and you want to fill a bag with items necessary for the trip. The maximum capacity of the bag is 15kg. There are 4 different items that you can take. Each item has a weight and a value which represents the level of importance. Your task is to find the ideal combination of items that maximises the value within the weight capacity W = 15kg of the bag.
The weights and values of the items are given below:
Item type Weight (kg) Value
I1 I2 I3 I4 5 2 4 6 11 5 4 2
You will be using a genetic algorithm to solve this task.
a. Explain how you will represent the individuals for encoding the problem.
[3 marks]
b. Give three examples of individuals using your representation.
[3 marks]
c. Explain how we can obtain an individual which is not valid given the task definition and write its genotype.
d. Consider a population with 4 members:
Candidate 1 has a fitness of 2 Candidate 2 has a fitness of 4 Candidate 3 has a fitness of 6 Candidate 4 has a fitness of 13
Use probabilistic selection to calculate the probability of selecting each candidate. Show your calculations.
[4 marks]
QUESTION 1 CONTINUES ON NEXT PAGE
Page 2
SEE NEXT PAGE
[5 marks]
May 2021 6CCS3ML1 and 6CCS3PRE
e. In genetic programming, the genotype is a program represented as a tree. Given the following 2 trees, select a node in each tree and apply the crossover operator (you can select any node you wish, except the root of the tree). Write the 2 offspring that you obtain.
[6 marks]
f. Write the equation of each offspring obtained in part (e) above.
[6 marks]
Page 3
SEE NEXT PAGE
May 2021 6CCS3ML1 and 6CCS3PRE
2.
a. You are given the 3 scenarios below. For each of these, determine the type of learning you would use to solve them – supervised learning, unsupervised learning, reinforcement learning – as well as an appropriate machine learning algorithm you would choose. Explain your answer.
i) A sales company has a database of its customers. It wants to auto- matically find out information about the customers and group them into market segments to improve ad targeting.
ii) A start-up has a database of images with people in real environments. Each image has been annotated with one of the 6 basic emotions: happiness, sadness, disgust, fear, surprise, and anger. The start- up wants to use this database to build a system that identifies the emotions expressed by people when entering their workplace.
iii) A company wants to develop a self-driving car that can make safe decisions.
[9 marks]
b. A multi-layer feedforward network has 5 input units, a first hidden layer with 4 units, a second hidden layer with 3 units, and 2 output units. How many weights does this network have? Do not include the biases in your calculations. Show your calculations.
[4 marks]
QUESTION 2 CONTINUES ON NEXT PAGE
Page 4
SEE NEXT PAGE
May 2021 6CCS3ML1 and 6CCS3PRE
c. The following diagram represents a feed-forward neural network with one hidden layer:
The input nodes to this network are nodes 1 and 2. The weights in the network are as follows:
w13 =−2 w14 =4 w23 =3 w24 =−1 w35 =1 w36 =−1 w45 =−1 w46 =1
Each hidden and output node uses the following activation function:
g(s)=1, ifs≥0
0, otherwise
Calculate the network output for the following input. Show your calcu-
lations.
x1 x2 01
QUESTION 2 CONTINUES ON NEXT PAGE
Page 5
SEE NEXT PAGE
[4 marks]
May 2021 6CCS3ML1 and 6CCS3PRE
d. Having done the forward pass in this network, what is the usual sequence of events for training the network using the backpropagation algorithm? You do not need to write the update rules nor do any calculations.
[13 marks]
3. You have a supervised machine learning model that takes inputs x and computes its output hw(x) using a weight vector w. Using a training set ((x1,y1)(x2,y2)…(xm,ym)), the model aims to minimise the following loss function:
m
E(hw) = (yi − hw(xi))2 (1)
i=1
a. What kind of problems can we solve with this model?
[3 marks]
b. Give three real-world example tasks for which you can use this model. [3 marks]
c. How would you define your hypothesis function hw(x) if your model is linear and multivariate?
[4 marks]
d. We are told that some training examples are more important than others and, hence, after training, it is important that there is a small difference between yi and hw(xi) for these examples. How might you modify your training algorithm to take this into account? Explain your answer.
[15 marks]
QUESTION 3 CONTINUES ON NEXT PAGE
Page 6
SEE NEXT PAGE
May 2021 6CCS3ML1 and 6CCS3PRE
e. You use the training data to train a model hw(x). A colleague presents you with another model trained using the same set of examples and loss function but with a different set of features, h′w′ (x′). How might you use these models to train a single, more powerful one? Justify your answer.
[8 marks]
f. How might you define the hypothesis function hw(x) of your new model in part (e)? Explain your answer.
[10 marks]
Page 7
FINAL PAGE