OMP3411/9814 Artificial Intelligence Term 1, 2021
Assignment 2 – Machine Learning (DRAFT ONLY)
Due: Friday 23 April, 10pm
Marks: 20% of final assessment for COMP3411/9814 Artificial Intelligence
Part 1: Decision Trees Question 1.1 (5 marks):
Consider the decision tree learning algorithm of Figure 7.7 and the data of Figure 7.1 from Poole & Mackworth , also presented below. Suppose, for this question, the stopping criterion is that all of the examples have the same classification. The tree of Figure 7.6 was built by selecting a feature that gives the maximum information gain. This question considers what happens when a different feature is selected.
Figure 7.1: Examples of a user’s preferences
- a) Suppose you change the algorithm to always select the first element of the list of features. What tree is found when the features are in the order [Author, Thread, Length, WhereRead]? Does this tree represent a different function than that found with the maximum information gain split? Explain.
- b) What tree is found when the features are in the order [WhereRead, Thread,Length, Author]? Does this tree represent a different function than that found with the maximum information gain split or the one given for the preceding part? Explain.
- c) Is there a tree that correctly classifies the training examples but represents a different function than those found by the preceding algorithms? If so, give it. If not, explain why.
Question 1.2 (5 marks):
The goal is to take out-of-the-box models and apply them to a given dataset. The task is to analyse the data and build a model to predict whether income exceeds $50K/yr based on census data (also known as “Census Income” dataset).
Use the data set Adult Data Set from the Machine Learning repository . Use the supervised learning methods discussed in the lectures, Decision Trees.
Do not code these methods: instead use the J48 implementation in Weka. Read the Weka documentation on Decision Trees, and the linked pages describing the parameters of the methods. You will need to download Weka, from he link above.
You should submit, as part of your PDF file, the decision tree you obtained, along with an explanation of the process you went through to get it. You can experiment with pruning the tree, including trying different pruning settings. What affect do these setttings have on the size of the tree and the accuracy?
This question will help you master the workflow of model building. For example, you’ll get to practice how to use the critical steps:
- Importing data
- Cleaning data
- Splitting it into train/test or cross-validation sets
- Feature engineering
Use the Weka documentation pages for instructions how to use J48. See also this WebCMS page.
Part 2: Inductive Logic Programming
Duce is a program devised by Muggleton  to perform learning on a set of propositional clauses. The system includes 6 operators that transform pairs of clauses into a new set of clauses. Your job is to write Prolog programs to implement 5 of the 6 operators. The other one is given as an example to get you started.
Inter-construction. This transformation takes two rules, with different heads, such as x <- [b, c, d, e]
y <- [a, b, d, f]
and replaces the with rules
x <- [c, e, z] y <- [a, f, z] z <- [b, d]
To make processing the rules easier, we represent the body of the clause by a list and we define the operator <- to mean “implied by” or “if’.
A Prolog program to implement inter-construction is given as an example to give you hints about how to write the remaining 5 operators.
:- op(300, xfx, <-).
inter_construction(C1 <- B1, C2 <- B2, C1 <- Z1B, C2 <- Z2B, C <- B) :- C1 \= C2,
intersection(B1, B2, B), gensym(z, C), subtract(B1, B, B11), subtract(B2, B, B12), append(B11, [C], Z1B), append(B12, [C], Z2B).
First, we define <- as an operator that will allow us to use the notation x <- y. The program uses Prolog built-in predicates to perform set operations on lists and to generate new symbols.
- The first line the program assumes that the first two arguments are given as propositional clauses. The remaining three arguments are the output clauses, as in the example above.
- inter_construction operates on two clauses that gave different heads, i.e. C1 \= C2.
- We then find the interaction of the bodies of the clauses and call it, B.
- gensym is a builtin predicate that creates a new name from a base name. So gensym(z, C) binds C to z1. Every subsequent call to gensym, with base z, will create names, z2, z3, …. Calling reset_gensym will restart the numbering sequence.
- At this point the last argument C <- B = z1<-[b, d] because C is bound to z1 and B is the intersection [b, d].
- The bodies Z1B and Z2B, are obtained by subtracting the intersection, B, from B1 and B2 and appending the single element [C]. So we can run the program: