Question/Answer Booklet COMPSCI 367
Student ID
Page 1 of 23
THE UNIVERSITY OF AUCKLAND
SEMESTER TWO 2020
Campus: City
COMPUTER SCIENCE
Artificial Intelligence
(Time Allowed: TWO hours)
NOTE:
This exam is out of 100 marks.
Attempt ALL questions.
Write your answers in the space provided in this booklet. There is space at the back for
answers that overflow the allotted space.
The use of calculators is NOT permitted.
Surname
Forenames
Student ID
Login (UPI)
Part Mark Marks Available
A 28
B 18
C 31
D 23
Total 100
Question/Answer Booklet COMPSCI 367
Student ID
Page 2 of 23
THIS PAGE HAS BEEN INTENTIONALLY LEFT BLANK.
Question/Answer Booklet COMPSCI 367
Student ID
Page 3 of 23
PART A: Pat Riddle’s material
Question 1
Why is it called a Markov Decision Process? What is the importance of the word “Markov”
what does it bring to the definition?
[2 marks]
Question 2
What are the main components of a Markov Decision Process? Which of these components
are the same as a classical planning problem and which are different?
[3 marks]
Question 3
What are the 3 main variables that you can calculate for a Markov Decision process? What
are the differences between them and which is most important?
[3 marks]
Question/Answer Booklet COMPSCI 367
Student ID
Page 4 of 23
Question 4
What are the main components of a Constraint Satisfaction Problem? Give an example of
each using one of the constraint satisfaction problems from assignment 3.
[3 marks]
Question 5
One of the main techniques used by constraint satisfaction solvers is ordering. What are the
two things that they order and in what order do they order them?
[3 marks]
Question/Answer Booklet COMPSCI 367
Student ID
Page 5 of 23
Question 6
In assignment 3, the iterative improvement algorithm did better than the constraint
satisfaction algorithm for some problems and not for others. Why is this the case? What is it
about those problems that make them more suitable for certain algorithms?
[3 marks]
Question 7
What kind of local search is genetic algorithm doing? Can you explain what it does in terms
of other local search algorithms?
[4 marks]
Question/Answer Booklet COMPSCI 367
Student ID
Page 6 of 23
Question 8
Why is Markov Decision Processes taught as an Expectimax search? How is what the
Expectimax search is doing the same as what the MDP is doing?
[4 marks]
Question 9
Explain what the differences are in the values for the Alpha-beta pruning and for Minimax
results? What is the main advantage of the Alpha-beta pruning algorithm?
[3 marks]
Question/Answer Booklet COMPSCI 367
Student ID
Page 7 of 23
PART B: Mike Barley’s material
Question 10
Given a unit-cost domain problem, P, with an optimal cost solution of 20, a front-to-end
heuristic h, whose max heuristic value is 9 and whose average heuristic value for this
problem is 7, and the GBFHS search algorithm with a split function that guarantees it
“meets-in-the-middle”. Explain why h is useless as a heuristic (i.e., is no better than blind)
for solving P. Specifically, what must be true of h’s value for GBFHS to expand a node?
[2 mark]
Question 11
Given a problem, P, in a unit-cost domain, where the forward and backward average
branching factor is b, the optimal solution cost for P is d, and an admissible and consistent
heuristic h, with an average value of x. For the sub-questions below, please specify a
formula.
(A) Approximately how many nodes will be expanded by A* using h?
[1 mark]
(B) Approximately how many nodes will be expanded by a blind bidirectional search
algorithm?
[1 mark]
Question/Answer Booklet COMPSCI 367
Student ID
Page 8 of 23
(C) Under what conditions will A* expand fewer nodes than the blind bidirectional search
algorithm?
[1 mark]
Question 12
Given the problem above, with the initial state on the left and the goal on the right.
(A) Describe the initial state in the state description language. Use the predicates
on(
table.
[1.5 marks]
(B) describe the goal using the goal description language.
[1.5 marks]
Question/Answer Booklet COMPSCI 367
Student ID
Page 9 of 23
Question 13
Given a PDDL domain that only has the following operator schema:
(:action move :parameters (?x ?y)
:precondition
(and (room ?x) (room ?y) (neq ?x ?y) (at-robby ?x))
:effect
(and (at-robby ?y) (not (at-robby ?x))))
Which predicates are:
(A) static:
(B) fluent:
(C) object-level:
(D) meta-level:
[2 marks]
(A)
(B)
(C)
(D)
Question 14
Explain why meta-level predicates are needed, give an example.
[3 marks]
Question 15
In our lecture on progression planning, we defined all of the predicates, except for
applicationResult(Step, Sit, NewSit). The effects of a step are expressed in the update
language.
(A) What type of literals are allowed in a step’s effects?
[1.5 marks]
Question/Answer Booklet COMPSCI 367
Student ID
Page 10 of 23
(B) Which language is used to express a step’s preconditions?
[1.5 marks]
(C) Clearly express the relationship between the resulting child state (NewSit) and the
parent state (Sit) and the effects of the step (Step). You can assume that “Effects” is
the list of effects for Step and can freely use it in your definition. You do not have to
use Prolog, you can use logic or English. Your definition should be of the following
form: for all literals L, L is in NewSit if and only if … Where you replace the ellipsis
(i.e., “…”) with your definition. Remember the effects of an operator are normally
expressed in an update language, you need to describe how to accomplish the effect’s
update.
[2 marks]
Question/Answer Booklet COMPSCI 367
Student ID
Page 11 of 23
PART C: Ian Watson’s material
Question 16
Data-driven and Goal-driven are two different types of rule-based reasoning. Describe the
differences between them and give an example where you would use each.
[5 marks]
Question 17
Describe the algorithm most commonly used in Case-Based Reasoning. You may use a
formula or a textual description.
[6 marks]
Question/Answer Booklet COMPSCI 367
Student ID
Page 12 of 23
Question 18
Using the Conceptual Graph notation create an ontology to describe going to a rock concert.
Your ontology must include at least:
● Traveling to the venue
● Buying a ticket for the show
You must use the linear form (textual) of conceptual graph, drawings of the conceptual graph
will earn no marks.
[10 marks]
Question/Answer Booklet COMPSCI 367
Student ID
Page 13 of 23
Question 19
(A) Define a CLIPS rule for the following pseudocode
IF the animal is a dog
THEN the sound made is woof
[3 marks]
(B) What happens if you define two rules in CLIPS both called “dog”?
[2 marks]
Question/Answer Booklet COMPSCI 367
Student ID
Page 14 of 23
(C) Define a CLIPS template to describe a car. Your car template should be able to handle
the following information:
ID: registration number
Name: car name
Type: sedan, sports, station_wagon, ute…
Manufacturer: Ford, Holden, Toyota, Honda…
Owner: name of owner
Transmission: manual, automatic
Engine: petrol, diesel, hybrid, electric
Engine Size: size in litres
Age: age in years
Under-warranty: no, yes
[5 marks]
Question/Answer Booklet COMPSCI 367
Student ID
Page 15 of 23
THIS PAGE HAS BEEN INTENTIONALLY LEFT BLANK.
Question/Answer Booklet COMPSCI 367
Student ID
Page 16 of 23
PART D: Michael Witbrock’s material
This table supplies logical symbols that you can cut and paste when answering questions
in this section.
Implication ⇒
Biconditional ⇔
Negation ¬
Conjunction ∧
Disjunction
(inclusive)
∨
Universal Quantifier ∀
Existential
Quantifier
∃
Question 20
The table for part D defines logical operators you can cut and paste. The table below defines
additional logical predicates, functions, and constants.
Predicate Example Use Meaning of Example
> 3 > 2 3 is numerically greater than 2
City(x) City(Xi’an) Xi’an is a city
InRegion(x,y) InRegion(Accra, Ghana) Accra is in Ghana
Function Example Use Meaning of Example
population(x) population(Christchurch) The population of Christchurch, 381599
Constant Example Use Meaning of Example
Auckland population(Auckland) The population of Auckland, an integer
Aotearoa population(Aotearoa) The population of Aoteraroa, an integer around
5 million
Question/Answer Booklet COMPSCI 367
Student ID
Page 17 of 23
Using the symbols and terms in the tables, write a ground first order logic formula that says
that Auckland is a city in Aotearoa with a population over one million.
(A) Write the ground first order logic formula in the box. Cut and paste logical symbols
from the table if needed.
[2 marks]
(B) Can the ground first order formula in your answer also be accurately represented
within the syntax and semantics of propositional logic? (Yes or No)
Write “Yes” or “No” in the box.
[1 marks]
(C) Using the same predicates, constants and function defined above, write a first order
rule that specifies that no city in Aotearoa has a greater size than Auckland.
Write the first order logic formula representing your rule in the box. Cut and paste logical
symbols from the table for section D if needed.
[4 marks]
Question/Answer Booklet COMPSCI 367
Student ID
Page 18 of 23
Question 21
Suppose you have the following ProbLog program, which models two ten-sided dice.
1/10::lands(D,S) :- die(D), between(1,10,S) %Disjunction
die(a). die(b).
throw(N, D1, D2) :- lands(D1,N1), lands(D2, N2), N is N1 + N2.
query(throw(19,a,b)).
(A) This program, when it is run, calculates the probability of throwing a 19 (this can
be done by throwing a=9,b=10 or a=10,b=9), it calculates a probability of 0.0199
for throw(19,a,b). What is the formula for soft-or that produces this estimate
for P((a9∧b10)∨(a10 ∧b9)). The formula you write will include P(a9∧b10) and P(a10
∧b9). Write the formula in the box. Cut and paste logical symbols from the
symbol table or from the question if needed.
[2 marks]
(B) Suppose we replace the line labelled with the comment % Disjunction with the
line:
1/10::lands(D,1); 1/10::lands(D,2); 1/10::lands(D,3); 1/10::lands(D,4);
1/10::lands(D,5); 1/10::lands(D,6); 1/10::lands(D,7); 1/10::lands(D,8);
1/10::lands(D,9); 1/10::lands(D,10) :- die(D).
This is an annotated disjunction. What value for the probability of throw(19,a,b)will the
program calculate now? Write the probability in the box.
[1 mark]
Question/Answer Booklet COMPSCI 367
Student ID
Page 19 of 23
(C) Explain in one or two sentences why the value calculated using the annotated
disjunction would be correct for actual physical unbiased ten-sided dice. Write your
explanation in the box.
[2 marks]
(D) Suppose that instead of two-dice throws, we want to allow for three-dice throws. i.e.
die(a). die(b). die(c). and test for them using a suitable query. i.e.
query(throw(19,a,b,c)).
How would you modify the bolded line in the version of our partly modified ProbLog
program given below, which uses annotated disjunction, so that it allows three-dice throws,
and can be used with the query “query(throw(19,a,b,c))” ?
1/10::lands(D,1); 1/10::lands(D,2); 1/10::lands(D,3); 1/10::lands(D,4);
1/10::lands(D,5); 1/10::lands(D,6); 1/10::lands(D,7); 1/10::lands(D,8);
1/10::lands(D,9); 1/10::lands(D,10) :- die(D).
die(a). die(b). die(c).
throw(N, D1, D2) :- lands(D1,N1), lands(D2, N2), N is N1 + N2.
query(throw(19,a,b,c)).
Write your modified version of that bolded line in the box.
[2 marks]
The probability 0.069 would be calculated by the new program query(throw(19,a,b,c)).
What would the program calculate for query(throw(30,a,b,c)). ?
Write the expected result of that query in the box.
[1 mark]
Question/Answer Booklet COMPSCI 367
Student ID
Page 20 of 23
Question 22
Suppose that you are training a very simple naïve Bayes sentiment classifier, with unknown
word removal and add-one (Lapace) smoothing. You have the following five training
documents (one sentence each), two from class – and two from class +.
CLASS DOCUMENTS
– Sad, bad service
– Sad cake service, I will not return at all
+ Not at all bad, delicious soup
+ Nothing bad about the service
+ Sad service, worth it for the soup
The following table has the counts for each word that appears in the training data above:
Word sad bad service I will not return nothing at all delicious soup about , the worth it for cake
Count – 2 1 2 1 1 1 1 0 1 1 0 0 0 2 0 0 0 0 1
Count + 1 2 2 0 0 1 0 1 1 1 1 2 1 2 2 1 1 1 0
Calculate the probability estimated, by your naïve Bayes estimator, for Class + and Class –
for the sentence “Bad service, soup and salad”. Show some working.
[2 marks]
What class would your classifier chose for that sentence “Bad service, soup and salad”.
[1 mark]
Question/Answer Booklet COMPSCI 367
Student ID
Page 21 of 23
What class would your classifier chose for the sentence “Sad service, cake and salad”. Show
some working.
[1 mark]
In the popular media, Machine-Learning-Based systems that produce classification errors are
often said to exhibit “algorithmic bias”. Does your naïve Bayes classifier exhibit this kind of
bias? If so, explain in a couple of sentences what the source of the bias is. If not, explain why
it is unbiased.
[2 marks]
Explain briefly why using feature vectors derived from pretraining neural language models
on large quantities of text might be better than a Bag-of-Words (BOW) approach in text
classification in mitigating data bias in practical settings. (One to two sentences). Also
explain why it might introduce bias that is hard to remove (One to two sentences).
[2 marks]
Question/Answer Booklet COMPSCI 367
Student ID
Page 22 of 23
OVERFLOW PAGE
This page was left blank for any questions that overflow.
(If you have used this page, please indicate clearly under the
relevant question that you have overflowed to this page.)
Question/Answer Booklet COMPSCI 367
Student ID
Page 23 of 23
OVERFLOW PAGE
This page was left blank for any questions that overflow.
(If you have used this page, please indicate clearly under the
relevant question that you have overflowed to this page.)