QUESTION/ANSWER BOOKLET
ID ………………… COMPSCI 367
THE UNIVERSITY OF AUCKLAND
SEMESTER TWO, 2017 Campus: CITY
COMPUTER SCIENCE
Artificial Intelligence (Time Allowed: TWO hours)
You must answer all questions in this exam.
Calculators are NOT permitted.
There is space at the back for answers that overflow the allotted space.
Surname Forename(s) Student ID Login (UPI)
Knowledge Engineering Machine Learning Problem Solving via Search
Page 1 of 24
QUESTION/ANSWER BOOKLET ID …………………
SECTION A: Knowledge Engineering
COMPSCI 367
Answer all questions in this section in the space provided. If you run out of space, please use the Overflow Sheet and indicate in the allotted space that you have used the Overflow Sheet.
Question 1
Expert system shells allow knowledge engineers to concentrate on eliciting knowledge and representing this as rules, without having to trouble themselves with programming inferencing methods. Draw a diagram showing the architecture of a typical expert system shell showing how each of the components interacts with each other and the user.
Page 2 of 24
QUESTION/ANSWER BOOKLET
ID ………………… COMPSCI 367
Question 2
Generate and Test is commonly used by experts to solve diagnostic decision problems. Draw a diagram describing the Generate and Test problem solving method illustrating its key components.
Page 3 of 24
QUESTION/ANSWER BOOKLET
ID ………………… COMPSCI 367
Question 3
You have been asked to build an expert system to provide valuations for a second-hand car dealership. You visit the dealership and obtain the following transcript of a conversation with an experienced salesman.
“Well obviously the most important thing that influences a car’s price is the make and model of the car and its mileage. The age of the car is important and of course its condition matters. Older European cars tend to hold their price better than older Japanese ones. Then of course there are the mechanics. The engine’s size and horsepower is important, but you also have to consider the mileage of the engine and how often it has been serviced. Then there are all the extras: like GPS, and stereo. The model, and condition of these is important as well. Then there’s all the other extras like air conditioning, ABS, tinted glass, leather seats, etc…. Finally there are add-ons like warranty and breakdown service. So as you can see there’s a lot that can influence the price of a car. Oh, I forgot to mention the wheels and tyres, the type, age and condition of them are very important as well. Sorry, I also forgot finance; we’ll drop the price if someone wants finance because we can make more money from the finance package.”
Analyse this transcript and draw an inference network or influence diagram to create a knowledge level model of the factors that influence the sale price of a car.
[Hint: use a spare page at the back of the exam paper to work out your answer and then copy your final version to the space on the next page.]
Page 4 of 24
QUESTION/ANSWER BOOKLET ID …………………
Question 3 answer…
COMPSCI 367 [10 marks]
Page 5 of 24
QUESTION/ANSWER BOOKLET
ID ………………… COMPSCI 367
Question 4
Describe the difference between explicit knowledge and tacit knowledge giving an example of each.
[4 marks].
Question 5
Describe how you would conduct a Turing Test and outline a common criticism of the Turing Test?
Page 6 of 24
QUESTION/ANSWER BOOKLET
ID ………………… COMPSCI 367
Question 6
Water freezes at zero degrees Celsius and boils at 100 degrees Celsius. Draw a graph that shows the fuzzy set membership functions for water that has four fuzzy logic sets: freezing, cold, warm, and hot.
Page 7 of 24
QUESTION/ANSWER BOOKLET
ID ………………… COMPSCI 367
THIS PAGE HAS BEEN INTENTIONALLY LEFT BLANK.
QUESTION/ANSWER BOOKLET FOLLOWS Page 8 of 24
QUESTION/ANSWER BOOKLET ID …………………
SECTION B: Machine Learning
COMPSCI 367
Answer all questions in this section in the space provided. If you run out of space, please use the Overflow Sheet and indicate in the allotted space that you have used the Overflow Sheet.
Question 7
Consider the following data set on the outcomes of matches between two professional tennis players A and B. Suppose we want to build a decision tree classifier that predicts the game outcome between these two players. Answer the following questions:
Morning Afternoon Night Afternoon Afternoon Afternoon Afternoon Afternoon Morning Afternoon Night Night Afternoon Afternoon Afternoon Afternoon
Match Type
Master Grand Slam Friendly Friendly Master Grand Slam Grand Slam Grand Slam Master Grand Slam Friendly Master Master Master Grand Slam Grand Slam
Court Surface
Grass Clay Hard Mixed Clay Grass Hard Hard Grass Clay Hard Mixed Clay Grass Hard Clay
A’s Winner
Yes A Yes A No A No B Yes B Yes A Yes A Yes A Yes A Yes B No A Yes B Yes B Yes A Yes A Yes A
a) Compute the information gain of splitting on the feature “A’s ”. Do not use
Laplace smoothing. Show working.
Page 9 of 24
QUESTION/ANSWER BOOKLET
ID ………………… COMPSCI 367
b) Suppose the root of the decision tree is “Court Surface”. What would be the predicted outcome for a match played on hard court?
Question 8
a) Briefly explain the concept of (order-1) Voronoi cells.
b) Suppose that you want to design a machine learning algorithm that will predict the number of passengers on a train service from Papakura to Britomart in the next hour. This could help plan and allocate personnel accordingly. Propose three possible input features which could be useful. State their respective domains.
Page 10 of 24
QUESTION/ANSWER BOOKLET
ID ………………… COMPSCI 367
(c) Suppose that we have three coloured boxes r (red), b (blue), and g (green). Box r contains 3 apples, 4 oranges, and 3 limes; box b contains 1 apple, 1 orange and no lime; box g contains 1 apple, 2 oranges and 1 lime. If a box is chosen at random with probability P(r)=0.1, P(b)=0.3, P(g)=0.6, and a piece of fruit is removed from the box (with equal probability of selecting any of the items in the box), then what is the probability of selecting an apple? If we observe that the selected fruit is in fact an orange, what is the probability that it came from the green box? Show brief working.
Page 11 of 24
QUESTION/ANSWER BOOKLET
ID ………………… COMPSCI 367
Question 9
(a) The following diagram plots a sample set containing two numeric input features X1 and X2 and two classes, indicated respectively by “+” and “o”. Suppose we apply perceptron learning algorithm to this dataset. Would the algorithm stabilise at a linear classifier that correctly classifies all samples in the dataset?
If so, write down a weight vector (w0,w1,w2) that corresponds to a classifier that correctly classifies all samples. Otherwise, briefly state why.
Page 12 of 24
QUESTION/ANSWER BOOKLET
ID ………………… COMPSCI 367
b) Apply the perceptron learning algorithm for the following sample set for one round. N denotes negative instances and P denotes positive instances. Start with weight vector (w0, w1, w2, w3) = (1,0,0,0). Apply the patterns in the given order. For each step of perceptron learning write down the applied pattern, the classification result and the update of the weight vector.
{(4,3,6,N), (2,−2,3,P), (1,0,−3,N), (4,2,3,N)}
Page 13 of 24
QUESTION/ANSWER BOOKLET
ID ………………… COMPSCI 367
Question 10
Decide which of the following sentences are true, and which are false.
(a) A machine learning algorithm computes a model from a set of training data, so as to be able to make reliable predictions on test data. The problem of overfitting occurs usually when the model is too complicated and fits the training data well, and as a result the model does not generalise beyond the training set.
(b) An agent is said to learn from experience E with respect to some class of tasks T and performance measure P, if it acquires more experience E through performing T while keeping the performance measure P unchanged.
(c) Supervised learning is a paradigm where the computer is presented with example inputs and their desired outputs, and the goal is to learn a general rule that maps inputs to outputs.
(d) Occam’s razor states that when more than one hypotheses are consistent with observation, choose the most sophisticated one as it may then have the best predictive power.
(e) Naive Bayesian classification relies on the assumption that all input features are independent of each other. If there are two input features that are not independent, then the resulting model would not have high accuracy.
(f) Suppose a crime has been committed. Blood is found at the scene for which there is no innocent explanation. It is of a type which is present in merely 1% of the population. Bob has this particular blood type. Since there is a 1% chance that Bob has the crime blood type if he were innocent, there is a 99% chance that he is guilty.
Page 14 of 24
QUESTION/ANSWER BOOKLET ID …………………
SECTION C: Problem Solving via Search
COMPSCI 367
Answer all questions in this section in the space provided. If you run out of space, please use the Overflow Sheet and indicate in the allotted space that you have used the Overflow Sheet.
Question 11
Write English sentences for the following first-order expressions. ∃x∀y∀z (likes(x,y) ∧ likes(y,z)) → ¬likes(x,z)
∀x∀y∀z (likes(x,y) ∧ likes(y,z)) → likes(x,z)
Page 15 of 24
QUESTION/ANSWER BOOKLET
ID ………………… COMPSCI 367
Question 12
Write Prolog code to define fottle/1. fottle(X) is only true if X is unmarried, younger than 31, and a female. Do this using only: married/1, female/1, age/2 (e.g., age(X, Age)), and the relation “<", e.g., Y < 7.
Question 13
What are the pro's and con's of using IDA* versus using A*? Make it clear when it is better to use IDA* and when it is better to use A*. Is the cost of making the repeated iterations a major cost for IDA*? If it is, then why is it and if it is not, then why is it not?
Page 16 of 24
QUESTION/ANSWER BOOKLET
ID ..................... COMPSCI 367
Question 14
Use the minimax procedure to propagate the values up from the leaves (of the game tree below) to the root. Label each of the four internal nodes with its propagated value.
13 10 8 14 5 2 7 14 16
Page 17 of 24
QUESTION/ANSWER BOOKLET
ID ..................... COMPSCI 367
Question 15
Use the α−β (alpha-beta) pruning procedure to propagate the values up from the leaves (of the game tree below) to the root. Cross out the nodes which get pruned and label each unpruned node with its propagated value.
13 10 8 14 5 2 7 14 16
Page 18 of 24
QUESTION/ANSWER BOOKLET
ID ..................... COMPSCI 367
Question 16
We have discussed heuristics in class with reference to solving puzzles (e.g., 15-puzzle), solving constraint satisfaction problems (e.g., the map coloring problem), and for playing 2- person games (e.g., chess). Give an example of a heuristic that we discussed in class for (1) a heuristic for the 15-puzzle, (2) a heuristic for the map coloring problem, and (3) a heuristic for chess. For each case, what is that heuristic trying to measure? In what sense are they all heuristics?
Page 19 of 24
QUESTION/ANSWER BOOKLET ID .....................
Question 17
COMPSCI 367
The addition above is a classic cryptarithmetic problem. Set this problem up as a constraint satisfaction problem as we did in class. Specifically list all the variables and their domains. Threeoftheconstraintsare:the"Alldiff"constraint,M≠0,andS≠0. Giveonemoreofthe remaining constraint equations.
Variables & their domains:
Constraint equation:
Page 20 of 24
QUESTION/ANSWER BOOKLET ID .....................
COMPSCI 367
- Overflow Sheet 1 -
Write the question number and letter next to your answer. You must ALSO indicate in the allotted space that you have used the overflow sheet.
Page 21 of 24
QUESTION/ANSWER BOOKLET ID .....................
COMPSCI 367
Overflow Sheet 2 -
Write the question number and letter next to your answer. You must ALSO indicate in the allotted space that you have used the overflow sheet.
Page 22 of 24
QUESTION/ANSWER BOOKLET ID .....................
Rough Working – This page will not be marked
COMPSCI 367
Page 23 of 24
QUESTION/ANSWER BOOKLET ID .....................
Rough Working – This page will not be marked
COMPSCI 367
________________________________________
Page 24 of 24