THE UNIVERSITY OF HONG KONG
FACULTY OF ENGINEERING
DEPARTMENT OF COMPUTER SCIENCE
Final Examination
COMP7404A Computational intelligence and machine learning
7 Dec 2019, 2:30 pm - 4:30 pm
This is an open book examination. All answers must be your own.
Answer ALL questions.
Write your university number on every page.
Write your answer into a single Microsoft Word file.
You may, if necessary, insert scanned handwritten answers into your Word file.
Submit your Word file to OLEX before the deadline.
Question Max. Mark
1 18
2 10
3 16
4 15
5 10
6 21
7 10
Total 100
Question 1 [18 marks total]:
Consider the search problem below.
4
Let A be the start state, Ebe the goal state and x be an integer variable s.t. I <= x <= 10.
Consider TSA only.
1.1 [6 marks]: Write down the order of explored states for (a) BFS, (b) DFS.
1.2 [6 marks]: Write down all values for x, s.t. the heuristic h(n) is (a) admissible, (b) consistent
for all nodes n.
1.3 [6 marks]: Write down all values for x, s.t. the number of explored states of A* is less than
that of BFS. If there is a tie in A* use LIFO to resolve it.
Page 2 of9
Question 2 [10 marks total]:
Peter (P), Mary (M), Otto (0) and Dirk (D) would like to rent an apartment in a particular Yuen
Long village house. The village house has three floors: G/F, 1/F, 2/F. Every floor has only one
apartment. P, M, 0 and D must be assigned to exactly one floor. Note that more than one person
can live in the same apartment. Consider the following constraints.
P and M cannot live in the same apartment.
D must live on a higher floor than 0.
D must live alone.
If P and O live together, they must be on 1/F.
If P and O live separate, one of them must live on the 2/F.
We are going to model this as a constraint satisfaction problem as follows.
Four variables P, M, 0 and D represent the different people above.
Three values 0, 1, and 2 representing the floors G/F, 1/F and 2/F, respectively.
2.1 [5 marks]: Consider the following partial assignment: 0 = 1. Other variables have full
domain. Apply forward checking.
2.2 [5 marks]: Let all variables have full domains. Enforce arc-consistency.
Page 3 of9
Question 3 [16 marks total]:
Let there be an MDP with an agent that has 5 possible actions. Up, Down, Left, Right and Exit.
We are going to use the same transition model that we have seen many times in class:
Up, Down, Left and Right transitions are successful 80% of the time and 20% of the time
one of the two perpendicular directions is chosen with equal chance.
Exit action are successful 100% of the time.
If the agent bumps into a wall it stays put.
The agent operates in the following grid world. Black squares represent a wall.
A
B
1 2 3 4 5
The states Al, A2, A3, and A4 only have Up, Down, Left and Right actions available and the
states B3 and AS only have the exit action available. All transitional rewards are O except for
R(A5, exit, TerminalState) = +I, and
R(B3, exit, TerminalState) = -100.
3.1 [4 marks]: Determine n*(Al), n*(A2), n*(A3) and n*(A4) assuming a discount of y = I.
3.2 [4 marks]: Determine V*(Al), V*(A2), V*(A3) and V*(A4) assuming a discount of y = I.
3.3 [4 marks]: Determine V*(A4) assuming a discount of y, where O < y in terms of y.
3.4 [4 marks]: We are adding a new available action: Woom (W). This action doesn't do
anything (i.e., agent stays put) except it guarantees the next time the agent takes an action it will
be successful 100% of the time. The special ability of W is only for one timestep. However,
action W can be taken an unlimited number of times. Determine V*(A4) assuming a discount of
y, where O < y < I. Give your answer in terms of y. Assume that the previous action was W.
Page 4 of9
Question 4 [15 marks total]:
In this question we are going to build an MDP and use approximate reinforcement learning to
pick an attraction in Disneyland. There is a chance that some attractions make you feel sick.
Initially you feel well and enjoy the attractions. You are getting rewards. When you are sick and
you continue visiting the attraction there is a chance that you feel well again. When you feel sick
and you continue visiting an attraction you will get a lower reward.
This is your first time in Disneyland. You don't know how much reward you may obtain while
sick or well. You also don't know what the chances are of getting sick/well again for each
attraction.
The available actions and some more information about them is available in the following table.
action type wait speed
Big Grizzly rollercoaster short slow
Iron Man ro 11 ercoaster long fast
Dumbo carousel short fast
Toy Soldier drop tower short slow
Leave Disney leave short slow
In our MDP, let there be two states: Well and Sick. Every attraction is an action. The leave
Disney action will end the current run through the MDP. Taking an attraction action will lead
back to the same state with some probability or take you to the other state. We are going to use
the following features
fo(state, action) = 1, if and only if type = rollercoaster,
f1(state, action) = 1,
fistate, action) = 1, if and only if wait = short,
fistate, action) = 1, if and only if type = rollercoaster,
and the weights: w O = 2, w 1 = 1, w 2 = 1, w 3 = 1/2. Assume a discount of y = 112 and a learning
rate of a = 1/2.
4.1 [3 marks]: Determine Q(Well, Big Grizzly)
4.2 [8 marks]: Apply an approximate Q-Learning update based on the sample
(Well, Big Grizzly, Sick, -9.5).
Write down all weights after the update is complete.
4.3 [4 marks]: Is Q(Well, Big Grizzly) = Q(Sick, action) for all actions after the update of 4.2?
Use at most two sentences to explain why / why not.
Page 5 of9
Question 5 [10 marks]:
In this question you are going to apply the Perceptron algorithm on four 2D training samples. Let
the training samples be given as follows.
x, X2 y
1 1 -1
1 -1 1
-1 1 -1
-1 -1 -1
In the table above, x1 and x2 are the features and y is the class label. Let all initial weights be
w 1 = w2 = 0.2 and let the bias be w0 = -0.2.
5.1 [4 marks]: Calculate the estimate y for all samples.
5.2 [6 marks]: Perform one epoch of training using a learning rate of 0.5.
Page 6 of9
Question 6 [21 marks]:
6.1 [4 marks]: Use KNN with euclidean distance to classify the point?. Show all classification
results for the following values of k = 1, 2, 3, . . . , 7.
+ + ·
+
- "' ··· · ··· -
-
6.2 [7 marks]: We will use the dataset below to learn a decision tree which predicts if students
pass COMP7404A (Yes or No), based on their cumulative GPA (High, Medium, or Low) and if
they studied (True, False).
CGPA Studied Passed
L F N
L T y
M F N
M T y
H F N
H T y
Draw the full decision tree that would be learned for this dataset using the entropy (use log2).
Show all calculations and write down the entropy values for all nodes in the tree.
6.3 [3 marks for correct answer, -3 marks for incorrect answer]: (True/False) Support vector
machines, like logistic regression models, give a probability distribution over the possible labels
given an input example. Use at most one sentence to explain.
6.4 [3 marks for correct answer, -3 marks for incorrect answer]: (True/False) The maximum
margin decision boundaries that support vector machines construct have the lowest
generalization error among all linear classifiers. Use at most one sentence to explain.
Page 7 of9
6.5 [4 mark for correct answer, -2 mark for incorrect answer]: Select all binary classifiers
that are able to correctly separate the training data (circles vs. triangles) given in the figure
below. Use at most two sentences to explain.
A. Logistic regression
1.0 •
B. SVM with linear kernel
C. SVM with RBF kernel 0.8
D. Decision tree
E. 3-nearest-neighbor classifier (with Euclidean distance)
0.6
•
0.4
0.2
0.0 •
0.0 0.2 0.4 0.6 0.8
Page 8 o/9
•
•
1.0
Question 7 [total 10 marks]
7.1 [4 mark for correct answer, -2 mark for incorrect answer]: In a medical application
domain, suppose we build a classifier for patient screening (True means patient has cancer).
Which of the following situations would you like your classifier to have? Only select one
answer, select the one that you think is most important. Use at most two sentences to explain.
The double greater-than sign denotes much greater-than.
(FP: false positive, FN: false negative, TP: true positive, TN: true negative)
A. FP>>FN
B. FN>> FP
C. FN=FP X TP
D. TN>>FP
E. FN X TP >> FP X TN
F. All of the above
7.2 [6 marks]: Consider a 2D binary classification problem with two classes:+ and -. The result
of some classifier is shown in the following figure.
CB CB CB ,. ... /_I
8
I
,. ...
CB G)
/_\
,_ I ,,. ... '+\ e ,_1 ,. ... ©·· /-1 ,,. ... .,,. .... ( - \ ,_, ' ,_ I
G) (3).;,
.,. ...
/_I ,,. ... 0 Predicted class: + , _, I 1-' ,_ I ,,. ... ' ., ...... / _ \ .. .,.. ..... '+' · 1_1 ' I ,,. ... ,,. ... ,_1 - I Predicted class: -CB ,_ I 1-' ,_ I ,. ... ' I ,. .... .·:,... ..... 1-' - ,,. ... 1-'
{_\ ' I /_\ ' - ' .I ,_ -
x i
Calculate the precision, recall and Fl-score of the classifier. Notations in this example are
identical to the one we used chapter 6 of the lecture notes.
END OF PAPER
Page 9 of9

欢迎咨询51作业君