EXAM COMP9414 23T2

To be consider before starting:

•    The time to complete the exam is 2 hours.

•    The starting time is 9:30am and finishing time is 11:30am

•    The exam contains 13 multiple-choice questions.

•    11 questions give 4 marks. Only 2 questions give 8 marks.

•    Total marks are 60.

The summary of questions is as follows:

Topic	Question	Marks
Search	IDDFS	4
Search	A*	4
Reinforcement learning	Softmax	4
Reinforcement learning	Returns	4
Neural networks	Single-layer perceptron	4
Neural networks	Neural design	4
Optimization	Tabu search	8
Computer vision	Averaging method	4
Computer vision	Split-and-merge method	4
Language processing	Bigram probability	4
Language processing	Minimum edit distance	4
Uncertain reasoning	Bayes nets	8
Uncertain reasoning	Fuzzy logic	4

TOPIC: Search – Question: IDDFS [4 marks]

Consider the following road map with distances indicated on lines drawn between towns (the map is not to scale). The straight-line distances form. each town to H are listed in the table.

What order are nodes expanded by iterative deepening depth first search when searching for a path between A and H? Where there is choice of nodes, take the first one by alphabetical ordering.

Assume the search algorithm includes cycle checking along a path, Tree-Search-IDDFS. Stop the search once the goal node is expanded.

a. A ABCD ABFCDEDCGH

b. A ABCD ABFCDH

c. A ABCD ABCDE ABFCDH

d. A ABCD ABFH

e. A ABCD ABFCDEGH

TOPIC: Search – Question: A* [4 marks]

Consider the following road map with distances indicated on lines drawn between towns (the map is not to scale). The straight-line distances form. each town to H are listed in the table.

What order are nodes expanded by A* search using the straight-line distances to H in the table as the heuristic function, when searching for a path between A and H? Where there is choice of nodes, take  the first one by alphabetical ordering. Stop the search once the goal node is expanded.

a. ADH

b. ABFH

c. ABCDEFGH

d. ACDH

e. ACEGH

TOPIC: Reinforcement learning – Question: Softmax [4 marks]

Consider an RL agent navigating a gridworld, with four possible action: up (U), down (D), left (L), and  right (R). The agent uses the softmax action selection method. Remember this method computes the probability of selecting an action using a Boltzmann distribution, as follows:

In a particular given state St, the agent has the following Q-values to decide what action to take next:

Q(U)	Q(D)	Q(L)	Q(R)
0.7698	0.6501	0.0252	-0.7698

What would be the action selected by the agent if the temperature T used is 0.9 and the random number drawn is 0.9021.

TOPIC: Reinforcement learning – Question: Returns [4 marks]

Consider the return equation shown below with a discount factor γ = 0.9 and a reward sequence of 7, 3, 1, 10, -10. The return G0  is equal to:

TOPIC: Neural networks – Question: Single-layer perceptron [4 marks]

Consider the training data shown in the following Table to divide the space. Using the single-layer perceptron learning rule with a learning rate α = 1.0 and initial weights w1  = 1, w2  = 0, and b = 1.5, what would be the final value of the weight after convergence?

Training example	x1	x2	Class
a	0.0	0.0	1
b	1.0	2.0	-1
c	2.0	-1.0	-1
d	-2.0	1.0	1

TOPIC: Neural networks – Question: Neural design [4 marks]

Taking into account the good practices for neural design, what would be the recommended number of neurons in the hidden layer for a multilayer perceptron to approximate a non-linear function of 6 inputs and 6 outputs if you have available 10,000 samples? Consider 60% data for training, 30% for  test, and 10% for generalization.

TOPIC: Optimization – Question: Tabu Search [8 marks]

Consider an optimization problem and a metaheuristic to find an approximate solution. The fitness function to evaluate candidate solutions is defined as y = x2. You are asked to implement the Tabu Search algorithm shown in the code below, taking into account the following:

•    For the initial solution, use a random number approximately between -10 and 10 from a standard normal distribution (i.e., μ=0, σ=1).

•    For the Tabu List use a numpy array.

•    The neighbourhood size is equal to 50 for each iteration.

•    Each neighbour is computed based on the current best solution as: best solution + a random number from a standard normal distribution.

•    The termination criterion is to find a solution with fitness lower than 1e-10.

•    Use a seed for random numbers equal to 55.

What would be the returned solution by the algorithm??

TOPIC: Computer vision – Question: Averaging method [4 marks]

Consider the binary image with dimension 8x7 shown below. The image can be represented in a 2- dimensional array using 1’s and 0’s as shown in the table below. Using the averaging method (creating a new image) with a threshold ε = 2 and a 3x3 sliding window, what would be the resulting image?

TOPIC: Computer vision – Question: Split-and-merge method [4 marks]

Consider the following 8x8 picture matrix.

Using the split-and-merge method for region finding, two possible solutions with ε <= 1 might be:

Which of the previous are valid solutions for the split-and-merge method with ε <= 1?

TOPIC: Language processing – Question: Bigram probability [4 marks]

The bigram probability is computed as:

Considering the following mini corpus containing 5 sentences:

<s> There is not much time until the next weekend </s>

<s> I love spending weekends at the beach </s>

<s> Next weekend I will go to the cinema </s>

<s> I went the last weekend at the stadium </s>

<s> Maybe I am thinking too much about the weekend </s>

What is the bigram probability P(at|weekend)?

TOPIC: Language processing – Question: Minimum edit distance [4 marks]

In a human-robot interaction scenario, a cleaning-table robot might be instructed by a human trainer with different advice, such as: get the cup, grasp cup, move left, move right, clean table, do task, among others. As the advice is given using an automatic speech recognition system, sometimes the received sentence might be wrongly identified.

We are particularly interested in knowing the minimum edit distance between two sentences: grasp cup and do task. Assuming insertion and deletion costs equal to 1 and substitution equal to 2, determine the Levenshtein distance for the two strings.

TOPIC: Uncertain reasoning – Question: Bayes network [8 marks]

Consider the following random variables:

rsp: regular sport practice.

bd: balanced diet.

hbp: high blood pressure.

sm: smoker.

mi: has suffered a myocardial infarction.

The causal relationships and the probabilistic knowledge are shown in the Bayes network below.

Using the network, compute the probability of being a smoker given that a myocardial infarction has been suffered and no regular sport is practised, i.e., P(SM|MI, ~RSP).

TOPIC: Uncertain reasoning – Question: Fuzzy logic [4 marks]

In a streaming platform, the analysis team is performing a study on how a “normal customer” uses

the platform. Based on the number of hours each customer uses the platform, they have ordered the customers and defined a fuzzy set for normal customers using a trapezoid membership function. The  parameters for the membership function are [5, 20, 60, 95] which means:

•    Customers in the lowest 5% of use have a membership equal to zero.

•    Customers between 5% and 20% of use have an increasing membership from zero to one.

•    Customers between 20% and 60% of use have a membership equal to one.

•    Customers between 60% and 95% of use have a decreasing membership from one to zero.

•    Customers in the highest 5% of use (between 95% and 100%) have a membership equal to zero.

For a customer located at position 72.5% of use compared with other customers, what would be the membership value?