CA686/CA686I - Foundations of AI - 2023-24

Sample paper

Section 1: Multiple choice

Answer all 20 multiple-choice questions. (2 marks each.) Total 40 marks. No negative marking.
Only the filled-in boxes will be looked at. No additional commentary or analysis will be read.
Remember to hand up the multiple-choice answer sheet!

We have two exemplars:
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?
1. (a) Rain, (b) No rain
2. (a) No rain, (b) Rain
3. (a) No rain, (b) No rain
4. (a) Rain, (b) Rain
Neural Networks and GAs can both be seen as hill-climbing on an unknown landscape by taking a finite number of samples. Which of the following is the case:
1. Neural Networks make a random move, GAs make a random move.
2. Neural Networks make a random move, GAs make a directed move.
3. Neural Networks make a directed move, GAs make a directed move.
4. Neural Networks make a directed move, GAs make a random move.
Consider a heuristic for human mate choice:
Have a relationship with n partners of fitness > f
Marry the next partner you find of fitness > g
where fitness is ranked by the individual out of 10.
Which of the following values for n,f,g (respectively) makes the most sense?
1. 10, 5, 8
2. 0, 8, 3
3. 0, 0, 8
4. 0, 5, 8
5. 10, 8, 3
6. 10, 0, 8
We are learning to represent a function Q(x). The input x is a 100 dimensional vector. Each dimension is an integer from 1 to 10. Instead of a lookup table to representing the function Q(x), we use a neural network. We have 100 input units, n hidden units, and 1 output unit. How many real-numbered parameters (weights and thresholds) do we have to set aside memory for?
1. 100 n
2. 102 n
3. 102 n + 1
4. 101 n
5. 101 + n
6. 101 n + 1
7. 100 + n
8. 100 n + 1
The following is a correct ordering of AI methods, from lesser to greater autonomy:
1. Genetic Algorithms, Supervised Learning, Reinforcement Learning.
2. Supervised Learning, Genetic Algorithms, Reinforcement Learning.
3. Supervised Learning, Reinforcement Learning, Genetic Algorithms.
4. Genetic Algorithms, Reinforcement Learning, Supervised Learning.
5. Reinforcement Learning, Genetic Algorithms, Supervised Learning.
6. Reinforcement Learning, Supervised Learning, Genetic Algorithms.
A 3-dimensional AND gate perceptron looks like:
1. w₁=w₂=w₃=0, t=1
2. w₁=w₂=w₃=0, t=3
3. w₁=w₂=w₃=0, t=0
4. w₁=w₂=w₃=1, t=3
5. w₁=w₂=w₃=1, t=1
6. w₁=w₂=w₃=1, t=0
One of these is known to be false:
1. In the future, humans will live forever on earth in artificial bodies, regularly backing up their brains in order to cheat death.
2. Machines have beaten world-class humans at chess.
3. AI (the construction of intelligent machines) is impossible.
4. Machines have beaten world-class humans at tennis.
5. In the future, immortal humans will travel to distant stars.
6. In the future, intelligent machines will exterminate the human race.
7. AI is possible.
In machine evolution, let the probability of an individual reproducing be its fitness divided by the sum of fitnesses of all individuals. Then:
1. Fitness must be ≤ 0
2. Fitness must be > 0
3. Fitness can have any value except zero.
4. Fitness can have any value.
5. Fitness must be < 0
6. Fitness must be ≥ 0
In machine evolution, we have 4 individuals, where individual i has fitness f(i):
```
 i     1  2  3  4 
```
```
 f(i)  0  5  4  5 
```
If 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    1/2   0     1/2 		
```
2. ```
 0    1     0     1 			
```
3. ```
 0    5/14  4/14  5/14 		
```
4. ```
 0    0.9   0.1   0.9 		
```
5. ```
 0    1     0     0 			
```
6. ```
 1/4  1/4   1/4   1/4 		
```
The set of inequalities that define a perceptron to implement NOT are:
1. t ≤ w < 0
2. 0 < w ≤ t
3. w ≤ t < 0
4. 0 ≤ t < w
5. t < w ≤ 0
6. 0 < t ≤ w
7. w < t ≤ 0
8. 0 ≤ w < t
Which is the correct ordering of these search methods, from the least work for the human programmer to the most work for the human programmer?
1. Metaheuristic, Domain-specific heuristic, Random search
2. Domain-specific heuristic, Metaheuristic, Random search
3. Domain-specific heuristic, Random search, Metaheuristic
4. Random search, Domain-specific heuristic, Metaheuristic
5. Metaheuristic, Random search, Domain-specific heuristic
6. Random search, Metaheuristic, Domain-specific heuristic
We are learning to represent a function Q(x). The input x is a 100 dimensional vector. Each dimension is an integer from 1 to 10. One approach to representing this function would be to have a "lookup table" or array of entries, where we have one entry Q(x) for each input x. This array would be initially blank and we would fill it in by learning. The size of the array is:
1. 100
2. 1000
3. 1010
4. 110
5. 10¹⁰⁰
6. 10
7. 100¹⁰
Consider a heuristic for human mate choice:
Have a relationship with n partners of fitness > f
Marry the next partner you find of fitness > g
where fitness is ranked by the individual out of 10.
Which of the following values for n,f,g (respectively) makes the most sense?
1. 10, 5, 8
2. 10, 8, 3
3. 10, 0, 8
4. 100, 0, 8
5. 100, 5, 8
6. 100, 8, 3
A neural network has 1 input unit, n hidden units, and 1 output unit. The weights on the input layer are all the same: w_ij = W₁. The thresholds of the hidden units are all the same: t_j = T. The weights on the output layer are all the same: w_jk = W₂.
This network is equivalent to a network with 1 input unit, 1 hidden unit, and 1 output unit, where (w_ij, t_j, w_jk) =
1. (W₁, T, n W₂)
2. (W₁, T, W₂)
3. (n W₁, T, W₂)
4. (W₁, n T, n W₂)
5. (n W₁, T, n W₂)
6. (W₁, n T, W₂)
An upper bound on the game-tree complexity of Xs and Os is:
1. 9³
2. 3!
3. 9!
4. 9⁹
5. 3³
6. 3⁹
Given a line in 2-dimensional space:
a x + b y = c
Define 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
1. weights: -a, -b, threshold: -c
2. weights: a, b, threshold: -c
3. weights: -a, -b, threshold: c
4. weights: a, b, threshold: c
In machine evolution, each individual has a genotype encoded in binary format. We repeatedly select 2 parents to make 2 children by copying the 2 genotypes, with the possibility of mutation and crossover. Let p_c be the probability of crossover between the 2 genotypes. Let p_m be the probability that any bit in the genotype mutates when it is inherited.
Only one of the following carries out a serious search of the state space. All the others are constrained by whatever happens to be the initial population. i.e. Only one of the following can generate all possible genotypes, given enough time:
1. p_m=1, p_c=1
2. p_m=0, p_c=1
3. p_m=0, p_c=0
4. p_m=0.1, p_c=0
5. p_m=1, p_c=0
In trying to predict boxing matches by matching to the nearest exemplar, we have two exemplars:
Opponent height - 186 cm. Opponent weight - 90 kg. Result - I won.
Opponent height - 180 cm. Opponent weight - 95 kg. Result - I lost.
The question is:
Opponent height - 185 cm. Opponent weight - 94 kg. Will I win?
We predict by Hamming distance to the nearest exemplar, (a) with height in cm, (b) with height in m. What does it predict?
1. (a) I win, (b) I lose.
2. (a) I lose, (b) I lose.
3. (a) I win, (b) I win.
4. (a) I lose, (b) I win.
In a neural network, the network generates a (vector) output y = (y₁,..,y_n). We then tell it the "correct" output O = (O₁,..,O_n). Consider the following as a measure of "error" E:

An example showing that this is this a bad measure of the error is:
1. y = (5,0,5), O = (-5,0,5)
2. y = (5,0,-5), O = (-5,0,-5)
3. y = (5,0,-5), O = (-5,0,5)
4. y = (5,0,5), O = (-5,0,-5)
We do machine evolution as follows:

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:
1. We should pick according to probabilities rather than an absolute number.
2. There is no problem.
3. It will end up focused on one solution.
4. No new solution is ever made.
5. We lose the best solutions after finding them.
6. 100 is too small.
7. Too many solutions reproduce.
8. 10 is too small.

Section 2: Long questions

Answer 3 long questions out of 5. (20 marks each.) Total 60 marks.

Each question gives maximum number of sentences for the answer. Do not exceed this.
You might like to write your answers as rough work first to figure out what sentences to use. Make sure any rough work is crossed out.
Put your sentences as bullet points not a paragraph.
If you answer more than 3 questions, I will pick the best 3.

Question 1

[Total marks: 20]

1(a) Chatbots talk about the physical world but they have no experience of it. They might talk about "chairs" but they have never touched a chair or sat in a chair. Discuss whether this matters or not.
Maximum length: 2 sentences
[5 marks]

1(b) AI people love competitions. Why?
Maximum length: 2 sentences
[5 marks]

1(c) Machines beat human champions in chess but not in tennis. Suggest an explanation why, focusing entirely on the inputs to the system.
Maximum length: 3 sentences
[5 marks]

1(d) A typical machine learning algorithm converges to a solution in a fairly short time. Discuss whether human learning converges in a similar way or not.
Maximum length: 2 sentences
[5 marks]

Question 2
[Total marks: 20]

2(a) Mathematicians have long-standing tools to maximise functions and calculate function values.
What is different about the "functions" AI programs try to maximise and calculate values for?
Maximum length: 3 sentences
[5 marks]

2(b) Is this function y = f(x) easy or hard to maximise from exemplars?
f(1.0372) = 80.
f(5.6063) = 100.
f(x) = 0 for all other x.
Maximum length: 3 sentences
[5 marks]

2(c) Consider a heuristic search as follows:
Initialise with 20 random solutions. Repeat for many iterations: { Test the 20 solutions. Pick the best n. Make small changes in them to generate 20 new solutions. }
If n=19 what will this look like?
Maximum length: 2 sentences
[5 marks]

2(d) Discuss trying to maximise the following function from exemplars. Explain what would happen during learning.
Input x is a number. It does not include the clock time.
The function is defined as follows:
if ( x > 10 ) f(x) = 1 if clock time is PM. f(x) = -1 if clock time is AM. else if ( x < -10 ) f(x) = -1 if clock time is PM. f(x) = 1 if clock time is AM. else f(x) = 0

Maximum length: 3 sentences
[5 marks]

Question 3
[Total marks: 20]

3(a) In the N-puzzle problem, we use a heuristic (distance to goal estimate) as follows: h(n) = number of pieces out of place.
Is this heuristic optimistic or pessimistic? And how is that useful?
Maximum length: 2 sentences
[5 marks]

3(b) What would Best-first search with a constant heuristic evaluation function look like? (A heuristic evaluation function that outputted a constant number c.)
Maximum length: 2 sentences
[5 marks]

3(c) When a problem is represented as a State Space Search problem, a data structure is constructed to represent the entire "search tree". True or false?
Maximum length: 2 sentences
[5 marks]

3(d) In the N-puzzle problem, we use a heuristic (distance to goal estimate) as follows: h(n) = number of pieces out of place.
If h(x) = 1 then are we close to the goal?
Maximum length: 4 sentences
[5 marks]

Question 4
[Total marks: 20]

4(a) Consider the character recognition problem for handwriting.
If a character is isolated from other characters, there may be a problem with missing inputs when we try to recognise it. Explain.
Maximum length: 3 sentences
[5 marks]

4(b) A mobile robot has Input state = (angle of direction of nearest wall, velocity value). Output behaviour = one of (turn left, turn right, stop, keep going).
The Input state is clearly missing some information. What are the consequences of this missing information?
Maximum length: 3 sentences
[5 marks]

4(c) In neural networks, why is it not a constraint to say that all networks are fully connected?
Maximum length: 1 sentence
[5 marks]

4(d) The following is the perceptron learning rule. We have multi-dimensional input, where each component of the input I_i is binary 0 or 1. It produces output y = 0 or 1. We show it the "correct" output O = 0 or 1. We modify the weights and the threshold by the rules:
w_i := w_i + C (O-y) I_i

t := t - C (O-y)

where C is some positive constant.
Question: What happens on input links with value zero?
Maximum length: 1 sentence

[5 marks]

Question 5
[Total marks: 20]

5(a) In a genetic algorithm (GA), let p_c be the probability of crossover.
What would happen if p_c = 1?
Maximum length: 2 sentences
[5 marks]

5(b) In a genetic algorithm (GA), let p_m be the probability that any bit in the chromosome mutates at the point where it is inherited from the parent by the child. Let the chromosome be binary, so that mutation means a bit flip.
What would happen if p_m = 0 (but you still had crossover)?
Maximum length: 4 sentences
[5 marks]

5(c) 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".
Show that as T -> infinity we tend to pick a random individual, no matter what the fitnesses.
Maximum length: 2 sentences

[5 marks]

5(d) In a genetic algorithm: What would happen if rather than picking the fittest, you define a minimum fitness that individuals have to reach in order to reproduce?
Maximum length: 1 sentence
[5 marks]

CA686/CA686I

Answer sheet

Black out the square that matches the correct answer.

Exam No:_____________________

Class:_____________________

Seat No:_____________________

Question	1.	2.	3.	4.	5.	6.	7.	8.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20