Introduction
In the early 1990s, machine learning research was largely divided between Explanation-Based Learning (EBL), which relied on deep domain theories, and Similarity-Based Learning (SBL), which focused on statistical patterns from large datasets. While SBL algorithms like ID3 are powerful, they often struggle with complex concepts unless provided with optimal features. Feature construction—the process of creating new features from combinations of existing ones—can bridge this gap, but the resulting search space is often mathematically intractable. This paper introduces CITRE, a system that uses partial domain knowledge to guide feature construction, making SBL both more accurate and computationally efficient.
The CITRE System
CITRE (Constructive Induction of Trees with Rule Extraction) operates through an iterative process of building decision trees and "inventing" new features from their branches. Unlike EBL, which requires a complete logical theory, CITRE utilizes "common sense" domain knowledge to prune the search space of new features.
The system employs three primary strategies:
- Domain-Knowledge Filtering: Predicates are used to filter out unlikely feature combinations. For instance, in a spatial domain like a board game, only adjacent squares might be considered for combination.
- Feature Generalization: Once a useful feature is identified, domain-specific operators create variations, such as translating a pattern across different parts of a game board.
- Deferred Pruning: Standard pruning techniques often remove the "raw material" needed for feature discovery. CITRE defers pruning until after feature construction is complete to preserve these potential insights.
Experimental Evaluation
The authors evaluated CITRE using a Tic-tac-toe classification task, where the goal is to predict if a board state represents a "win for x." The dataset consisted of 958 legal final states, with training sets ranging from 100 to 500 examples.
Key Results
The experiments compared standard ID3 against CITRE with varying levels of domain knowledge. The results highlight the trade-offs between accuracy, model complexity, and computational cost.
- Accuracy: Feature construction significantly outperformed the baseline. Adding generalization operators provided the highest gains, exceeding the ID3 baseline by approximately 18% at 500 training examples.
- Conciseness: While feature construction naturally increases tree size compared to the simple ID3 baseline, the use of domain-knowledge filtering kept the resulting hypotheses significantly more manageable and readable than exhaustive search methods.
- Efficiency: Although exhaustive feature construction is computationally expensive, the combined method of filtering and generalization achieved high accuracy while maintaining manageable CPU times compared to unguided search.
Discussion and Future Work
A key insight from this work is that domain knowledge does not need to be perfect to be useful. CITRE demonstrates that even "hunches" or simple spatial rules can act as powerful heuristics for feature discovery.
However, the current implementation has limitations. The filtering mechanism is currently binary; a more flexible "guide" approach might be more robust. Additionally, the generalization operators used were hand-tailored for the Tic-tac-toe domain. Future research should focus on developing more universal generalization operators and exploring how to integrate domain knowledge more fluidly into the search process.
Summary updated