Character regression

When solving problems using machine learning methods, as a rule, we choose the most suitable algorithm in the context of the problem, as well as the method of setting its parameters.

Let's consider a slightly different approach: instead of choosing the algorithm by ourselves, we will develop a program that can automatically generate algorithms for solving problems.


A stochastic program design method based on the use of a genetic algorithm is called genetic programming.
')

A few words about the genetic algorithm

A genetic algorithm is an optimization method based on the idea of ​​natural selection as a means of achieving the best result. The generalized formulation provides the ability to use this algorithm for solving various problems. All you need is:

1. how to solve the problem can be encoded in the form of chromosomes, which have the ability to mutate and interbreed
2. determine the fitness function, which calculates how optimal is the solution encoded by a particular chromosome
3. Having an initial chromosome population and fitness function, using a genetic algorithm, you can find chromosomes that correspond to optimal solutions of the problem

Of course, the genetic algorithm has certain disadvantages associated with its stochastic nature, but based on my own experience , I can conclude that it finds acceptable solutions in the context of resource-time constraints.

Genetic programming and symbolic regression

I propose to consider in more detail the concept of genetic programming on the example of symbolic regression - the task of finding a formula that describes a certain relationship. More formally, it can be formulated as the construction of a regression model in the form of a superposition of given functions .

A fairly convenient way to present a program is a syntax tree. In this case, the role of "programs" is played by algebraic formulas. Leaf nodes correspond to variable or numeric constants, and non-leaf nodes contain an operation that is performed on the child nodes.

Example syntax tree:


It should be noted that for each syntactic tree there are an infinite number of semantically equivalent trees, for example:


We will use syntactic trees as chromosomes.

Genetic operations on syntactic trees

Crossing can be done by exchanging randomly selected subtrees:


Mutations can come up with many different options, but ultimately, in its implementation, I settled on the following:

1. Replacing a function with a randomly selected other:
   
   
   
2. Replacing a subtree with a randomly generated subtree:
   
   
   
3. Deleting a non-leaf intermediate node:
   
   
   
4. Create a random node that is assigned to the new root of the tree:
   
   
   
5. For nodes with noncommutative operations, swapping child subtrees in places:
   
   

The syntax tree's fitness function calculates how well the corresponding algebraic formula approximates the data, and, in fact, is the sum of the squares of the deviations of the values ​​of the generated function from the training data.

The initial population is a collection of randomly generated syntax trees.

Optimization

In general, the described operations of crossing and mutation should be sufficient to find a solution. But, based on my experience, I can say that in this case - a more or less acceptable solution will be long enough. Therefore, I will describe several optimizations that speed up the search for solutions.

1. Let's consider two formulas created in the process of finding solutions (the red crosses are training data):
   
   It is easy to see that the blue straight line is in general quite close to the training data, unlike the green parabola - which means it has a smaller sum of squares of deviations relative to the training sample.
   
   But, on the other hand, the naked eye can see that the parabola is just what we need.
   
   It's all about the coefficients. As you may have guessed, the coefficients of each tree are optimized. And to optimize the coefficients, of course, a genetic algorithm is used!
   
   In this case, the chromosome is an array of numbers:
   
   
   
2. Since we work only with real numbers, it is convenient to operate with functions in which the domain of values ​​is a subset of the domain, for example:
   
   +, -, sin (x), cos (x), ln (abs (x) +0.00001), sqrt (abs (x)), etc.
   
   Thus, as a result of performing genetic modifications, we will be guaranteed to receive syntax trees that do not contain errors.
   
   
3. There are combinations in which a subtree contains leaf nodes with only numeric constants. You can calculate its value and simplify the syntax tree:
   
   
   
4. Another optimization is to limit the maximum depth of the tree (of course, this imposes its own limitations on the search space for solutions, but the need for this optimization is dictated by practical considerations):
   
   
   
5. To avoid a situation where all the trees in a population are similar to each other (the genetic algorithm is stuck in a local minimum), there is a non-zero probability of completely replacing one of the trees with a randomly generated one.
   

Enough theory, let's see how it works in practice.

Let's try to find a formula that will satisfy the following pattern:

x	y	z	f (x, y, z)
26	35	one	830
eight	24	-eleven	130
20	one	ten	477
33	eleven	2	1217
37	sixteen	7	1524

At 111 iterations we get the formula:



Which after transformations turns into a formula that almost coincides with the required one:



Below is the dynamics of the solution formation





It is interesting to follow the stages of solution formation:

• At first, the dependence on the variable x is found (this stage is not shown in the figure, since the error value is still very large - approximately 130,000)
  
• then the formula is transformed into a quadratic dependence on x (the sum of squared deviations is ~ 3000)
  
• then the dependence on the variable y is identified (the sum of squared deviations is ~ 500)
  
• and finally, after optimizing the numerical parameters and identifying the dependence on the variable z , an optimal result is achieved.
  

One more example

Sometimes formulas are obtained that are not so obvious. For example, once, when trying to get the formula I got the following result:



But if you take advantage of the identity:



It can be shown that the resulting formula is correct:

If you want to experiment

Console utility

1. You must have Java runtime installed
   
2. Download the file symbolic_regression_1.0.jar from here.
   
3. In the same directory where symbolic_regression_1.0.jar is located, create a file (for example, data.txt ) with the following content:
   

   # allowed functions are: ADD SUB MUL DIV SQRT POW LN SIN COS
   # set which functions to use:
   ADD MUL SUB
   
   # looking for:
   f (x, y, z) -?
   
   # define training set:
   f (26, 35, 1) = 830
   f (8, 24, -11) = 130
   f (20, 1, 10) = 477
   f (33, 11, 2) = 1217
   f (37, 16, 7) = 1524
   

   
   
4. Run a search for a solution:
   
   java -jar symbolic_regression_1.0.jar data.txt
   
   The solution is considered to be found if the sum of squared deviations is less than 10. If the solution is not yet found, then after every 50 iterations you will be asked if you want to continue.
   

Java programmers

You can find the source code here: github.com/lagodiuk/genetic-programming

Instead of conclusion

On a rather limited number of formulas, which I managed to check, good results were obtained, there were also successful experiments in finding antiderivatives and derivatives.

Also, genetic programming can be quite successfully applied to the automatic construction of neural networks ( here is a small demo of the application in which I implemented this approach ).

Another idea is to apply a similar approach (together with QSAR techniques) to automatically construct the structures of chemical compounds with desired properties.

Literature

On the web you can find a lot of material on the subject of genetic programming.
Separately, I want to note the following sources:

1. Toby Segaran, Programming Collective Intelligence
2. Site creator of the concept of genetic programming