A popular quiz show

Description

INSTRUCTIONS
a. Answer all three questions
b. Each question carries 20 marks
This assessment consists of exam-style questions and you should answer as you
would in an exam. As such, citations of sources are not expected, but your answers
should be from your own memory and understanding and significant stretches of text
should not be taken verbatim from sources. Any illustrations or diagrams you include
should be original (hand or computer drawn). You may word-process your answers,
or hand-write and scan them. In either case, please return your answers as a single
PDF. If you handwrite, please make sure the pages are legible, the right way up and
in the right order. Your submission should be your own unaided work. While you are
encouraged to work with your peers to understand the content of the course while
revising, once you have seen the questions you should avoid any further discussion
until you have submitted your results. You must submit your completed assessment
on MMS within 8 hours of you downloading the exam. Assuming you have revised the
module contents beforehand, answering the questions should take no more than three
hours.
Page 2 of 6
1. Learning
(a) Consider a round of the popular quiz show “Who Wants to Be a
Millionaire?” A contestant is presented with a question and four possible
answers, call them A, B, C, and D, only one of which is correct.
Unfortunately, in our case, it so happens that the unlucky contestant is
entirely ignorant on the topic at the root of the question, which makes the
selection of the correct answer a random guess. Compute the entropy
associated with this choice and provide an intuitive explanation of the
value you get. [4 marks]
(b) Being unwilling to risk an entirely random choice, our contestant from (a)
decides to use the “Phone a friend” lifeline. The friend, who can be
considered a reliable knowledge source, is not entirely certain what the
correct answer is, but provides the following probabilities associated with
the four answers: 70%, 20%, 5%, and 5% respectively. Compute the entropy
associated with the new choice that the contestant is presented with and
provide an intuitive explanation of the value you get. [4 marks]
(c) Still cautious, the contestant decides to use another lifeline, 50-50, whereby
two incorrect choices, randomly selected by a computer, are eliminated.
These end up being choices B and D. Compute the entropy associated with
the new choice that the contestant is presented with and provide an
intuitive explanation of the value you get. [4 marks]
(d) Entropy is often used as the basis for a neural network loss/error function
in the form:
𝐸 = −∑𝑡𝑗
ln 𝑜𝑗
𝑗
where 𝑡𝑗
is the desired target output of neuron 𝑗 and 𝑜𝑗
is its actual output.
If the activation function of a neuron in the last output layer is:
𝑜𝑗 =
𝑒
𝑧𝑗
∑ 𝑒
𝑧𝑖
𝑖
where 𝑧𝑖
is the output of the neuron 𝑖 in the penultimate layer, derive the
expression for the gradient of the error function with respect to 𝑧𝑖 and
explain how this result would be used in backpropagation based training
of the network. [8 marks]
[Total marks 20]
Page 3 of 6
2. Uncertainty
(a) Consider the following Bayesian Network
(i) Assume all random variables are binary, how many parameters are
needed to specify the conditional probability tables of the Bayesian
network?
[2 marks]
(ii) Factor the joint probability distribution based on the network.
[2 marks]
(b) Consider the following Bayesian Network, where variables A-D are all
binary random variables.
(i) What is D’s Markov blanket?
[1 mark]
(ii) What is the probability P(C=true|B=false)? Be sure to show the
intermediate steps.
[2 marks]
Page 4 of 6
(c) Given the following problem description,
After being infected with COVID, patients will carry COVID virus in their bodies.
Test method A’s accuracy depends on the virus load of the testee and also depends
on how the sample is collected. It is assumed that virus load can be categorised into
zero, low, medium, and high (four categories); and test sample can be taken either
by the testee themselves or by clinic staff. You should also assume a test result can
either by positive or negative. One wants to know what is the probability that they
are infected with COVID given a test result.
Design a Bayesian Network for this problem. State any assumptions made
clearly. How many parameters are needed for your model? You do not
need to specify the exact conditional probability tables (CPTs). [5 marks]
(d) Your friend has two coins: one fair and the other is bent. You do not know
the probability of a head turning up for the bent coin. He always uses the
fair coin at the beginning and switches to the bent coin after an unknown
number of coin tosses, then he will switch back to the normal coin after
another few rounds of coin tosses, which is also unknown. Assume N coin
tosses in total have been tossed, with all N results recorded.
(i) Design a Bayesian Network that is suitable to solve the problem. You
need to specify the CPTs for the network. State any assumptions
made.
[4 marks]
(ii) Outline how Gibbs Sampling can be used to infer both the unknown
switching times and the unknown probability of the bent coin. You
only need to use pseudo code when describing the algorithm.
[4 marks]
[Total marks 20]
Page 5 of 6
3. Searching
(a) Consider the wolf, goat, and cabbage problem shown below:
A farmer wants to cross a river and take with him a wolf, a goat, and a cabbage.
There is a boat that can fit himself plus either the wolf, the goat, or the cabbage.
If the wolf and the goat are alone on one shore, the wolf will eat the goat. If the
goat and the cabbage are alone on the shore, the goat will eat the cabbage. How
can the farmer bring the wolf, the goat, and the cabbage across the river?
(i) What is the size of the state space? What is the branching factor for
this problem?
[4 marks]
(ii) Suppose the farmer has upgraded his boat which can fit himself plus
two items now. What is the size of the state space and branching factor
for this problem? What is the minimum number of crossings needed?
[6 marks]
(b) After graduating from St Andrews, you have relocated to a new city to start
your career. You want to know how to get from your home at S to your
workplace U. Always use alphabetical order to break ties when deciding
the order in which to expand a node.
(i) Consider the state space graph given below. Using breadth-first
search with an extended list, draw the search tree that is explored by
the search. What is the final path that is found from S to U? Be sure
to show your reasoning and any calculations carried out.
[4 marks]
(ii) Some streets have more traffic than others. Your neighbour kindly
provides you with the information about the travel time on each
Page 6 of 6
street, i.e. the number of minutes needed to traverse between the
nodes (they are labelled on the “streets”, or edges). On top of it, he
also provided you estimates of distance heuristics between each node
to the destination U. The estimates are labelled above each node. For
example, the estimated distance from C to U is 10.
You are going to use A* search algorithm without an extended list
and a heuristic distance (as provided) to find a path from S to U. Draw
the search tree and number each node as it is expanded, from 1 to n.
Show the path you have found. Can you find a better path? Be sure to
show your reasoning and any calculations carried out.
[6 marks]
[Total marks 20]
*** END OF PAPER ***