At the forefront of Artificial Intelligence

Decision Trees in Prolog

Imagine a factory quality assurance robot must analyze a passing conveyor belt for faulty objects. It follows these criteria:

Shape Colour Size Action

Round Green Small Reject

Square Black Big Allow

Square Brown Big Allow

Round Brown Small Reject

Square Green Big Reject

Square Brown Small Allow

Note that only 6 out of a 12 possibilities (assuming 2 shapes, 3 colours, 2 sizes) have been explicitly outlined by the criteria. From these 6, the machine needs to be able to create heuristics by which to decide what objects to allow and what objects to reject. This is often done using a decision tree.

Our Decision Tree

So what would our decision tree look like for this example? We could have several possibilities, but here is one:

Decision Tree

See how you can follow the tree with any of the above criteria. Also note that instead of drawing branches for both black and brown coloured items, we have treated them as "Green" and "non-Green" (marked as *). This was because our criteria never distinguished between black and brown objects (see the second and third criteria).

So, given this tree, would the machine allow or reject a round, black and big object? It would allow it, by following the right-hand branch for "non-green" and then the left-hand branch for big objects.

Representation in Prolog

% Our example test object (round, big, black)
prop(a, colour, black).
prop(a, size,   big).
prop(a, shape,  round).

% Our tree!
classify(Obj, reject) :-
  prop(Obj, colour, green).

classify(Obj, allow) :-
( prop(Obj, colour, black)  ;
  prop(Obj, colour, brown) ),
  prop(Obj, size, big) .

classify(Obj, allow) :-
( prop(Obj, colour, black)  ;
  prop(Obj, colour, brown) ),
  prop(Obj, size,   small),
  prop(Obj, shape,  square) .

classify(Obj, reject) :-
( prop(Obj, colour, black)  ;
  prop(Obj, colour, brown) ),
  prop(Obj, size, small),
  prop(Obj, shape, round) .

This might seem slightly counter-intuitive to some people. Indeed, our tree suddenly isn't represented like a tree at all, but has been reduced back down to a series of if-then statements (or Prolog clauses). Nevertheless, the Prolog environment is very conducive to this sort of program. We simply tell Prolog what conditions satisfy an allowed object and what conditions cause the object to be rejected. Notice that here we've group black and brown together and OR-ed them together, instead of creating a separate non-green predicate.

Learning Algorithm

A human can create a decision tree from a set of criteria fairly easy, but a computer requires an algorithm. Algorithms used for decision tree creation are much more complicated than the one presented here. For this reason, we will not cover any specific source code. Interested readers might want to check the accompanying source code for Computational Intelligence, by Poole, Mackworth and Goebel. We will though, cover the basic pseudo-code:

createTree (tree, exampleTable)
  if all examples have the same classification C,
    tree is a single node, C.

  else
    choose an attribute A with n values V1 to Vn

    split examples into n sets E1 to En
      where for i all elements in Ei have Vi for A.

	Remove attribute A from E1 to En

	The tree now has a root labelled A, branches for V1 to Vn.
	  Branch Vi leads to Ti where createTree(Ti, Ei).
end ;

For example, given our example at the top of this page. Our criteria don't have all the same classification, so we choose an attribute (for example, colour). We split the example set into two groups (green and non-green), then "remove" colour from our example set. Now we recursively call the createTree function on our left tree V1. This does have all examples with the same classification (reject), so this classification becomes the node. We then start the process over again with our right-hand tree.

The above paragraph probably makes no sense if you don't either have a very clear mental picture of our decision tree, or a pen and paper in front of you. The algorithm might seem a little complicated, but it isn't if you understand what it is doing. Step through the rest of our example using only the steps presented in this algorithm and you should understand it fine.

Conclusion

There are several problems with our algorithm: there is no way of determining which attribute to select at any given time, standard decision trees cannot deal with elements with the same attributes but different classifications, and as with many machine learning algorithms, overfitting it a problem. Nevertheless, understanding the basics of decision tree learning thoroughly is imperative - we all must start somewhere. Again, for inquistive readers, check this page for some more advanced decision tree Prolog code.

Submitted: 29/01/2003

Article Toolbar

BibTeX entry