# CS代考 COMPSCI 367 Student ID – cscodehelp代写

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(

[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 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 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 naï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 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.

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

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 23 of 23