Abstract
COverage-based Genetic INduction (COGIN) is a novel framework for symbolic induction that leverages genetic algorithms (GAs) to evolve sets of classification rules. Unlike traditional decision tree algorithms that rely on greedy, stepwise search, COGIN employs a global, probabilistic search strategy. By integrating a coverage-based filter to manage rule competition and diversity, COGIN effectively handles complex, non-linear problems such as the multiplexor function, matching or exceeding the performance of state-of-the-art decision tree methods.
Introduction
In the early 1990s, symbolic induction—the automated discovery of human-interpretable "if-then" rules—was primarily driven by algorithms like ID3 and C4. These methods build models through a series of local, greedy decisions, such as selecting the attribute that provides the highest immediate information gain. However, this approach often fails in noisy environments or complex search spaces where feature interactions are non-linear. Greedy choices can lead to suboptimal models that require extensive post-processing (e.g., pruning) to generalize well.
Greene and Smith proposed COGIN as a fundamental shift from local stepwise search to global search using Genetic Algorithms. By treating rule discovery as an evolutionary process, COGIN aims to overcome the "blind spots" of traditional induction methods.
Methodology: The COGIN Framework
COGIN represents a model as a population of single-condition rules that collectively form a disjunctive set. The core innovation of the system is the Coverage-Based Filter, which manages the transition between generations.
As shown in Figure 1, the evolutionary cycle involves:
- Rule Representation: Rules are maintained in a population where each rule competes for "coverage" of training examples.
- Coverage-Based Filter: Candidate rules are filtered by allocating training examples based on fitness. A rule survives only if it "claims" at least one example not already covered by a superior rule. This mechanism ensures diversity and prevents model bloat.
- Fitness Function: COGIN uses a "lexicographically-screened entropy" measure to find rules that maximize information gain while maintaining acceptable error tolerances.
- Reproduction: Rules undergo crossover and mutation to generate new candidates, which then compete with the existing model for inclusion in the next generation.
Experimental Evaluation
The authors evaluated COGIN using the Multiplexor Problem (6, 11, and 20-bit versions: F6, F11, F20). Multiplexors are challenging for decision trees because address bits only become informative when combined with data bits, creating a non-linear complexity that often misleads greedy algorithms. Training sets ranged from 50 to 1,000 examples, with performance tested on a holdout set of 1,000 unseen cases.
Results and Discussion
COGIN demonstrates significant advantages over traditional decision tree methods, particularly as problem complexity increases.
As detailed in Figure 3, COGIN consistently outperformed standard C4 decision trees in accuracy across nearly all test cases. Notably, COGIN's performance was comparable to "Derived Rules"—a version of C4 that utilizes sophisticated post-processing to optimize rule sets. COGIN achieved these competitive results through its basic search process alone, without requiring additional post-processing steps.
Key Insights
- Global Search Efficiency: By exploring the fitness landscape globally, COGIN avoids the local optima that trap greedy algorithms when initial splits are misleading.
- Data-Driven Succinctness: Interestingly, as training data increases, COGIN's models often become smaller and more accurate. The GA effectively identifies the simplest underlying logic as more evidence becomes available.
- Niche Competition: The coverage filter forces rules into specific "classification niches," preventing redundancy and ensuring each rule contributes uniquely to the model's predictive power.
Conclusion
COGIN successfully demonstrates that genetic algorithms can be a powerful alternative to greedy search for symbolic induction. While its models were sometimes larger than those produced by post-processed decision trees—partly due to the lack of a "default rule" mechanism—its accuracy and scalability are impressive. Future work may involve incorporating post-processing phases to further simplify models and exploring COGIN's robustness in even noisier data environments.
Summary updated