Hypercuboid-Formation Behaviour of Two Learning Algorithms

1. Introduction

In the interpretation of the Focussing algorithm presented by Bundy et al. (ibid.) the description space consists of a set of relation trees and execution of the algorithm involves the manipulation of upper markers (which collectively define the most general form of the concept being learned) and lower markers (which collectively define the most specific form of the concept being learned). The form of this marker-manipulation is reasonably simple: following the presentation of a new positive instance, one or more lower markers may be raised so that the most specific form of the concept covers the new instance: following the presentation of a new negative instance, an upper marker may be lowered so that the most· general form of the con­ cept no longer covers the new instance.

In an alternative interpretation (Thornton 1987) the descrip­ tion space is a geometric space and execution of the algo­ rithm involves the shrinking of an outer hypercuboid (which defines the most general form of the concept being learned) and the expansion of an inner hypercuboid (which defines the most specific form of the concept being learned). Hypercuboid-manipulations correspond to marker­ manipulations in the obvious way: following presentation of a new positive instance, the inner hypercuboid may be expanded so u to enclose the point which corresponds to the new instance: following presentation of a new negative instance, the outer hypercuboid may be shrunk so as to exclude the point which corresponds to the new instance.

To help clarify this alternative interpretation two descrip­ tions of the behaviour of the Focussing algorithm will be contrasted. The first of these descriptions will invoke the standard, marker-oriented interpretation: the second will Suppose that a description space consists of two trees called · A" and "B" whose structure is as depicted in Fig. 1. (Instances in this description space are simply conjunctions of tip nodes taken from trees A and B; e.g. Al & B3.) The Focussing algorithm is presented with a sequence of four instances from this description space: <Al & 82, A3 & 82, Al & B1. A1 & 82>. The first two elements are positive instances of the concept to be learnt and the second two are negative instances. Presentation of the first positive instance (i.e. initialisation) causes the placing of upper markers at the root nodes of both trees and lower markers at the appropriate tip nodes (Al & 82). Presentation of the second positive instance (A3 & 82) causes the lower marker in tree A to be raised to the parent of Al. Presentation of the first negative instance (Al & B1) causes the upper marker in tree B to be lowered and presentation of the second negative instance (A1 & 82) causes the upper marker in tree A to be lowered. The positions of markers at this point are as depicted in Fig. 1.

I

·

The hypercuboid-oriented interpretation of the behaviour of the algorithm in this case is as follows. We say that the description space has two dimensions called "A" and "B" which range over the values {A1. Al, A3} and {B1. 82, 83} respectively. Presentation of the first positive instance (ini­ tialisation) triggers the construction of an inner hypercuboid enclosing the Al/82 cell and an outer hypercuboid enclosing the entire space. Presentation of the second positive instance causes the inner hypercuboid to be expanded so u to include the A3182 cell. Presentation of the two negative instances cause the outer hypercuboid to be shrunk to exclude both the A1182 and Al/81 cells. The structure of the inner and outer hypercuboids at this point is as shown in Figure 2. (The outer hypercuboid is drawn using ·.­ characters; the inner hypercuboid is drawn using "+" charac­ ters.)

Note that the sequence of instances described does not enable the Focussing algorithm to construct a fully-specified concept: the most general form of the defined concept is not identical to the most specific form. Under the standard .interpretation the evidence for this is the fact that one set of markers do not coincide (i.e. one of the trees is not firmed-up). In the hypercuboid-oriented interpretation the evidence is the fact that the hypercuboids are not identical.

2. The disjunctive-concept probkm.

Bundy et ai. show that there are sequences of positive and negative instances which. when presented to the Focussing algorithm. will cause upper markers to be moved below lower markers or lower markers to be moved above upper markers. Such an event corresponds to the emergence of an inconsistency and the failure of the algorithm. This problem is frequently referred to as the disjunctive-<:oncept problem on the grounds that such sequences may be associated with disjunctive concepts.

An inconsistency (i.e. the inversion of an upper and a lower marker) is described. under the hypercuboid-oriented interpretation. as the situation which arises when an inner hypercuboid boundary extends beyond an outer hypercuboid boundary. Viewing inconsistencies in this way leads to the observation that (i) there are precisely two situations which will cause inconsistencies to arise and (ii) that these situa­ tions will always lead to inconsistencies regardless of the order in which instances are presented.

Consider Fig. 3 which shows the geometric form of the pre­ viously defined description space. Positive instances are dep­ icted as "Ps"; negative instances are depicted as "Ns". Two positive instances are depicted (P1 and P2) and one negative instance (N1).

Note that as things stand it is impossible to construct a hypercuboid which encloses all the Ps and excludes all the Ns; clearly. any hypercuboid which encloses all the Ps must extend beyond a hypercuboid which excludes all the Ns. Translated into the standard interpretation. this observation says that. in any set of (upper and lower) markers which both cover all the positive instances and exclude all the negative instances. there will be at least one lower marker which is above an upper marker. Presentation of the corresponding set of instances will therefore inevitably lead tO an inconsistency regardless of the presentation schedule.

If the only positive instance was P2. a valid hypercuboid (i.e. one which encloses all the Ps and excludes all the Ns) could be constructed. but not by the Focussing algorithm. The reason is very simple. The Focussing algorithm actually manipulates markers not hypercuboid boundaries and its boundary-manipulation capabilities are therefore constrained. It can locate boundaries at positions X and Y in some dimension D if and only if the values of D falling between X and Y are descended from a unique node in a tree of the underlying tree-based description space. The values in the singleton set (83) are not descended from a unique node in the tree-based description space. therefore hypercuboid boundaries cannot be positioned so as to enclose them. Since any valid hypercuboid for (P2. N1) must have such boundaries. we can infer that the Focussing algorithm can­ not construct a valid hypercuboid for this set of instances.

The Focussing algorithm then can fail either because (i) the valid hypercuboid does not exist or because (ii) it cannot be constructed due to constraints on boundary manipulations. In either of these situations failure will occur regardless of presentation schedules.

A useful distinction can therefore be made between two di1£erent versions of the disjunctive-<:oncept problem: a strong version corresponding to situation (i) and a weak version corresponding to. situation (ii). Drawing this distinc­ tion leads to the observation that techniques such as the "least-disjunction" procedure (Utgolf 1985) and "tree-hacking" (Bundy et al. 1985) which. in effect. alter the set of pos­ sible boundary positions by introducing novel disjunctions into the underlying description space. can alleviate the weak version of the disjunctive-<:oncept problem but not the strong version.

3. Assignment heuristics

A modification of the Focussing algorithm which is capable of learning disjunctive-<:oncepts is associated with Mitchell et al. (1983). This technique (called Shell Creation by Bundy et al. 1985) involves the construction of what are. in effect. multiple sets of markers (i.e. "rule-shells"). Under the hypercuboid-oriented interpretation this technique corresponds to the construction of sets of inner and outer hypercuboids (Thornton 1987).

Note that. in the case where multiple inner and outer hypercuboids have been constructed. the presentation of a new instance does not have deterministic consequences. If the new instance is a positive instance. then an inner hypercuboid may have to be expanded to enclose it. If the new instance is a negative instance. then an outer hypercu­ boid may have to be shrunk to exclude it. The question is (in both cases): which particular hypercuboid should be chosen?

Bundy et al. have noted that there appears to be no infalli­ ble way of choosing how to assign new instances to existing hypercuboidslrule-shells (1985, p. 170). The conclusion seems to be that assignments must be carried out using a heuristic.

There are obviously many possible Ulignment heuristics that might be used; however we can Imagine a completely general heuristic which computes preferenc:es for Ulignments on the basis of explicit features of the data (I.e. which doel not employ domain-knowledge). It can be lhown that the preferences computed by this heuristic must atlsfy certain criteria. (We consider the cue where there are two de!ned "points" In the description space named P1 and Pl.)

We can assume that the completely general heuristic (like any other heuristic) must behave systematically. Therefore (i) the computed preference for Ulignlng an Instance occu­ pying P1 to a hypercuboid enclosing Pl must be identically equal to the computed preference for Ulignlng an instance occupying P2 to a hypercuboid enclosing P1; (ii) the com­ puted preference for Ulignlng an Instance occupylna P1 to a hypercuboid enclosing P1 must have a maximum value. since the limiting cue Is the Ulignment of an instance to a single-cell hypercuboid which already encloees it.

In addition. we can Infer that preference~~ generated by the heuristic must be Intrinsically coherent. Thla meana that the computed preference for usignlng an instance occupying P1 to a hypercuboid enclosing P2 must not be outweighed by the computed preference for usignlng P1 flnt to .,me intermediate hypercuboid, and then on to the one enclosing P2. If computed preferences were of this .,rt, then we would be able to Increase our level of preference for any particular assignment simply by devising ever more ela­ borate assignment schedules.

Any heuristic which atisfies these criteria must exploit what is, In dect. a valid distance function over the description space. Presented with any two points In the description space. the heuristic must be capable of generating a distinct level of preference for usignlng one of the two points to a hypercuboid enclosing the other. Thla level of preference. Interpreted as a measure of distance, atisfies all the axioms for a mathematical distance function, including triangle Inequality. reflexivity and symmetry.

4. TM ClU.rifictltion algorithm

Bundy et al. (ibid.) note that the Classification algorithm, associated with Quinlan (1983) and Hunt (1966), Is capable of dealing flawlessly with disjunctive concepti. In their presentation of this algorithm, the description space Is an attribute-value space and the action of the algorithm involves (an iteration of) the llelection of an attribute A followed by the splitting of the lnstanc:es (which are all given In advance) Into sets. such that all the lnstanc:es In a given set have the same value of A. This proc:ea terminates when every set of Instances contains either uniformly poli­ tive or uniformly negative lnstanc:es. The .UUC:ture of attri­ bute choices forms a decision tree (i.e. disjunctive rule) for the concept underlying the Instances.

In the hypercuboid-oriented Interpretation of this algorithm (Thornton 1987), the description space ia a geometric space consisting of K dimensions each of which ranges over the possible values of a single attribute. Instances correspond to points In the normal way. Initialisation of the algorithm corresponds to the construction of a single hypercuboid which encloses all the points in the description space. Thla hypercuboid is then subdivided Into K hypercuboids, where K is the number of values of the chosen attribute. Any of the K hypercuboids which do not contain uniform 1nstanc:es are then further subdivided. The division proc:ea continues until all hypercuboids contain Instances which are either Note that a hypercuboid constructed by the Classification algorithm will have boundaries which, for each dimension D. enclose either a single value of D or the complete range of D. In other words. the bound4ries In any one dimension of a hypercuboid formed by the Classification algorithm must, by de!nition. be either maximally close or maximally distant.

If we consider the entire set of possible hypercuboids which can be constructed In any given geometric space of a rea­ sonable size, and compare it with the set of hypercuboids which can be constructed In the same space using boun­ daries which are of the described form, we will conclude that the size of the former set is overwhelmingly greater than the size of the latter set. The implication is that the Classi11.cation algorithm can only construct a small propor­ tion of the possible hypercuboids In any given space and must therefore be assumed to be only capable, In general. of constructing a small proportion of the possible disjunc­ tive concepts for a given domain.

.5. Summary

We have shown that under the hypercuboid-based Interpre­ tations of the Focussing algorithm and the Classification algorithm a number of possibilities emerge: (i) a simple account of the disjunctive-concept problem can be presented; (ii) a distinction can be made between a strong and a weak version of the problem; (iii) techniques such as tree-hacking can be shown to alleviate only the weak version; (iv) solu­ tions to the problem which Involve the construction of multiple hypercuboids and the exploitation of completely general assignment heuristics can be shown to exploit what are, In dect, valid distance functions over the description space; (v) the Classification algorithm can be shown to be capable of forming only a subset of the possible disjunctive concepts for a given domain.

ACKNOWLEDGEMENTS

I would like to thank Allan Ramsay. Guy Scott. Steve Draper. Claire O'Malley and Andrew Law for providing extremely helpful comments on this paper.