Complex Concept Acquisition through Directed Search and Feature Caching

Abstract

Difficult concepts arise in many complex, formative, or poorly understood real-world domains. High interaction among the data attributes causes problems for many learning algorithms, including greedy decision-tree builders, extensions of basic methods, and even backpropagation and MARS. A new algorithm, LFC, uses directed lookahead search to address feature interaction, improving hypothesis accuracy at reasonable cost. LFC also addresses a second problem, the general verbosity or global replication problem . The algorithm caches search information as new features for decision tree construction. The combination of these two design factors leads to improved prediction accuracy, concept compactness, and noise tolerance. Empirical results with synthetic boolean concepts, bankruptcy prediction and bond rating show typical accuracy improvement of 15%-20% with LFC over several alternative algorithms in cases of moderate feature interaction. LFC also explicates latent relationships in the training data to provide useful intermediate concepts from the perspective of domain experts.