Questions about GP and On-Line Learning

[aklandi]

Hello,

I recently discovered GP and find it fascinating. To explicitly learn the mathematical expression is quite different than the implicit learning neural networks do! I'm interested in how GP works with on-line learning, and I imagine since there is an evolutionary process on-line learning feel natural. But, I'm not sure I've quite grasped all the details, and it makes me question whether my intuition is right. So, I think if one feeds one data point at a time, the algorithm should update the mathematical expression, and perhaps a few data points at a time might yield better results. I think the max_samples parameter for gplearn allows me to specify what percentage of data points to look at at once, but do all data points have to be available? what if all data points are not available? What would the loop below do?

   while data keeps coming:
       est_gp.fit(data[0], data[1])

Each time est_gp.fit is run, the method goes through N possible functions and modifies functions if needed. However, if it does this for one data point, when a new one is introduced, will it take the winning model from the previous data point and throw it into the new population?

Thank you for entertaining my thoughts! I did not know where else to discuss them.

[trevorstephens]

Hi @aklandi this is the right place :smile: I'm glad you find it fascinating, me too, that's really why I built this package in the first place.

I don't know how online learning would work with GP to be honest. The fitness is measured over all data points and essentially averaged to find a hyper-plane much like SVM but with an equation behind the shape of that plane. If adding new data, the "population" would have some memory of what was good with the bulk lot of data that you used to start the training, but I suspect that the new data would quickly overrule that population with new programs that fit only the new data the best.

This package is built largely to wrap GP such that it behaves much like a regular machine learning algorithm. Online learning has not been implemented and so I suspect that the solutions you get by using something like warm start on small new data "blocks" would not generalise well to full datasets.

[aklandi]

Interesting. I think it makes sense that the fittest program from the previous training cycle would beat the new random program(s) in a tournament, but could evolution change what happens in following generations? (I'm still trying to fully understand what's going on).

When I run the gp_est.fit on a sliding window of data points, like

for i in range(length of data - window length):
    gp_est.fit(x[i:(i+window length]), y[i:(i+window length])

I got a program yielding predictions significantly better than when I did whole data. It was also significantly slower, and how "fit" a selected program was during a particular window varied, but the fitness was often lower than whole data fitness. At least for the data I am using to experiment. I'd love to hear your thoughts.

[trevorstephens]

No doubt it will be slower! With this snippet, you are not doing online learning, you are in fact deleting your previous model and then refitting the entire estimator on a different small piece of data from scratch with every loop.

The closest you might get to online learning would be to train each step in evolution on a new chunk using the warm start functionality: https://gplearn.readthedocs.io/en/stable/advanced.html#continuing-evolution

I have no idea how that will perform though! Not really what it was designed for...

[aklandi]

Dang. Okay. The warm_start doesn't perform poorly, but I'm not sure this is the way to go. I may have to go back to the drawing board when it comes to code to perform on-line learning and genetic programming. But I wonder what you're thoughts are about my ideas?

• one data point (or one window of 2-3 data points): find the fittest program for these data points
• when another data point is received: the winning program from above will continue, but will be included in a new population of programs; the new data will be included to determine the next fittest program
• continue until N data points are received

A google search for "genetic programming on-line learning" doesn't yield anything along the lines of what I'm looking for. Perhaps there is a reason they aren't combined.

[remiadon]

Hi there,

I recently tried to implement an online version of GP, and here was my approach:

1. initialize a set of population_size random expressions, just like in the batch version of gplearn
2. initialize a set of online metrics (eg. online version of Mean Absolute Error)
3. when a new (x, y) pair comes in
   • evaluate all expressions by replacing symbols by their corresponding values in x
   • update the online metric corresponding to each expression given y
   • [optional] give more weight to recent points when updating the metric
   • every n iterations (default to 100): 1) select the top 50% performing expressions 2) apply random mutation on them 3) use this newly mutated expressions to replace the 50% poorly performing expressions
   • set the current expression to the top performing expression

Careful though, I searched on the web and there is nothing about such algorithm. This is only my "crafty" version of it. I don't pretend it to be efficient, and I have no proof of its validity. It's only an experiment.