The Surprisingly Effective Genetic Approach to Feature Selection

Original article was published by Andre Ye on Artificial Intelligence on Medium

In genetic algorithms, a population of candidate solutions, also known as individuals, creatures, or phenotypes, are evolved towards better solutions in an optimization problem. Each candidate has a set of properties that can be mutated and altered.

These properties can be represented as a binary string (a sequences of zeroes and ones), but there exist other encodings. In the case of feature selection, each individual represents one selection of features, and each ‘property’ represents one feature, which can be turned on or off (1 or 0).

The evolution of individuals begins with a random generated population, meaning each’s properties are randomly initialized. Evolution is an iterative process, and the population in each iteration is referred to as a generation. In a genetic feature selection in a dataset with 900 columns, an initial population may consist of 300 individuals, or randomly generated combinations of on/off switches.

In each generation, the fitness, which is the function of the problem being solved, of each individual is evaluated.

One direct fitness function would be to simply evaluate the accuracy of a model when trained on that subset of data, or another of many possible model metrics. This can be a bit costly, though, so it should only be used with small datasets or populations.

An alternative is use a variety of cheaper-to-access metrics that can assist in evaluating the fitness of each solution. Some include:

  • Collinearity. Make sure that features in a subset do not contain similar information by evaluating the overall correlation of each subset.
  • Entropy / separability. With the current dataset, how well separated are the classes? The more separable the data, the better it is.
  • Hybrid. Combine these metrics with others like variance or how normally distributed the data is to yield a combination that satisfies the needs of the model.

With some controllable randomness injected to stimulate proper evolutionary discovery, individuals on the fitter side (scoring a better on the fitness function) are randomly selected. Randomness is added and ranking is not based on pure highest score because that would allow for little exploration and is not how evolution is conducted in the real biological world.