TL;DR
This paper introduces GALA, a novel preprocessing algorithm that automatically generates new, informative features for existing machine learning algorithms. By combining absolute and relative measures of feature quality, GALA effectively identifies synergistic attribute combinations, leading to improved accuracy and reduced concept complexity across various learning algorithms and datasets.
What Problem Does This Paper Address?
Inductive learning algorithms often struggle with suboptimal representations. The "vocabulary" of features used to describe data heavily influences a learner's ability to find accurate concept descriptions and its convergence speed. Standard algorithms that consider attributes one by one can miss the value of combined features, leading to suboptimal local decisions. While "constructive induction" aims to address this by automatically creating new features, many existing methods are intertwined with the learning process, limiting their applicability, or rely on greedy strategies that perform poorly on real-world data. This paper tackles the challenge of creating a general-purpose, data-driven constructive induction method that acts as a preprocessing step, enhancing the performance of various learners without requiring them to be modified.
Methods
GALA employs a "generate-and-test" approach as a preprocessing step. Its core novelty lies in its feature generation and filtering mechanisms:
- Booleanize: It transforms real and nominal attributes into boolean ones by selecting a single value from their range. For continuous attributes, it creates
f > vandf <= vboolean attributes, while for nominal/boolean attributes, it usesf = vandf != v. - Generate: It iteratively generates new boolean attributes by conjoining existing ones using "and" and "not" operators.
- GainFilter: This is the crucial filtering step. It uses a combined metric:
- Absolute Measure: Gain Ratio (GR) of the new attribute.
- Relative Measures: Upper-RGR and Lower-RGR, which quantify the synergy of a new attribute (a conjunction of two parent attributes) over its parents. These measures are only considered if the new attribute has a better GR than its parents. GALA keeps attributes that have both a good absolute gain ratio and a good relative gain ratio, aiming to find features that offer significant improvement beyond their individual components.
Datasets
The paper evaluates GALA on:
- Artificial Domains: Four boolean functions (f1-f4) were used, similar to those in previous work (Ragavan & Rendell, 1993). These functions varied in difficulty and had irrelevant attributes.
- Real-World Domains: Several datasets from the UCI repository were used, including: Cleveland heart disease, Bupa liver disorder, Credit screening, Pima Diabetes, Wisconsin Breast Cancer, Wine, and Promoters. These datasets featured a mix of nominal and continuous attributes.
Key Insights and Ideas
- Preprocessing Power: GALA's success as a standalone preprocessing step highlights the importance of representation engineering before applying learning algorithms.
- Synergy is Key: The combination of absolute (Gain Ratio) and relative (Upper/Lower-RGR) measures is critical. Simply looking at absolute gain can lead to selecting attributes with minor improvements, while relative measures help identify truly synergistic combinations.
- Data-Driven Advantage: GALA's data-driven nature makes it adaptable to various learning algorithms, unlike hypothesis-driven methods that depend on prior knowledge.
- Crisp Feature Focus: GALA primarily generates crisp boolean features, which are particularly beneficial for algorithms like perceptrons and backpropagation that might struggle with complex, non-crisp representations.
Key Results
- Artificial Domains: GALA consistently improved the accuracy of C4.5, CN2, perceptron, and backpropagation, often significantly, compared to using the learners alone. It also reduced the complexity of the learned concepts.
- Real-World Domains: Similar improvements were observed on real-world datasets. GALA significantly increased accuracy in 21 out of 27 cases across different learners. It consistently improved perceptron and backpropagation and often improved CN2 and C4.5.
- Efficiency: GALA typically generated only one new attribute on average per domain, yet this attribute was often useful and selected by the learning algorithm.
- Ablation Studies: Removing the relative gain ratio measure (using only absolute gain) led to a significant decrease in accuracy, underscoring the importance of the relative measures. Similarly, removing the GainFilter entirely increased the search space dramatically without a corresponding accuracy gain.
Limitations and Future Work
- No Pruning: The current version of GALA lacks a pruning mechanism, meaning some generated attributes might be too complex and not improve accuracy. The authors suggest studying pruning techniques for future work.
- Limited Operators: GALA currently only uses "and" and "not" boolean operators. Extending these operators to include relational operations or other forms could enhance performance and applicability.
- Non-Crisp Attributes: GALA is limited to generating crisp boolean features. The authors intend to extend GALA to find non-crisp attributes in future research.
Summary updated