2.7.3 Instance-based Learning

Instance-based learning techniques work essentially by keeping typical attribute examples for each class.

Aha, Kibler and Albert [AKA90] define a set of instance-based learning algorithms that have three defining characteristics:

A similarity function:

This tells the algorithm how close together two instance are. Although this sounds easy, there is a great deal of complexity in choosing the similarity function, especially in situations where some of the inputs are enumerated. For example, if you were trying to match people, and one attribute was hair colour, what does distance mean in the context of hair colour?

A ``typical instance'' selection function:

This tells the algorithm which of the instances to keep as examples. How do you know which instances are ``typical'' and which are atypical?

A classification function:

This function is the one that when given a new case, decides how it relates to the learned cases. For example, this function might be the instance to which it is closest in location.

IBL's are known by many other names, and there are many variations on the basic theme. There are three that Aha, Kibler and Albert propose in their paper:

IBL1:

Store all example instances and simply find the closest instance -- then the class of this instance is the class of the closest instance. The large number of instances that need to be stored, however, can require large amount of space.

IBL2:

Similar to the above, but throw away instances in the training set that would have already have been correctly classified. This saves some space.

IBL3:

Like IBL2, but makes some assumptions about the data and uses a statistical methods to ``weed out'' irrelevant or noisy instances.

In addition, the above can be augmented by the application of a k-nearest neighbour (k-nn) approach [CH67,Har68,Gat72]. Instead of looking at the single nearest point and classifying according to that, we look at a collection of the nearest points and use a ``voting'' mechanism to select between them.

They share many problems with neural networks, such as the ``tweakability'' of the system -- due to having to set up the three functions discussed above, and finding an optimal set of them. They also suffer from the ``extractability'' problem, in that it is basically a very unstructured way of learning -- it merely stores the typical values without processing the data in any way. No ``concepts'' are produced in a human readable format.

The other problem is that they sometimes require moderately large amount of storage, even with the optimisations of IBL2 and IBL3. This is not a problem in itself, but can impose problems for fast searching for the nearest point.

On the other hand, they are easy to test, conceptually simple, and are able to segment the space in complex ways.