Genetic algorithms for feature selection

By Fernando Gomez, Alberto Quesada, and Roberto Lopez, Artelnics.

Many typical machine learning applications, from customer targeting to medical diagnosis, arise from complex relationships between features (also-called input variables or characteristics).

Feature selection, or input selection, is the process of finding the most relevant inputs for a model.

Feature selection techniques help identify and remove unneeded, irrelevant, and redundant features. Indeed, that variables do not contribute to or decrease the accuracy of the predictive model.

Contents:

  1. Feature selection.
  2. Genetic algorithms.
  3. Initialization operator.
  4. Fitness assignment operator.
  5. Selection operator.
  6. Crossover operator.
  7. Mutation operator.
  8. Process and results.
  9. Conclusions.

Feature selection

Mathematically, inputs selection is formulated as a combinatorial optimization problem.

The objective function is the predictive model's generalization performance. This is represented by the error term on the selection instances of a data set.

The design variables are the inclusion (1) or the exclusion (0) of the input variables in the neural network.

An exhaustive selection of features would evaluate 2N different combinations, where N is the number of features.

This process requires lots of computational work and, if the number of features is significant, it becomes impracticable. Therefore, we need intelligent methods that allow the selection of features in practice.

Genetic algorithms

One of the most advanced algorithms for feature selection is the genetic algorithm.

The genetic algorithm is a stochastic method for function optimization based on the mechanics of natural genetics and biological evolution.

In nature, organisms' genes tend to evolve over successive generations to better adapt to the environment. The genetic algorithm is a heuristic optimization method inspired by the procedures of natural evolution.

Genetic algorithms operate on a population of individuals to produce better and better approximations.

The algorithm creates a new population every generation by selecting individuals according to their fitness level in the problem domain. These individuals are then recombined together using operators borrowed from natural genetics. The offspring might also undergo mutation.

The following figure depicts a state diagram for the feature selection process with the genetic algorithm.

Genetic algorithm state diagram

This process leads to the evolution of populations better suited to their environment than the individuals who originated it.

In our case, each individual in the population represents a neural network.

Genes here are binary values, and represent the inclusion or not of particular features in the model. The number of genes is the total number of input variables in the data set.

The number of individuals, or population size, must be chosen for each application. Usually, this is set to be 10 N, being N the number of features.

Next, we describe in detail the operators and the corresponding parameters used by the genetic algorithm.

1. Initialization operator

The first step is to create and initialize the individuals in the population. Since the genetic algorithm is a stochastic optimization method, we usually initialize the individuals' genes randomly.

To illustrate this operator, consider a predictive model represented by a neural network with six possible features. If we generate a population of four individuals, we have four different neural networks with random features.

The next figure illustrates this population.

Genetic algorithm population

As we can see, each individual is represented by 6 binary genes. Each positive gen means that the corresponding feature is included in the neural network.

2. Fitness assignment operator

After the initialization, we need to assign a fitness value to each individual in the population.

We train each neural network with the training instances and then evaluate their error with the selection instances.

A significant selection error means low fitness. Those individuals with greater fitness have a higher probability of being selected for recombination.

The most used method for fitness assignment is known as a rank-based fitness assignment.

With this method, the selection errors of all the individuals are sorted.

A fitness value is assigned to each individual, which only depends on the population's rank position and not on the actual selection error.

The fitness value assigned to each individual with the rank-based method is:

$$\Phi(i) = k \cdot R(i) \qquad where \quad i = 1,...,N.$$

Here κ is a constant called selective pressure, and its value is fixed between 1 and 2. Higher selective pressure values make the fittest individuals have more probability of recombination. The parameter R(i) is the rank of individual i.

The following table depicts the selection error, the rank, and the corresponding fitness of each individual in our example.

Selection error Rank Fitness
Individual 1 0.9 1 1.5
Individual 2 0.6 3 4.5
Individual 3 0.7 2 3.0
Individual 4 0.5 4 6.0

Where we have chosen κ=1.5 to calculate the fitness value. Note that, for calculating the population fitness, we have trained 4 different neural networks .

We can plot the above fitness values in a pie chart. Here the area for each individual in the pie is proportional to its fitness. The following picture shows the fitness pie.

Genetic algorithm fitness pie chart

As we can see, the fittest individual (#4) has the biggest area (40%), and the least fitted individual (#1) has the smallest area (10%).

3. Selection operator

After a fitness assignment has been performed, the selection operator chooses the individuals that recombine for the next generation.

The individuals most likely to survive are those more fitted to the environment. Therefore, the selection operator selects the individuals according to their fitness level. The number of selected individuals is N/2, being N the population size.

Elitism selection makes the fittest individuals survive directly for the next generation. The elitism size controls the number of directly selected individuals, and it is usually set to a small value (1,2,...).

One of the most used selection methods is the roulette wheel. This method places all the individuals on a roulette, with areas proportional to their fitness, as we saw above. Then, the roulette is turned, and the individuals are selected at random. The corresponding individual is selected for recombination.

The following figure illustrates the selection process for our example.

Genetic algorithm selection

In this case, neural network #4 has been selected by elitism, and #3 has been selected by the roulette wheel. Note that, although individual #2 has more fitness than #3, it has not been selected due to the stochastic nature of the genetic algorithm.

Here the number of selected individuals is half of the population size.

4. Crossover operator

Once the selection operator has chosen half of the population, the crossover operator recombines the selected individuals to generate a new population.

This operator first picks two selected individuals at random. It then combines their features to get four offspring for the new population. Crossover stops when the new population has the same size as the old one.

The uniform crossover method decides whether each of the offspring's features comes from one parent or another.

The following figure illustrates the uniform crossover method for our example.

Genetic algorithm crossover

Here we have generated four offspring from two parents. Some features of each neural network correspond to one ancestor, and some other features to the other.

Here the population size remains constant.

5. Mutation operator

The crossover operator can generate offsprings that are very similar to the parents. This might cause a new generation with low diversity.

The mutation operator solves this problem by changing the value of some features in the offspring at random.

To decide if a feature is mutated, we generate a random number between 0 and 1. If this number is lower than a value called the mutation rate, that variable is flipped.

A standard value for the mutation rate is 1/m, where m is the number of features. With that value, we mutate one feature of each individual (statistically).

The following image shows the mutation of one offspring of the new generation.

Genetic algorithm mutation

As we can see, the fourth input of the neural network has been mutated.

At this point, we have a new population.

Process and results

The whole fitness assignment, selection, recombination, and mutation process is repeated until a stopping criterion is satisfied. Each generation is likely to be more adapted to the environment than the old one.

The following figure shows the typical behavior of the successive generations. The blue line represents the mean selection error of the individuals. The red line represents the selection error of the best individual.

Genetic algorithm typical behavior

As we can see, the mean selection error at each generation converges to a minimum value.

The solution to this process is the best individual ever. This corresponds to the neural network with the smallest selection error among all those we have trained.

In our example, the best individual is the following:

Genetic algorithm best individual

The above neural network is the selected one for our application.

Conclusions

Input selection is becoming a critical topic in machine learning. Many data sets contain a large number of features, so we need to select the most useful ones to be included in the neural network.

One of the most advanced methods to do that is the genetic algorithm.

Some advantages of genetic algorithms are the following:

And some disadvantages are:

In conclusion, genetic algorithms can select the best subset of our model's variables, but they usually require much computation.

Neural Designer implements a more advanced genetic algorithm that the one described in this post. You can find it at the input selection section in the model selection panel.

Neural Designer has a powerful genetic algorithm model selection

Related posts: