Fast Genetic Algorithm for feature selection -- A qualitative approximation approach

Overview

• Evolutionary Algorithms (EAs) are often computationally expensive due to the need to evaluate a large number of fitness functions
• This paper proposes a two-stage surrogate-assisted evolutionary approach to address the high computational cost of using Genetic Algorithms (GAs) for feature selection
• The approach involves defining "Approximation Usefulness" to ensure the correctness of EA computations when using an approximation, and constructing a lightweight qualitative meta-model through active selection of data instances
• The paper applies this approach to the GA-based CHC algorithm, creating CHCQX, which is shown to converge faster and find more accurate feature subset solutions, especially for large datasets
• The thinking behind this approach is also demonstrated to be applicable to Swarm Intelligence (SI) algorithms, with results shown for a qualitative approximation adaptation of Particle Swarm Optimization (PSO)

Plain English Explanation

Evolutionary Algorithms (EAs) are a powerful set of techniques inspired by the process of natural selection. They're used to optimize complex problems by iteratively "evolving" potential solutions, much like how species evolve in the natural world. However, EAs can be computationally expensive because they require evaluating the "fitness" of a large number of potential solutions, which can be a time-consuming process.

For example, imagine you're trying to train a new machine learning model as part of an EA. Each time you evaluate a potential solution, you'd need to train the model and measure its performance, which could take a long time, especially for large datasets.

To address this issue, the researchers in this paper propose using an "approximation" or "surrogate" model to estimate the fitness of potential solutions, rather than having to do the full, expensive evaluation. They define a concept called "Approximation Usefulness" to help ensure that this approximation doesn't introduce errors into the EA process.

The key idea is to construct a lightweight, qualitative meta-model by actively selecting a subset of the data instances to use. This meta-model can then be used to guide the EA's search for optimal solutions, rather than having to do the full, expensive evaluations.

The researchers apply this approach to a Genetic Algorithm called CHC, creating a new version called CHCQX. They show that CHCQX is able to converge to high-quality solutions much faster than the original CHC, especially for large datasets with over 100,000 instances.

The researchers also demonstrate that the thinking behind this approach can be applied to other types of Evolutionary Computation algorithms, like Swarm Intelligence methods. They show results for a qualitative approximation adaptation of Particle Swarm Optimization (PSO), called PSOQX.

Overall, this research presents a promising approach for making Evolutionary Algorithms more computationally efficient, which could unlock their use in a wider range of real-world applications, such as materialized view optimization, target set selection, and quantization-aware neural network approximation.

Technical Explanation

The key technical elements of this paper are:

1. Approximation Usefulness: The researchers define a concept called "Approximation Usefulness" to capture the necessary conditions for ensuring the correctness of EA computations when using an approximation (or surrogate) of the true fitness function. This provides a framework for reasoning about the suitability of approximations in EAs.

2. Lightweight Qualitative Meta-model: The researchers propose a procedure to construct a lightweight, qualitative meta-model by actively selecting a subset of data instances. This meta-model is then used as an approximation of the true fitness function within the EA.

3. CHCQX Algorithm: The researchers apply their surrogate-assisted approach to the Genetic Algorithm called CHC, creating a new variant called CHCQX. CHCQX uses the qualitative meta-model to guide the search for optimal feature subset solutions, leading to faster convergence and higher accuracy, especially for large datasets.

4. PSOQX Algorithm: To demonstrate the broader applicability of their approach, the researchers also create a qualitative approximation adaptation of the Particle Swarm Optimization (PSO) algorithm, called PSOQX.

The key experimental results show that CHCQX is able to converge to feature subset solutions of significantly higher accuracy compared to the original CHC algorithm, particularly for large datasets with over 100,000 instances. The researchers also provide results demonstrating the effectiveness of PSOQX, the Swarm Intelligence adaptation of their approach.

Critical Analysis

The researchers have presented a compelling approach for addressing the computational challenges of using Evolutionary Algorithms in real-world settings. By leveraging lightweight, qualitative meta-models as approximations of the true fitness function, they are able to achieve significant speedups in convergence while maintaining high-quality solutions.

One potential limitation of the approach is the need to carefully define the "Approximation Usefulness" conditions to ensure the correctness of the EA computations. While the researchers provide a framework for this, the specific conditions may need to be tailored to the problem domain and the characteristics of the approximation being used.

Additionally, the performance of the meta-model construction process may be sensitive to the specific dataset and problem characteristics. The researchers have demonstrated the effectiveness of their approach on several datasets, but further research may be needed to understand its broader applicability and any potential limitations.

It would also be interesting to see how the proposed surrogate-assisted approach compares to other techniques for improving the efficiency of Evolutionary Algorithms, such as gradient-enhanced Gaussian process surrogates or machine learning-enhanced multi-objective optimization.

Overall, this research represents an important contribution to the field of Evolutionary Computation, providing a practical and effective approach for making these powerful optimization techniques more accessible and applicable to real-world problems.

Conclusion

This paper presents a two-stage surrogate-assisted evolutionary approach that addresses the computational challenges of using Genetic Algorithms (GAs) for feature selection in large datasets. By defining "Approximation Usefulness" and constructing a lightweight qualitative meta-model, the researchers are able to create a more efficient variant of the GA-based CHC algorithm, called CHCQX, that converges faster and finds more accurate feature subset solutions.

The key innovation of this work is the use of a qualitative meta-model as an approximation of the true fitness function, which allows the EA to explore the search space more efficiently. The researchers also demonstrate the broader applicability of this thinking by adapting it to a Swarm Intelligence algorithm, Particle Swarm Optimization (PSO), creating PSOQX.

This research has important implications for making Evolutionary Algorithms more practical and usable in real-world settings, where computational efficiency is a critical concern. By addressing these challenges, the proposed approach could unlock the use of EAs in a wider range of applications, such as materialized view optimization, target set selection, and quantization-aware neural network approximation. Overall, this work represents an important step forward in the field of Evolutionary Computation.