3
$\begingroup$

I'm trying some different techniques to optimise a Boosted Gradient Regressor by using an evolutionary programming technique to try and find the most efficient set of features. So far I've been having some good results (Been able to remove 65% of the features with an increase in accuracy), but I'm not impressed with how expensive each epoch is to run (in terms of time). Currently, this is a very expensive problem to optimise, 2^79 as there are a maximum of 79 features to choose from, which is 6.0446291e+23 possible feature permutations.

So far, each individual in my population has a binary encoded gene, where 1 = use this feature, and 0 = do not use this feature. Each individual in a population is evaluated by running the boosted regressor with the selected features, and then the RMSLE is calculated. I start to see good results around 3 hours into the optimisation function (I'm not doing any parallel computing).

I've been doing a little bit of research into how I can attempt to "predict" how good my boosted regressor will be without actually needing to evaluate its performance. So far I've found the following techniques:

  1. Problem Approximation. I can see how this would be useful in some specific cases, but as I'm not really able to reduce the complexity of evaluating how accurate my boosted regressor is it seems irrelevant.
  2. Functional Approximation. I think this is quite an interesting technique. They whole premise is to approximate the fitness of an individual without actually needing to evaluate the function
  3. Fitness Inheritance. This also seems rather interesting, and perhaps the most efficient of the methods listed above? Individuals are clustered into specific groups, and then the "represented" individual of each cluster has its fitness evaluated, and then the remaining individual's fitness are approximated by upon a distance measurement.

I could see some issues with these techniques though. If the combination of features used don't have a linear relationship with the output, then surely the function approximation would have a hard time approximating the potential fitness of an individual? I'm a bit stumped on what to further look at.

Improve this question
$\endgroup$
13
  • 1
    $\begingroup$ Gradient boosting algorithms like LightGBM and XGBoost calculate importance of the variables used. This could be used as an approximation of how good a regressor is, but it is not precise. You can also try recursive feature elimination, where you eliminate one feature based on importance or based on models without the variable, and repeat this procedure recursively till you have no variables left. $\endgroup$ – keiv.fly Aug 13 '18 at 15:19
  • $\begingroup$ Yeah maybe I should give a bit more of a background. I know I could use tree-based algorithms to calculate feature importance, or maybe some correlation algorithms or PCA. I'm specifically just looking at evolutionary algorithms at the moment. Thanks though. $\endgroup$ – Johnathan Brown Aug 14 '18 at 8:22
  • $\begingroup$ What did you mean by boosted gradient regressor? A tree-based algorithms or some other algorithm? $\endgroup$ – keiv.fly Aug 14 '18 at 13:34
  • $\begingroup$ To be honest, I don't quite think the algorithm being used to evaluate the set of features is that relevant, as the error I get back can be minimised. Rather, I'm wondering how I could measure the fitness of an individual without needing to train a machine learning algorithm to evaluate the set of features. Though, to answer your question a boosted gradient regressor is part of the "Boosting" family of machine learning algorithms where an ensemble of decision trees are used. $\endgroup$ – Johnathan Brown Aug 14 '18 at 13:43
  • 1
    $\begingroup$ You can try evaluating fitness on a sample. This is similar to stochastic gradient descent in neural networks. Random sampling allows it to be close to the original data with almost the same fitness, but the calculation time is significantly smaller. In neural networks sampling actually increases generalization ability of the forecast. $\endgroup$ – keiv.fly Aug 14 '18 at 22:02
1
$\begingroup$

According to the two papers (Limited Evaluation Evolutionary Algorithm (LEEA) and Limited Evaluation Cooperative Co-evolutionary Differential Evolution Algorithm (LECCDE)) you can approximate the result of the evolutionary algorithms by applying the algorithm not on the whole dataset but on mini-batches like in SGD (Stochastic Gradient Descent). This significantly reduces computation time (about 25 times in LECCDE paper for an ANN on MNIST dataset).

According to Prellberg 2018 Limited Evaluation Evolutionary Optimization the training times of LE algorithms is still 10 times longer than the Adam variation of stochastic gradient descent. In your case it is not possible to calculate gradients.

The following changes to the evolutionary algorithm are proposed in the first paper (LEEA):

  1. Use mini-batching while ensuring the diversity of the expected outputs.

Ideal mini-batch size in LEEA was determined experimentally to be 2. ...To apply the idea of diversity in minibatches, the output range is divided into two equally sized sections, and examples selected so that each mini-batch contains one example for both sections of the range. A new mini-batch is randomly generated at the beginning of each generation.

  1. Use ancestor fitness for evaluation.

f'=(f_p1 + f_p2)/2*(1-d) + f.

Where f' is the individual's modified fitness. f is the fitness of the individual against the current mini-batch. f_pn is the fitness of parent n. d is a constant decay value.

The second paper (LECCDE) points to the following speed-up using Limited Evaluation algorithms:

LECCDE vs CCDE for different datasets:

Dataset    Parameters   Speedup             Accuracy
WBC        1652          1.10 times faster  1.2% worse
ESR        9052          2.05 times faster  0.3% worse
HAR        28406         4.00 times faster  0.2% worse
MNIST      47710        25.3  times faster  unknown
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.