Artificial Intelligence Survey Assignment 4

CMPT 310 - Artificial Intelligence Survey
Assignment 4

10 marks
Important Note: Students must work individually on this, and other CMPT 310, assignments. You may not discuss the specific questions in this assignment, nor their solutions
with any other student. You may not provide or use any solution, in whole or in part, to or
by another student.
You are encouraged to discuss the general concepts involved in the questions in the context
of completely different problems. If you are in doubt as to what constitutes acceptable
discussion, please ask!
Question 1 (4 marks)
The table on the right contains
(fictitious) examples of holiday
trips. Relevant attributes are
the destination country of the
trip, the season during which the
trip took place, the type of trip,
and its length in weeks. The target attribute is how much fun
the trip was.
attributes goal example
country season type weeks fun
1 Italy summer repose 2 much
2 Italy winter sports 1 much
3 Austria winter culture 1 little
4 Austria winter repose 3 little
5 Austria winter sports 1 much
6 Spain summer repose 3 much
7 Spain summer sports 2 much
8 Spain winter repose 2 little
(You may assume that all possible values of the attributes are already mentioned in the
examples.)
(a) Generate a decision tree from these examples using the Decision-Tree-Learning
algorithm in order to predict the expected fun for arbitrary holiday trips. Determine
the best attribute for each test by means of computing information gains. Please
show and explain all steps.
(b) From the examples, find two decision lists (DL) predicting the expected fun. The first
list should comply with (i), the second with (ii).
(i) The tests of the DL contain as few literals as possible (e.g. only one, if possible).
(ii) The DL consists of as few tests as possible (e.g. only one, if possible).
1
Question 2 (3 marks)
The table on the right
contains (again fictitious)
examples of observations
about movies. Attributes
represent the genre of
the movie, the number of
celebrity main actors, the
amount of marketing that
was done, the production
costs, and whether the
movie was well received
by critics or not.
attributes goal example
genre actors marketing cost reception
1 SciFi 2 much high good
2 Comedy 3 little low bad
3 Comedy 1 little medium bad
4 Drama 2 much low good
5 Drama 1 little high good
6 SciFi 3 much low good
7 Comedy 1 little high good
8 SciFi 2 little low bad
In this question, a perceptron shall be trained using the examples in the table. To this
end, in part (a), the attributes have to be transformed into numeric inputs first. Then, in
part (b), Neural-Network-Learning can be applied.
(a) For encoding the examples use the eight inputs ID, IC, IS, I#, IM, Ih, Im, Il
, where
the attributes “genre”, “marketing”, “cost” are encoded by the following schemes:
genre ID IC IS
Drama 1 0 0
Comedy 0 1 0
SciFi 0 0 1
marketing IM
much 1
little 0
cost Ih Im Il
high 1 0 0
medium 0 1 0
low 0 0 1
The values of the attribute “actors” can directly serve as input I# since they are
numeric. For the goal attribute “reception”, 1 represents “good” and 0 represents
“bad”.
Set up the following table of transformed examples where T denotes the correct
output.
example ID IC IS I# IM Ih Im Il T
1 0 0 1 2 1 1 0 0 1
2
.
.
.
8
For which of the attributes “genre”, “actors”, “marketing”, “cost”, and “reception”
did we use local encoding, and for which ones or distributed encoding?
2
(b) Use the transformed examples of part (a) to train a perceptron that has eight inputs,
namely ID, IC, IS, I#, IM, Ih, Im, Il with corresponding weights WD, WC, WS, W#,
WM, Wh, Wm, Wl
. Let the activation function be step0
, the learning rate be 2, and
the weights initialized by +1. (For the given examples, these settings yield a fast
convergence.)
As a trace of the Neural-Network-Learning algorithm applied to the examples
of part (a), set up the following table where O denotes the perceptron output and
E = T − O is the error. You must include the output and the error for every example
but you may omit weights whose values are not changed. In the table below, the first
half of epoch 1 is already entered.
example O E WD WC WS W# WM Wh Wm Wl
initial. +1 +1 +1 +1 +1 +1 +1 +1
epoch 1
1 1 0
2 1 −1 −1 −5 −1
3 0 0
4 0 +1 +3 −1 +3 +1
5
6
7
8
epoch 2
1
.
.
.
8
epoch 3 .
.
.
[Hint: If you did not make a mistake — neither here nor in part (a) — it should turn
out that all examples are correctly predicted in epoch 3. Thus use this hint to verify
your solution (as a necessary (but not sufficient) condition).]
You are invited to solve this question by implementing the perceptron learning
algorithm and applying the program to the given examples. Of course, you can solve
it “by hand”, too.
3
Question 3 (3 marks)
(a) Construct a feed-forward neural network that has at most one hidden layer (i. e., it is
a perceptron or a feed-forward 2-layer network) and represents the 3-ary Boolean
function
f1(x1, x2, x3) = (x1 ≡ (x2 ∧ x3))
using only step functions as activation functions.1
(b) Can the following Boolean function be represented by a perceptron, using only step
functions? If yes, present one, if no, explain why this is the case.
f2(x1, x2, x3) = (x1 ∧ x2 ∧ x3) ∨ (¬x1 ∧ ¬x2 ∧ ¬x3))
1
stept
(x) = 0 , if x < t; stept
(x) = 1 , if x ≥ t.
4