Forgetting and Compacting data in Concept Learning

1 Introduction

Incremental concept learning algorithms maintaining a hypothesis consistent with all data (usually called ez­ amples or instances) have to store all previous data as soon as any backtracking is involved. Excep­ tions are, e.g., the Candidate Elimination algorithm [Mitchell, 1982], because it searches bi-directionally (i.e., specific-to-general and general-to-specific) and breadth­ first, or algorithms searching specific-to-general in a con­ junctive tree-structure language, as Incremental Non­ Backtrackin& Focusing [Smith and Rosenbloom, 1990]. [Hirsh, 1992j even prefers a representation storing all negative examples together with S over storing S and g in case g can grow exponentially or can be infinite. [Bundy et al., 1985] argues that for learning disjunctive concepts all data will have to be stored anyway.

One of the goals of concept learning is compaction of the information provided to the algorithm. Therefore, in cases where all instances have to be memorized, prefer­ ably no redundant information should be stored. In this paper, we remove redundant instances in a language in­ dependent way by partially ordering them, according to their information contents. In [Sebag, 1994] and [Sebag and Rouveirol, 1994] this is done for negative examples in a conjunctive tree-structure, resp. first order logic language. According to the partial order, we only have to store minimal and maximal instances, while forget­ ting the ones with less information content. However, we have to take care that the search algorithm does not lose any solutions, does not search previously discarded parts of the search space again, and retains its most in­ teresting properties.

We develop this idea in the framework of the Iterative Versionspaces algorithm (ITVS) [Sablon et al., 1994]. Nevertheless, we argue that it has a much wider ap­ plication potential. The theory is formulated indepen­ dently from any concept learning algorithm or search strategy and independently from the chosen concept rep­ resentation language. The partial order on instances is defined solely in terms of the "is more specific than" relation. Identifying and removing redundant instances can be used in any incremental algorithm that stores all instances, and even in a preprocessing phase of a non-incremental concept learning algorithm, to reduce its actual processing time. The reason for studying this problem in the context of ITVS, is that we believe the datastructures and complexity measures of ITVS con­ tribute to understanding the nature and the complexity of concept learning.

We ensure that the main properties of ITVS are re­ tained: a worst case space complexity linear in the num­ ber of instances, and a worst case time complexity of testing a candidate hypothesis for maximal generality or maximal specificness also linear in the number of in­ stances. The cost of extending the ITVS algorithm is a global increase in time complexity quadratic in the number of instances. The gain is twofold: firstly stor­ ing less instances will reduce the memory needed by the algorithm. Secondly, in case the size of S or g is expo­ nential in the number of instances, the worst case time complexity of the search is exponential in the number of instances. With a branching factor b, reducing the num­ ber of instances with a factor k, would then reduce the time complexity with a factor b/c.

The paper is organized as follows: Section 2 briefly reviews the definitions and invariants of the datastruc­ tures used in ITVS. Section 3 describes the theoretical background for discarding instances. In Section 4 we give an algorithm for updating ITVS's datastructures consistently. In Section 5 we show that the most impor­ tant properties of ITVS are preserved. Related work is discussed in Section 6. Finally we conclude in Section 7.

2 Iterative Versionspaces

In this section, we will briefly introduce some notation and review the ITVS algorithm. For a more detailed description of ITVS, we refer to [Sablon et al., 1994].

The language of hypotheses is denoted by .C. We as­ sume the single representation trick applies 1 , so that in­ stances also belong to .C. Both relations "is more specific than" and the classical "is covered by" on .C can then be denoted by one symbol ~. We assume there is a max­ imal element T and a minimal element .l in .C. As in [Mellish, 1991] ITVS accepts four kinds of instances:

• a positive lowerbound (or positive example) i must be more specific than the target concept c, i.e., i ~ Cj
• a negative lower bound (or negative example) i must not be more specific than the target concept c, i.e., -.( i ~ c );
• a positive upperbound i must be more general than the target concept c, i.e., c ~ i;
• a negative upperbound i must not be more general than the target concept c, i.e., -.( c ~ i ).

The set of all instances at a given moment is denoted by I. Positive lowerbounds and negative upperbounds are referred to as a-bounds. Positive upperbounds and negative lowerbounds are referred to as g-bounds. That hypothesis c is consistent with the instance i, is denoted by c "' i. For a given positive lowerbound, resp. neg­ ative upperbound, i and a hypothesis c, the complete generalization operator lub( c , i ) (least upper bounds), resp. msg( c, i) (most specific generalizations), com­ putes the maximally specific generalizations of c consis­ tent with i. For a given positive upper bound, resp. nega­ tive lowerbound, i and a hypothesis c, the complete spe­ cialization operator glb( c , i ) (greatest lower bounds), resp. mgs( c , i) (most general specializations), com­ putes the maximally general specializations of c consis­ tent with i. S is the set of all maximally specific hy­ potheses consistent with I, 9 the set of all maximally general hypotheses consistent with I. In order to repre­ sent the set of all consistent concept representations by S and 9 , we assume that the admissability constraint holds on .C, i.e., every chain in .C contains a maximal and a minimal element [Mitchell, 1978].

ITVS is a bi-directional incremental depth-first search algorithm on .C using the following datastructures:

• ITVS stores one current maximally specific hypoth­ esis s and one current maximally general hypothesis g, both consistent with all a-bounds and g-bounds;
• ITVS stores all a-bounds in an array I, and all g­ bounds in an array I 9 · n, is the total number of a-bounds, ng is the total number of g-bounds;

1 [Sablon, 1995] shows that the presented results can be generalized beyond the single representation trick.

• ITVS stores specific-to-general backtrack infor­ mation on the stack 2 B,, containing triplets 3 ( ind , Sind , altind ) , called choicepoints (see Fig­ ure 1 ); ind is an index in I,, Sind is a hypothesis, and altind is a non-empty list of hypotheses used to backtrack on s and to test maximal specificness of s. Similarly, the stack B 9 contains choicepoints ( ind , gind , altind ), where ind is an index in I 9 , gind is a hypothesis, and altind is a non-empty list of hypotheses used to backtrack on g and to test maximal generality of g.

Figure 1 shows a stack B, with three choicepoints. El­ ements of .C are drawn as squares. In each choicepoint the squares on the left of Sind are already discarded al­ ternatives. altind contains the alternatives still to be explored. Sind is the alternative currently explored: its minimal generalizations are in the next choicepoint.

The Candidate Elimination algorithm of [Mitchell, 1982] is a bi-directional breadth-first algorithm which computes and stores S and 9 completely for every new instance. ITVS being a depth-first algorithm only stores one element s E S and one g E 9, together with back­ track information B, and B 9 · When s (or g) is incon­ sistent with a new instance, ITVS generalizes s (resp. specializes g), or selects a next alternative on B, (resp. on B 9 ) and reprocesses all instances encountered since the choicepoint of the alternative was created. Therefore ITVS stores all instances in I, and I 9 · By backtracking, ITVS can reconstruct S and 9 for each new instance.

During the search the following invariants hold:

1. s E S and g E 9;
2. for all choicepoints ( ind1 , s1 , alt1 ) on B,: s1 =<- s and -.( a1 =<- s ) for every a1 · in alt1; s1 and all elements of alt1 are maximally specific hypothe­ ses consistent with all g-bounds and the first ind1 a-bounds; for every choicepoint ( ind2 , s2 , alt2 )

2 We employ the usual operations push, pop and is_empty on stacks. Elements are added on and removed from the top of the stack.

3 W.r.t. [Sablon et al., 1994] choicepoints are extended with -'ind, resp. 9ind, necessary for an efficient implementa­ tion of the algorithms in Section 4 (see also footnote 7).

• closer to the top of B,: ind1 < ind2, s1 ~ s2, s1 ~ a2 and ·( a1 ~ a2 ) for every a1 in alt1 and for every a2 in alt2;
• for all choicepoints ( ind1 , g1 , alt1 ) on B 9 : g ~ gl and ·( g ~ a1 ) for every a1 in alh; g1 and all elements of alt1 are maximally general hypothe­ ses consistent with all a-bounds and the first ind1 g-bounds; for every choicepoint ( ind2 , g2 , alt2 ) closer to the top of B 9 : ind1 < ind2, g2 ~ g1 and a2 ~ g1 ·( a2 ~ a1 ) for every a1 in alt1 and for every a2 in alt2;
• Completeness of sand B,: for all c E £,consistent with I, s or an alternative on B, 4 is more specific than c;
• Completeness of g and B 9 : for all c E £,consistent with I, g or an alternative on B 9 is more general than c.

Note that ifthe top choicepoint of B, has index n., Sind of the top must be equal to s. Also note that the alterna­ tives on B, are actually the roots of the search subtrees that are still to be searched. ITVS tests for maximal specificness of an hypothesis a3 by testing whether or not there is an alternative a1 on B, which is more spe­ cific than a3 (see Figure 1). In other words, this tests whether the search subtree rooted by a3 is a subtree of the tree rooted by a1. If it is, a3 is not further gen­ eralized at this moment (so it is not allowed in alt3 ), because either it is not maximally specific, or it will be generalized later when all generalizations of a1 are be­ ing searched. Thus an optimal generalization operator 5 , meaning that every hypothesis is generalized only once, is implemented explicitly. All these arguments dually hold for g and B 9 ·

An important theoretical result about ITVS is the fact that its worst case space complexity is linear in the num­ ber of instances, while the worst cast case time com­ plexity could be exponential (though only a linear fac­ tor worse than the Candidate Elimination algorithm, if S and 9 are exponential in size and have to be computed for each new instance). Another result is the fact that the worst case time complexity of testing maximal speci­ ficness of s or maximal generality of g is also linear in the number of instances.

3 Redundant instances

In this section, we will develop a theory to reason about redundant instances. Due to space limitations proofs are omitted and can be found in lSablon, 1995].

We first define the information elements we are fo­ cussing on. Theorem 2 proves they are redundant.

Definition 1 (s-prunable and g-prunable)

• i1 E I, is s-prunable w.r.t. i2 E I, iff

·with "an alternative on B." we mean "an element of altind for a choicepoint ( ind , Sind , altind ) on B.". Also, with "all alternatives on B ·" we mean "all elements of altind for all choicepoints (jnd , Sind , altind ) on B.".

& An optimal generalization operator is dual to an optimal refinement operator (see [Sablon et al., 1994]).

• i1 and i2 are both positive lowerbounds such that i1 ~ i2, or
• i1 and i2 are both negative upperbounds such that i1 ~ i2, or
• i1 is a negative upperbound and i2 is a positive lowerbound such that i1 ~ i2.
• i1 E I, is s-prunable in I, iff 3i2 E I, such that i 1 is s-prunable w. r. t. i 2 ·
• i1 E I 9 is g-prunable w.r.t. i2 E I 9 iff
• i1 and i2 are positive upperbounds such that i2 ~ i1, or
• i1 and i2 are negative lowerbounds such that i2 ~ i1, or
• i 1 is a negative lowerbound and i 2 .is a positive upperbound such that i2 ~ i1 .
• i1 E I 9 is g-prunable in I 9 iff :li2 E I, such that i1 is g-prunable w. r. t. i 2 ·

Theorem 2 Given c E £. Also given i1, i2 E I 9 such that i1 is g-prunable w.r.t. i2, or i1, i2 E I. such that i1 is s-prunable w. r. t. i2. Then i2 ,...., c implies i1 ,...., c. 0

The proof of Theorem 2 is a repeated application of the transitivity of~. As a consequence of Theorem 2, we do not have to store all instances, but rather only the non s-prunable ones and the n·on g-prunable ones. In other words, only the mazimally general positive lowerbounds and negative upperbounds, and the mazimally specific positive upperbounds and negative lowerbounds are to be stored. Whenever we detect that a previously stored s-bound i1 is s-prunable w.r.t. a newly provided one i2, we replace i1 by i2 in I,.

So far we assume all instances are provided to the con­ cept learning algorithm. However, under certain condi­ tions new instances with an information content equiv­ alent to the provided ones can be automatically created. Moreover, the automatically created instances enforce that more provided instances will become s-prunable or g-prunable, so that less instances have to be stored, i.e., data is compacted without loss of information content. We will now describe some conditions under which such instances can be automatically generated.

Lemma 3 Given c E £. Also given

1. two positive lower bounds il and i2 such that lub{ i1 , i2 ) = { i } , or
2. two positive upperbounds il and i2 such that glb( i1 1 i2 ) = { i }.

This means that whenever two positive lowerbounds have a unique least upper bound they may be replaced by this least upperbound without loss of information, and whenever two positive upper bounds have a unique great­ est lowerbound, they may be replaced by this greatest lowerbound. Note that in a conjunctive tree-structure language and in Inductive Logic Programming using 8subsumption lub and glb are always unique.

Theorem 4 Given i1 E I and a new instance i2, fulfill­ ing Condition 3.1 or Condition 3.2. The set of hypothe­ ses consistent with I U { i } is the set of hypotheses con­ sistent with I U { i2 }. Moreover, i1 is s-prunable w.r.t.

i under Condition 3.1 1 and g-prunable w.r.t. i under Condition 3.2. D

In particular, in the case of a positive lowerbound i 2 , for instance, i can be provided to ITVS instead of i2 without losing any solutions. Then i 1 becomes redun­ dant. Whenever a least upperbound i replaces a positive lowerbound i1, all other a-bounds will have to be checked whether they are not a-prunable, or whether they have more than one least upperbound with i. Unfortunately, the result of replacing instances repeatedly depends on the order in which the instances are provided.

Negative instances cannot be generalized or special­ ized in the same way. However, a special kind of negative instances can be transformed to positive instances.

Definition 5 (A general notion of near-miss) A near-miu 6 w. r. t. c E .C is a negative lowerbound in such that { :z: E mga( T 1 in } I c ~ :z: } is a singleton { iu }.

Because of the single representation trick, positive lower­ bounds are also in .C. Given a near-miss in w.r.t. a pos­ itive lower bound ip, the target concept must be more general than ip to be consistent with ip, but also more specific than the corresponding iu to be consistent with i,.. In other words, iu is a positive upperbound con­ straining the search space in the same way as in does. If we replace each near-miss w.r.t. a positive lowerbound by its equivalent positive upper bound, we can apply The­ orem 4 when appropriate. [Sablon, 1995] also formulates a dual result for a-bounds.

This definition of near-miss is consistent with the usual definition in a conjunctive tree-structure language, since mgs( T , in ) will only be a singleton if in and a differ in only one attribute. Theorem 4 explains that providing the only consistent maximally specific hypothesis a as positive lowerbound is equivalent to providing all actual positive lowerbounds. In this case all near-misses can be replaced by exactly one positive upperbound, since the corresponding positive upperbounds have only one greatest lowerbound (glb). This corresponds to the re­ sult of [Smith and Rosenbloom, 1990].

4 The algorithm

In the previous section we have determined which in­ stances are redundant. We will now modify ITVS such that no redundant instances are stored. This will be enforced by the following two extra invariants:

1. no element in I, is a-prunable , and
2. no element in I 9 is g-prunable.

Given these invariants, how to update ITVS's datas­ tructures once a redundant instance is detected? We describe an extension of ITVS to discard a-prunable in­ stances. Pruning g-prunable instances from I 9 is done dually. Also, replacing instances using Theorem 4 is not discussed because of space limitations.

In ITVS, when i1 is a-prunable w.r.t. i, a naive method to update B, would be replace i 1 in I, by i and to reprocess all a-bounds with an index in I, larger than the index of i 1 . However, this reprocessing could lead to recomputing and generalizing previously discarded ele­ ments of .C. Therefore, we will update all alternatives on B., instead of recomputing them, while respecting B, 's invariants. A dual argument holds for B 9 ·

5 0riginally introduced by [Winston, 1975].

Further on we also need the following lemmas:

Lemma 6 Given c1, c2 E .C with c1 ~ c2 and a positive lowerbound i:

Lemma 7 Given c1, c2 E .C with c1 ~ c2 and a negative upperbound i:

These lemmas assure that generalization in some sense preserves the property of being more general. Analogous lemmas exist for glb and mgs (see [Sablon, 1995]).

We will now describe how we extended ITVS to satisfy Invariant 6 and Invariant 7. When a new a-bound is provided to the original ITVS, this a-bound is added to I., then g and B 9 are updated, and then s and B, are updated. W.r.t. the original ITVS only the latter operation (i.e., the call generalize( s , B, , Bind ) in line @on page 399 of [Sablon et al., 1994]) should be replaced by a call to Algorithm 1 with the same arguments.

Given the a-bound i:

• 1 Search I, from 1 to n, for the first instance I, [nc] that is s-prunable w.r.t. i, or such that i is s-prunable w.r.t. I,[nc]
• 2 If no such instance can be found, then handle i as before in ITVS
• 3 Otherwise, remove i from I,, and:
• 4 If i is s-prunable, then do nothing
• 5 Otherwise, I, [nc] must be s-prunable. Then:
• 6 Replace I, [nc] by i
• 7 Generalize B, as in Algorithm 2 This yields s, B, and ind, the index up to where s is consistent with all a-bounds
• 8 Find a consistent with I and corresp.
• B, with the call generalize( s , B, , ind)
• 9 Return sand B,

Algorithm 1 Handling a new a-bound

Algorithm 1 first checks whether Invariant 6 on I, is still satisfied (Step 1 ). If it is (Step 2), ITVS continues as before (i.e., with the call generalize( s , B, , Bind ); see above). If i is s-prunable, it is just removed from I, (Step 3 and Step 4). Otherwise it is also removed from I., and then replaces I,[nc] (Step 6). Then B, must be updated to satisfy Invariant 2 and Invariant 4 of Section 2 (Step 7). This is explained in Algorithm 2. The result is a new maximally specific concept representation s, the updated B., and an index ind such that s is consistent with all g-bounds and with the first ind a-bounds. Fi­ nally, a new maximally specific concept representation consistent with all instances must be computed using the procedure generalize of [Sablon et al., 1994]. This call will satisfy Invariant 1. In Algorithm 1 and Algo­ rithm 2 neither g, nor B 9 , nor I 9 , nor n 9 are changed, so Invariant 3 and Invariant 5 are preserved all the time.

"

Figure 2 Two consecutive choicepoints of B,

--·

In general terms, Algorithm 2 works as follows: it first pops the choicepoints of B, that are to be generalized from B, and pushes them onto a temporary stack Bh. It then generalizes these choicepoints one by one w.r.t. the new instance i. The result is a new B, satisfying Invariant 2 and Invariant 4. Simultaneously, all instances i' s-prunable w.r.t. i are removed from I., by shifting the instances following i' towards the front. We will now discuss Algorithm 2 in more detail.

Step 10 to Step 14 consist of initializations. Bh con­ sists of all choicepoints of B, with index larger than or equal to nc in reversed order (Step 12). Also, it is en­ sured that the bottom choicepoint on Bh has s as Bind (Step 11) to handle s as any other Bind, and to be cer­ tain that Bh is not empty. For each ind, new..llind will replace Bind on the generalized B,; new _ind is the index in I, up to where elements of I, have been checked for not being s-prunable, and up to where new..llind is con­ sistent with all a-bounds; n~ is the index up to where J, contains the non s-prunable instances of I, [l..nc]. Ini­ tially, new_ind = n~ = nc (Step 14), since I, [nc] was the first s-prunable instance in I, (see Algorithm 1). Finally, pruneJh will be true iff the rest of Bh cannot be gen­ eralized consistently; prune_Bh is initialized to false .

Let ( ind1 , s1 , alt1 ) and ( ind2 , s2 , alt2 ) be two consecutive choicepoints such that ind1 < ind2, s2 and the elements of alt2 are more general than s1 , maximally specific and consistent with all g-bounds and with I,[l] to I, [ind2]. This situation is presented in Figure 2. The squares depict the state of the two choicepoints before Algorithm 2. The dashed arrows represent ::;.. The cir­ cles are generalizations of the square they are connected to. The numbers inside the circles are labels.

We explain what happens inside the repeat-loop (Step 15) when choicepoint ( ind2 , s2 , alt2 ) is popped from Bh (Step 16). Suppose that choicepoint ( ind1 , s1 , alt1 ) has already been generalized: the new s1 is labeled 1, the elements of the new alt1 are labeled 2 and 3. First s2 is generalized (Step 17): gens1 should contain all maximally specific consistent generalizations of s2 , not reachable from an alternative on B, and not yet explored or discarded before. First all minimal general­ izations consistent with i are computed: if i is a positive lowerbound it is the set lub( s2 , i ); if i is a negative up­ perbound it is the set msg( s2 , i ). On Figure 2 these generalizations are labeled 4 and 5. From this set of generalizations, generalizations that are not consistent (Step 18), or not maximally specific, as well as those still reachable from some alternative in alt2 or on B,, are removed. The latter two conditions are implemented as in ITVS by Step 19 and Step 20 (see Section 2). This shows the use of an optimal generalization operator is still possible in the extended ITVS. Finally, since all el­ ements in gens1 are generalizations of s2, and since all alternatives more general than s2 and still to be explored are the alternatives on Bh, together with s, Step 21 se­ lects only those generalizations more general than s or than some alternative on Bh. The list of selected ele­ ments is assigned to gens1. In gens1 all elements are more general than the hypothesis labeled 1, since each of the generalizations of s2 is more general than some generalization of s1 (Lemma 6 and Lemma 7) and since the ones more general than the elements labeled 2 (which are on B, already) are not selected for gens1.

Then all elements of alt2 are generalized (Step 22): gens2 should contain all maximally specific consistent generalizations of the elements of alt2, not reachable from another alternative on B,. First all minimal gener­ alizations consistent with i are computed: if i is a posi­ tive lower bound it is the union of all sets iub( a , i ), with a E alt2; if i is a negative upperbound it is the union of all sets msg( a , i ), with a E alt2. On Figure 2 this union consists of the circles labeled 6. From this union, generalizations that are more general than another such generalization (Step 23), not consistent (Step 24), or not maximally specific, as well as those still reachable from some other alternative in gens1 or on B,, are removed. The latter two conditions are again implemented as in ITVS by Step 25 and Step 26. The selected elements are assigned to gens2. Like for gens1, all elements of gens2 are more general than the hypothesis labeled 1.

Then, if gens1 is empty, every generalization of s2 consistent with i is more general than an alternative on B,. Therefore it is not necessary to generalize the other alternatives on Bh, since they are all generalizations of s2, so prune...lh is set to true (Step 28). All remaining non s-prunable instances of I, are shifted in I, towards the front (Step 29).

Otherwise, if gens1 is not empty, of all instances I,[new_ind + 1] up to I,[ind2] only the ones not s­ prunable are shifted in I, towards the front, thus re­ moving the s-prunable ones (Step 31).

Then a new value for new_sind must be chosen. If gens1 is not empty, one element of gens1 is chosen. If it is empty, an element of gens2 is chosen. In both cases, the rest of gens1 U gens2 contains alternatives to be ex­ plored later, and is assigned to altind· If gens1 and gens2 are both empty, a choicepoint ( ind , Sind , altind ) is popped from B., and one of the elements of altind is chosen as new_sind· If gens1, gens2 and B, are all empty, no hypothesis consistent with all instances ex­ ists. Consequently, ITVS fails and halts. In all three non-failing cases, new _sind and all elements in altind are then consistent with all g-bounds, and consistent with 1,(1] up to I,[ind]. Since ind is the index up to where new_sind is consistent with all s-bounds, and the numher up to where the elements of I, are checked for being s-prunable, ind must be the new value of new_ind.

By induction, Invariant 2 holds after the loop. After the loop n~ is assigned ton, (Step 36), since it is the in­ dex up to where I, contains all non s-prunable s-bounds. Finally, new_sind, consistent with new_ind s-bounds, the updated B, and new_ind are returned.

[Sablon, 1995] proves that Invariant 4 is also preserved, i.e., that no solutions are lost during the update of B,.

5 Discussion

First note that Invariant 6 and Invariant 7 are expressed solely in terms of I,, reap. I 9 , and are therefore indepen­ dent of any search strategy or concept language: they only constrain the set of instances that is stored.

We now discuss the cost of extending ITVS with Al­ gorithm 1 and Algorithm 2.

Theorem 8 The original ITVS and the eztended ITVS have the same worst case space complezity: they are lin­ ear in the number of instances. 0

In the case of s-bounds, the proof actually shows the following: suppose i1 - i2- i3 is a sequence of s-bounds, where i 1 is s-prunable w.r.t. i 3 , and not s-prunable w.r.t. i 2 · When provided to the extended ITVS, this sequence gives exactly the same B, as when the sequence i 3 - i2 were provided to the original ITVS 7 · Consequently, both algorithms have the same worst case space complexity.

For the worst case time complexity, we count the num­ ber of ~ tests (see also [Mitchell, 1982]).

Theorem 9 The worst case time complezity of the ez­ tended ITVS has an eztra term of 0{ n 2 }, where n is the number of instances. 0

On the one hand, no parts of the search space are ex­ plored more than once in the extended ITVS. On the other hand, as a consequence of Theorem 8, the worst case time complexity of the tests for maximal general­ ity and maximal specificness remain linear in the num­ ber of instances. Consequently, we only have to add the overhead of testing instances for being s-prunable or g-prunable, and the overhead of updating B, and Bg­ In case no s-prunable instances are provided to the ex­ tended ITVS, it will have an overhead w.r.t. the original ITVS of comparing each new s-bound to all previous s-bounds, and comparing each new g-bound to all pre­ vious g-bounds. Furthermore, for detecting near-misses and their dual counterpart, s-bounds are also compared to g-bounds, and vice versa. If an instance is found to be s-prunable, the major term in generalizing B, is the com­ parison of each newly generated hypothesis in Step 22 to all elements on B., i.e., also a term of 0( n 2 ).

7 Note that we really needed to extend the original repre­ sentation of ITVS with Bind to obtain this result. If we would not be able to generalize Bind in each choicepoint (see Step 17 of Algorithm 2), but rather generalize only altind, and finally generalize s, the worst case space complexity would be worse than the one of the original ITVS. In that case each alterna­ tive on B, would potentially be replaced by b, others (where b, is the generalization branching factor), in the worst case leading to b';· alternatives on B,.

Although the worst case time complexity has increased w.r.t. ITVS's, it has only increased with a quadratic term, while, if the size of S or 9 is exponential, reduc­ ing the number of s-bounds, resp. g-bounds, would also reduce search time with an exponential factor. ·

6 Related Work

The ideas extend the work of [Sebag, 1994], [Sebag and Rouveirol, 1994] and [Smith and Rosenbloom, 1990] in a language independent framework. In [Sebag, 1994], which is restricted to conjunctive tree-structure lan­ guages, negative lowerbounds are converted into pos­ itive upperbounds, and only those nearest to the tar­ ~et concept (i.e., the most specific ones) are stored. In lSebag and Rouveirol, 1994] this is extended to nega­ tive lowerbounds in ILP, which are represented by in­ tegrity constraints and ordered by 0-subsumption. In our framework we can generalize the notion of a nearest miss (which is introduced in [Sebag, 1994] and defined as a negative lowerbound which is not s-prunable) to all negative instances neither s-prunable nor g-prunable.

Two aspects of INBF [Smith and Rosenbloom, 1990] can be compared to ours. In the specific-to-general search INBF drops all positive examples, because no backtracking is needed in searching specific-to-general in a conjunctive tree-structure language. Using Theorem 4, our approach would also drop all positive lowerbounds, except one (which would then coincide with s), because any two positive examples will have only one least upper­ bound. In the general-to-specific search INBF processes and then forgets all near-misses w.r.t. s. Its maximally general hypothesis upper is only kept consistent with all positive examples and all near-misses, so no backtrack­ ing is needed. Our notion of a near-miss generalizes this approach, by converting all negative lower bounds to pos­ itive upperbounds, and considering their greatest lower­ bound (i.e., upper) as a positive upperbound.

[Hirsh, 1990] informally describes a technique of "skip­ ping data that do not change the versionspace" in the context of the Incremental Versionspace Merging algo­ rithm. Intersecting a versionspace V S1 with V S2, and then with a subset V S2' of V S2 will always yield the lat­ ter intersection. Consequently the first intersection oper­ ation was not necessary. In our framework, we more for­ mally describe the approach using the notions s-prunable and g-prunable, we relate these notions to the concept of near-misses and to INBF, and provide a framework to automatically generate new information elements.

7 Conclusion

We have introduced the notions of s-prunable and g­ prunable instances and a generalized notion of near-miss. Using these we identified redundant instances. We also introduced automatically created instances, that made other instances redundant without any loss of informa­ tion. This resulted in data compaction. Furthermore, as in [Smith and Rosenbloom, 1990], this paper shows that near-misses (and their dual counterpart) play a very im­ portant role in converging towards the target concept.

We have also shown how s-prunable and g-prunable instances can be discarded in the framework of Iterative Versionspaces, without losing the most important prop­ erties of the ITVS algorithm.

Acknowledgements

Luc De Raedt is supported by the Belgian National Fund for Scientific Research and by the ESPRIT project Nr. 6020 on ILP, and is co-financed by the Flemish Govern­ ment under contract no. 13/0/4.