Empirical Bias for Version Space

1. Introduction

We assume the reader to be familiar with the main concepts elaborated by Mitchell [1978] in his work on generalization as a search in a version space (VS). We just want to emphasize in this section the main limitation of the approach and the need for a more constrained algorithm.

1.1 The issue : the bias

The candidate elimination algorithm (CEA) is a double constrained search in a space lying between and represented with two sets of generalizations: a boundary set S of most specific generalizations and a boundary set G of most general generalizations. The main limitation we want to address in this work is the constraint on acceptable generalization languages due to the quadratic dependency of the complexity of the algorithm to the size of the boundary sets. Due to the cost of an elementary treatment for a single instance, the size of S and G becomes too large for applications where the version space contains large "slices", that is large sets of ;::::_uncomparable elements 1 (see § 2.1 ). The issue is to impose further restrictions on the shape of the version space.

1 Note that it only weakly depends on the branching of the

Several means have been explored in order to express constraints on the class of admissible and inadmissible patterns for generalizations. The main ideas have been to take into account a theory of the domain of learning [Michalski,1983], to introduce a bias on the language of generalization (and/or. on the generalization operators) and then refine it by necessity [Utgoff, 1986], and to specify a more constrained preference criterion [Blumer, 1987; Nicolas, 1988].

1.2 What is needed

All these attempts share the common characteristic to introduce formalized knowledge in the generalization mechanism. Though it is the neatest way to focus the search mechanism, we claim that this represents only one part of the control knowledge. We need a more empirical ability to express constraints, according to the empirical approach chosen in generalization from examples. Concept learning is dedicated to a performance element. This performance element may have some ideas about the shape of the concept definitions it needs. However, it is not coherent to ask for this knowledge only in an abstract way. since it is assumed that the main work of the generalization algorithm is abstraction on the data of the performance element

We illustrate our purpose on several cases.

· Assume the performance element to be a human specialist Even if he does not know the precise definition, nor formalize enough knowledge to help the search of the concept he is looking for, he seldom has no idea of it. He can generally give an approximate definition of this concept This generalization is not consistent in most cases but provides useful hints on the type of generalizations that the specialist is looking for. This may be considered as a form of learning by instruction.

·When the performance element is automated, it may also be the case that approximate generalizations are available.

partial ordering ~.

Our ideas originate in fact from such a situation. We are tackling a "real world" problem, the conceptual clustering of phlebotomine sandflies of French Guiana [Lebbe et al., 1989]. On the one hand, we need a rich representation language which precludes the simple application of the CEA. On the other hand, we use a statistical module which is able not only to build some clusters, but also furnish some clues concerning the form of each cluster characterization. It provides information about attributes involved in the emergence of a cluster which can be combined to build some approximate generalizations.

·Finally, another way to generate approximate descriptions is to use a generalization algorithm with a strong bias on a training set of instances. The bias leads on one side to a search in a high level abstracted space and ensure a quick convergence of this search. On the other side the learned generalizations are rough (they are likely to become inconsistent with the treatment of more instances) and represent only an indication of the desired ones. Note that if we know some means to exploit these approximations, this process may be iterated. For example, we may first restrict the generalization langage to kCNF descriptions, with k fixed, and progressively increase k by a constant step p.

2. The version space revisited

We assume now that approximate descriptions (generalizations) are available as an input for the C.E. algorithm. The issue then becomes : How to extend it in order to make profit of these supplementary data without loosing the good properties of the original algorithm? The two subproblems are: 1) How to fonnalize an approximation and 2) How to modify the original algorithm. The development of the ftrst point has led to the concepts of focus set and seed set, which are presented in this section. The second point is the subject of section 3.

The focus set is a set of consistent descriptions (approximations). The elements of the seed set may be not consistent.

2.1 Definition of a focus set

We introduce in this paragraph the basic concept of our extension. The Version Space approach requires the initialization of two sets of descriptions, namely the S-set and the G-set. We require the consideration of a new set of descriptions for our algorithm, called the Focus set (F-set). This set is intended to provide a structural bias on the version space. Indeed, a version space may be viewed as a collection of paths between some element of S and some element of G. The focus set restricts the allowed paths by giving intermediate nodes along these paths.

Let us ftrst introduce a preliminary definition. Definition Let x, y, z be descriptions. x and y are ;;:: _comparable or there exists a path between x andy iff -Q.y v y~. We note xQy y is between x and z (resp. strictly between) iffxq~ v uy~x (resp x>y>z v z>y>x). We note ye [x~~z] (resp. ye ]x~~z[ ) These definitions may be naturally extended for sets.

The focus set is simply a set of descriptions which have to belong to the initial VS (we say VSdefinable), such that every concept description c (a target generalization) is "attainable" by at least one of these (say fbest)· We now make precise this concept of attainability in a VS. The casual reader may skip to the proposition without inconvenience. To be attainable means at least to be comparable with. However, we need a supplementary property, governing the consisten­ cy of the whole set. This property will guarantee, during the search for generalizations, that no interaction between two or more elements of the focus set precludes the paths leading from fbest to c to be eventually followed by the search algorithm. For this purpose, we introduce the notion of representativeness. A set of descriptions F is representative of a set of concepts if, when there exists a path from a element ofF to a concept, there exists a no-deviation path between these two elements. That is, a set of descriptions F is representative of a set of concepts if, for every path starting at the same element ofF, one going through c and the other {the deviation) through another element f ofF not comparable with c, there exists a third distinct element ofF which is comparable with c and not comparable with f.

Formally, it leads to the following definition.

Definition Let C be the set of target (consistent with any proposable instance and VSdeftnable) concept descriptions. F is representative ofC iff 'v'ceC 3feF 'v' fieF

f<>c" (f~1" --..fl<>c ~ 3f2eF --..fl<>f2 "f2<>c) F is a focus set iff F is VSdeftnable and representative of C.

For instance, consider the version space containing the formulas pvqvr, pvq, pvr, p,q,r, pAq, pAr, pAqAr. Assume C={q} to be the target concept and fl~f2 iff f1 ~f2. Then F={pvq,p} is not representative of C, because pvq is the only element ofF comparable with q, p ~ pvq and --,p<>q. However, {pvq, p, q} and {pvq, pAq} are focus sets.

We next state that the focus set is an extension of the boundary set concept (proofs may be found in [Nicolas 91]).

Proposition

• 1 The S-set S and G-set G of any VS of C are focus sets.
• 2 Let F be a focus set. Then SuF and GuF are focus sets.

2.2 Interpretation of a focus set

We now want to show that, if the focus set is an extension of the boundary set concept, the size of the version space itself, with a natural interpretation of this focus set, may only be reduced with the input of such a set. This is because it leads to an extension of the constraints on the set of consistent generalizations. We defme for this purpose the interpretation of the focus set in terms of a search inside a version space.

We first recall the interpretation of the boundary sets in the Candidate Elimination Algorithm of Mitchell, with the point of view of focus sets. Consider the union of boundary sets U=SuG characterizing a version space. It is a focus set (propositions 1&2). Now, the goal of the CEA. may be defined in terms of the maintenance of this focus set with the input of new instances. The updating method is a kind of bidirectionnal search, with the following meaning: in order to maintain one of the boundary sets B, consider all the paths from each inconsistent element b of B to the consistent elements of U\B 2'!:_comparable with b.

We keep this same point of view to describe the search when considering an additionnal focus set F. Then, the set of generalizations to be maintained becomes U = SuGuF. The updating method is a bidirectionnal search, with the following meaning: in order to maintain one of the boundary sets B, consider all the paths from each inconsistent element b of B to the elements of U\B 2'!:_comparable with b and "nearest" from b (that is most specific if B=S or most general if B=G). Otherwise stated, we do not explore the paths between two comparable points from the boundary sets but we explore the paths between two comparable points from the focus set Since the focus set is representative, we ensure that eventually, a path leading to a concept defmition will be explored.

We end this section with an illustration of the decrease of complexity of the search on a simple but enlightening example. Assume the language of generalizations to be representable with a boolean lattice of boolean functions with n variables (2n atoms). The initial version space is characterizedwith S = {False} and G={True} and contains exactly 2 2 n consistent generalizations (these can be built from the variables and the v," and...., connectives). Assume the focus set F to be composed of elements involving only m variables m~n. Then it is easy to show that the search for consistent generalizations will be focussed such that none of the elements of the inner version space, which is the boolean lattice generated from the n-m other variables, will be explored. That is, the size of the search space is reduced by 2 n-m at least 2 . A related problem consists of determining how far we can go in the reduction, given a suitable focus set. In our example, the answer is quite simple. The maximum of reduction is reached when there is only one path in the version space to be considered. In the boolean lattice, all paths are 2n long. So, one can ultimately reduce the size of the search to 2n, that is, the elements of the focus set itself. More generally, if the focus set contains two adjacent nodes of the lattice, the space is reduced by 2n -1 elements.

2.3 Definition of a seed set

One of the basic points common to all generalization methods consists of effectively producing the set of concept defmitions, starting from a well-chosen set of descriptions and then progressively refining them by application of generalization and specialization operators, in order to achieve the selection criteria. The focus set provides such a set of descriptions.

However, providing a set, whose elements belong to the version space, are representative of the concept descriptions, and differ from S or G, may be too strong a constraint in practice. This motivates the introduction of the seed set This definition is much less constraining than the previous one. It is intended to formalize the intuitive notion of "generalization pattern". The aim of the seed set is to capture the minimal assumptions to be made about such models or patterns, in order to guarantee that a solution can be reached. The next section provides a definition of the projection of the seed set on the version space, leading to the production of an associated focus set

Definition Let D be a set of descriptions

Dis a seed set iff D and Sou:Jo (initial version space) are comparable.

Note that this condition is not really restrictive, since D may be completed with as many elements of So lAio as necessary to obtain the comparability. The definition no longer requires that the elements of the set be consistent or representative of the concepts. However, even if it does not appear in the definition, recall the basic underlying assumption that elements of the seed set share strong links with the target generalizations.

The issue then is to map the seed set on to a focus set, taking advantage of this assumption. The idea is to keep the same notion of proximity between descriptions as in the generalization algorithm itself. That is, a description d 1 is close to a description d if they are comparable and a description d 1 is closer to a description d than a description d2 if d 1 is between d 2 and d.

2.4 Seed set and focus set

These last definitions rely on the focus set and the seed set concepts in such a way that the seeds are minimally generalized or specialized (closest to their original description). The notion of projection on a version space reflects these minimal refinements. F 0 is proposed first. If it is not sufficient to find the concept C, then the new projection F1 is produced and the algorithm restart from these new approximations, etc ... The focus set is defined as the convergence of a sequence of trials F 0· F 1· F 2·· .. (see figure) progressively loosening the strength of the links between the seed set D and its projection (in the direction of S or G), until the boundary S or G is reached.

Definition Let S and G be the boundary sets of a version space. Let D be a seed set.

f is a projection of de D on (S ,G) with respect to a set of descriptions E iff 'Vxe (]fQd]\E)

f SGdefmable) "fQd" f~ (E\S\.AJ)" x not SGdefmable F is the closest focus set from D w.r.t. E .if['Vf

feF¢::> 3de D s. t f is a projection of don (S,G) w.r.t. E

The next proposition reflects the desired properties of this definition.

Proposition For every seed set D, there exists a set E s.t the closest focus set F from D w.r.t. E is a focus set

proof: It is sufficient to choose for E the set of all descriptions. In that case, since D and S OI..AJO are comparable, the projection reduces to SOI..AJO. which is a focus set

However, this choice forE represents a worst case, where the search occurs in the whole initial version space. The seed set is not pertinent, i.e., it conveys no additional information with respect to SO\..()(). The idea of the algorithm is to start from a closest focus set F where E=0 ("nearest" from D) and in case of failure, to restart with E:=F. More generally, each time a failure occurs, E is replaced with the union of the previous E and the closest focus set w .r. t this previous E.

Note that this search for the closest focus set can not be stated as a search in a version space, as there are no instances involved here.

3 The Informed Candidate Elimination algorithm

We designed a generalized version of the CEA, able to take into account the seed set as a new source of knowledge (this is not concurrent with the inclusion of other types of control knowledge). The CEA has two interesting properties that we need to preserve. First, its strategy is a bidirectionnal search. And second, if a concept is SoGo-definable. (i.e., in the original version space), then it will be found eventually. Since we have no idea of how accurate are the elements of the focus set for the concept at hand, the algorithm has to include a "repair" strategy, loosening the bias until the production of consistent generalizations for the whole set of instances. In fact, if the focus set is of no help for the defmition of the concept, the behaviour of the algorithm converges towards that of the CEA.

The general schema of the algorithm remains unchanged with respect to Mitchell's work. However, taking into account the duality of S and G and in order to emphasize the parameters and components of the generalization process, we present a parameterized form of this algorithm. A more detailled algorithm may be found in [Nicolas, 1991].

~ Informed_ Candidate_Elimination (S o,G O.FO) S:=SO; G:=Go; F:=FO; reset-instances;

.wnil single solution w: no solution w: no more instances %(S=G)Asingleton(S) or S=0 v G=0 or end_of_file%

w

1:= read_instances;

~ type(!) .il

positive -+ remove_in_boundary (incomplete, G)

update_boundary(incomplete, S)

remove_equivalent_or_not__preferred (S)

negative -+ remove_in_boundary(weakly _inconsistent, S) update_boundary(weakly_inconsistent,G) remove_equivalent_or_not_preferred (G)

end case end until

gil no genernlization: l F0=0

%unsucessfull search in the whole version space so, GO .tb!<n print no generalization

~ F1:=repair_focus_set(FO,SO,�O~

Informed_ Candidate_Elimination(SO ,GO.F1)

gil single generalization: print learning completed ~no more instances: print current version space endproc

The CEA requires the specification of two types of transformations on generalizations : most specific generaliza­ tions and most general specializations. Note that our algorithm requires the definition of two new simplified types of transformations on descriptions during the repair strategy. The specification of a projection is indeed a search for most specific generalizations and most general specializations, but it does not involve any instance. An illustration of these new operators is given in the next section.

4. Example: a feature value intervals space

This problem derives from the one described in [Mitchell, 1978]. It must be clear that it remains didactic.

The goal is to define a concept, whose characteristics are attributes taking their values in the domain of integerss. An instance is a vector (conjunction) of attributes with particular values. Assume here that the descriptions are represented with only two attributes. Following the single representation trick, instances are expressed in the same langage as generalizations. Assume the chosen representation to be:

<concept>~ (<interval (x)>, <interval (y)>) <interval (x)> ~ <int> <op> x <op> <int> <int> ~ integer ( E Z) I -oo I +oo

For example, the instance (5,3) is represented as (5~5. 3~y~3). The matching predicate and the order of specificity between concepts is simply the inclusion relation between couples of intervals. For example, the concept (3~x~7, 2~y~3) is more specific than (-1~x~7. O~y<+oo). Due to space restrictions, we can not give the diagrams illustrating the behaviour of the algorithm. Intermediary and final results of the algorithm are presented with the previous syntax, but we strongly encourage the reader to draw a graphical representation of the concepts.

Assume the following scenario for the initialization part.

The algorithm reads a frrst poSitive instance (1,1).

S is initialized to the singleton ( (1 ~ x ~ 1 , 1 ~ y ~ 1)}

Furthermore, we dispose of two approximative models, leading to the seed set

Then, a procedure computes the closest focus set from D and leads to the following result (notation: each element of the focus set has the form <identification number, description, list of immediate predecessors, list of immediate successors, list of comparable elements of S, list of comparable elements of G> ):

Elements 1 and 2 ofF are just the elements of S and G. The other elements are the least definable generalizations f of each element of D, that is, such that 2f.:!g.

We describe now the behaviour of the algorithm with the input of instances in the following order ( + for positive instances,- for negative instances):

The computation gives for Set G, after step (instance) 2: S = ((gx~2,gy~3),(~~1.~y~1) };

G = {(-oo <X~ 2,- oo <y<+oo), (-oo <X< +oo,- oo <y ~2)}

S has "absorbed" the focus points and contains fairly general concepts. After step (instance) 3:

Since the next positive instance is not included in any element of G, the algorithm fmd no generalization at step 4. The procedure repair_focus_set then computes a new focus set. In this example, assume the generalization operator of the projection is replacing one of the bounds of the elements in the focus set with the corresponding bound of a comparable element of the boundary sets. We are sure that the process converges in at most 4 calls for the repair procedure (one for each bound in a couple). Each time, instances are considered from the beginning.

The new focus set contains the following concepts:

With this new focus set, learning may be completed after step 5 and leads to the following boundary sets:

The convergence of the algorithm is remarkable in this case, where we only need 6 instances. Without D, the S set would be unchanged, but the G set would be

S. Related work

Many studies involving the bias problem have been developed since Mitchell emphasized the issue [Mitchell, 1980]. The common goal shared by all these studies is to hasten the convergence of the boundary sets. If one more deeply investigates the existing methods, one can divide them further in three main directions:

1. Definitions of constraints or properties on the set of preferred generalizations. Bias is included in the selection criteria. Michalski handles for this purpose a Lexicographic Evaluation Function concept [Michalski, 1983], to be defmed at a user level. At a theoretical level, we proposed some general logical criteria [Nicolas, 1988] for the selection of generalizations when the representation language includes negations and disjunctions.
2. Multiplication of the effect of an instance. Bias is included in a theory. Hirsch's approach [1989] consists of using a theory able to determine for some instances their type

(positive or negative). This theory allows the generalization of the explained instances with an EBG technique and to generate in such a way multiple instances of the same type and same explanation of their type. A related technique is the perturbation [Kibler and Porter, 1983], wich automatically explores the "nearest" instances from the observed instance.

3) Change of the representation language. Bias is included in the language. Utgoffs algorithm [Utgoff, 1986] initially searches for generalizations in a restricted space defined with a restricted language. In case where no generalization is found, the language is augmented with new terms which are linked to the previous one so as to produce a generalization. Russel and Grosof [Russel and Grosof, 1990] use a determination knowledge base, expressing dependencies between concepts, to build a pertinent version space for the concept to be learned.

Our approach may be viewed as a fourth direction, striving towards the inclusion of bias in the search control sets which are the boundary sets. One of the basic assumptions of learning from examples is that the knowledge is easily accessible at a specific, "instanced" level, but hard to produce at an abstracted, "theoretical" level. Our proposition is based on the same assumption. We require the bias at an empirical level.

Rendell's classification of biases [Rendell, 1987] considers three kinds of biases. Fixed bias is defined once for all, independently of any application. Parameterized bias is adjusted for some application by the user. Variable bias may evolve during learning, according to its results on some particular problems. The kind of bias we propose is basically a parameterized one. However, the focus set may be not only user defined, but also automatically generated from the results of another module (like a data analysis tool). This initial bias may be then refmed, if no satisfying generalization is found. Consequently, the bias possesses also a variable characteristics.

6. Conclusion

We have proposed a general framework enabling the development of further studies in the field of constrained generalization algorithms. It shifts the limitations on "blind" inductive learning [Dietterich, 1989] to the issue of building interesting approximations of the concept to be learned.

The worst case complexity remains unchanged in terms of S and G but it has to be defined in terms of the structure of the focus set or, even better, in terms of the structure of the seed set A basic interesting property is that the growth of the focus set is solely dependent on the growth of boundary sets: the other elements can just be discarded by the algorithm. The other main issue that remains to be explored is the design of an algorithm optimizing the adaptation of the bias (that is, choosing the new elements in the focus set) when the ICE

algorithm fails to produce a generalization. A related question occurs with the design of the seed set. Actually, it seems reasonnable not to produce this set once for all, but iteratively, with progressive refinements towards more and more detailled approximations.