Olivier Gascuel

Bernadette Bouchon-Meunier

Gilles Caraux

Patrick Gallinari

Alain Guénoche

Yann Guermeur

Yves Lechevallier

Christophe Marsala

Laurent Miclet

Jacques Nicolas

Olivier Gascuela

Bernadette Bouchon-Meunierb

Gilles Caraux3

Patrick Gallinarib

Alain Guenochec

Yann Guermeurb

Yves Lechevallierd

Christophe Marsalab

Laurent Miclete

Jacques Nicolasr

Richard Nock

Mohammed Ramdanib

Michele Sebagg

Basavanneppa Tallurr

Gilles Venturinih

Patrjck Vittec

Twelve numerical, symbolic and hybrid supervised classification methods

Keywords: Supervised classification, statistical methods, discriminant analysis, neural networks, classification trees, machine learning approaches, hybrid methods, waveform recognition problem

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

INTRODUCTION

Survey Motivation and Outline

Supervised Classification is the problem of learning a classification function from exam ples. If these examples are patients described through a certain number of symptoms or images of digits described by pixel values, a classification fu nction tcorresponding author. E-mail: gascuel@lirmm.fr *The authors are members of the French research group SYMENU which is composed of fifty participants from ten laboratories. SYMENU stands for "Numerical-Symbolic Discriminatio, n Methods". The group is supported by the French Ministry of Research and Education.

518

--�--•-•••----------must predict the class of these elements, in other words an illness or a digit. The goal is to construct these classification functions by using a set of previously clas sified examples a.s the only a priori knowledge. This is called the learning set. The subject is vast, involving numerous applications, and has already been extensively explored in the fields of statistics, pattern recognition and artifi cial intelligence. Depending on the field in question, supervised classifi cation appears under differ ent names ranging from discriminant analysis, discrimination and concept learning. Over the last ten years, several new approaches have appeared, in particular due to developments in the domains of Neural Networks and Machine Learning. These approaches share one common factor in that they facilitate the coexistence of sym bolic aspects, such as those found in example representation or in the manner in which the learned classification function is expressed, and numerical aspects, such as the introduction of frequencies and probabilistic criteria.

The aim of this paper, written by the French research group SYMENU, is to study these hybrid approaches, which combine symbolic and numerical aspects. We shall present a certain number of methods conceived (or improved) by members of our group. These methods issue mainly from Machine Learning and from re search on Classification Trees done in Statistics. They may also be qualified as "rule-based" in that they all use, in some respects, typically AI rules for form IF description THEN class. We shall provide a presentation of these methods, which should be simple but sufficiently complete, thus demonstrating the various ways of combining both the symbolic and numerical aspects, as well as the advantages and the inconveniences of these combinations. Besides, numerous other supervised clas sification approaches exist, which are mainly numerical and derived from Statistics, Pattern Recognition and Neural Networks. We shall present the most frequently used and cited of these methods. This will enable us to illustrate the specifici ties of hybrid, rule-based approaches. Moreover, the mere principle as well as the properties and recent developments of these classical methods often seem not to be well known by the Machine Learning community, and this paper could serve as an introduction to these aspects.

In the last few years, several systematic comparisons of various methods on data sets have been published. 6135 1 6 2 . In particular, King et al. provide a confrontation between 17 well-known methods (CART, CN2, C4.5, SMART, ... ) on 12 real word sized problems. Our purpose is somewhat different. Most of the methods we present are original, or very recent. Therefore, we decided in favour of a precise, explanatory description of these methods, rather than an extensive experimental comparison which could be seen as untimely. To illustrate the differences among the methods presented, we have evaluated them according to a classical problem of supervised classification, that of "Waveform Recognition"4 which is known to be difficult for rule-based approaches. Our objective was to show experimentally that our original hybrid algorithms have better performances (on this difficult problem) than classical symbolic methods such as, for example, CART, and that they are not very far from well established numerical methods such as, for example, Fischer's linear discriminant function.

519

This paper is organized as follows. First, we shall define more formally the subject of supervised classification and introduce the notation (Sec. 1.2). A brief history will allow the methods to be contextualized (Sec. 1.3). Then, we shall outline the main points of the hybrid approaches (Sec. 1.4). The waveform recognition problem is presented in Sec. 1.5. A comparison of methods is not that easy to accomplish, even on a particular application. Thus, a certain number of criteria have been retained which are presented in Sec. 1. 6. Tihe remainder of the article is devoted to a description of the methods them selves . In order to provide a sufficiently large scope of supervised classification, we first describe several classical methods: Sec. 2 addresses the main statistical ap proaches with particular emphasis on four classical methods; Sec. 3 describes Neu ral Networks, and. more especially the Multi-Layer Perceptron; Sec. 4 presents the CART Classification Tree approach of Breiman et al. [START_REF] Breiman | Classification and Regres sion Trees[END_REF] Remaining parts are devoted to original contributions. Section 5 proposes the combination of Classification Trees and Fuzzy Sets. Sections 6-8 present methods based on the use of Decision Rules, similar to the rules of an expert system: the first adopts a combinatorial approach; the second describes "Decision Committees" which are a simple and comprehensible way of combining rules; the third relies on the use of a Genetic Algorithm. The two following parts look at methods derived from the Version Space approach43: Sec. 9 proposes the combination of this approach and of a Hierarchical Clustering based pre-processing; Sec. 10 is also related to the Star Algorithm4 1 and is based on the use of "constraints". The fina] sections (11 and 12) provide a general discussion of our results and observations, and conclude the paper.

Supervised Classification

Let us assume that we have a set of examples E, called the learning set, of cardinal n. As a general rule, this set constitutes only a small part of the entire range of possible examples which is often infinite. Each example, which we shall denote (x, c) represents a pair (description, class). The description x belongs to the description space X. In the case where the description is of the value-attribute type, the description space is a product space X = X1 x X 2 x • • • x Xp, in which each Xj is the set of values possible for the jth attribute. The value of this attribute for a given description x is denoted as Xj. The class c of an example is an element of the classes {Ci, C2, ... , C9}. The set Ei s thus partitioned into g subsets E1, E2, . .. , E9, of cardinal ni, n2, .. . , n9, respectively. In the special case where there are only two classes, these are denoted C+ and C_. In this case, one frequently refers to the learning of a concept, the positive examples being those of E+ and the negative examples or counter examples are those of E_. Note that each example is assigned to a single class. However, the same description may correspond to several examples belonging to different classes. Therefore, the link between the description and the class is not necessarily functional, or deterministic. In practice, this is almost never the case as the description is generally incomplete and partially erroneous. Our goal is to build a classification function from these learning examples, thus allowing a class to be attributed to a new example whose class is unknown. The general principle consists in constructing a function which will enable a good reclas sification of the learning examples. However this principle does not suffice, since the goal is to achieve, above all, good performance on the new examples. In order to estimate it, a test set is used which is independent of the learning set. In practice, we have a finite set of examples that we divide into one (or several) learning sets and one (or several) test sets. Due to the nondeterministic nature of the problems processed, and because the learning set generally constitutes only a small subset of the possible examples, it must be admitted that the classification function cho sen does not provide a perfect reclassification of the learning examples. Excellent results on the .learning set do not necessarily yield excellent test results, therefore a compromise between learning performance and test performance must be found.

Moreover, one often wishes the learning procedure to provide a classification func tion containing explanations on the class partition observed on the data.

A Brief History

Supervised classification has quite a long history; our purpose here therefore will be to provide a limited scope of the subject. We shall concentrate on a broad outline highlighting the specificity of the hybrid approaches.

The discriminant function of Fisher1 7 was one of the first methods to appear. In this method, examples are represented by points of RP, and classes are separated by linear or quadratic surfaces which are optimal when the classes are Gaussian (cf. Sec. 2). The Rosenblatt Perceptron56 also uses a representation in RP with linear decision surfaces while enabling an adaptive, or incremental, learning, which means that it iis capable of taking examples into account consecutively as each one "arrives". Current Neural Network models, in quite a number of cases, are direct descendants of the Perceptron (cf. Sec. 3).

The 1960's saw the development of several studies in pattern recognition, notably statistical pattern recognition. Duda and Hart15 and Fukanaga21 provide a general presentation of that period. Among these studies, Sonquist and Morgan64 produced the first works to appear on Classification Trees whose methods are still considered today as the pivots of the hybrid approach. Tree-based approaches are interesting from two points of view. On the one hand, they naturally integrate qualitative or symbolic representations; on the other hand, they contain a very high explanation power (cf. Secs. 4 and 5). They also constitute a nonparametric method class in that they do not presuppose a data. model. Other nonparametric approaches were also developed; notably Parzen's Kernel method49 and the k-Nearest-Neighbor technique.11 These approaches are not only simple to implement, they also contain remarkable asymptotic properties (cf. Sec. 2). Concerning binary data processing (represented in {O, 1 }P), it is worth mentioning the works of Bongard3 and those of Quinqueton and Sallantin,52 who present an alternative to Classification Trees and who are primarily responsible for some of the methods which will be presented below (cf. Secs. 6 and 7).

In the field of Artificial Intelligence, the development of supervised classification methods dates essentially from the beginning of the 1970's, with the famous "Arch Concept Learning" problem as devised by Winston.75 These methods contributed to the capacity to learn from structural example descriptions, thus abandoning the value-attribute model used in all of the above-mentioned approaches. Several repres•entation modes were envisaged, notably those based on semantic networks75 and on predicate logic. 70 Mitchell43 showed that in the AI methods, a more or less explicit solution, or version, space exists, partially ordered by a generalization relation. Moreover, Mitchell proposed an algorithm to search this space (cf. Secs. 9 and 10). Other methods were proposed, notably the Star algorithm,41 (cf. Secs. 8 and 10) while the notion of generalization was also explored, 1 4 particularly within the scope of Inductive Logic Programming. [START_REF] Muggleton | Inductive Learning Programming[END_REF] Neural networks have come to the forefront due to the work of Hopfield33 on associative memory models, inspired by statistical physics. In the field of supervised classification, a decisive step was reached with the development of the Multi-Layer Perceptron. [START_REF] Rumelhart | Learning internal representations by error propagation[END_REF] The MLP associates the notion of hidden cells40 with a learning al gorithm of the stochastic gradient type, such as the backpropagation of the error gradient, thus enabling a break-away from the linear framework. Large scale appli cations have been. handled successfully, notably in the domain of speech processing60 and character recognition. 1 2

Hybrid Approaches

Hybrid approaches comprise both neural network methods and other more typical AI methods as mentioned above. Neural networks are close to numerical methods, and the symbolic aspect appears mainly in the network architecture which is sym bolic by nature, and which expresses a priori knowledge on the problem processed. This symbolic aspect appears also in recent studies which aim at giving explanatory virtues to the networks, especially by implementing rule extraction mechanisms.62 Concerning AI methods, although originally symbolic, it was soon obvious that an overly logical approach,4 1 aiming to construct perfect classification functions on the learning set, was not the best solution. Thus the idea emerged of construct ing classification functions with "good" learning performance, this being quantified by statistical numerical criteria. 9•22 More generally, the proximity of the problem lends itself to a more natural cooperation between the statistical approach, the neu ral network approach or that used in Al For example, validation methods, of the cross-validation or bootstrap type, 2 8• 6 5 naturally apply to "nonstatistical" meth ods. This is also the case for certain fundamental results produced by Vapnik and Chervonenkis,68 which can prove the asymptotic consistency of numerous meth ods, notably neural24 and those based on classification trees.4 Finally, numerous statistical algorithms may be used, for example, to conduct data pre-processing47 (Sec. 9).

The hybrid approaches thus constitute a research domain, rather than a set of well defined methods. They take advantage of the tools and results from various fields -statistics, pattern recognition, neural networks and artificial intelligence. Among the main objectives pursued, the following may be mentioned: performance, whether in terms of calculation time or classification error rate; the explanatory nature of the learned classification function; the capacity to handle complex data, represented for example in predicate logic, which cannot be handled by conventional numerical methods.

The Waveform Recognition Problem

Waveform recognition is an artificial problem which was introduced by Breiman et al. 4 in the study of classification trees. In their book, these authors used two illustrative applications: the digit recognition problem, and the waveform problem. With the former, their classification tree program, CART, achieves excellent results, in terms of both classification accuracy and tree size. And they chose the waveform problem precisely because it is difficult for classification trees, thus providing a better illustration of program behavior. Moreover, the first rule-based programs issued from machine learning do not solve the problem better. For example, CN29 obtains results which are not as good as those of CART, while the SDL5 which relies on a heavy, simulated annealing algorithm, only slightly improves the CART performance. Therefore, we chose this problem for the same reasons as Breiman et al., and because it appeared challenging for our approaches.

The problem is to discriminate between three classes of waveforms. Each wave form simulates a quantitative chronological phenomenon observed in 21 regularly spaced instants. It is an object characterized by a point of R 2 1.

Analytical class definition

The three classes are obtained by combining three basic waves two by two. The latter, which we shall denote hi, h2, and h 3 are represented in Fig. 1. They are unimodal and dephased. They are associated by a random convex combination before being perturbed by a random Gaussian noise. Thus, considered analytically, class C1, C2 and C 3 elements are respectively conceived through the expressions:

x = uh1 + (1 -u)h2 + e, x = uh1 + (1 -u)h3 + e, x = uh2 + (1 -u)h 3 + e,
where u is a random variable of uniform density on the [O, 1] interval, and where c is a random Gaussian centred vector, with a variance-covariance matrix unity. We also consider the classes to be equiprobable. It may be noted that in the absence of the e Gaussian noise, the three classes would be represented in R 21 by the three sides of the hi, hz and h3 summit triangle, as shown in Fig. 2. In this case, the problem would be deterministic. A perfect assignment function (without classifi cation error) should consist in assigning each description x to the corresponding class on the side to which x belongs. The random Gaussian noise will perturb these considerations. The effect produced is that each point of R 2 1 is an acceptable description in terms of the three classes, and the problem is no longer deterministic. Given that the classes are equiprobable, we can demonstrate that the minimal error assignment rule, or Bayes rule (cf. Sec. 2.1), consists in assigning a description x to the class whose conditional probability density is maximum. The assignment areas are now not so easy to defi ne. Nevertheless, we can predict that the bound aries, points of equilibrium between the conditional densities, trace "quasilinear" surfaces. In fact, we know that for symmetrical reasons, at least one of these bound aries is perfectly linear. This boundary corresponds to the vertical axis passing by h3 in Fig. 2. The other boundaries, represented in the fi gure by a dotted line, are not necessarily linear, however they are most likely to be quite regular. More over, in the regions which are near the summit h 1 and h2 of the triangle, regions of high uncertainty and high density, these boundaries must be well approximated by hyperplanes passing by (or close to) hi, respectively h 2 . The quasi linearity of the optimal boundaries explains, to an extent, the success of certain methods such 524 0. GASCUEL ET AL.

•--•�---•• •-•---� .
-----

• -----..

Attribute discretization

The attributes presented above are all continuous. We transformed the eleven learning sets and the test sample, in order to evaluate the performance of the methods on discrete data which are nearer to symbolic. The initial quantitative attributes were split into 21 binary descriptors and 21 ternary descriptors. As a result, each of the files initially drawn for the quantitative attributes produced two discretized files. Boundary identification, essential in coding the quantitative attributes, was achieved through maximization of the link between the partition into classes and that obtained by discretization in intervals of the variable to be coded.

This link was measured using the x2 criterion. The algorithm we used specifically. This coding was then applied to each of the files.

Evaluation Criteria

We selected a certain number of criteria to evaluate the methods, which are shown in Table 1. The first column describes the type of data processed: binary, ternary or continuous. The following columns give the average results obtained on the 11 learning files. Each criterion shall now be examined in greater detail. The classification error rate is the proportion of cases where the example class is not identified by the learned classification function. This proportion is estimated by using the test sample described above. The Test column gives the average result obtained on the 11 learning files, as well as the standard deviation (number in brackets). A high standard deviation indicates that the method is unstable, and can sometimes yield bad results. The 3 Test(i) columns give the results obtained for the three subsets of the test set, corresponding to each of the 3 classes. When the results in the columns are unbalanced, this means that there is a "weakness" in the method. For example, in Table 1, it may be noticed that the method classes the examples of the first class poorly. The Train column gives the average results, and the standard deviation obtained on the learning sets. A low score in this column does not necessarily indicate that the method is good. What is important is that the difference between learning and test is not too high. If this is the case, the method has a tendency towards rote learning. Most likely, it has too high a degree of freedom.

Computing time

It is possible to distinguish between two calculation times, the required learning time: CPUtrain, and the required time to decide on a new example class: CPUtest, which is the time required to classify the 5000 examples of the test set. Depending on the application in question, the relative importance of learning and test time will vary. If, for example, the data being processed is scientific data with a very long acquisition time, a learning time of several days is not always a drawback. However, if an exploratory procedure is adopted to try to "understand" the data, by varying the method parameters as well as the description mode, then the learning must be quick. The same applies to the decision: the waiting time for a medical diagnosis may be a few seconds; the decision must be "real-time" in the case of phoneme recognition for continuous speech processing.

Explanation size and power

The Size column shows the complexity of the learned classifi cation function. Of course there is no unique measurement. In the case of numerical methods, we count the number of parameters. In the case of more symbolic (or logical) methods, it is possible to count for example, the number of literals used. Size is directly 526 linked to the explanation power of the method. The greater the size, the lower the explanation power of the classification function. Moreover, for equal sizes, it is usuall y easier to interpret a logical formula than a mathematical formula based on real parameters. Again, the results should be modulated in function of the application : a good explanation power is of little use for phoneme recognition, but is indispensable in the medical field. Finally: it is worth pointing out that size and decision time are mandatorily correlated.

1.6.4. Finding a compromise Generally speaking, a compromi se must be found between the qualities mentioned above. For example, a low size associated with a high explanation power is usually obtained at the expense of a high error r;ate. Neverthele ss, we are also aware of the fact that too high a size often corresponds to rote learning, and to an equally high error rate. From another point of view, it is often more difficult to optimize in the discrete space, and thus obtain logic:a.l formulae containing explanation, than to optimize in the continuous space, which yields numerical functions and few ex planations. Also, certain methods such as the k-Nearest-Neighbor, do not proceed to any learning. However, this is balanced by a high decision time. It is an empty quest to hope for a perfect method , and depending on the application one quality will be given preference over another.

STATISTICAL METHODS

We consider here two approaches which are very classical in statistical pattern recognitio n: the pammetric approach, which we expound in the Gaussian frame work , and the nonparametric one. These two approaches are opposed in principle, and reveal two distinct ways of treating the subject. However, first, we shall intro duce the Bayes Minimal Error Decision Rule w hich plays a central role in statistical discrimination.

Bayes Minimal Error Decision Rule

As we have seen in Sec. 1.2, the problems treated are rarely deterministic, and ob jects from two different classes often adhere to the same description. Thus, Classifi cation which proceeds from example description is automatically subject to a degree of incertainty. Bayes Decision Rule cons ists in assigning the object described by x to the class Ci such that Pr(Ci/x) is maximum. It is easy to demonstrate that this rule is optimal, in the sense that it minimizes tbe misclassification probab ility. In reaJiity, however, it is very rare to know the class probabilities given the description. On the contrary, it is much easier to find out, or to estimate, class probabilities and the description distribution given the class. Using the Bayes theorem, an operational expression may then be found:

P (c•/ ) = Pr(Ci)f(x/Ci) r , x f ( x ) ,
where f(x) and f(x/Ci) represent, respectively the density and conditional density of x. The denominator of this expression being independent of Ci, the Bayes Deci sion Rule consists in assigning x to the class which maximizes Pr(Ci)f(x/Ci). Let us now consider the case where the c;lassification is binary (g = 2). By putting (f(x/C+))

(Pr(C+))

>.(x ) = ln f(x/C_) . + ln Pr(C_) ' (1)
we find that the Bayes Decision Rule is expressed as

Vx, If A(x) � 0 Then C+, Else C_.
From this expression, it results that the surface defined by the equation >.(x) = 0 is the boundary separating the two areas assigned to C+ and C_ in X.

It should be noted that precise knowledge of the probability laws ruling the descriptions of the objects to be classified is essential when implementing the Bayes Decision Rule. However, in most cases these laws are unknown. But they can be estimat�d by diverse methods, the most classical of which we are going to examine below.

Parametric Methods; the Gaussian Case

We shall assume in this section that the conditional probability laws of descriptions are elements of a known family defined by a vector (). More precisely, the generic an alytical expression f(x/8) is known, however, the ()i parameters, which characterize the distribution of each class Ci remain unknown. The parametric approach uses the Bayes Decision Rule after having estimated these unknown parameters from the learning examples. In the most general case, this estimation is often carried out through the maximum likelihood method. However, here we shall only discuss the Gaussian case, which is easier to process.

Let us assume that the description x of an object to be classified consists of p continuous attributes (x E RP), and that the set of descriptions of each class Ci is randomly dispersed in RP according to a Gaussian distribution with mean vector µi and variance-covariance matrix Ei.

In this case, the conditional density of x is expressed as The Bayes Decision Rule now consists in minimizing the expression [START_REF] Battiti | First and second order methods for learning: between steepest descent and Newton's method[END_REF] where �l (x, µi) is the Mahalanobis distance between x and the mean description of the class Ci: D.�1 (x , µi) = (x -µi ) t E i1 (x -µi).

If we admit that a priori probabilities of classes are identical and that the variance covariance matrixes are equal (Vi, Ei = E), it derives from (2) that the Bayes -•----Decision Rule consists in minimizing �E(x, µi)-In this particular case, we then assign an object described by x, to class Ci whose mean description µi is the nearest to x. In a more general manner, we show that the equality of the variance-covariance matrices induces a linear discrimination. This is illustrated simply by examining the binary case (g = 2). By developing Eq. ( 1), one finds the linear expression t -1

)

( P r(C+) )
-X(x) = (x -µ)I: (µ+ -µ_ + ln P r(C_) , whereµ = 4(µ+ + µ_). The optimal separation surface between C+ and c_ is a hyperplane of RP, of equation ..X(x) = 0, defi ned by p + 1 parameters.

In the general case, by developing expression (2), one easily fi nds that the bound ary is a surface of the second degree in x (Ref. 15, p. 30) and that it is defined by 1 + p ( p + 1) /2 parameters. Hence, the discrimination is said to be quadratic. The Gaussian model, like all parametric models, requires an initial phase of parameter estimation (or learning). This consists in simply estimating the coordinates of the mean vectors /.ti and the matrix elements �i on the examples of the learning set.

We applied the method described above to wavefo rm data, by assuming, on one hand, the equality of the variance-covariance matrices (linear discrimination) and, on the other hand, the inequality of these matrices (quadratic discrimination) . The three types of data were processed using the DISRIM procedure of the SAS so�ware, running on a Spare 2. Results are given in Tables 2.1 and 2.2. What is noticeable is the robustness of the Gaussian approach. In fact, performance undergoes little degradation when we drop the Gaussian hypothesis by binarization or ternarization of the continuous descriptors. Moreover, this hypothesis appears to be extremely interesting on the level of •Calculation time, due to the existence of an analytical solution [START_REF] Battiti | First and second order methods for learning: between steepest descent and Newton's method[END_REF]. The learning time is the shortest among all the methods, if the pro cedures without learning are excluded (Sec. 2.3). We would also like to highlight the fa�t that the quadratic discrimination results are not as good as those for linear discrimination.. In fact, the overparameterization of the quadratic discrimination is not worthwhile in this case. It serves only to improve the discrimination of the ele ments of the learning set and not those of the test sample. This phenomenon occurs frequently, and is revelatory of the equilibrium to be found between the precision of the learning and the real test performance.

Nonparametric Methods

In statistical supervised classification, the nonparametric approaches are charac terized by the absence of an a priori hypothesis on the conditional distribution of the examples in the description space. As above, we use the Bayes Decision

Rule by trying to identify the class Ci which maximizes the a posteriori proba bility Pr(Ci/x). In order to achieve this, and assuming the class probabilities as a priori knowledge, we need to estimate the conditional densities f(x/Ci) of the descriptions. Statistical nonparametric methods proceed through local estimation of these densities, the two most outstanding approaches being that of Parzen's Kernel49 and k-Nearest-Neighbor.11

Parzen's Kernel method

Let x be the description in RP to be classed. We denote then as Wh(x) the hyper cube (or window) centred on x of side h. For Ci fixed, let ki ( x) be the number of examples of Ei included in Wn(x). We can easily demonstrate that where lwh (x) is the indicator function associated to the hypercube Wh(x) and where

Xe is the description of the example e. It seems only natural to take ki(x)/ni as the estimation of the conditional probability of membership to the window W h ( x).

By dividing this probability by the volume vh = hP of the window, we obtain the estimation of the conditional density

!� ( /C • ) = k i (x)/ni = ]_ " 2._ 1 (x -Xe ) X i ,,. L...J u W1(0) h • Vh n i eEEi Vh ( 3)
Moreover, Hand27 has shown that this estimation converges towards the density f (x/Ci), if the dimension h of the window diminishes according to a law in 0(1/ foi), when ni increases. Equation (3) defines f (x/Ci) as the sum of Boolean contributions of each learn ing example of class Ci, and the h parameter determines the "scope of action" of these examples. The result is that f(x/Ci) is, by construction, a discontinuous function even though f(x/C;,) usually is a continuous function. This is not very satisfactory even when we know that the discontinuity tends to disappear as ni increases. In order to smooth f(x/Ci), we define a less contrasted contribution of examples by using a continuous function for characterizing the scope and intensity of the example infl uence. Expression (3) may then be generalized by where K is a positive function, called kernel, such as

J J 1 (X-Xe) K(u)du = Vii K h dx = 1. ( 4
)
This latter expression, associated with (4), makes f(x/Ci)'s integrate equal to one, and thus estimation ( 4) may be assimilated to a probability density. The term h is called the smoothing factor. This parameter plays a determining role by defining both the amplitude and the scope of the influence of the learning examples.

If too high, we would tend to level off the variations of f(x/Ci)• However, if too low the estimation of f (x/Ci) will become a "comb'' with multiple peaks localized at the points of the learning sample. For waveform data, we have chosen a Gaussian kernel, as is usually the case It has the advantage of defining a symmetric influence around examples as well as a progressive extinction of the contribution of these examples as one departs from the description to be classed. We tested the method for different values of h (0.5, 1 and 2), using the Euclidean distance. The results are very stable. In Table 2.3, we provide only the statistics obtained for the case where h = 1. The CPU times are those provided by the SAS software running on a Spare 2. The size is that of the data, since there is no prior learning phase, i.e. 300 (examples) x 21 (descriptors).

k-nearest-neighbor method

Let us reconsider the first part of Eq. ( 3)

f (x/ C i) = ki(x)/ni . v h
This relation encompasses two nondetermined terms, with a common structural link: ki(x) and Vh (the term ni is known from the learning set). Two attitudes may be adopted for the calculation of f(x/Ci): either we fix the volume Vh and we count the number ki(x) of examples belonging to this volume, or we fix the value and then adapt the volume Vh so that it contains exactly ki(x) examples. The first approach is that adopted above, the second is the base of the k-Nearest-Neighbor technique, or k-NN. This method implements an intuitive idea, which consists in assigning to x the most represented class among the k nearest neighbors of x. As h above., the k parameter plays a very delicate role. Too weak a value for k induces a classification function which is too specific of the learning sample. Too high a value of k will tend to make the classifi cation function uniform; this function will then retain the most frequent class. It should be pointed out that when the size of the learning sample increases indefinitely, and if we take a value of k in 0(1/ Jn), the k-NN assignment rule converges towards the Bayes Decision Rule.

In waveform processing, we applied the k-NN method for several values of k (1, 30, 75 and 100), using the Euclidean distance. Best results were obtained when k is around 30, the value retained in Table 2.4. The CPU time is that of the SAS software on Spare 2. As in the previous case, the size is that of the data.

Discussion

The error rates of both nonparametric methods used are fairly close, and roughly equivalent to that of linear discrimination (Table 2.1). This may be explained by the characteristics of the problem in which the decision surfaces are quasilinear (Sec. 1.5), so that the Gaussian assumption does not appear as a handicap. Dif ferent results could be obtained with another problem. It has to be underlined that both nonparametric methods obtained unbalanced error rates among the three classes. Examples from the fi rst class are often poorly predicted. In real-world

532 -----
applications, such a characteristic would usually be considered a heavy flaw. More over, from a practical point of view, one important element of these methods is that they do not conduct a priori learning phase. Therefore, their learning time and explanation power are null, yet the decision time is relatively long. Neverthe less, various pre-processing techniques can be performed to reduce the complexity of nearest neighbors based recognition. 1 3 In this case, the learning time is not null and the recognition time is cut down. The fi rst solution consists in reducing the sample size while extracting prototype examples. 7 • 29 In this case, we speak of the "condensed" nearest neighbor rule. We performed experiments using the edition method 74 which consists in removing from the learning sample the examples which are poorly classifi ed during a first application of the standard k-NN method. Our results with binary data show that the performance is slightly improved (23.0%) while the number of retained, prototype examples is greatly reduced (56 in aver age, instead of 300) as is the decision time. Other methods structure the learning sample and organize the search. Several solutions exist, which are usually based on trees 20 and which make it possible, in some cases, to find nearest neighbors in approximately constant average time. 7 1 However, the performance of these latter methods degrades rapidly with the dimension of the representation space. They could hardly be used to deal with the waveform problem, unless preprocessing the data by reducing the representation space dimensionality (Ref. 15, pp. 246-248) .

NEURAL NETWORKS

1. The Multi-Layer Perceptron Model

Neural Networks include a wide range of models which differ in functional fo rm, the classes of functions approximated , the criteria optimized and the learning algo rithms. Generally, learning consists in estimating the value of numerical quantities, the weights, characterizing the model, from a learning set of patterns. Supervised classification is one of the favourite applications of many of those models. We refer to Hertz et al. 3 1 for a more detailed presentation of Neural Networks. We used the Multi-Layer Perceptron (MLP) model 57 for our tests. It is one of the most common and simplest nonlinear network models. MLP's are nonparametric systems as defined in Sec. 2. Like all networks, an MLP is a combination of basic elements called cells. These are computational units which receive input data from RP, and produce a real output in R. The transfer fu nction characterizing such a unit has the following form:

The parameters w = (w1 , . . . , wp ) are the weights of the cell, w 0 is the bias, x = ( X 1 , ... , Xp) is the input to the cell and y its computed output. In the basic MLP model, the activation function f is usually defi ned as follows:

e Ku _ e -Ku f( u ) = e Ku + e -Ku . In a basic MLP, the units are arranged in successive layers with connections between layers. Data is sent to the input layer for a copy and is afterwards processed sequentially by the successive hidden layers. Cells belonging to the same layer compute in parallel, the outputs of the cells of layer m being the input to layer m + 1. The last layer provides the answer of the system and is called the output layer. We only consider systems with a single hidden layer. Figure 3 depicts a three layers MLP. A bias cell (index 0) enables the bias terms Wio to be introduced. It is permanently set to 1 and is connected to all cells in the subsequent layers. The composition of elementary transfer functions of the different cells is called the global transition function of the network. This function, </>, is defined from RP to Rq and can be written for the ith output by combining the local activation functions of the different units:

Yi = </>i(x) = f ( ww + � Wij f(wjo + r;kWjkXk)) , J
where j indexes the hidden units and k the input units. </> being a combination of elementary nonlinear functions, its complexity may be adjusted by varying the number of hidden cells.

The Learning Algorithm

Let us consider a network with a fixed architecture. Its transition function is then defined by the value of the connection weights. The difference between the desired outputs and the outputs computed by this model, or the matching of the model to the data, is characterized by a cost function Q. Learning consists in minimizing this function by adjusting parameters of the model. One of the most common cost functions is the quadratic error, i.e. the square of the Euclidean distance between desired and computed outputs . This is the function we have used here. Usually, the desired outputs for a classification task are indicators of classes (i.e. if x E Ci, all components of y are equal to 0 except the ith which is equal to 1).

Classic algorithms for MLP are based on gradient techniques. The basic version described below is known as the steepest descent method. Let us consider a given network. Starting from an initial confi g uration, a gradient algorithm will modify the values of the parameters by successive adjustments which aim at minimizing the error criterion Q according to the rule:

W = W -E8Q/8w ,
where c is the learning rate. It monitors the amplitude of the modifications and can be fi xed or variable during the algorithm. It is set to 0.01 in the experi ments described below. The classical learning algorithm for MLP i s called back propagation. 57 It constitutes an implementation of an adaptive gradient algorithm on a MLP. 73 Other, more sophisticated learning algorithms were proposed67 which are mainly based on secon d order minimization techniques, 2 or on the conjugate gra dient principle.44 These algorithms tend to converge faster than the back propagation, and usually find apparently better parameter values, according to the cost function Q measured on the learning set. Impressive differences between the back-propagation and a quasi-Newton approach have been reported by Chung and Setiono8 using artificial data. However, this type of result is generally not observed with real world problems, and the improvement obtained on the learning set is rarely confirmed on the test set. Mo reover, the convergence speed of these algorithms often makes it difficult to use early-stopping which consists in stopping the algorithm before convergence, and which is one of the most efficient procedures to avoid overfitting with neural methods. For example, with waveforms, we have tested the conjugate gradient procedure44; the computation time was divided by between 2 and 5 depending on the number of iterations, but we were unable to reach the same level of classification accuracy.

The Classification Rule

The Classification Rule used for MLP consi sts in assigning a description to the class identified by the maximal computed output. The ith output of the MLP is, in some respects, an estimate of Pr(C i /x). This quantity is thus directly estimated here, unlike the statistical methods introduced in Sec. 2 which estimate the conditional densities of the data.

Results

Data were normalized per component for each training and test set. Two series of experiments were run, the first on a network without hidden layer, the second on a network having an hidden layer of fi ve units. Invariably, the output cells are sigmoi' d transfer functions. The Bayes Decision Rule being quasi-linear (refer to Sec. 1.5), we did not test more complex networks. Moreover, we tested two algorithms, the

----•-��-•----• ••- --•----
standard backpropagation and Moller's 44 conjugate gradient. The results obtained with backpropagation for both networks are given in Tables 3.1 and 3.2. In the size column, we indicate the number of weights of the corresponding network. The CPU time is approximate and was measured on a Spare 10. The performance obtained for continuous data is almost optimal (i.e. close to 14%). The results obtained for ternary data are also similar. Note that whatever the data set, both systems give equivalent performances, despite a slight overparameterization of the second. When using the conjugate gradient algorithm with five hidden units, the performance is a little wor�e (18.23 with continuous data) which indica,tes a slight overfitting, but the running time is about 6 times faster. Besides, early stopping appears necessary with this learning algorithm, but it necessitates a fi ne tuning which is not that easy to achieve when disposing of only 300 learning examples. Network performance is among the best we obtained in this study. This might be a little surprising, since these methods have not used their nonlinear potential here. The comparison with statistical methods is particularly interesting (refer to Sec. 2). Although the optimal surfaces are quasi-linear, linear discriminant analysis leads to poorer results. The explanation might lie in the fact that data significantly deviate from the Gaussian model, and the quasi-linear optimal surfaces are only imperfectly approximated by the analytical solution (2) derived from the Gaussian hypothesis. Moreover, the sigmoid shape of the transfer function used on the output

----------• . �---- ----
units enables us to concentrate on the descriptions located near the boundaries, thus allowing more precise learning of the latter. Classification trees are usually binary, and can be represented as shown in Fig. 4. The circular nodes are decision nodes and the square nodes are terminal nodes. Each decision node has a binary question associated with it, and each terminal node has a class Ci associated with it. In our example of Fig. 4, there are two classes which are respectively Ill and Well, while the binary questions are based on the attributes Te mperature which is continuous, Throat-irritation which is binary and Cough ( E {none, dry, loose}) which is qualitative. The tree classifies a description x through a chain of binary decisions. Starting at the root node and proceeding down the tree, tests are conducted using questions to determine whether the description goes to the left or right descend.ant. The description is then assigned to the class of the terminal node in which it lands. A tree path from root to leaf constitutes a production (or decision) rule similar to those of expert-systems of the MYCIN type.63 For instance, the following rule may be extracted from the tree of Fig. 4 [Temperature < 38] and [Throat-irritation = Ye s] -t fll. This demonstrates the explanation power of the approach, thus the reasons for its success in Artificial Intelligence. The rules conceived are easy to interpret as they are written using description language that the user has defined to describe data.

TREE-BASED CLASSIFICATION, THE CART METHOD

Given a learning set, most approaches to classification tree design determine the binary questions in a stepwise top-down fashion: the training set E is associated to the root of the tree; a binary question is chosen which splits E into two subsets; this splitting process is repeated for both subsets, for their descendants and so on. Now, there are three basic issues in classification tree design:

(1) selecting an appropriate binary question for each decision node;

(2) determining an appropriate set of terminal node; and

(3) selecting an appropriate class for each terminal node.

For each decision node, the binary question is usually selected by optimizing a splitting criterion among a set of possible questions. Frequently, these questions are based on the use of a single description attribute, as in Fig. 4, but they may also be based on linear 4 or neural net 26 combinations of these attributes. The terminal node set is usually determined by halting the splitting by subject to some stopping criterion, or by continuing the splitting until all terminal nodes have pure class membership and then pruning back. Pruning is the more recent approach and has better properties. Finally, the class for the terminal nodes is obtained using the majority rule, or a weighted majority rule in the case of nonuniform misclassification cost. In the following, we shall briefly describe the popular CART method which was the first to propose the pruning approach. More details are given in the book of Breiman et al. 4

The CART Method

The set of possible binary questions

In the standard use of CART, each question i s based on a single attribute, and not on some (e.g. linear) combination of the initial attributes. The form of these binary questions depends on the type of associated attributes. A binary attribute obviously generates a single binary question. A qualitative attribute taking m values generates 2m-l -1 binary questions which correspond to the nonempty bipartitions of its values, e.g. the attribute Cough defined above generates the questio_ ns: "Cough := None", "Gough = Dry?" and "Cough = Loose" which correspond to the bipartitions: {None} I {Dry, Loose}, {Dry} I {None, Loose} and {Loose}l{None, Dry}. A continuous attribute Xj generates questions having the shape " xJ < v?". There is a priori an infinite number of possible values for v, and CART only considers those defined by the equation v = (v1 +vi+1)/2, where the ViS are the consecutive values taken by the attribute on the examples attached to the node to be split. Thus, if this node contains m examples, ( m -1) binary questions are envisaged for each continuous attribute. Finally, ordered attributes, such as size E {small, medium, big}, are dealt with in the same way as continuous ones.

Tree growing and splitting criterion

In the tree growing phase, a large tree, T, i s grown by recursively finding binary questions until all terminal nodes have a pure or nearly pure class membership or cannot be split fu rther. Questions are chosen among the set of possible questions by optimizing a splitting criterion. The criterion retained by CART i s based on the Gini index. Let t be the node to be split, E be the set of training examples attached to t, and Pr( Ci/ E) be the proportion of examples from E which belong to class Ci . The Gini index defi nes the impurity of E as i(E) = L: Pr(Ci/E)Pr(Ci/E) .

i =f:j

This impurity is maximum when for every index i we have Pr(Ci/E) = 1/g (g is the number of classes), and is minimum (= 0) when all examples from E are in the same class. The aim is to fi nd the binary question which most reduces the impurity of E. Let us consider a given binary question B, Ef the subset of E corresponding to the answer Yes to B, and E� the subset corresponding to No ( L stands for left and R for right). The reduction of impurity brought by Bi s defined by

f}.(E, B) = i(E) -Pr(Ef / E)i(Ef) -Pr( EN/ E)i(EN) ,
where Pr(Ef / E) and Pr(E�/ E) are the proportions of examples from E which are respectively in Ef, and in EN_. Finally, the binary question chosen for splitting t is the one which maximizes this criterion.

Tree pruning

In the tree pruning phase the large tree, T, is pruned back to avoid overfitting the training data. This process consi sts in removing some branches of T which do not significantly improve the error rate, but which make its size (or complexity) high. A pruned subtree is selected by minimizing an error rate estimate over a parametric family of pruned subtrees. This family is generated as follows. Suppose each node in T is assigned a class Ci based on majority vote. Then we may compute the error rate on the training sample of any pruned subtree S of T. Let R(S) be this resubstitution error estimate. Now define the error-complexity of a pruned subtree S(c T) by

Ra(S) = R(S) + alSI ,
where a � 0 and ISi is the number of terminal nodes in S. The desired family of pruned subtrees T0 (a � 0) is obtained by minimizing the error-complexity crite rion for each fixed value of a: R0(Ta) = min scT Ra(S). Note that To = T and Ta = root(T) when a is large enough. From a computational stand point, it is not easy to obtain Ta for any given value of a, so that CART uses an algorithm which starts from To (= T) and, by iterative pruning of "weak" branches, produces a se quence of smaller and smaller subtrees until root(T) is reached. Moreover, it may be shown that this sequence, (Ta.), is a subset of the family (T0). From this sequence, -•• ---------------a pruned subtree, Ta •, is then selected by minimizing and "honest" estimate, R, of the probability of error CART can use several methods to obtain honest estimates of the error probability. The simplest approach is to use an independent test sample. But this approach does not allow all of the training data to be used for both growing and pruning the tree, so that it is precluded when the number of training examples is low. In this case, the usual approach employed in this study is based on a cross-validation estimate of the error probability.

Results

Results obtained by CART 1.1 using the default options are displayed in Table 4. The (average) tree size is measured by the number of edges, and the CPU time is obtained on a Spare 2. Among the methods experimented in this study, classifica tion trees have one of the best explanation powers. These classification functions , however, are also endowed with one of the poorest discrimination powers, which illustrates the dilemma explanation/discrimination power. It is a recognized fact that the waveform problem is difficult for classification trees. The use of a more appropriate coding such as that used in (Sec. 9), enables tree results to come very close to those obtained by other methods. Moreover, analogous results may be obtained by using linear combination of attributes in the decision nodes, instead of single attributes (for more details see Ref. [START_REF] Breiman | Classification and Regres sion Trees[END_REF]). The results obtained here do not therefore prejudice classification tree results on other applications. number of subsets of their domain. Most of the known methods to discretiz-e con tinuous attributes are used prior to the construction of the tree. [START_REF] Catlett | On changing continous attributes into ordered discrete attributes[END_REF]

J(j) = L Pr( Et/ E)e(Ei) . i 541 •----
A fuzzy measure of information , the entropy-star measure, can also be defined in the same way. If F1 , F2 , ... , Fk are fuzzy sets of E, we now have k !* (Fi , F2 , ... , Fk) = l: P r *(F1)e*{F1) .

l=l

When splitting E by means of the attribute j, the information gain represents the decrease of uncertainty on the classes Ci entailed by the use of j .6.(j) = e(E) -J(j)

or, with the fuzzy quantities � *(j) = e*(E) -J*(j) .

To split the training set, we look for convenient fuzzy sets Fi , F2 , ... , Fk for each continuous attribute j, and this search will be explained in the next section. To construct the tree, we choose the attribute with the highest fuzzy information gain /:i * (j). Then, the best attribute corresponds to the minimum of J * (j).

Fuzzy set determination and threshold computation

To construct the fuzzy subsets of E attached to a given continuous attribute j, we build a partition of xj into fuzzy sets which is satisfying for the identification of Use of these functions in a tree node.

The dilatation and erosion operators are used a fixed number of times, so that the discretization's complexity remains linear (once the attribute values have been sorted). It follows that the complexity of the whole algorithm is the same as CART's or ID3's, i.e. O(pnd) where di s the depth of the tree. 66 If the tree is well-balanced, we have d = O(log(n)), and the time complexity is O(pnlog(n)). This i s also the complexity needed for sorting the attribute values, prior to the algorithm runs.

Classification Function

Generally, when a classification tree is used to classify a new example, the values of this example are compared with the computed thresholds. However, a threshold is not generally a value which really occurs in the training set. It i s imprecise in nature because there is no precise information about the values between [ and b_.

Restricting the descent to a single branch of the tree for these values may not be very efficient . It is better to enlarge the threshold to an interval. An estimate probability may then be associated with the outcome of this test. 5 1 In our approach, we use the values found during discretization as boundaries for the imprecise interval, and a graduality of membership to a path for the values near the threshold. At a given tree node, the description to be classified is associated with each of the edges issuing

•����--������� from the node, with a degree equal to its degree of membership to the fuzzy subsets associated with that edge, as defined in Fig. 5. A path to a leaf is then associated with a collection of degrees and we can aggregate these membership degrees by means of fuzzy aggregation operators.

A path from the root to a leaf is equivalent to a rule "If (and P 1 P 2 ... P k) Then Ci'' , where the premises correspond to the fuzzy events associated with the edges of the path, and where the conclusion is the class attached to the leaf. In order to aggregate the premises, we use a conjunctive operator, and to aggregate the conclusions of all the rules corresponding to a given class, we use a disjunctive operator from fuzzy set theory. More specifically, in order to achieve the intersection of the premises, we use the usual operator known as triangular norm (t-norm for short), and to achieve the union of the conclusions, we use a triangular conorm (t-conorm for short). In this study, we employed the t-norm and the t-conorm defined by Zadeh,7 6 which are respectively the minimum and the maximum. The final decision is the class which has the highest membership degree. We can foresee other uses for these membership degrees which take into account all the degrees found on the paths. For example, a classification into continuous classes can be made by computation of a barycentric value from all the obtained classes, or, in a fuzzy framework, it would be useful to preserve the decision as a fuzzy subset of the set of classes, with the obtained degree.

Results

Our approach is essentially concerned with the problem of the construction of clas sification trees when continuous values occur, and we present here our results on the continuous data sets only (Table 5). The average size of the trees is the number of edges. The CPU time is indicated for a program written in C, running on a Sun station Spare 10. We observe that the results are slightly enhanced by the use of fuzzy trees compared to results obtained by CART which considers crisp (non fuzzy) tests for the thresholds. However, the average sizes of CART trees and fuzzy trees are not the same, so that further studies would be needed to obtain a more precise comparison.

EMPTY MONOMIALS

Method Overview

This method builds discriminant functions between classes, the elements of which are described with binary attributes. These functions are conjunctions of Boolean

------- ---••------
variables. The conjunctions that we use are selected because they never appear in one specific class, but are attested in the other classes a minimum number of times. So these conjunctions are characteristic elements of non-membership of a given class Ci , i.e. characteristic of "not-Ci '' . We shall first describe our method for a problem with only two classes C+ and c_, represented by positive and negative examples. These belong to the sets E+ and E_ whose union constitutes the learning set E. A new description is classified into C+ (resp. C_) according to the number of characteristic rules of not-C_ (resp . not C+ ) it satisfies. We can measure two error rates, one on the learning set, the other on the test set. On the learning set, there may be no error, but there might be indecision, since it is possible to find an element of E that satisfies no rules. On the test set, errors are obviously possible. Moreover, some uncertainty may occur, either because an example does not satisfy any characteristic features of C+ and c_, or because it possesses the same quantity of both.

In the Boolean framework, a conjunction of attributes (generators of Boolean algebra) with values 0 or 1 is a monomial, and monomials are conjunctions of liter als. On the set E, a monomial covers some elements, those having the same values as those of the monomial attributes. If there is no element of E to present this conjunction of literals, this monomial is said to be empty on E. The empty mono mials of E+ (resp. E_) indicate not-C+ (resp. not-C_ ). To build our discriminant functions, we first enumerate all the empty monomials of E+, then those of E _, and we only keep monomials that cover at least q elements of E_ (resp. E+), q being a parameter. Moreover, we only consider empty monomials with a minimal length, since an empty conjunction lengthened with other literals stays empty.

The building of empty monomials has been studied for a long time, because it is connected with the minimization of Boolean function problems. Let F be a Boolean function given as a disjunction of complete monomials (disjunctive normal form), or equivalently as a T Boolean array (with p attributes, T has p columns). To minimize F we look for all its prime implicants that are the empty monomials of the complementary function F. To solve this very important problem for cir cuit design,72 numerous algorithms have been proposed (Karnaugh, Mc Cluskeyand Quine, cf. Ref. [START_REF] Flegg | L 'algebre de Boole et son Utilisation[END_REF]) that start from f'. This is not very practical in our framework, since f' is the complementary array of T in {O, l}P. Therefore, we have chosen Kuntzmann's36 algorithm, which works directly on T and can be adapted, particu larly when the number of literals must be bounded, or when only positive forms of attributes are required.

Let us suppose that we: are building the empty monomials of E+ (the procedure is the same for E-). The algorithm is sequential, and it builds the successive lists of empty monomials. After examining the i first elements of E+ the resulting list is denoted as Li. Let ei be an element of E+ and Si be the set of the complementary forms of its literals. For instance, if ei = x1x2x3x4 we have Si = {x1 ,x2, x3, x4 }. The first list L1 is initialized with S1. Each step corresponds to the examination of a new element ei and produces the list Li from list L i -l• When the whole set E+ has been check, the resulting list contains all the empty monomials of E+.

--•-----This algorithm is based on the following proposition: Let >. E Si and µ E Li-11 (1) If µ contains .\ then µ E Li;

(2) If µ does not contain >., then the conjunction µ>. belongs to Li.

The proof is easy. If µ is an empty monomial that contains >., as >.( E Si) is not in ei, µ is still empty. If µ contains �' µ>. contains >..X, and it is useless to add it to Li. Finally, if µ contains neither >. nor >., µ' ).. is empty since µ was empty and >. is not in Ci• The Kuntzmann's algorithm is the iterative application of this proposition, using the rules (1) and (2) in a specific order: L 1 is initialized with S 1 For i = 2 to IE+ I

For each literal >. E Si { Copy in Li all the monomials of Li-1 that contain >. and delete them from Li-1;

If one of them is equal to .\, .\ is removed from Si } For each literal >. E Si and any monomial µ E Li-l { When A 1. µ and µ>. ¢ Li, add µ>. to Li }

End of For i

The complexity of this algorithm depends on the length of empty monomial lists, that cannot be predicted. In the worst case, this length is exponential in the number of attributes, so it cannot be used for large size problems. To get Li from list Li -l, either we copy monomials remaining empty or we enlarge them with one literal in Si. So it is very simple to generate only monomials having a bounded number of literals , which is attractive in our context. Moreover, the number of monomials having a bounded length lm a x is polynomial, and consequently the enumeration procedure has a worst case complexity O (plmax ) .

Application to the Wa veform Problem

We applied the method described above to the binary description of the waveforms. We shall now explain how we adapted this method, and how we choose the param eter values using the original data of Breiman et al. [START_REF] Breiman | Classification and Regres sion Trees[END_REF] For each class of the learning set compared to the union of the others, we enu merate its empty monomials having at most k literals, or k-monomials. Then, for any description to be classified, we count the number of monomials of each class covering this example. The greater the quantity for a class, the smaller the chance of belonging to it. Thus, we have three scores corresponding to the classes, and we assign a description to the one which has the smallest score, i.e. the class having the minimum number of empty monomials covering this example. When considering a learning example, there is at least one class with a score equal to 0, but there may be several. In that case, there is indecision. For a test example, there may be two or three scores obtaining the minimum value. If the actual class does not give a minimum score, we count an error, and so indecisions are only between alternatives , one of them being the correct class. If there are two tied classes, the third one is discarded, and this becomes a double indecision; if there are three, we have a triple indecision.

First, we tried empty 2-monomials. Among the 300 instances of the learning set, there are 162 double indecisions and 2 triples. This means that there are only 136 elements that are (correctly) classified. This great rate of uncertainty (553) led us to consider empty monomials with length 3. There are respectively 567, 604, 564 for the three classes. Now, 48 double indecisions and no triple remain, which corresponds to 843 of correctly classified elements. Then, we discarded monomials covering less than 103 of the negative examples, i.e. less than about 20 examples. This selection criterion gives 265 monomials for class C 1 , and we took the same number for the other classes, retaining monomials with the best covering rate. For the learning set, there are now 56 double indecisions, no triple and 244 waveforms correctly classifi ed. For the test set that contains 5000 waveforms, the number of double indecisions is 858, corresponding to 173 and there is no triple. The number of errors is 681, and the number of elements correctly classified is 3461. Uncertainty can be treated according to two options:

-Either we do not take a decision, and then there are only 4142 classified elements.

Consequently, the error rate is 16.5%; -Or we toss up to decide the class when there is indecision, and the decision will be correct one time out of two. In that case, there will be 681 + 429 errors, corresponding to an error rate of 22%.

Results

For the 11 learning sets, we limited the number of selected monomials to 250. Sometimes, all of them do not cover 103 of the elements of the other classes, and often there are less than 250. When there are more than 250, we keep those having the greatest covering rate. The average number of selected monomials is 225 per class, most of them having length 3. On average, there are 1094 double indeci sions, that is 223, which are not uniformly distributed; there are less for class C2 than for class C 1 or C3 . The average number of errors is 625 corresponding to 133 of the waveforms. If we insist on classifying the whole test set, tossing up for a decision, there will be 547 new errors which will give 23.43 on the whole set. The CPU time corresponds to a program written in Basic and running on a Macintosh Power Book 165. The size is the number of monomials multiplied by their length. Results are given in Table 6. A decision committee consists of a set of rules {(ti, vi )} where each ti (the condition part) is a. monomial (or conjunction of lite rals) and each Vi (the conclusion part) is a g component-vector, Vi j taking its va lues in { -1, 0, 1}. These values express that the ith rule is respectively in favour, neutral and in disfavour of the class C1 . A default rule is added to this set of rules: in a way, it expresses the a prfori distribution of classes, and it is used in case of indecision. To classify an example, we calculate for each class C1 the sum v. 1 of the jth components of the fired rules. After that, the sums v.1 are compared. When one of these is strictly greater than the others, it designs the selected class. In the other cas e, we use the default class to choose among the classes having the highest scores. An example is given in Fig. [START_REF] Catlett | On changing continous attributes into ordered discrete attributes[END_REF]. In (a) we give the decision committee itself, in (b) the result of 548 this decision committee for the example x1x2X3X 4 X 5 , and in (c) the result of this decision committee for the example x1 X2X3X 4 X5. In both cases, two rules are fi red. In case (b), the chosen class is C1, and in case (c), the decision is given by the default class, and is 02. Small-sized decision committees, such as the one above, are easy to interpret, and they need only a pencil to be used, like classification trees, or Rivest's decision lists. [START_REF] Rivest | Learning decision lists[END_REF] The difference is that rules are neither ordered (as in decision lists) nor organized in a dichotomic way (as in classification trees). Decision committees might also be viewed as linear discriminators whose coefficients belong to { -1; O; 1}, and are able to use conjunctions of literals. Finally, note that when there are two classes, it is convenient to state that a rule in favor of one class be in disfavor of the other. We can then state that the conclusion has one value belonging to { -1, 1} which indicates that the rule is respectively in disfavor and in favor of class 01 or, equivalently, respectively in favor and in disfavor of class C2 (an example is given in Fig. 7). However, in supervised da.ssification we only consider functions whose size (number of literals) is limited. The result given above demonstrates that if we take a decision committee with sufficiently high size k', we can represent any func tion whose size is k. In order to compare decision committees with other classes of functions, we therefore need to establish a link between k and k'. Take the case of classification trees and consider Fig. 7, in which we show two ways of coding a classification tree by a decision committee. On the basis of this figure, it is clear that classification trees whose depth is k can be coded by deci sion committees whose monomials have a length of k at most. If we define the size of a classification tree more naturally to be the number of its edge,,,<; (8 in the previous example), and the size of a deci sion committee to be its number of literals ( 5 and 8 before), we can show that any tree of size k can be coded by a decision committee whose size is at most (k2 + 6k)(g -1)/8g. To give a concrete example, let us consider the classification tree found by CART , 4 for the waveform recognition problem. It is composed of 20 edges. The preceding result shows us that by exploring the set of decision committees whose size is no more than 44, we explore a set of functions that -contains any classification tree of size 20, and thus the one found by CART.

X I . .t2

Other results of the same type can be derived for other classes of fu nctions. Let us mention however that the possibility to duplicate a rule allows us to come as close as desired to li near separators having real coefficients, and allows us to simulate the ordering of monomials in a decision list (the first rules are duplicated in order to make the decision when they are fired).

The Learning Algorithm

We can demonstrate that finding the decision committee whose size is bounded and which makes the fewest number of errors is an NP-Ha.rd problem. We are therefore obliged to use approximate methods. We tested numerous algorithms among which some were based on simulated annealing, as in Ref. [START_REF] Carvalho | SDL, a stochastic al gorithm for learning decision lists with limited complexity[END_REF]. The algorithm we retained proceeds in two stages ; it begins by extracting a certain number of "good" rules and then puts them in a decision committee having a "good , , performance on the training sample. We are now going to examine these two procedures separately.

7.2.L Extracting good rules

The algorithm us€d is a version of PLAGE restricted to Boolean representations.23 The aim is to find all of the most general rules satisfying certain numerical criteria. The principle is to make a breadth-first search of the set of monomials , organized

--------• • • � ••----------------•
according to the generalization relationship. This search is top-down and starts with the most general monomials, i.e. those having only 1 literal. A monomial m is evaluated by two numerical criteria: (1) we impose that it covers a sufficiently high number of examples N of the learning sample;

(2) we impose that it has a sufficiently high discriminant power. This power is measured by the x 2 criterion, used here as an heuristic, rather than for its statistical properties. For each class Ci, we calculate the quantity Q i using the x2, as indicated below 1) is satisfied, and when the maximum of the Q is is greater than a threshold T, we construct a rule having mas condition. For any i, if (Qi < T) then the ith component of the rule is O; otherwise if (adbe > 0) this component equals 1, and it is -1 otherwise. When a monomial is retained to form a rule, all of its specializations are pruned. If m is not retained, we calculate a promise function that gives the best score that could be reached by a specialization of m. If this promise is lower than T, all the specializations of m are also pruned. Finally, the algorithm stops when all monomials have been pruned or ev aluated.

The worst case complexity of this algorithm is exponential in the number of attributes. In practice, the computation time depends on the chosen thresholds. If they are badly adjusted the algorithm will explore the whole space of all monomials, and this time will be prohibitive. Inversely, the case might occur where only the monomials having a single literal are produced, and the rest of the space is pruned. Experimentally, this algorithm allows us to find rules having 3 literals, from de scriptions based on more than 100 binary attributes, in less than one hour of CPU on Spare 10.

Rule aggregation to form a good decision committee

The objective of this algorithm is to extract from the set of rules previously cho sen, a subset that, when assembled, constitutes a decision committee having a low error rate on the training set. The general principle is analogous to that used in agglomerative methods of hierarchical classification. First, we partition the rules into singletons reduced to single rules. At each step, the algorithm achieves the union of two subsets belonging to this partition, and the number of elements of this partition diminishes by one element. These two subsets are chosen by maximizing a gain criterion R among the set of pairs of elements of the partition. The algorithm stops when the best union of pairs of elements of the partition leads to negative or null value of R. We then extract from the partition the subset of rules which forms the decision committee having the lowest error rate.

Let L be a set of rules. We defi ne its error rate, eL, to be that of the Decision Committee formed by these rules and completed by the best possible default rule (according to the error rate computed on the learning set). The criterion R L,L' measures the gain expected from the union of the two sets L and L'. It is defined by the equation When this criterion is positive, the Decision Committee formed by the union of L and L' has a lower error rate than that of the two Decision Committees taken in isolation. All along the algorithm, we therefore try to group rules representing a high gain rather than a low error rate. This enables us not to forget rules that could, once reunited in a Decision Committee, constitute a good classification procedure.

Let us point out the fact that the results obtained using this algorithm are much better than those of the greedy approach which consists in choosing the best rule and adding rules one by one, while minimizing the error rate, until no gain is possible.

Finally, the complexity of this algorithm is in O(nr 3 ), where r is the number of rules found by the preceding procedure, and n the number of examples.

Results

The learning algorithm described above has been evaluated on binary and ternary data. The CPU time corresponds to a nonoptimized program written in C, running on a Sun Spare 10. The size of the decision committees obtained is the number of literals. Results are given in Table 7. We notice that the performance of decision committees is not so far from that of neural networks and much better than that of classification trees. The size of the resulting decision committee is always small, and thus achieves one of the objectives of symbolic methods, which is to produce dis criminant fu nctions with a good explanatory power. The rules found generally have only one literal. This explains the small amount of time needed for computation.

When different thresholds are chosen (smaller for N and higher for T), computation time and rule size increase, but results are not better.

----• -------- •• -----
individual is adapted to the problem. Starting initially with a randomly generated population where each individual has been evaluated, the genetic algorithm selects a subset of individuals by choosing the best individuals of the population with a high probability. Then, these selected individuals are used as parents in order to produce the next generation. To achieve this, an individual must be represented as a string of genes in order to be able to use genetic operators such as crossover or mutation. The crossover operator selects two parents and randomly exchanges two substrings of genes in order to create two new individuals. The mutation operator randomly modifies some genes of an individual and aims at introducing new or forgotten genes in the population. These operators aim to create better and better individuals by combining useful genes of their parents. A new population of the same size as the preceding one is created using these operators, and the algorithm will continue such evaluation-selection-crossover-mutation cycles until a stopping criterion is fulfilled. Genetic algorithms can be appli ed to machine learning problems. 34 • 69 In this case, each individual represents knowledge such as rules, neural networks or Lisp functions. The evaluation function is computed using a learning set and may mea sure, for instance, whether or not an individual correctly classifies the examples in this set. The aim of the algorithm is then to find the individual that correctly classifies the greatest number of examples. The algorithm we shall present, called SIA, follows this line of approach.

Input-Output Model

SIA takes as input:

-Ex amples. Each example is described with attributes. For instance, these at tributes can be Colour or Size. Each example has a special attribute that rep resents its class and that takes discrete values. For instance, the Fly attribute that may take the values yes or no can be the class attribute to be predicted using the two other attributes. The attribute values can be missing, indifferent or undefined. SIA can also deal with tree-structured values. For instance, the Colour attribute may ta.ke the specific values red or orange, and a more general value red-like. -Biases. These biases are preference given by the user who may like .to favor some rules. For instance, the user may ask for specific rules that take into account many attributes, or for general rules. This aspect is expressed using a parameter which is denoted as f3 in the following. In order to handle noise, the user may also give a maximum allowed error rate for each learned rule, denoted as a. -Search intensity. The user can let the genetic algorithm spend more or less time for learning rules, by modifying the stopping criterion. This intensity is denoted by Nbmax and its use is detailed in the following.

Finally, SIA outputs rules of the following form:

If (Colour = red-like) and (Size E [4.3, 7.8]) Then Fly = yes .

These rules can be used by SIA to predict the class of an unclassified example, or to analyze the database by providing the user with symbolic and thus understandable results.

The Learning Algorithm

SIA is a covering algorithm inspired from AQ4 2 which uses a genetic algorithm as search algorithm: an example of the learning set is chosen as a seed, and then the genetic algorithm tries to find the best rule that covers this example; another uncovered example is then chosen to learn another rule, until all examples are covered. For instance, let us suppose that the chosen example is:

(Colour = red) and (Size = 5.4) and (Fly = yes) .

The genetic algorithm is going to generalize this example into a rule. This example is initially translated into a very specific rule, denoted by Rinit in the following, that would be in our example:

If (Colour = red) and (Size E [5.4, 5.4]) Then (Fly = yes) .

Then, the genetic algorithm uses a population of rules that are all at least as general as this initial rule. Its aim is to find a rule that maximizes the criterion which is defined by the user, like for instance "the most general rules with less than 103 classification errors" . This population of rules evolves using the principles described earlier and using genetic operators adapted to the high level representation of the rules.

The mutation operator randomly generalizes a rule by performing one or more of the following operations:

-Enlarging an interval. For instance, the (5.4, 5.4] interval can be changed to [4.7, 5.6], where 4. 7 and 5.6 are other values of the Size attribute that are observed in the learning set. -Generalizing a tree-structured attribute. For instance, in the previous rule, the value red can be changed to red-like. -Dropping a condition. For instance, the condition over the Size attribute in the previous rule can be dropped, which generates the rule "If (Colour = red) Then (Fly = yes)" .

The crossover operator exchanges conditions between two parent rules. For instance, with the following two parent rules:

If (Colour = blue
•---•�------• ------- ----•••�-
Each generated rule is evaluated through the evaluation fu nction. For a given rule R, this function equals:

f(R) = c(R) -anc(R) + {3g(R) c(R) + nc(R)
where c( R) is the number of examples that R classifies correctly, nc( R) is the number of examples that R misclassifi es and where g(R) is the generality of R, measured by the proportion of dropped attributes in R condition part. Having f3 < 1, this function ensures that the accuracy of learned rules, i.e. c(R)/c(R) +nc(R), is above a/1 +a. This is due to the fact that the initial rule satisfies f (Rinit) 2 0, and that the algorithm may only improve this rule. The higher f3 is, the greater importance given to generality. Usually, we choose 0 < {3 < 1. In this case, fi rst importance is given to the accuracy of rules, and among the rules having the same accuracy, the most general is prefered.

The genetic algorithm stops when more than Nbmax rules have been generated

without improving the best rule of the population. The best rule found is then added to the list of rules that will be output. SIA then chooses another example which is not covered by any learned rules, and uses this example as a new seed for learning another rule. The genetic algorithm is called up several times until all the examples in the learning set are covered. The overall algorithm :i s the following:

1 Let x be an uncovered example 2 Generalize x into a rule R* using the GA: 2a Translate x into a specific rule Rinit and

Initialize the rule population P to Rinit 2b Randomly select one or two parent rules in P, Generate one offspring R using genetic operators and Evaluate R using f. 2c Add R to P if P contains less than 50 rules or replace the worst rule Rof P with R if f(R) > f(R-) . 2d Repeat steps 2b and 2c until the best generated rule R* has not been improved for more than Nbmax generations.

3 Output R* and Go to 1 if some examples are still uncovered.

Let p denote the number of attributes. For the sake of simplicity1 let us suppose that these attributes are binary. In the worst case, the genetic algorithm generates all possible rules, that is 0(2P), and this for every search it performs. This yields an exponential worst case complexity of the whole algorithm. Of course, this worst case complexity is never reached in practice. For instance, in the waveform learning problem, the maximal number of rule evaluations would be in the order of 101 1 , but SIA evaluates only 10 5 rules in practice.

Classification Procedure

Given a set of rules and a description z to be classified, SIA looks for the rule which is the closest to z, and chooses the dass that appears in the conclusion part of ---• --------this rule. This technique is similar, in a way, to the Nearest Neighbor algorithm (Sec. 2.3). The distance used takes into account the quality of the matching between the rule and the example. Let us consider a rule R. The distance d(R, z) equals 0 when R matches z exactly. Or else, the distance is equal to the proportion of R's conditions which do not match z. When several rules are at the same distance fro m z, the rule with the best performance on the learning set is chosen, according to the evaluation function described previously.

Results

Results on the waveform problem are given in Table 8. The CPU time corresponds to a Pascal program running on a Sun Spare 10 workstation. The Size column corresponds to the number of rules (80) multipli ed by the mean number of conditions in the learned rules [START_REF] Breiman | Classification and Regres sion Trees[END_REF]. In this test, SIA tries to find the most general rules with a maximum error rate of 103 on the learning set (a = 9 and f3 = 0.1). Thus, SIA performance on the learning set is good. This also explains why the number of learned rules is high. While SIA is a stochastic algorithm which does not always learn the same rules on two different runs with the same learning set, the standard deviations obtained are quite low. SIA has been successfully applied to several databases, but SIA does not get a better performance on the waveform problem compared to the other methods. This may be due to the fact that noise is not handled very well either in the learning or classifi cation procedures. However, one should note that this learning task is rather "simple" for SIA because there are no unknown or tree-structured attributes in the data. The genetic algorithm is also more flexible than other heuristic based search. For instance, the criteria to be optimized can be easily modifi ed by the user, without any modifi cation of the search algorithm. This may allow SIA to take into account user preferences for some attributes over some others, or to use any, e.g. nonuniform, misclassification cost functions. The flexibility of genetic algorithms also allows SIA to be enhanced in order to deal with fi rst order logic representation, 1 without changing its main principles.

VERSION S P ACES

The Version Space Framework

Version spaces were developed by Mitchell43 as a general framework of combinatorial learning algorithms for the discrimination between two classes, C+ and C_ (positive 556 and negative instances). The goal is to represent the set of solutions discriminating C + from C _ , in a given characterization language. For this purpose, one structures the space of all sentences of the language with a partial ordering called generalization relation. This relation is such that a sentence s is more general than another sentence s' if it covers a superset of examples, and this is denoted as s � s'. One then builds two sets, the set S of all more specific solutions (minimal w.r.t. this order) and the set G of all more general solutions (maximal w.r.t. this order) . This is done incrementally on the set of instances. Initially, S = { .l} (solution rejecting all instances) and S = {T} (solution accepting all instances). At each step, if the new instance i is positive (resp. negative), the elements of S (resp. G) are minimally generalized (resp . specialized) in order to cover (resp. reject) i, with a set of operators depending on the chosen language. In case of Boolean descriptions, This approach presents some important characteristics from the point of view of supervised classification . First of all, this method is primarily intended to find the set of solutions which perfectly discriminate the learning examples. When no such solution exists, the version space approach is faced with a difficulty, the treatment of which constitutes the main subject of thi s section. On the other hand, the fact that all solutions are retained makes the method relatively insensitive to the presence of irrelevant or redundant attributes. Finally, in common with most generalization methods, the language of characterization is part of the data. This language may then be adapted to the application, without changing the method.

Version Spaces and the Waveform Problem

We considered that the examples were described with binary attributes. In this case, a natural characterization language is the set of monomials that one may build from these attributes. Generalization ordering corresponds to the cover relation between monomials (m 1 � m2 iff m2 ::::} m1). Note that in this case, the set S is always reduced to a singleton. This being stated, the waveform problem is difficult for Version Spaces. Results clearly show that it is not a good method for this problem. The main reasons are:

-First of all, it is a problem with more than two classes and consequently, not directly within reach of this method. As already outlined before, the solution is to produce as many version spaces as the number of classes. However, this requires a new decision rule to be built , combining the individual decisions of each version space.

-Second, the chosen description language is insufficient to characterize each class.

The "sequential" nature of the data is not taken into account. Characterizations are particularly sensitive to a. translation factor, and this is clearly not desirable.

-Finally, a certain degree of covering between classes exists (the problem is not deterministic). One is not always guaranteed of being able to discriminate per fect]y, even between the tra ining examples. Therefore, we are not looking for a method to challenge the results of classical methods such as linear discrimination (Sec. 2.2), largely more suited for this par ticular application. We would prefer to sho,w how the results of the basic method may be improved in a symbolic-numerical framework.

Description Language

We experimented with the binary coding described in Sec. 1.5. This language be ing particularly poor, we tried several alternative codings of the continuous data, in order to enrich the basic descriptions while remaining in a domain of binary attributes. The most interest ing results were obtained with a coding scheme sug gested by Breiman et al., 4 based on a moving average calculation on raw data.

More precisely, we computed the moving average for windows of size 1, 3 and 5, and coded the result with 2 Boolean threshold attributes (xi < 3 and Xi > 6), that leads to a coding of length p = 126 bits. On average, this coding allows us to "reduce" the noise attached to these contiguous attributes whose values, before the noise has been added, are necessarily very close. It includes therefore a considerab le knowledge of the data generation model. For instance, in the case of classification trees, it provide an increase of about 83 of the recognition rate.4

Training Example Selection

The search algorithm in the version space is initialized with a set S reduced to the element 1-(recognizing no description) and a set G reduced to element T (recognizing all the descriptions). S and G are then refined, taking into account the examples of the learning set incrementally.

When the language is not sufficient to describe the data (this is in fact the case for the waveform problem), the algorithm may stop in two different states. Either We used a hierarchical ascending clustering algorithm (CHAVL ), based on the Likelihood Linkage Analysis method. [START_REF] Lerman | Foundations of the likelihood linkage analysis (LLA) classifğcation metho d[END_REF] We start with the calculation of the raw similarity between any two examples. This raw measurement is standardized with respect to its theoretical mean and standard deviation, calculated on an indepen dence assumption basis, and the final index corresponds to the likelihood of the similarity. The hierarchy is then built step by step, following the maximum likeli-

� ---�-------------• - . • ------- --------••• -----
hood criterion. First, we measured the raw similarity with the number of attributes simultaneously true in both examples. The results, while noticeably improving the results of a random partition (approximately 10%), presented a relatively high standard deviation ( 4 % ) . The best classification results were obtained for a raw sim ilarity measuring the number of identical windows of 2 or 3 contiguous attributes in the two compared sequences.

The Classification Function

As many version spaces are produced there are classes to be discriminated. It is necessary then to build a classification rule which seeks for a consensus between the different judges represented by each version space. After numerous trials, we adopted a solution where each judge has g ballot papers to be di stributed among the g classes following its decision function. This corresponds to a rule choosing the class Ci maximizing the following function fi : fi(x) = L /ii (x) where i=l,g

If dvs; (x) = C+ then fti(x) = g and fij (x) = 0 for j =Ji;

If dvs, (x) = C_ then fii (X) = 0 and fij (X) = gjg -1 for j =Ji; I f dv Si ( x) =? then fij ( x) = 1 for every j .

Results and Discussion

Results given in Table 9 have been obtained from binary data, using a classification based on windows of 2 attributes (Sec. 9.4), and on continuous data coded according to the method of Breiman et al. Finally, the more general formula covering x and rejecting x ' is:

D(x, x') =[Smooth = Yes] or [Height < 7) or [Width > 12] or [Colour = Hot-colour] .
The disjunction D(x, x') is the G-star built from the unique positive example (x, c) (the seed) and the unique negative example (x', c ' ). The selector based on a given attribute is present iff this attribute is informed for both x and x' (which enables easy handling of missing values), and if it takes different values for x and -The G-star of a seed (x, c) is the conjunction of the constraints D(x, x ' ) derived from all its counter-examples. However, a counter-example gives rise to a con straint iff, at the time it is considered, it still belongs to the star. Otherwise, it is discarded. The classification of a new description z is based on the learned G-stars: z is clas sified in the most frequent class among the stars G(x , c) it belongs to. Membership to a star may be tuned according to two parameters:

-The first parameter denoted as c allows us to handle "noisy" descriptions: z belongs to G(x, c) if it sati sfies at least a percentage (100 -c) of the constraints in the star.

-The second parameter denoted as M controls the generality of constrain.ts: z satisfies a constraint D(x, x') iff it satisfies at least M selectors in this constraint.

When Mi s 1, D(x, x') is simply used as a disjunction of the selectors; otherwise, D(x, x') is used as an M-of-N concept. This heuristic is motivated by the fact that, when M is 1, most z happen to satisfy any D(x, x') (especially when the problem domain involves many continuous attributes); hence they belong to most stars, and are classified in the most represented class! This drawback disappears as expected when M increases.

Since the total number of selectors in the stars is upper-bounded by n2p, the classification of an example has a complexity in O(n2p).

Results

Parameter c varied from 0 to 203 and parameter M varied from 7 to 11 in our experiments. Parameter c influences the performance in a classical way: when it increases, the performance decreases on the training set, while on the test set it increases at first, then decreases. In fac t, the only crisp difference occurs between (c = 03) and (c = 5%). For a given value of £, the performance is quite stable depending on M. However, an increase in M can to some extent counter-balance an increase of E. For instance, the best results on continuous data are obtained for (c = 10%, M = 8) and (c: = 20%, M = 9). The program is implemented in C++ and runs on a HP 710 workstation. The size is expressed as a number of stars and a total number of selectors. Note that this huge number of selectors allows one to efficiently grasp an arithmetic concept in a logical manner. On the other hand, it needs bunches of selectors to mimic arithmetic skills (imagine approximating an oblique line through stepwise functions). The theory hidden in the G-stars is therefore unintelli gible. However any decision can be explained through the common points between the case z at hand, and the seeds (x, c) of the stars to which z belongs. Results are given in Table 10, and are among the best we obtained in this ----study. Thus, it appears that the constraint-based approach effici ently overcomes the limitati ons of the Version Space regarding disjunctive and overlapping concepts and noisy data. Moreover, we wou]d like to emphasize that constraint-based learning may be extended to a subset of first order logic. 5 8 It is obvious that the choice of a particular problem favors certain methods over others. All the conclusions of this study, particularly on the misclassification rate, cannot therefore be extrapolated to other problems and other domains. Neverthe less, certain characteristics of the methods appear in the results presented. Some methods learn more rapidly, others decide more quickly, or are endowed with a bet ter explanation power. Table 11 and Fig. 9 highlight these different characteristics.

Except the Best coding item, they are derived from results obtained by methods on binary data, which are those which more clearly justify the use of a hybrid approach, if we exclude the Fuzzy Classification Trees (Sec. 5) which are basically intended to deal with continuous attributes. For this latter method, we used results from Table 5 which were obtained for continuous data. The twelve methods are classified according to the following six criteria:

-To tal Misclassification Rate for which we provide the detailed ordering, although this could be questioned as said before. Moreover, because of the stochastic nature of the problem, this ordering might be slightly modified if other learning and test sets were used. This is clearly shown in Fig. 9 where the 953 standard confidence interval of the expected error rate is represented (Test ± l.96a / Vll ).

When performing a Student test, we see that the only 95% significant differences between consecutive methods are between: MLP and Constraint-based, Empty Monomials and Genetic approach, Genetic approach and Q. Fischer, Q. Fisher and Fuzzy Classification Trees, Classifi cati on Tree and Ve rsion Space. If we now consider for a given learning set the interval in which the misclassification rate lies with probability 95% (obtained from Fig. 9 by enlarging the confi dence intervals by a factor �� 3, 5), we see that it is not unlikely to observe a learning set such that a rather poor method, e.g. Q. Fisher, performs better than a good method, e.g. L. Fisher. In practice it may be said , therefore, that the fi rst 9 methods are not extremely different , while the last 3 yield very inferior results. Besides, the standard deviation is widely different from one method to another. Some methods (e.g. P arzen's Kernel or k-NN) have quite a high variability, while some others, typically hybrid methods (e.g:. Empty Monomials and Constraint-based) present a low standard deviation. -Misclassification rate in the first class, indicated as Test (l), for which we also provide the detailed ordering. We selected this criterion because the first class seems to be much harder to predict correctly. It follows that some methods, e.g. Parzen's Kernel, obtained very unbalanced results among the three classes. These latter methods rarely predict the fi rst class and take few risks. On the other hand, methods such as Empty Monomials, take more risks, obtain well balanced res � lts and inevitably are . not excellent considering the total misclassifi cation rate. Therefore, the misdassifi cation rate in the fi rst class enables the point of view given by the total misclassifi cation rate to be completed and corrected (see Fig. 9). -Lowest misclassification rate observed during this study, depending on the coding scheme, indicated as Best coding. Again, we selected this criterion to complete and correct the misclassification rates obtained with binary data. Indeed, some methods have the ability to directly handle continuous data or have sufficiently low computational cost that it is possible to use a sharp non-binary discretization of continuous attributes. Most of these methods takes advantage of these data which contain more information than binary data (Fig. 9). The most important improvement is obtained for the k-NN method, while the exceptions are CART whose results are better with the binary data (Table 4), and Parzen's Kernel which is only slightly improved by ternary and continuous codings (Table 3). The Empty Monomials and Genetic methods which have only been tested with the binary coding, probably because of computational cost, are penalized. Finally, the most impressive difference is obtained with Breiman's coding (Sec. 9.3) which was only applied to the two poorest methods (i.e. CART and Version Space) and which makes them close to the best. This proves, if proof is needed, that the coding stage is of primary importance and that it must be conducted by using as much as possible the knowledge we have about the data1 and by considering the properties of the classification method we envisage.

Learning Time for which three categories of methods were considered: (1) those which provide an instant response ($ 1 second); (2) those for which the waiting time is reasonable ($ 1 minute); (3) others which are not likely to be envisaged in the case of an exploratory procedure aimed at "understanding" the data. The times as indicated throughout the article were all measured on different equip-ment. To o i btain comparable results we considered the Spare 2 (Sec. 2) as the basic machine (power = 1), and we have corrected the other running times by using the following power ratios: Mac (Sec. 6) � 1/10, Spare 1 (Sec. 4) � 1/2, Spare IPX (Sec. 9) and HP710 (Sec. 10) � 1, Spare 10 (Secs. 3, 5, 7 and 8) � 2. This is clearly a quite rough estimate, but our categories are not affected by reasonable modifications of these ratios.

-Decision time for which we also considered three categories: (1) quick response for 5000 test examples (� 10 seconds); (2) reasonable time (� 2 minutes); (3) others not to be envisaged in an exploratory approach. If we take the decision time for a single example, all the methods are sufficiently rapid (� 1 second) to be used , for instance, in the case of medical diagnosis.

-Size for which we also provide three categories: (1) results directly exploitable and interpretable; (2) size sufficiently reduced so that useful information may be drawn from the results wi thout much difficulty; (3) size such that the compression aspect (or resume) of data is practically absent. For example, classifi cation trees are in the fi rst category, linear discrimination (66 parameters) in the second, while quadratic discrimination ( 696 parameters) is in the third category.

It may be noted that among the "best" methods, we find Linear Discrimina tion, Multi-Layer Perceptron and Decision Committees, which are similar in several aspects. The performance of these methods may certainly be explained by their appropriateness for the problem. Moreover, the analytic solution of Fisher's Dis criminant Function, combined with the well optimized implementation of the SAS software , yields high computational efficiency. However, if we try to compare the hybrid methods with the most classical methods presented (Fisher's Discriminant Function, Parzen's Kernel, k-NN and Classifi cation-Tree), we see that there are some methods which are more powerful in terms of error rate, for example, Neu ral Network or Constraint-based methods. Moreover, most hybrid methods obtain results which are better balanced than those obtained by the classical methods. Concerning Neural Networks, similar results have been found in other studies. [START_REF] King | STATLOG: Comparison of fĄfą fĞcation algorithms on large real-world problems[END_REF]•54 Likewise, the Decision Committee method is as explanatory as that of Classifi cation Trees, yet the results obtained by the former are vastly superior at the performance level. This somewhat contradicts a conclusion of King et al. (Ref. 35, p. 312) which was that "symbolic algorithms all performed very similarly and that there is no obvious best algorithm". The explanation, developed below, is very likely linked to the notion of vote in decision taking, used by the best hybrid methods. Therefore, these experimental results are very encouraging. It remains to verify that these good performances can also be observed with various large real-world classification problems. Preliminary results in that direction have already been obtained for the Decision Committe method. 4 8

CONCLUSION

In this article we presented twelve supervised classification methods, some classical and some original, which combine numerical and symbolic aspects. We would now like to make some general remarks about the methods presented, and try to draw some conclusions.

First of all, it appears that the symbolic aspect of the methods presented is predominantly linked to the notion of rule. This is clear in all of the methods, with the exception of the purely numerical (Sec. 2). The rule notion, which emerges in the earliest studies on Machine Learning, and is linked to expert systems and to the search for explanation virtues, takes on various fo rms. We fi nd juxtaposed, Tree Based and Decision Committee methods (Secs. 4, 5 and 7) on one hand, and on the other hand, those based on empty monomials (Sec. 6) and constraints (Sec. 10).

In the first case, we find rules which are indeed close to those of expert systems, whilst in the latter the rules are extremely numerous and primarily characterize the description space. It is also to he noted that Neural Networks, which are inherently numerical, integrate a certain notion of rule if they possess a hidden layer. This hidden layer contains the "rule" conclusions defined throu gh the first weight layer, while the next layer shows how these rules should be combined.

Concerning the numerical aspects, the notion of vote in decision taking has considerable importance. This occurs on two levels. First, in several methods, rules are fired through a partial matching procedure, in other words, through a counting and threshold comparison procedure. Now, in most methods, the decision is taken based on a set of fi red rules and not on the basis of a single rule. Exceptions to this are the classification-tree methods, which in light of the results on waveforms, seem to be penalized by this characteristic. Numerical methods, particularly Fisher's Linear Discrimination and Neural Network s, integrate the voting notion through the more general notions of weighted sum and activation function.

Different solutions are proposed by these methods for finding rules, for evaluating those rules individually and collectively, for firing rules, and for combining their decisions. Other solutions exist, which are not presented here, among which we may cite those inspired by neural networks, such as Refs. 26 and 62. Deepening the theoretical results is a promising research field to be explored in future studies. This would make it possible to find paths through the diversity of the solutions proposed at present , to specify formal bases of certain approaches and to explain the often positive experimental results obtained by these methods.

Several methods presented integrate the notion of generalization, and that of solution or version space. They proceed by exploration of this space, and extract the pertinent points which are used to form the condition part of rules. Thus, they are able to pass from simple attribute-value descriptions to more complex system descriptions, based on subsets of predicate logic, or on graph-based formalisms. This passage has already been studied for several methods we have presented, 58• 69 and applications for other description types, notably biological sequences, have been conducted successfully. 22•25 We think that this capacity to process complex data, a.s well as the results obtained here on a problem known to be hard for rule based approaches, is very encouraging for the future of supervised classification hybrid methods.

Fig.. 1 .

 1 Fig..1. The three basic waves.

Fig. 2 .

 2 Fig. 2 . Schematic representation of the three classes.

Fig. 3 .

 3 Fig. 3. A three-layer perceptron.

4. 1 .

 1 Overview Tree-based methods are used to construct classification functions which can be represented by a decision tree. These methods are well-known and widely employed in both statistical Pattern Recognition and Machine Learning. Since the seminal article of Sonquist and Morgan,64 an impressive amount of research on tree-based classification has been conducted in both fields, among which we shall only cite here those of Breiman et al. 4 and Quinlan. 50

Fig. 4 .

 4 Fig. 4. A binary classification tree.

  538

5 .

 5 FUZZY CLASSIFICATION TREES 5.1. Overview We are primarily concerned here with the problem of the construction of classifica tion trees when (some) attributes are continuous. With such data, usual symbolic classification trees do not give excellent results. The key point is the discretization of these attributes, i.e. the partitioning of an infinite number of values into a fini1te 540 ------------

Fig. 5 .

 5 Fig. 5. (a.) Membership functions associated with the fuzzy events {xi < Vj} and {xi > Vj }; (b)

Fig. 6 .

 6 Fig. 6. (a) A decision committee; (b) Result for the example x1x2x3x4x5; (c) Result for the example x1 :f'2x3x4 xs.

Fig. 7 .

 7 Fig. 7. Two ways (b) and (c) of coding a decision tree (a) by a decision committee.

  b + c + d) ( adbe ) 2 Qi = (a +b)(a +c)(d +b)(d +c) • When condition (

8 .

 8 LEARNING RULES WITH A GENETIC ALGORITHM 8.1. The Genetic Algorithm Principles Genetic algorithms are optimization procedures inspired from the mechanisms of natural selection. 3 2 In order to solve an optimization problem, these algorithms use a population where each individual represents a possible solution to the problem. Such an individual i s evaluated using an evaluation function that measures how well the

  ) and (Size E[4.4, 7.84]) Then (Fly = yes), If (Colour = red) and (Size E [3.5, 5.6]) Then (Fly = yes), the following rules can be generated by exchanging the condition over the Colour attribute: If (Colour == red) and (Size E [4.4, 7.84]) Then (Fly = yes), If (Colour = blue) and (Size E [3.5, 5.6]) Then (Fly = yes) .

  554

  which we used for the waveform problem, a convenient representation of the G set allows an O(n2) time complexity, where n is the number of instances.46 The decision dvs of the membership class of a new description xi s taken on the basis of the version space VS = ( S, G) following the rule: dvs(x) = C+ If '<:/s E S, x $ s, i.e. x belongs to the class of examples ; dvs(x) = C_ If '<lg E G, -.(x � g), i.e. x belongs to the class of counter-examples; dvs(x) =? Or else, i.e. x can be classified in either two classes indifferently.

  We tried to characterize the examples corresponding to each class proposed by Breiman et al.4 with respect to its complementary set, e.g. C1 w.r.t. C2 U C3. The opposite is also possible, and one may choose C2 U C3 for the class of examples and C 1 for the class of counter-examples. In the second case, the problem comes down to the characterization by empty monomials, as carri ed out in Sec. 6, but the results are clearly inferior. On the other hand, using both characterizations slightly ___ , ______ -improved the results, at the expense of a doubling of the number of literals in each characterization.

  it converges on a single solution before having treated all training examples, or -------•-• •----it detects that no solution exists. The simplest way, retained here, that always guarantees the existence of at least one solution, is to reject all examples producing an empty version space. It must be clear that this process can lead to an acceptable solution only if training examples have been adeptly selected for their presentation. Furthermore, a good scheduling of these examples reduces the complexity of the calculation by allowing a fa ster convergence of the algorithm. The goal is to produce this ordering by means of a hierarchical classification of the training examples. One selects the higher nodes in the tree, corresponding to a cluster in which all examples belong to the same class, and represented by circled nodes in Fig. 8. In this way, one builds a partition of the examples in homogeneous clusters, that are then sorted in decreasing order of size. While learning class Ci, one alternates, in decreasing order of size, the presentation of a group of Ci and the pre sentation of a group of another class. Thus if classification is correct , one learns as a priority the most relevant aspects of the charac terization, covering the largest set of examples. Thus, the tree in Fig. 8, where leaves are labeled with the name and the class of the examples, leads to the following presentation if one tries to learn class C 1 ( + for example and -for counter-example): (et, et , et, e1, e;, et, et, e;, e;).

  Fu rthermore, note that the very same tree may serve to produce disjunctive for mulae by learning monomials for each group of a partition of the tree. For instance, if one cuts the tree just below the root , one obtains a partition of the examples in 2 groups that gives the 2 fo llowing presentations for class C 1 : (et , et, et, e1, e;: , e;, e7) and (et, et, e}, e2, ej", e7). One may alternatively choose the counter examples only in the cluster containing the examples, but this generally leads to significantly lower results. In the case of waveforms, this possibility of introducing disjunctions has not brought a noticeable gain in recognition.

Fig. 8 .

 8 Fig. 8. Hierarchical clustering of the examples e1, e2, ... , e9, the class being indicated on the internal nodes, or on the edges.

  (Sec. 9.3), using a classification based on windows of 3 attributes. The CPU time corresponds to a program written in C and Prolog, which is relatively well optimized (original research results were necessary for this purpose, 4 6 and which runs on a Spare IPX 32 Mega ( � Spare 2). This includes the time of clustering training examples, which is about 20 seconds. The obtained length is expressed in terms of the number of literals and corresponds to the generation of 12 sets (S and G for each class and characterizing either the examples or the counter-examples).

x'

  (up to a given precision in the case of real values).

Fig. 9 .

 9 Fig.9. Ordering of the twelve methods with: their a.verage total misclassification rate on binary data (horizontal stroke); the 953 standard confidence interval of this average rate (vertical line); their average misclassification rate in the first class (white circle); their lowest average mi sclassi.fication rate observed during this study, depending on the coding s<:heme (black circle: continuous data, black triangle: ternary data, black square: Breiman's coding).

  Learning and test sets Eleven learning sets, each of them under three different codings as described below, were distributed within the SYMENU group. The first set corresponds to data used by Breiman et al. to test the CART program performance. The other ten were drawn at random, according to the process described above. Each set consists of 300 examples drawn independently (note that the a priori probability of the classes

-----

as the statistical parametric methods and neural networks. We shall discuss the subject at greater length in what follows.

According to Breiman et al.4 the error rate of the Bayes rule is around 14% for this problem. No classification function, even if it is learned on an infinite number of examples, can expect to beat this performance. As the learning sets which we manipulated were of limited size (n = 300), we cannot even expect to reach this optimal result due to the sampling noise.

1. 5.2.

is 1/3). As it was possible to make use of several comparable learning sets, this enabled us to show quite precise averaged results, and to highlight the variability of these results. Using the same process, and independently of the learning sets, we drew a test sample of 5000 examples. The classification methods which we shall present in the following were validated using these test examples.

Table

  1. Format of tables to be completed for the various methods (numbers are given only as illustration).

	Data	Train	Test	Test(l)
	Binary	17.33	223
		(1.13)	(13)

Table 2 .

 2 1. Parametric approach, linear discrimination.

	Data	Train	Test	Test(l)	Test(2)	Test (3)	CPU train	CPU test	Size
	Binary	17.33	223	28.93	18.63	18.63	0.3"	l"	66
		(l.13)	(13)
	Ternary	15.93	19.93	28.83	15.53	15.53	0.3"	l"	66
		(1.8%)	(0.5%)
	Contin.	12.83	20.4%	23.53	19.83	17.93	0.311	1"	66
		(1.3%)	(13)

Table 2 .

 2 3. Nonparametric approach, Parzen's Kernel method.

	Data	Train	Test	Test(l)	Test (2)	Test(3)	CPU train	CPU test	Size
	Binary	3.3%	22.7%	47.8%	8.73	11.5%	O"	893"	300 x 21
		(2.03}	(1.5%)						= 6300
	Ternary	0%	21.7%	35.5%	15.3%	14.2%	O"	86611	300 x 21
			(0.6%)						= 6300
	Contin.	0%	22.2%	26.4%	18.7%	21.4%	O"	933 1 1	300 x 21
			(1.2%)

=

6300

������ ���� �� �� �� �-

Table 2 . 4

 24

	Data	Train	Test	Test (l)	Test (2)	Test (3)	CPU train	CPU test	Size
	Binary	03	23.33	46.03	10.63	13.23	O"	2321 1	300 x 21
			(2.13)						= 6300
	Ternary	03	20.43	42.53	9.93	8.93	O"	24511	300 x 21
			(1.73)						= 6300
	Contin.	03	18.33	31.83	10.33	12.9%	O"	258"	300 x 21
			(1.73)

. Nonparametric approach, k-nearest-neighbor method. = 6300

Table 3 .

 3 1. Two-layer perceptron.

	Data	Train	Test	Test(l)	Te st(2)	Test (3)	CPU train	CPU test	Size
	Binary	14.933	20.873	25.423	18.273	18.863	240"	2011	66
		(1.593)	(0.613)
	Ternary	12.233	18.093	23.713	15.313	15.173	240 11	20 11	66
		(1.553)	(0.683)
	Contin.	10.83	17.313	20.493	16.353	15.063	240"	2011	66
		(1.053)	(0.823)

Table 3 .

 3

	Data	Train	Test	Te st(l)	Test (2)	Test(3)	CPU train	CPU test	Size
	Binary	12.53	21.263	25.61%	18.523	19.603	300"	2011	128
		(1.383)	(0.903)
	Ternary	9.63	18.793	23.213	17.133	18.793	300 11	2011	128
		(1.093)	(0.873)
	Contin.	7.83	17.153	:21.83	14.163	15.443	30011	2011	128
		(1.333)	(0.923)

2. Three-layer perceptron with five hidden units.

Table 4 .

 4 Tree-based approach, the CART method.

	Data	Thain	Test	Test (l)	Test (2)	Tes t(3)	CPU train	CPU test	Size
	Binary	22.93	29.9%	34.63	29.13	26.0%	29"	26"	17.6
		(1.03)	(2.23)
	Ternary	22.53	30.53	33.373	31.223	26.74%	33"	17"	12.6
		(0.73)	(1.633)
	Con tin.	19.83	31.13	29.73	32.13	31.5%	60"	34"	7.4
		(1.13)	(1.23)

  1 16 This may be done for several reasons, e.g. to reduce the running time. Our method, like CART described above (Sec. 4), proceeds dynamically by adjusting the thresholds at each tree's node according to the attached examples. However, we have observed that, if we split the domain of an attribute into two subsets at a given threshold, we obtain imprecise tested values near this threshold, because all possible values of the attribute are not present in the training examples. The solution we propose is to use membership degrees for examples with values near the threshold, establishing a gradual split of the values. During tree construction, we employ a fuzzy measure of information 53 to discretize and to compare the continuous attributes. To classify a new example, we aggregate membership degrees obtained by a given example on a path of the tree, using the fuzzy set theory. 76Let us now consider a. noncontinuous attribute j, associated with the sparse domain Xj = {v1,v 2 , . .. ,vk}• This attribute splits E into k subsets El whose

	i =l
	Using this notion, the classical entropy can be extended to a fuzzy measure of
	entropy
	e*(E) = L-Pr*(Ci/E) log(Pr*(Ci/E)) .

5.2. A Dynamically and Fuzzy Entropy-Driven Discretization

5 .. 2.1. Splitting criterion We must choose the best attribute that will be used to split into subsets the set of training examples E attached to a given node t. A cost function is used to determine this choice, which is based on a fuzzy measure of entropy. Let us use the same notation as in Sec. 4.2. The classical Shannon entropy has, in some respects, a meaning similar to that of the Gini index (Sec. 4.2), and is defined by e(E) = L -Pr(Ci/ E) log (Pr(Ci/ E)) . i In our model, classical sets are replaced by fuzzy sets and we have to define a fuzzy probability. Let n = { w 1 , ... , Wr} be a set of events, each one associated with a probability Pr(wi)• Let F be a fuzzy set defined on n with membership function f F. The fuzzy probability of the fuzzy set F is r Pr*(F) = L f F(wi) • Pr(wi) .

i conditional probabilities are denoted as Pr( Et/ E). The classical information of this split (or the measure of conditional entropy) is defined as

Table 5 .

 5 Fuzzy classification trees.

	Test	Te st{l)	Test{2)	Test (3)	CPUtrain	CPUtest	Size
	29.963	34.73	25.9%	27.13	5"	54"	26.4
	(1.253)

Table 6 .

 6 Empty monomials.It seems clear that the quality of the decisions depends on the number of selected empty monomials; we use a large number, because below the threshold of 100 the uncertainty numb er increases very fa st (greater than 1500). So, conside ring the size of the classification function, it is a poor method. Even if we were to design a selec tion strategy to reduce the number of monomials, keeping the same covering rate, we would never reach the efficiency of the Decision Comm ittees method (Sec. 7), Secs. 1.5 and 4.2). Literals associated with variab les are denoted as xi, x1, x2, x2, •.. , Xp and x.v•

	Test (l)	Test(2)	Te st(3)	CPUtrain	CPUtest	Size
	25%	21%	24 3	330"	444"	2025

7. DECISION COMMITTEES

7 .1. Introduction

Decision committees use expert-syste m-like rules. They try to associate the ex planatory character of classification trees with an additive combination of the rule, in the same way as MYCIN-like expert systems.

[START_REF] Shortlifęe | Computer Based Medical Consultations: MYCIN[END_REF]

The decision is taken on the basis of a set of fired rules, and not on the basis of a single rule (or a path from the root to a leaf) as in classification trees. This additivity exists in linear discrimination and in neural networks, and partially explains the performance of these approaches which are often better than those based on classification trees. Our aim is to find small-siz ed decision. committees. Even though they do not constitute a radically new type of classification procedure (Refs. 3 and 52, Sec. 6), decision committees have given rise to few studies, especially in the form presented here. For more details, further theoretical and expe rimental results, the reader shall refer to Ref. 48.

7.1.l. Notations and definitions

We shall consider here that examples are described by binary attributes, these being possibly derived from nonbinary ones (qualitative , ordinal, ... ) by following a classical discretization procedure (Ref.

4,

  7 .1. 2. Comparison with other classification functionsLet us consider first the Boolean case (g = 2). Classes C1 and C2 represent truth val ues True and Fa lse, and the truth table of any Boolean function can be transcribed directly under the form of a decision committee whose monomials are composed of p literals. This means that by multiplying the number of rules and the number of literals, we can represent every Boolean function by a decision committee. This result can be extrapolated to a greater number of classes.

Table 7 .

 7 Decision committees.

	Data	Train	Test	Test (l)	Te st(2)	Test(3)	CPU train	CPU test	Size
	Binary	20.53	23.03	32.83	20.73	15.93	25"	3"	20
		(1.53)	(0.8%)
	Ternary	16.63	20.53	33.0%	14.83	13.6%	23"	5"	28
		(1.8%)

(1.43)

Table 8 .

 8 SIA genetic algorithm.

	Data	Train	Test	Te st(l)	Te st(2) Te st(3) CPUtrain CPUtest	Size
	Binary	43	24.33	27.73	20.83	24.3%	30011	30"	4 x 80 = 320
		(0.73)	(0.73 )

Table 9 .

 9 Version spaces.There is generally a single monomial in G (and S). These monomials are rel atively short in the case of the initial binary coding (about 2 literals), and much longer in the cMe of Breiman's coding (about 18 literals, but for a code 6 times longer) . Exhibited learning times show a linear progression with respect to the num ber of attributes. The recognition rates found have to be appreciated in relation to the error rate on the training set, corresponding to the percentage of training examples that were not taken into account, due to the inadequac y of the character ization language. A related interesting indicator is the number of examples treated before the convergence of the algorithm. This number is given between brackets in column Te st(l). For an acceptable coding, there must be no convergence, i.e. one must find 300. The slight difference between results obtained on the training set and those on the test set is to be noted. Note also that results are less accurate for class 1, more difficult to characterize in a conjunctive way.

	Data	'Train	Test	Test(l)	Test(2)	Test(3)	CPU train	CPU test	Size
	Binary	30.9%	31.9%	37.53	29.23	29.1%	35"	0.2"	27
		(3.6%)	(2.3%)	(62)
	Breiman's	17.43	21.6%	28.9%	19.23	16.73	70"	0 .311	214
	Goding	(1.93 )	(2.03)	(300)

  So constraint-based learning investigates the coupling of the Version Space and .the Star Algorithm. On the one hand, a bottom-up exploration enables us both to deal with disjunctive concepts and handle noisy data. On the other hand, the need for evaluation and control is avoided by defining the star of a seed (x, c) M the G set derived from this seed: the G-star associated to seed (x, c), noted G(x, c), is the more general formula covering x and not covering any training example belonging to another class. A constraint-like representation, inspired from Ref. 46, enables a Notation and Defi nitions We restrict ourselves to linear (real, integers) and nominal (discrete or tree structured) attributes. Let (x, c) denote a seed. Let E_ be the set of training examples that belong to a class different from c. The G-star G(x, c) is the conjunc tion of the constraints derived from the examples in E_, called counter-examples to (x, c). Before defi ning a constraint, let us recall the notion of selector.4 1-A selector is a Boolean fu nction defined on the problem domain X, which is denoted as [attribute = VJ; in the case where attribute is nominal , this function takes value true for x in X i:ff the value attribute(x) equals value V (or is more specific than V if the domain of attribute is a hierarchy); in the case where attribute is linear, it takes the value true iff attribute(x) belongs to interval V.-The constraint derived from counter-example (x', c'), noted D(x, x'), is the dis junction of the most general selectors that cover x and reject x', called maximally discriminant selectors. Let us consider the following data:

	10. CONSTRAINT-BASED LEARNING
	10.1. Method Overview Smooth Height	Width Colour Class
	Constraint-based induction is a new Machine Learning algorithm58•59 inspired from x = Yes 3 19 Red C+
	both the Star Algorithm AQ41 and the Version Space approach. 43 Since these ap proaches were presented previously (Secs. 8 and 9), we shall only recall the limita x' = No 7 12 Blue C_
	tions which motivated their hybridizati:on and embedding in the constraint-based
	induction frame.
	Version Space fails to handle disjunctive concepts, overlapping concepts, and/or
	noisy data. FUrthermore, the size of the G set may be exponential when using
	the standard disj unctive representation.30 Star Algorithms partly overcome such
	limitations through a bottom-up exploration of the examples. However, the stars
	are built under control of the expert, who explicitly provides criteria for sorting the
	number of solutions to be kept.
	polynomial building and handling of G-stars with attribute-value descriptions. Note
	that this representation handles continuous attributes directly, as opposed to some
	approaches (e.g. Secs. 6, 7 and 9) which require prior segmentation of continuous
	attribute domains. Finally, to classify an unknown description z, we use a simple

idea which exists, for example, in the k-NN method and in some methods already presented: z is classified in the most frequent class among the stars to which it belongs. 561 10.2. Attribute Smooth is binary; so the maximally discriminant selector based on this attribute is [Smooth = yes] . Attributes Height and Wi dth are linear. Hence, the maximally discriminant selectors based on these attributes are respectively: [Height < 7] and [Width > 12]. Last, assuming Hot-colour is the most general value for attribute Colour such that it covers Red and rejects Blue, then the max imally discriminant selector based on attribute Colour is [Colour = Hot-colourj .

  not yet rightly classified given the stars formerly built. The star of a seed (x, c) is the conjunction of all constraints derived from the counter-examples of (x, c) , and the constraint derived from a counter-example (x', c ' ) is the disjunction of all maximally discriminant selectors covering x and rejecting x' (see above). Note that this representation of G is polynomial with respect to the number of attributes and

	. 562	---	••--____ _ __ _ _ _ _ _ _ ___ ,,
	examples, whereas the usual representation (as a disjunction of conjunctions) is pos
	sibly exponential.30 This allows polynomial learning (and classification). Building a constraint is in O(p), building a star is i� O(n2p), and the entire learning process is in O(n3p).

10.3. Algorithms

As in the Star Algorithm, learning examples are considered randomly. An example becomes a seed, i.e. gives rise to a star iff, at the moment it is considered, it is

Table 10 .

 10 Constraint-based learning.

	Data	Train	Test	Test(l)	Test(2)	Test(3)	CPU train	CPU test	Size
	Binary	22.8%	21.63	25.63	21.63	17.13	62"	388"	stars 87
		(0.5%)	(0.33)						Sel 33000
	Cont in.	18.03	18.03	18.13	18.13	17.73	5011	303"	stars 77
		(0.63)	(0.23)

Sel 55000 11. ABOUT THE RESULTS ON THE WAVEFORM RECOGNITION PROBLEM

Table 11 .

 11 Ordering of the methods accordin g to six criteria. Test, Test (l), CPUtrain, CPUtest and Size have the same meaning as in previous tables and have been obtained on binary data.Best coding provides the ordering of the methods according to lowest misclassification rate observed in this study, depending on the coding scheme; B stands for Binary, T for ternary, C for continuous and BR for Breiman's coding (Sec. 9.3).

	Method	Test	Test (l)	Best coding	CPU train	CPU test	Size
	L. Fisher	3	5	4T	1	1	2
	Q. Fisher Parzen	9 4	7 12	6 c 8T	1 1	1 3	3 3
	k-NN	6	11	3 c	1	3	3
	MLP	1	2	1 c	3	2	2
	Decision tree	11	9	9 BR	2	1	1
	Fuzzy decision tree	10	6	12 c	3	2	2
	Empty mo nomials	7	1	10 B	2	2	3
	Decision com.	5	8	5 T	2	1	1
	Genetic approach	8	4	11 B	3	2	2
	Version space	12	10	7 BR	2	1	1
	Constraint based	2	3	2 c	3	3	3