TL;DR
This paper introduces GEFS, a genetic algorithm-based approach for selecting feature subsets for individual classifiers within an ensemble. By optimizing for both accuracy and diversity, GEFS demonstrates improved performance over standard ensemble methods like Bagging and AdaBoost, highlighting the value of ensemble-specific feature selection.
What Problem Does This Paper Address?
Traditional feature selection aims to find the single best subset of features for a given learning algorithm. However, recent advances in machine learning have shown that combining multiple "weak" learners into an ensemble can significantly boost performance. The key to a successful ensemble is not just that its individual members are accurate, but that they also make different errors. This paper addresses the challenge of how to select feature subsets for these ensemble members to maximize both individual accuracy and, crucially, disagreement among them, a problem that is computationally more complex than traditional feature selection.
Methods
The paper proposes the Genetic Ensemble Feature Selection (GEFS) algorithm. GEFS uses a genetic algorithm (GA) to evolve a population of neural network classifiers, each trained on a different subset of features. The process involves:
- Initialization: Creating an initial population of classifiers by randomly selecting feature subsets. The size of these subsets is varied, and features can be duplicated to potentially aid learning.
- Evolution: Using genetic operators like crossover and mutation to generate new candidate classifiers from the current population.
- Fitness Evaluation: Each classifier's fitness is a combination of its prediction accuracy and its diversity relative to the rest of the ensemble. A parameter $\lambda$ balances these two objectives.
- Selection: The population is pruned to keep only the fittest individuals.
- Ensemble Formation: The current population of fittest classifiers forms the ensemble, whose output is typically an average of individual predictions.
- Adaptive $\lambda$: The algorithm dynamically adjusts $\lambda$ based on the ensemble's error, population error, and diversity to better balance accuracy and disagreement.
GEFS is described as an "any-time" algorithm, meaning it can produce a useful ensemble at any point during its execution, and longer runs can potentially yield better results.
Datasets
The authors evaluated GEFS on 21 datasets obtained from the University of Wisconsin Machine Learning repository and the UCI data set repository. These datasets were chosen for their real-world relevance, varied characteristics (continuous/discrete features, number of classes, number of examples), and suitability for previous research. Table 2 in the paper provides a detailed summary of these datasets and the neural network architectures used.
Key Insights and Ideas
- Ensemble Feature Selection is Distinct: The core idea is that finding feature subsets for ensemble members requires optimizing for disagreement in addition to accuracy, a goal not addressed by traditional feature selection.
- GA as a Global Search: Genetic algorithms are well-suited for the enormous search space of feature subset combinations for ensembles.
- Diversity is Key: The paper empirically supports the theoretical notion that diverse classifiers are crucial for ensemble success.
- Simple Initialization is Effective: Even a randomly generated initial population of feature subsets can yield competitive results, suggesting that GEFS can quickly establish a good baseline.
- "Any-Time" Learning: The ability of GEFS to improve its ensemble performance over time as it runs longer is a practical advantage.
Key Results
- GEFS, even with its initial population, performed competitively with or better than Bagging and AdaBoost on many datasets.
- Running GEFS for longer (up to 250 networks) generally led to improved performance, outperforming both Bagging and AdaBoost on several datasets.
- A win-loss-tie comparison showed GEFS (with 250 networks) winning against Single Net (20-1-0), Bagging (18-3-0), and AdaBoost (15-6-0), indicating its superior performance.
- The adaptive $\lambda$ mechanism and the dynamic length of feature subsets are presented as novel aspects of the GEFS approach.
Limitations and Future Work
- Limited Scope of Base Learner: The current implementation of GEFS uses neural networks. The authors suggest extending GEFS to other inductive learning algorithms like decision trees and Bayesian learning.
- Parameter Tuning: While $\lambda$ is adapted, other GA parameters (e.g., maximum feature subset size) could be further investigated.
- Combining with Other Ensemble Techniques: Future work could explore combining GEFS with AdaBoost's approach of emphasizing misclassified examples.
- Computational Cost: While GEFS is an "any-time" algorithm, longer runs still incur computational cost, which might be a limitation for extremely large datasets or time-critical applications.
Summary updated