6.4 INSTANCE-BASED LEARNING 239
is necessary to modify the distance function as described below to allow the dis-
tance to a hyperrectangle to be computed. When a new exemplar is classified
correctly, it is generalized by simply merging it with the nearest exemplar of the
same class. The nearest exemplar may be either a single instance or a hyperrec-
tangle. In the former case, a new hyperrectangle is created that covers the old
and the new instance. In the latter, the hyperrectangle is enlarged to encompass
the new instance. Finally, if the prediction is incorrect and it was a hyperrec-
tangle that was responsible for the incorrect prediction, the hyperrectangle’s
boundaries are altered so that it shrinks away from the new instance.
It is necessary to decide at the outset whether overgeneralization caused by
nesting or overlapping hyperrectangles is to be permitted or not. If it is to be
avoided, a check is made before generalizing a new example to see whether any
regions of feature space conflict with the proposed new hyperrectangle. If they
do, the generalization is aborted and the example is stored verbatim. Note that
overlapping hyperrectangles are precisely analogous to situations in which the
same example is covered by two or more rules in a rule set.
In some schemes generalized exemplars can be nested in that they may be
completely contained within one another in the same way that, in some repre-
sentations, rules may have exceptions. To do this, whenever an example is incor-
rectly classified, a fallback heuristic is tried using the second nearest neighbor if
it would have produced a correct prediction in a further attempt to perform
generalization. This second-chance mechanism promotes nesting of hyperrec-
tangles. If an example falls within a rectangle of the wrong class that already
contains an exemplar of the same class, the two are generalized into a new
“exception” hyperrectangle nested within the original one. For nested general-
ized exemplars, the learning process frequently begins with a small number of
seed instances to prevent all examples of the same class from being generalized
into a single rectangle that covers most of the problem space.
Distance functions for generalized exemplars
With generalized exemplars is necessary to generalize the distance function to
compute the distance from an instance to a generalized exemplar, as well as to
another instance. The distance from an instance to a hyperrectangle is defined
to be zero if the point lies within the hyperrectangle. The simplest way to gen-
eralize the distance function to compute the distance from an exterior point to
a hyperrectangle is to choose the closest instance within it and measure the dis-
tance to that. However, this reduces the benefit of generalization because it rein-
troduces dependence on a particular single example. More precisely, whereas
new instances that happen to lie within a hyperrectangle continue to benefit
from generalizations, ones that lie outside do not. It might be better to use the
distance from the nearest part of the hyperrectangle instead.