Only the filledin boxes will be looked at. No additional commentary or analysis will be read.
Start with 100 random solutions.
Repeat:
Test all 100 for fitness.
Pick the 10 best.
Make 10 copies of each to construct the next generation.
Loop again.
The problem with this is:
i 1 2 3 4
f(i) 0 1 2 1If we use a "Soft max" probability distribution with a "temperature" parameter T to choose who reproduces, then as T > infinity the probability of each individual reproducing goes to:
1 0 0 0
1/4 1/4 1/4 1/4
0 1 1 1
0 0 1 0
0 1/4 1/2 1/4
0 1 0 1
0 1/2 0 1/2
Temperature 22 degrees, pressure 1000 mb. Rain.
Temperature 15 degrees, pressure 990 mb. No rain.
Then the question is:
Temperature 17 degrees, pressure 1010 mb. Will there be rain?
We predict by Hamming distance to the nearest exemplar, (a) with pressure in millibars, (b) with pressure in bars. What does it predict?
y = a x + bDefine a perceptron that receives x and y as input and fires if and only if the point is on this side of the line:
y ≤ a x + b
i 1 2 3 4
f(i) 0 1 2 1If we use a "Soft max" probability distribution with a "temperature" parameter T to choose who reproduces, then as T > 0 the probability of each individual reproducing goes to:
1/4 1/4 1/4 1/4
0 1/2 0 1/2
1 0 0 0
0 1/4 1/2 1/4
0 1 1 1
0 0 1 0
0 1 0 1
a x + b y = cDefine a perceptron that receives x and y as input and fires if and only if the point is on this side of the line:
a x + b y ≤ c
Answer 3 of the 5 long questions. 20 marks each. Total 60 marks.
Question 1  [Total marks: 20] 
1(a) 
Imagine a heuristic search to maximise a function f(x) by trial and error.
The heuristic repeatedly proposes a value for x and receives a value for f(x).

[4 marks] 
1(b) 

[6 marks] 
1(c)  Invent a heuristic for either car buying or job hunting. Explain how it may fail.  [4 marks] 
1(d) 
Consider searching a "search tree":

[6 marks] 
Question 2  [Total marks: 20] 
2(a) 
Chess has a branching factor of about 35.
The average length of a chess game is about 80 plies.

[3 marks] 
2(b) 
Consider breadthfirst search:

[8 marks] 
2(c) 
Consider how heuristic search picks the next state to examine:

[3 marks] 
2(d) 
Consider using Bestfirst search:

[6 marks] 
Question 3  [Total marks: 20] 
3(a) 

[5 marks] 
3(b) 
In a genetic algorithm (GA),
let the probability of an individual being picked for reproduction be:
p = my fitness  sum of fitnesses of all creatures

[3 marks] 
3(c) 
In a genetic algorithm (GA),
let p_{c} be the probability of crossover.

[6 marks] 
3(d) 
In a genetic algorithm (GA),
let each individual i have fitness f(i),
and let its probability of reproducing, p(i), be:
where T is the "temperature".
i 1 2 3 4 f(i) 0 0 0 1

[6 marks] 
Question 4  [Total marks: 20] 
4(a) 
Consider the character recognition problem for handwriting.

[4 marks] 
4(b) 
You are using the Hamming distance
as a simple distance metric to recognise faces.
Inputs are images of 10 pixels by 10 pixels.
Pixels are black or white.

[8 marks] 
4(c)  Given exemplars:
Answer the following questions.Temperature 22 degrees. No rain. Temperature 15 degrees. Rain.

[4 marks] 
4(d) 

[4 marks] 
Question 5  [Total marks: 20] 
5(a) 

[6 marks] 
5(b) 
Define the 2 perceptrons that fire for the 2 sides of the line:
y = a x + b 
[3 marks] 
5(c) 
In the following multilayer network, the threshold values are circled.
The weights are listed along each link.
The input units take values 0 or 1.

[5 marks] 
5(d) 
Using the notation on this course, here is the backprop rule for the output layer
of a multilayer network:

[6 marks] 
Class:_____________________
Seat No:_____________________

