SAMIA: A Bottom-up Learning Method Using a Simulated Annealing Algorithm

Abstract

This paper presents a description and an experimental evaluation of SAMIA, a learning system which induces characteristic 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. SAMIA 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 combines a bottom-up induction process and a simulated annealing strategy which performs a 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. The paper reports the results of several experiments and compares the performance of SAMIA with two other learning methods, namely ID and CN. Accuracies on test instances and concept description sizes are compared. The experiments indicate that SAMIA'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 SAMIA's concept descriptions is lower than both ID's and CN's one.