Lookahead Feature Construction for Learning Hard Concepts

Abstract

Difficult real-world concepts occur when a domain is poorly understood. The relationship of such a concept to its primitive attributes is complex and obscure. The resulting difficulty for learning algorithms can been quantified in terms of attribute interaction, concept complexity, or function variation. One measure of attribute interaction is entropy or blurring, which ranks synthetic boolean and real-world concepts in the same order as typical induction algorithms' decreasing accuracy. Empirical results show that high blurring degrades the accuracy of decision tree builders, extensions of basic methods, alternative symbolic approaches, backpropagation, and multi-variate adaptive regression splines. Greedy decision tree learners become inaccurate because they assess one attribute at each node. A new global search algorithm, LFC, for decision tree learning uses directed lookahead to address feature interaction, improving accuracy at reasonable cost. LFC also addresses the general verbosity problem in decision trees. The algorithm caches search information as newly constructed features. Its hypothesis representation is variable, from decision trees at one extreme to decision lists on the other. The combination of lookahead search and feature construction markedly improves performance, giving accuracies unobtained by any other algorithms, including those that do global search alone or feature construction alone.