Question 1

(a) A number of archaeological finds have been classified by an expert into periods based

on three attributes as follows.

(i) What period (1, 2 or 3) would a naive Bayes classifier give to a find that was from location A, that was metal, and that had decoration, if it had been trained on the above examples? You do not need to smooth any probabilities in your calculation. You must clearly show the calculation steps used to obtain your answer.  (Only one mark will be given for just the answer,  the rest of the marks are for the

calculations.)

(ii) A decision tree is needed for classifying new finds based on the above finds.

i. What is the entropy of the set of nine finds? Show how your answer is calcu- lated.                                                                                                    [2 marks]

ii. In order to decide which attribute to split on at the root of the tree, the infor- mation gain for two of the attributes has already been calculated as follows.

Attribute      Information Gain

Decoration    0.0294

Location       0.0183

Calculate the information gain for the remaining attribute: Material.  [3 marks]

iii. Your result should show that Material is the best attribute to split on at the root of the tree. Now consider the next step in constructing the decision tree. Splitting on Material gives two nodes which correspond to the glass finds and the metal finds. Calculate the Information Gain for the Location attribute at the Metal node.                                                                                   [3 marks]

(b) A binary (black and white) image consists of two long horizontal black lines each two

pixels high and with a one pixel high gap between them, which was intended to consist entirely of white pixels. However, as shown in the diagram below, the gap between the black lines includes some additional black pixels. These additional pixels are noise and need to be removed. The noise pixels always occur singly as in the example, so you can assume that you never get two adjacent noise pixels. Note that the image is considered to consist of the black pixels with the white pixels being the background.

(i) How effective at removing the noise would be to filter the image with a 3 x3 median filter? You should say clearly whether the processing would remove the noise pixels and give a reason for your answer.  You should also say, giving reasons, whether the processed image would include any new black pixels not present in the original image.                                                                                                          [3 marks]

(ii) An alternative approach to removing the noise pixels would be to use a mor-

phological technique.  What morphological operation you would choose and what structuring element would be used to remove the noise pixels? Explain briefly how this operation would achieve the desired result.                                       [3 marks] 

[Question 1 total: 20 marks]

Question 2

(a) Consider the following graph diagram of a search space. Each circle represents a state

and the arrows represent possible action transitions. S is the start state and there are two goal states:  G1 and G1.  The cost  of each action is given by the number next to the arrow. Each state is labelled by an identifying name (S, A–F, G1, G2, H) and also a number. The number is the value of a heuristic function, which gives an estimate of the cost of getting to the nearest goal from that node.

 1

B

20

50

(i) Write down the optimal path from S to one of the goals                         [1 mark]

(ii) Write down the sequence in which nodes will be expanded until one of the goal

states is reached, while performing a best first search (also known as greedy search).

[2 marks]

(iii) Write down the sequence in which nodes will be expanded, until one of the goal

states is reached, while performing a uniform cost search.                     [2 marks]

(iv) Write down the sequence in which nodes will be expanded until one of the goal

states is reached, while performing an A*  (A-star) search.                    [2 marks]

(b)  Answer  parts  (i)  and  (iii)  of this  question  on  the  supplementary  answer

sheet provided. Hand this in at the end of the exam along with your answer booklet.

At a certain point in an adversarial game the move possibilities are modelled by the following game tree:

7  3   1    2  9  5    3   1  5    1  3  6    1  2  3    3  4  5    1  2  3    7  6  5  

(i) Use Minimax to compute the values of all the non-leaf nodes and add these to diagram (i) on the supplementary answer sheet.                                      [2 marks]

(ii)  To make the optimal next move, should Max take the left, middle or right branch?

Briefly explain your answer (in 1 or 2 sentences).                                      [1 mark]

(iii)  By annotating diagram (iii) on the supplementary answer sheet, show how alpha-

beta pruning can be used to efficiently calculate the minimax without looking at all nodes. Clearly indicate which nodes and/or sub trees are pruned from the search. Assume that the tree is evaluated in left to right order.                          [3 marks]

(c) In the Leapfrog puzzle, black and white counters are arranged in a line with the black counters on the left and the white counters on the right, with a space between them. We shall consider the case with two black and two white counters, as shown below:

Two types of move are allowed: sliding — a counter that is next to the space can move into the space; and hopping — a counter can jump over one  other counter (of either colour) into the space, provided that the space is immediately on the other side of the other counter. So from the initial state shown, either of the counters next to the space can move into it, the leftmost black counter can jump over the other black counter into the space, or the rightmost white counter can jump over the other white counter into the space.

The puzzle is solved if the black counters are on the right and the white counters on the left, with the space between them.  The aim is to solve the puzzle in  the  smallest number of steps.

(i) Any state that arises in the Leapfrog puzzle can be represented as a sequence of 5 symbols representing the contents of each of the spaces, in left to right order. Let B stand for a black counter, W stand for a white counter and ‘ _ ’ stand for the space. Then the initial state would be represented by BB _ WW .

Using this notation for states, draw a search tree that represents all possibilities for the first two  moves that can be made in the Leapfrog  puzzle.  You may omit from your tree all the cases where the second move is simply the reverse of the first move (which would result in a return to the initial state).                      [2 marks]

(ii)  Suggest an uninformed  search strategy that would be well-suited to solving the

Leapfrog puzzle and briefly explain (in 2–4 sentences) why your suggested strategy is good for this puzzle.                                                                               [3 marks]

(iii) Specify a heuristic function that could be used to guide an informed search for a

solution to this problem.                                                                       [2 marks]

[Question 2 total: 20 marks]

Question 3

(a)  Translate the following sentence into Propositional Logic:

If I am early I shall see you on Tuesday otherwise I won’t.

(b)  Translate the following sentences into First- Order Predicate Logic:

(i) A black dog bit a small child.

(ii) All the children who live in Otley know each other.                                [3 marks]

(c) Use propositional resolution  to show that the following set of propositional clauses is

inconsistent:                                                                                                        [5 marks] { {A,  -B},  {C},  {-A,  -C},  {A,  B,  -C,  D},  {-C,  -D,  E},  {-E} }

(d) In each of the following cases state whether the two terms can be unified and if so give the substitutions that unify the terms.

(i)  R(X, f(X), b),      R(a, f(a), Y)                                                                   [1 mark]

(ii)  G(a, b, c),             G(X, Y, h(X))                                                                  [1 mark]

(e) Using only rules specified in the limited rule set given below, construct a Natural De-

duction proof of the following sequent:                                                             [6 marks]

P V Q,  P → Ax[S(x)],  (Q V R) → S(a)  上   S(a)

Natural Deduction Rule Set:

[ P ]na      [ Q ]nb             

  VIr             VIl                      VEn

  →E

Where P , Q, C are any formulae, φ(ν) is a formula containing variable ν and κ is any constant (so φ(κ) is the formula resulting from substituting κ in place of ν in φ(x)).

[Question 3 total: 20 marks]

Question 4

(a)  Consider the following regular expression intended to recognise URLs.

pattern  =  r’\bhttps?://(?:[a-z]+\ .*)+\b’

Example strings to be used for testing the regular expression patterns include:

This  is  NOT  a  valid URL  https://uk  and  I  should  NOT  use  it .

This  is  a  valid URL  http://www .good .com  and  I  can  use  it .

This  is  a  valid URL  https://uk .good .com  and  I  can  use  it .

This  is  a  valid URL  http://google .com  and  I  can  use  this  too .

This  is  a  valid URL  https://www1 .good .com  and  I  can  sometimes  use  this . This  is  a  valid URL  https://www1 .good2 .com  and  I may  also  use  this  too . This  is  a  valid URL  good .com  and  I might  use  it .

This  is  a  valid URL  https://www .also-good .com  and  I  sometimes  prefer  this  way . This  is  a  valid URL  http://also-good2 .com  that may  sometimes  be  useful .

The above list includes one false positive match for the regular expression. State which string is the false positive match and justify why this is the case.  Modify the regular expression to exclude this false positive match.                                                [5 marks]

(b)  The sentence

The  Go  champion  strikes  back  to  beat  Google’s  DeepMind  AI .

has been processed with a stemmer and a lemmatiser. The outputs are given below:

[Output1]

the  go  champ  strikes  back  to  beat  googl  ’  s  deepmind  ai  .

[Output2]

The  Go  champion  strike  back  to  beat  Google  ’  s  DeepMind  AI  .

For each output, state whether it is from a stemmer or a lemmatiser. Use the example to describe the difference between stemmers and lemmatisers.

[3 marks]

(c)  Two classification models, C1 and C2, have been trained on a data set of 768 instances of patient records with the aim to predict whether a patient would test positive or negative for diabetes. The confusion matrices of both classifiers are shown below:

(i) Which classifier is more accurate? Show your working.

(ii)  Compare the Precision and Recall of both classifiers for predicting positive cases

on the data set. Show your working.                                                        [4 marks]

(d) For each of the following pairs of machine learning concepts, briefly describe the most important difference between the two: