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 By completing this assessment, I agree to the following declaration: I understand the University expects all students to complete coursework with integrity and honesty. I promise to complete all online assessment with the same academic integrity standards and values. Any identified form of poor academic practice or academic misconduct will be followed up and may result in disciplinary action. As a member of the University’s student body, I will complete this assessment in a fair, honest, responsible and trustworthy manner. This means that: • I declare that this assessment is my own work, except where acknowledged appropriately (e.g., use of referencing). • I will not seek out any unauthorised help in completing this assessment. (NB. Unauthorised help includes a tutorial or answer service whether in person or online, friends or family, etc.) • I declare that this work has not been submitted for academic credit in another University of Auckland course, or elsewhere. • I am aware the University of Auckland may use Turnitin or any other plagiarism detecting methods to check my content. • I will not discuss the content of the assessment with anyone else in any form, including, Canvas, Piazza, Chegg, Facebook, Twitter or any other social media within the assessment period. • I will not reproduce the content of this assessment in any domain or in any form where it may be accessed by a third party. • I declare that I generated the calculations and data in this assessment independently, using only the tools and resources defined for use in this assessment. • I declare that I composed the writing and/or translations in this assessment independently, using only the tools and resources defined for use in this assessment. Student Support If you wish to raise concerns during your online exam, please call the Contact Centre for advice. The Contact Centre will be open Monday to Friday 8.00 am – 9.45 pm (NZ Time) and Saturday 8.00 am – 5.45 pm (NZ Time) throughout the Exam period. If you need help during your online exam please call Auckland: 09 373 7513, New Zealand: 0800 61 62 63, or International: +64 9 373 7513 if you are unable to call please email
[email protected] and provide contact details and description of issue. If you have an issue with Canvas, live chat is available 24 / 7 with Canvas Support, via the Help button within your Canvas left-hand sidebar. If you are in New Zealand, you can also call the Canvas Support Hotline on 0800 005 205. Question/Answer Booklet COMPSCI 367 Student ID Page 3 of 23 THIS PAGE HAS BEEN INTENTIONALLY LEFT BLANK. Question/Answer Booklet COMPSCI 367 Student ID Page 4 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 5 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 6 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 7 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 8 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 9 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(
, ) 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] Question/Answer Booklet COMPSCI 367 Student ID Page 10 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 11 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 12 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 13 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 14 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 15 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 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.) 欢迎咨询51作业君
