Constructive induction using non-algebraic feature representation

Learning hard concepts in spite of complex interaction among attributes makes constructive induction necessary. Most constructive induction methods apply a greedy search for constructing new features. The search space of hard concepts with complex interaction among attributes has high variation. Therefore, a greedy constructive induction method falls in local optima when searching this space. A global search such as genetic algorithms is more convenient for hard concepts than a greedy local search. Existing constructive induction methods based on genetic algorithms still suffer from some deficiencies because of their overly restricted representation language, which in turn, defines search space. In this paper we explain how the search space can be decomposed into two spaces and we present a new genetic algorithm constructive induction method based on a non-algebraic representation of features. Experiments show that our method outperforms existing constructive induction methods.