Generating Redundant Features with Unsupervised Multi-Tree Genetic Programming

Andrew Lensen, Bing Xue, Mengjie Zhang

Abstract

Feature selection (FS) is a critical component of modern machine learning, particularly as high-dimensional datasets become more prevalent. However, evaluating the efficacy of FS algorithms is challenging due to the difficulty of obtaining datasets with known, complex redundant features. While synthetic noise is easily generated, creating complex, non-linear redundancy that mimics real-world data remains a significant hurdle. This paper introduces GPRFC (Genetic Programming for Redundant Feature Creation), an unsupervised multi-tree genetic programming approach designed to evolve difficult redundant features. Initial experiments demonstrate that GPRFC can successfully generate complex features that significantly degrade the performance of standard feature selection algorithms, providing a robust tool for benchmarking.

Introduction

In the field of machine learning, Feature Selection (FS) aims to identify and remove "bad" features—those that are either irrelevant (noise) or redundant (providing information already captured by other variables). To rigorously test FS algorithms, researchers typically augment existing datasets with synthetic bad features to see if the algorithm can correctly identify and exclude them.

While adding irrelevant noise is straightforward, generating meaningful redundancy is surprisingly difficult. Most current benchmarking techniques rely on simple linear transformations, such as multiplying a feature by a constant. Such simple redundancies are easily detected by modern FS algorithms, leading to an overestimation of their performance. Real-world data often contains complex, non-linear relationships (e.g., the relationship between age and income) that are much harder to untangle. This work addresses this gap by proposing a method to automatically evolve "hard" redundant features.

The GPRFC Method

The authors propose GPRFC, which utilizes Multi-Tree Genetic Programming (GP) to create these complex features. Unlike standard GP, which typically evolves a single solution tree, each individual in GPRFC consists of $n$ distinct trees. Each tree takes a "source" feature from the original dataset as input and transforms it into a new, redundant feature.

The "Push-Pull" Fitness Function

The core innovation of GPRFC is its unsupervised fitness function, which relies on Mutual Information (MI)—a statistical measure of the shared information between two variables. The fitness function operates on a "push-pull" principle:

  1. Maximize Redundancy (The "Pull"): The system encourages each evolved feature to have high MI with the original source feature, ensuring it captures the underlying signal.
  2. Maximize Diversity (The "Push"): Simultaneously, the system penalizes features that are too similar to one another. This prevents the GP from simply evolving $n$ identical copies of the same transformation.

Because this process relies solely on the relationships between features and does not require class labels, it is a purely unsupervised learning approach. The GP uses a function set including arithmetic operators ($+$, $\times$), trigonometric functions ($\sin$, $\tan$), and conditional logic (if-then-else) to construct these transformations.

Experimental Evaluation

The method was evaluated using five distinct datasets to test its versatility across different machine learning tasks:

  • Classification: Iris (4 features), Wine (13 features), and Vehicle (18 features) from the UCI repository.
  • Clustering: Two synthetic datasets (10d10cE and 10d40cE) generated using an ellipsoidal cluster generator.

Key Insights and Results

Emergent Complexity

One of the most striking findings was the system's ability to evolve complex statistical behaviors from simple primitives. For example, when applied to the Iris dataset, the GP evolved a feature that closely resembled a sigmoid curve, despite the sigmoid function not being included in the original function set. This suggests that GPRFC can synthesize the kind of non-linear complexities found in natural data.

The "Temptation" of Redundancy

High-quality redundant features are particularly dangerous for FS algorithms because they often exhibit high Information Gain. An algorithm might be "tempted" to select a redundant feature over the original because it appears statistically superior, even though it adds no new information and increases the model's complexity.

Impact on Feature Selection Performance

To test the difficulty of the generated features, the authors applied a standard feature selection algorithm, Sequential Forward Floating Selection (SFFS), to the augmented "Vehicle" dataset.

  • On the original dataset, SFFS achieved 71% accuracy.
  • On the augmented dataset (containing GPRFC-generated features), the algorithm's accuracy plummeted to 47.3%.

This drastic drop indicates that the evolved features successfully "tricked" the SFFS algorithm into selecting a suboptimal subset of features, proving that GPRFC can create the "hard" redundancy required for rigorous benchmarking.

Limitations and Future Work

While GPRFC represents a significant step forward, the authors identify several areas for improvement:

  • Multivariate Redundancy: Currently, GPRFC creates redundancy from a single source feature. Future iterations could explore redundancy that exists between groups of features.
  • Computational Complexity: Calculating Mutual Information for continuous variables is computationally intensive, which may limit the scalability of the approach as population sizes grow.
  • Function Set Refinement: The current model excludes random constants to simplify the search space; including them might produce even more varied and "natural" looking features.

Conclusion

GPRFC provides a novel and effective method for generating complex, non-linear redundant features. By moving beyond simple linear transformations, this approach allows researchers to create more challenging and realistic benchmark datasets, ultimately leading to the development of more robust feature selection algorithms.

Summary updated

Abstract

Recently, feature selection has become an increasingly important area of research due to the surge in high-dimensional datasets in all areas of modern life. A plethora of feature selection algorithms have been proposed, but it is difficult to truly analyse the quality of a given algorithm. Ideally, an algorithm would be evaluated by measuring how well it removes known bad features. Acquiring datasets with such features is inherently difficult, and so a common technique is to add synthetic bad features to an existing dataset. While adding noisy features is an easy task, it is very difficult to automatically add complex, redundant features. This work proposes one of the first approaches to generating redundant features, using a novel genetic programming approach. Initial experiments show that our proposed method can automatically create difficult, redundant features which have the potential to be used for creating high-quality feature selection benchmark datasets.
BibTeX
@inproceedings{lensen2018generating,
  author = {Andrew Lensen and Bing Xue and Mengjie Zhang},
  title = {{Generating Redundant Features with Unsupervised Multi-Tree Genetic Programming}},
  booktitle = {EuroGP},
  year = {2018},
  url = {https://openreview.net/forum?id=2qPHHg4jvM},
}
Figure