CS代考 COMPSCI 367 Student ID

Question/Answer Booklet COMPSCI 367 Student ID
THE UNIVERSITY OF AUCKLAND
SEMESTER TWO 2020 Campus: City
COMPUTER SCIENCE Artificial Intelligence
(Time Allowed: TWO hours)
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)
A 28 B 18 C 31 D 23
Marks Available
Page 1 of 23

Question/Answer Booklet COMPSCI 367 Student ID
THIS PAGE HAS BEEN INTENTIONALLY LEFT BLANK.
Page 2 of 23

Question/Answer Booklet
Student ID
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?
PART A: ’s material
COMPSCI 367
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?
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?
Page 3 of 23

Question/Answer Booklet COMPSCI 367 Student ID
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.
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?
Page 4 of 23

Question/Answer Booklet COMPSCI 367 Student ID
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?
Question 7
What kind of local search is genetic algorithm doing? Can you explain what it does in terms of other local search algorithms?
Page 5 of 23

Question/Answer Booklet COMPSCI 367 Student ID
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?
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?
Page 6 of 23

Question/Answer Booklet
Student ID
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?
PART B: ’s material
(A) Approximately how many nodes will be expanded by A* using h?
COMPSCI 367
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.
(B) Approximately how many nodes will be expanded by a blind bidirectional search algorithm?
Page 7 of 23

Question/Answer Booklet COMPSCI 367 Student ID
(C) Under what conditions will A* expand fewer nodes than the blind bidirectional search algorithm?
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(, ) and clear(thing) where thing can be a block or the table.
[1.5 marks]
(B) describe the goal using the goal description language.
[1.5 marks]
Page 8 of 23

Question/Answer Booklet
Student ID
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))
(and (at-robby ?y) (not (at-robby ?x))))
Which predicates are: (A) static:
(B) fluent:
(C) object-level: (D) meta-level:
(A) (B) (C) (D)
Question 14
Explain why meta-level predicates are needed, give an example.
COMPSCI 367
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]
Page 9 of 23

Question/Answer Booklet COMPSCI 367 Student ID
(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.
Page 10 of 23

Question/Answer Booklet
Student ID
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.
PART C: Ian Watson’s material
COMPSCI 367
Question 17
Describe the algorithm most commonly used in Case-Based Reasoning. You may use a formula or a textual description.
Page 11 of 23

Question/Answer Booklet COMPSCI 367 Student ID
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]
Page 12 of 23

Question/Answer Booklet
Student ID
Question 19
(A) Define a CLIPS rule for the following pseudocode
IF the animal is a dog
THEN the sound made is woof
(B) What happens if you define two rules in CLIPS both called “dog”?
COMPSCI 367
Page 13 of 23

Question/Answer Booklet COMPSCI 367 Student ID
(C) Define a CLIPS template to describe a car. Your car template should be able to handle the following information:
Manufacturer:
Transmission:
Engine Size:
Under-warranty: no, yes
registration number
sedan, sports, station_wagon, ute…
Ford, Holden, Toyota, Honda…
name of owner
manual, automatic
petrol, diesel, hybrid, electric
size in litres
age in years
Page 14 of 23

Question/Answer Booklet COMPSCI 367 Student ID
THIS PAGE HAS BEEN INTENTIONALLY LEFT BLANK.
Page 15 of 23

Question/Answer Booklet COMPSCI 367 Student ID
PART D: ’s material
This table supplies logical symbols that you can cut and paste when answering questions in this section.
The table for part D defines logical operators you can cut and paste. The table below defines additional logical predicates, functions, and constants.
Implication Biconditional Negation Conjunction
Disjunction (inclusive) Universal Quantifier
Existential Quantifier
Question 20
City(x) InRegion(x,y)
population(x)
Auckland Aotearoa
Example Use
City(Xi’an) InRegion(Accra, Ghana)
Example Use
population(Christchurch)
Example Use
population(Auckland) population(Aotearoa)
Meaning of Example
3 is numerically greater than 2 Xi’an is a city
Accra is in Ghana
Meaning of Example
The population of Christchurch, 381599
Meaning of Example
The population of Auckland, an integer
The population of Aoteraroa, an integer around 5 million
Page 16 of 23

Question/Answer Booklet COMPSCI 367 Student ID
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.
(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.
(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.
Page 17 of 23

Question/Answer Booklet COMPSCI 367 Student ID
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.
(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.
Page 18 of 23

Question/Answer Booklet COMPSCI 367 Student ID
(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.
(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.
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.
Page 19 of 23

Question/Answer Booklet COMPSCI 367 Student ID
Question 22
Suppose that you are training a very simple naï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 cake service, I will not return at all + Nothing bad about the service
The following table has the counts for each word that appears in the training data above:
Sad, bad service
Not at all bad, delicious soup
Sad service, worth it for the soup
Count-21211110110 00200001
Count+12200101111 21221110
Calculate the probability estimated, by your naïve Bayes estimator, for Class + and Class – for the sentence “Bad service, soup and salad”. Show some working.
sad bad service I will not return nothing at all delicious soup about , the worth it for cake
What class would your classifier chose for that sentence “Bad service, soup and salad”.
Page 20 of 23

Question/Answer Booklet COMPSCI 367 Student ID
What class would your classifier chose for the sentence “Sad service, cake and salad”. Show some working.
In the popular media, Machine-Learning-Based systems that produce classification errors are often said to exhibit “algorithmic bias”. Does your naï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.
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).
Page 21 of 23

Question/Answer Booklet
COMPSCI 367
Student ID
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.)
Page 22 of 23

Related Posts