1. a. Explain the following axiom of utility theory. What does it mean? Illustrate your answer with an example.
((↵ ) and ( )) ! 9p[p, ↵; 1 p, ] ⇠
b. Considering the following labelled graph. For each arc from x to y, the label is the
cost of travelling from x to y. B2G2L
1432
A5C8H I3M 221
D1E1J4 4
F5K
i. Use breadth-first search to find the shortest path from A to M. Give the search
[5 marks]
tree, and briefly explain how you obtain the shortest path.
[3 marks]
ii. Use the A⇤ algorithm to find the shortest path from A to M . Assume the heuris- tic function h is such that h(x) = 1 for all nodes x apart from M. Give the
search tree, and briefly explain how you obtain the shortest path.
iii. Is the A⇤ algorithm with the heuristic function used in part ii guaranteed to find
an optimal solution on this graph? If so, why? If not, why not?
COMP0024 1 TURN OVER
[6 marks]
[2 marks]
c. For each of the following knowledgebases, state whether the knowledgebase is con- sistent or inconsistent. If it is consistent, give a satisfying model of the knowledge- base. If it is inconsistent, give a proof that it is inconsistent.
1 ={(((↵! )^(↵!¬ ))_ ),(↵_ )! ,¬ }
2 ={((↵! )^(¬↵! )),¬¬ _¬(¬ ^¬ ), !¬ , !¬ } 3 ={((↵! )^(¬ !¬↵)), _¬ _¬ , _¬↵,¬ _¬ }
[9 marks]
d. Let h ,↵i and h , i be arguments. If h ,↵i is a direct undercut of h , i, is it the case that h , ↵i undercuts h , i? Give a proof, or counterexample, as appropriate. Start your answer with definitions for undercut and direct undercut.
[8 marks]
e. For each of the following graphs, give each of the preferred extensions, grounded extensions, and stable extensions (if they exist).
AD
[9 marks]
ABC CBA
BC
G1 G2 G3
f. For the ID3 algorithm, consider a set of examples T to be classified and a set of attributes A. Assume a binary classification and binary attributes. For an attribute 2 A, what is that minimum value for gain( ) and what is that maximum value for gain( )? Give a clear and precise explanation in terms of the I and E functions, and the numbers of positive and negative examples in T .
[8 marks] [Total for Question 3: 50 marks]
COMP0024 2 CONTINUED
2.
(a) A boolean function F(x1, x2, x3) is defined by the truth table below:
x1
x2
x3
F(x1, x2, x3)
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
0
(i) In a two-layer binary decision neuron (BDN) net realisation of this function, based on the expression of the above definition in first canonical (‘sum of products’) form, how many hidden units would be needed?
[1 mark]
(ii) Write down an algebraic expression in product form for each of the functions that would need to be performed by these hidden units.
[4 marks]
(iii) Using the constructive rule derived from digital circuit theory, which is based on the representation of a Boolean function in first canonical form, obtain for each hidden unit a weight vector $ = ($’, $), $*) and a threshold s that would allow the required function to be performed.
[4 marks]
(b) A neuron receives four external inputs 10, -20, 4 and -6, with corresponding synaptic weights 0.8, 0.2, -1.0 and -0.5. Assuming a threshold of zero in each case, calculate the output of the neuron under the following circumstances:
(i) the neuron is linear (no output transform applied);
(ii) the neuron is represented by a McCullough-Pitts model;
(iii) the neuron uses a sigmoidal firing function;
[2 marks] [2 marks] [2 marks]
COMP0024 3
TURN OVER
(c) It is desired to store the two binary patterns (1,0,1) and (0,1,0) in a 3-node Hopfield net. Using the version of the Hopfield parameter setting rule that calculates values for the neuron thresholds as well for their weights:
(i) calculate an algebraic form for the Hopfield energy function 4(5′, 5), 5*); [5 marks]
(ii) draw a state transition diagram for the system, labelling all transitions with their probabilities, and showing the energy levels of the system;
[9 marks]
(iii) comment on the content addressable memory (CAM) properties of the system.
[3 marks]
(d) Consider the reinforcement task for a single 2-input ARP unit defined by the truth table
5′ 5) 6T(5) 6′(5)
0 0 0.7 0.2 0 1 0.4 0.2 1 0 0.8 0.3 1 1 0.3 0.7
where 67(5) is the probability of the neuron receiving a reward for action y in input context x and the neuron has the initial parameter vector w = (0,0,0).
In this example the probabilities of encountering patterns (0,0) and (1,1) are equal. The probabilities of encountering (0,1) and (1,0) are also equal. However (0,0) or (1,1) are three times as likely to be seen as either of the others.
(i) Calculate the probabilities of encountering each of the four patterns.
[4 marks]
(ii) What is the value of the initial performance measure Minit?
(iii) What is the value of the maximal performance measure Mmax?
[3 marks] [3 marks]
COMP0024 4
CONTINUED
(e) One possible use of an mxm Kohonen map is as a preprocessor for data that will be subsequently be input to a multilayer perceptron (MLP) classifier, with the values passed on to the MLP after Kohonen training being the m2 activation values (weighted sums of inputs, not including in this case a bias) of the Kohonen neurons.
(i)
(ii)
What would you consider to be the advantages of such a two-stage hybrid system, and on what kinds of data would you expect it to perform best?
[4 marks]
Suppose such an approach was used for 25-dimensional input data, these being mapped initially on to a 10×10 Kohonen grid before the Kohonen neuron activations are used as input to a subsequent MLP. Explain why the benefits of a hybrid system might in this case not be seen, and why such a system might in fact perform worse than an MLP alone.
END OF QUESTIONS
[4 marks] [Total for Question 2: 50 marks]
COMP0024
5
TURN OVER