Symbolic-Regression Boosting

In machine learning, a weak learner is defined as a learner that can produce an hypothesis that performs only slightly better than random guessing, while a strong learner can with high probability output an hypothesis that is correct on all but an arbitrarily small fraction of the instances.

In his seminal paper, “The strength of weak learnability”, Schapire schapire1990strength described a method “for converting a weak learning algorithm into one that achieves arbitrarily high accuracy.” Over the years, a plethora of highly successful boosting algorithms that transform weak learners into strong ones have been devised Chen:2016 ; freund1997decision ; friedman2001greedy ; LightGBM2017 .

A recent rigorous benchmarking study of four symbolic regression algorithms versus nine machine learning approaches found that “symbolic regression performs strongly compared to state-of-the-art gradient boosting algorithms” (they also found that “in terms of running times [symbolic regression] is among the slowest of the available methodologies”) orzechowski2018 . Herein we wish to combine boosting with symbolic regression, asking whether gradient boosting might improve a strong(er) learner in the form of a symbolic regressor. We answer in the affirmative, demonstrating that improved results can be readily obtained, at relatively little added cost.

In the next section we describe our method and discuss related work. Section 3 presents the experimental setup and our results, followed by concluding remarks in Section 4.

For our experiments we used the popular scikit-learn Python package scikit-learn ; sklearn-website due to its superb ability to handle much of the tedious desiderata of machine learning coding and experimentation. We then chose the GPLearn package stephens2019gplearn , which implements tree-based genetic programming (GP) symbolic regression, is relatively fast, and—importantly—interfaces seamlessly with scikit-learn.

The main idea behind SyRBo is simple: we replace the boosted weak learner of gradient boosting (typically a decision tree) with a (possibly) strong learner, specifically, a GP-based symbolic regressor.

Algorithm 1 provides the pseudocode (the code is available at https://github.com/moshesipper). SyRBo receives the number of boosting stages as a parameter (one might consider the actual number of stages to be one less, as the first stage performs the initial prediction). Fitting a model to data is done in a standard gradient-boosting manner, through successive stages, where each stage fits a learner to the pseudo-residuals of the previous stage; prediction is performed by summing up all learner predictions. The only change involves the learners themselves, which are not decision trees but rather symbolic regressors, evolved by calling the SymbolicRegressor function with the given population size and generation count (both set to 200). The function set used by SymbolicRegressor is given in Table 1. To facilitate the symbolic regressor’s handling of diverse features scales, the dataset rows undergo L2 normalization (i.e., the feature values in a row have a unit L2 norm).

We note that our aim herein was to demonstrate SyRBo’s being an add-on that can be added to any symbolic regressor. As such, this paper is not about symbolic regression per se, but about performance benefits to be gained if one is using it. We thus contented ourselves with the standard function set of gplearn (adding only 2 conditionals), with all other parameters set to defaults (except for population size and generation count).

Regarding previous work, it would seem that by and large the emphasis in boosting techniques has been on weak learners, typically decision trees. Works using strong learners in the context of boosting employed mainly AdaBoost-like freund1997decision boosting. Modest success was attained by fink2004mutual ; Harries1999 . wickramaratna2001performance showed that boosting a strong learner with AdaBoost may, in fact, contribute to performance degradation. Within the domain of GP, AdaBoost-like boosting of dataset sample weights has been used with some success iba1999bagging ; karakativc2018building ; oliveira2006using ; paris2001applying . Perhaps closest to our work is that of Oliveira2015 , who presented an interesting iterative approach, Sequential Symbolic Regression, wherein each iteration applies a transformation based on a geometric semantic crossover operator. In contrast, our work is based on gradient boosting, is more generic in that it can work with any form of symbolic regression, and is also easier to code and apply to any extant project.

Can this (fairly) simple gradient boosting-like setup improve symbolic regression? We tested SyRBo on regression datasets from the PMLB repository orzechowski2018 , using our cluster of Intel^® Xeon^® E5-2650L servers. Of the 120 datasets we selected the 98 with 3000 instances or less. Figure 1 shows a “bird’s-eye view” of the datasets.

The pseudo-code for the experimental setup is given in Algorithm 2. For each dataset we performed 30 replicate runs, with 5-fold cross validation per replicate. SyRBo and SymbolicRegressor (with equal population size and generations) were trained on 4 folds and tested on the left-out test fold.

For each of the 98 datasets we recorded the mean absolute error attained per algorithm over each of the 30 replicate runs, per each of the 5 test folds (i.e., following training). We ran 4 separate experiments, over all 98 datasets, with number of stages equal to 2, 3, 4, and 5, respectively.

Table 2 shows a summary of our results (detailed results can be found in the Appendix). For each dataset we computed the median of the test scores of all 30 replicates, with 5 folds per replicate (a total of 150 test-score values). A win for SyRBo was then a better (lower) median value than SymbolicRegressor. To assess whether a win for a specific dataset was significant or not, we performed a 10,000-round permutation test, comparing the scores of SyRBo with SymbolicRegressor; if the p-value was $<0.05$ the win was considered significant, else it was not (in which case SyRBo was at least not performing worse than SymbolicRegressor). In addition, when SyRBo “lost” to SymbolicRegressor we performed a 10,000-round permutation test, comparing the two algorithms’ scores; if the p-value was $>=0.05$ the loss was considered insignificant.

As seen in the table, statistically significant improvements can often be attained, and, moreover, rarely does SyRBo result in statistically significant worse results. Using SyRBo is thus a good bet, and, furthermore, it is easily coded and the added computational cost is not high.

We presented SyRBo, a gradient boosting-style algorithm, wherein the decision tree is replaced by a symbolic regressor. Testing the merits of our new method we showed that symbolic regression results can be consistently improved. Moreover, as can be seen in Algorithm 1, coding SyRBo on top of any symbolic regressor is straightforward, and the added cost is simply a few more evolutionary rounds. SyRBo is essentially a simple add-on that can be readily added to a symbolic regressor, often with beneficial results.

There are a number of avenues we can offer for future exploration:

• •

  Add known boosting tricks of the trade, such as a learning rate and dynamic early stopping (similar to XGBRegressor’s ‘early stopping rounds’ parameter).

• •

  Our focus herein was on regression. It would seem worthwhile to examine SyRBo for classification.

• •

  We used a rather basic symbolic regressor. The GP literature is rife with many other types of regressors, which might be used in conjunction with SyRBo. More generally, other types of GP might offer productive ways to evolve programs that might serve as strong learners.

• •

  Comparison to non-symbolic-regressor methods.

• •

  While we focused on gradient boosting, other types of boosting techniques might be examined as to whether they might be a good fit for SyRBo.

This work was supported by National Institutes of Health (USA) grants LM010098, LM012601, AI116794. We thank Hagai Ravid for spotting an error in an earlier version of the code.

The results of all experiments over all datasets are given in Tables 3,  4,  5, and 6 for number of stages equal to 2, 3, 4, and 5, respectively. As noted in Section 3, for each of the 98 datasets we recorded the mean absolute error attained per algorithm over each of the 30 replicate runs, per each of the 5 test folds. We then computed the median of these scores, which are presented under ‘mean absolute error’ in the tables. Under ‘pval’ we show the results of the 10,000-round permutation tests between the scores of SyRBo and SymbolicRegressor, with a ‘!’ denoting a significant win for SyRBo and a ‘=’ denoting an insignificant loss for SyRBo. Under ‘run times’ we show the median run times for SyRBo and SymbolicRegressor. ‘SR’ denotes SymbolicRegressor.