ÉLÉNA: A Bottom-up Learning Method

Abstract

This paper presents a description and an experimental evaluation of éLéNA, a learning system which induces characteristic and discriminant concept descriptions from positive instances, negative instances, and a background knowledge theory. The resulting concept description is expressed as a disjunction of conjunctive terms in a propositional language. Each conjunctive term is the maximal specific generalisation of a subset of the positive instances. éLéNA works in three steps. The first step consists in an exhaustive use of the theory in order to extend the instances representation. Then the learning component performs a bottomup beam search through the concept description space. During the final step, the theory is used again in order to reduce each conjunctive term of the resulting formula to a minimal representation. Basically, éLéNA has the same features as our previous system SAMIA but its learning component is different. The paper reports the results of several experiments and compares the performance of éLéNA with two other learning methods, namely ID and CN. Accuracies on test instances and concept description sizes are compared. The experiments indicate that éLéNA's classification accuracy is roughly equivalent to the two previous systems. Morever, as the results of the learning algorithms can be expressed as a set of rules, one can notice that the number of rules of éLéNA's concept descriptions is lower than both ID's and CN's one.