Building the Building Blocks: From Simplification to Winning Trees in Genetic Programming
Authors: Lucija Planinić
Marko Đurasević
Stjepan Picek
Domagoj Jakobovic
Venue: ICLR 2022 Submitted (2022)
Keywords: Genetic Programming
Building Blocks
Regression
Bloat
Experimental evaluation

Abstract: Genetic Programming (GP) represents a powerful paradigm in diverse real-world applications. While GP can reach optimal (or at least ``good-enough'') solutions for many problems, such solutions are not without deficiencies. A frequent issue stems from the representation perspective where GP evolves solutions that contain unnecessary parts, known as program bloat.
This paper first investigates a combination of deterministic and random simplification to simplify the solutions while having a (relatively) small influence on the solution fitness. Afterward, we use the solutions to extract their subtrees, which we denote as winning trees. The winning trees can be used to initialize the population for the new GP run and result in improved convergence and fitness, provided some conditions on the size of solutions and winning trees are fulfilled. To experimentally validate our approach, we consider several synthetic benchmark problems and real-world symbolic regression problems.

Under review as a conference paper at ICLR 2022
BUILDING THE BUILDING BLOCKS: FROM SIMPLIFI- CATION TO WINNING TREES IN GENETIC PROGRAM- MING
Anonymous authors Paper under double-bling biind review
ABSTRACT
Genetic Programming (GP) represents a powerful paradigm in diverse real-world applications. While GP can reach optimal (or at least "good-enough") solutions for many problems, such solutions are not without deficiencies. A frequent issue stems from the representation perspective where GP evolves solutions that contain unnecessary parts, known as program bloat.
This paper first investigates combination of deterministic and random simplifi- cation to simplify the solutions while having (relatively) small influence on the solution fitness. Afterward, we use the solutions to extract their subtrees, which we denote as winning trees. The winning trees can be used to initialize the pop- ulation for the new GP run and result in improved convergence and fitness, pro- vided some conditions on the size of solutions and winning trees are fulfilled. To consider several synthetic benchmark
experimentally validate our approach, problems and real-world symbolic regression problems.
INTRODUCTION
Genetic programming (GP) is an evolutionary algorithm (EA) used automatically generate com- puter programs to solve specific tasks (Koza, 1992). Up to now, GP has been used in diverse domains like image analysis (Varniab et al., 2020), cybersecurity (Picek et al., 2018), or scheduling (Nguyen et al., 2017). What differentiates GP from other types of evolutionary algorithms is the fact that the solutions are commonly represented as expression trees. Naturally, due to specific solution representation, appropriate variation operators need to be used. Unfortunately. while being very successful in diverse domains, GP also faces certain perresntationnssecifi problems. Indeed, the GP process will introduce redundancy and functionally useless sections of programs, commonly denoted as program bloat (Koza, 1992; Blickle et al., 1994).
Program bloat cause various issues to the GP process. As consequence of bloat, the evolution process can prematurely terminate and explore large parts of the search space that are not promising. Since the solutions with program bloat will be more complex than needed, the interpretability of solutions will suffer. Additionally, program bloat can be connected with some forms of building blocks, i.c., parts of the solutions that can be combined form even more fit solutions.
As there are no universal ways to deal with program bloat, this problem is difficult. Commonly used methods are mostly based on applying various forms of simplification reduce the complexity of solution and eliminate any useless details. While such techniques can reduce program bloat, there are further questions to consider. For instance, simplification can be done at the end of the evolution process (Hooper & Flann, 1996) but also during the evolution process (Wong & Zhang, 2006; 2007). As simplification will reduce redundancy, it can also have negative effects on the diversity of the obtained solutions and decrease the protection of useful building blocks within solutions from the destructive nature the crossover operator (Blickle et al., 1994).
Numerous works have explored the issues of program bloat or how to simplify the GP solutions as discussed in Section 2. What is more, multiple works have discussed the notion of building blocks for GP (Langdon & Poli, 2002), but widely accepted definition for building blocks is still not agreed upon. A somewhat similar concept to building blocks has been recently discussed in the deep learning community. There, the Lottery Ticket Hypothesis for artificial neural networks discussed

---

Under review as a conference paper at ICLR 2022
how "...a randomly initialized dense neural network contains sub-network that is initialized such that, when trained in isolation, can match the test accuracy of the original network after training for at most the same number of iterations.", ,, which surmises the existence of "winning ticket" for neural networks (Frankle & Carbin, 2019). This opens up the question of the existence of something like winning tickets for GP.
This work considers simplifications (both exact and heuristic ones) in tree-based GP applied for symbolic regression, and show that building blocks play an important role. More precisely, our contributions are:
We present new technique conduct heuristic simplification for GP. We combine the heuristic simplification with the exact one, allowing us to reduce the tree sizes significantly. We discuss new concept in GP that we denote as winning trees. While there are sim- ilarities between winning trees and building blocks, the main differences stem from the fact that the winning trees have constraints on fitmess and tree depth. We introduce the notion of winning trees to help us understand better how to guide the evolutionary process to highly-fit solutions.
We provide extensive experimental analysis to showcase that the evolutionary process when using winning trees can result in 1) more fit solutions, 2) faster convergence, and 3) a more robust evolutionary process. Additionally, we discuss the depth constraints for winning trees and show they work well only of sufficient size, coupled with the appropriate solu- tion depth.
2 RELATED WORK
Several studies have already dealt with the problem of simplifying the expression trees evolved by GP. These methods can roughly be divided into two groups, methods that simplify the expression without changing the behavior of the original expression and those which, by simplifying the ex- pression, change its behavior compared to the original one. The former group consists mostly of methods that perform algebraic simplification. These methods apply predefined algebraic rules to replace part of an expression with a simpler but equivalent one. In the literature, such methods are usually denoted as algebraic simplification or editing. Such a method was applied by (Wong & Zhang, 2006), and (Zhang et al., 2006) online during the evolution; the authors defined 30 algebraic rules which were applied the evolved trees in the population. The algebraic simplification method was combined with hashing, which helped to determine equivalent expressions (Wong & Zhang, 2006; 2007). These methods hash sub-expressions and determine whether certain expressions are equivalent or not based on the hash value. This helps the algebraic procedure to detect situations that would otherwise go undetected.
The second group of simplification methods introduces modifications that can change the expres- sion's behavior. The idea is to detect parts of the expression that are not meaningful and remove them, although this might affect the numerical outcome. The main question is how to determine which parts of the expression should be climinated. (Kinzett et al., 2008; 2010) proposed the ap- plication of a numerical simplification based on node contribution to reduce the complexity of the evolved trees. (Song et al., 2009) pruned trees by removing a child an operator with two ar- guments if, when removed, the removal does not change the output of the node beyond given threshold. (Garcia-Almanza & Tsang, 2006) proposed method for tree pruning applied to decision trees used to generate classification rules for financial stock markets. The method consists of ex- tracting rules from a decision tree, evaluating them, and then pruning the rules that did not achieve the expected pruning threshold in the evaluation phase. A constant sub-tree pruning method was proposed by (Rockett, 2020). This pruning scheme replaces a subtree with constant value. The constant is calculated as the expectation of the subtree, which replaced on the entire dataset.
Building blocks were first discussed in the context of genetic algorithms short, low-order, and highly fit schemata that are sampled, recombined, and resampled to provide solutions of higher fitness (Goldberg, 1989). Intuitively, building blocks are small parts of a solution that can be formed into larger, more fit components through genetic operators. Defining a building block for GP is more difficult, where some common (traditional) interpretations 1994), a rooted subtree (Rosca, 1997), and block of code (Angeline Kinnear, 1996). In this work, will follow the work from Langdon and Poli that define building blocks as parts of the solution
subtree to solution tree (Altenberg,
2

---

Under review as a conference paper at ICLR 2022
that can be combined to form more fit solutions but without any constraints on fitness, length, or order of building blocks (Langdon & Poli, 2002). We note a recent work by O'Neill et al. where the authors discuss transfer learning for GP and how to create valuable material as building blocks dynamically (O' Neill et al., 2017). Still, we consider this work orthogonal to ours as we do not aim transferability while imposing other constraints.
Since its definition, several studies which focus on the lottery ticket hypothesis have been made. For instance, (Chen et al., 2020) used observations from the work on the lottery ticket hypothe- sis (Frankle & Carbin, 2019) to find trainable and transferable subnetworks in pre-trained BERT models, which are commonly used natural language processing, (Frankle et al., 2020) used it- erative magnitude pruning (IMP) to determine "whether a neural network optimizes to the same, linearly connected minimum under different samples of SGD noise".
METHODOLOGY
To evaluate the winning trees hypothesis for GP, we need to consider the expressions that GP obtains. There is no guarantee that the expressions obtained by GP are exact (i.e., they represent the exact solution), and at the same time, they contain many unnecessary subexpressions. This is often true when GP executed for longer periods, and bloat starts occurring (Luke Panait, 2006). To mitigate this problem, introduce methods for reducing the complexity of the expression trees. We denote these methods as simplification, for the exact procedure and pruning, for the heuristic procedure.
3.1 SIMPLIFICATION
The goal of the simplification approach is simplify the expression without changing its behavion: Therefore, this approach replaces expressions with equivalent but simpler ones. One such example would be replace the expression The rules for simplification in our experiments are based on common algebraic axioms and aim reduce the size of the expression, such as the example above, and the complete list is given in Appendix A, Table 7. The applied rules are not exhaustive, and more rules can be defined and used. However, the given set of rules has shown be enough to simplify the obtained expressions.
0 with æ since the first one includes two redundant symbols.
The simplification is performed using the Compare-Match algorithm proposed in (Steyaert & Fla- jolet, 1983). The algorithm includes two recursive functions, Match and Compare. The Match function iterates through the expression tree from the root node through all of its subtrees and de- termines whether it can find a pattern P in the given expression T. a match is found, then P is replaced by simpler expression defined for that pattern. Finding patterns is performed by the Com- pare function, which traverses through the expression tree and returns tree it could locate pattern P in the expression tree, otherwise returns false. The Compare function applies additional Map function to retrieve the information about the located pattern. The outline of the method is given in Appendix Algorithm
3.2 PRUNING
Unlike simplification, which is exact and does not change the behavior of the expression, the pruning method allows the expression to be simplified by removing parts of it, which will directly influence its output. This means that the expression does not necessarily need to have the same output value for a given input before and after pruning. This technique is performed so that certain elements in the expression are simply replaced by neutral element for a given operator. For example, in the expression + +XY, where X and Y represent arbitrary subexpressions, the expression can be pruned by removing either operand and replacing with a neutral element for summation, which is O. Thus, it is possible to obtain either + or +OY. In that way, one part of the expression can be removed while keeping the rest of the expression fixed. Each binary operator has its neutral element, which for the summation and subtraction are O, whereas, for multiplication and division, they equal to 1. Unary operators do not have a neutral element as they represent a single expression. Thus, they not considered in the pruning process.
3

---

Under review as a conference paper at ICLR 2022
The removal of certain subexpressions can change the behavior of the entire expression. To observe how the modifications influence the expression's 's behavior (the semantics), we monitor the change in fitness between the original expression and the pruned one. If the fitness improves or stays the same, the change is accepted. Our approach also allows pruning to be performed even if it reduces the fitness compared to the original expression; however, a limit is imposed how much the simplified expression can be worse than the original one.
The procedure that performs the pruning starts from the root node of the expression tree and traverses the tree. At each node, it replaces the current node with a corresponding neutral element. Then, the new expression is evaluated, and its fitness is compared to the fitness of the original expression. The new expression is accepted if it does not degrade the performance of the original expression beyond a certain degree. In our experiments, we set that the solution should not be degraded beyond 1,5% of its original quality. Naturally, this parameter can be arbitrarily chosen to balance the complexity and quality of the expressions. If the change not accepted, then the procedure continues the traversal through the expression tree. Otherwise, if the change was accepted, the procedure is restarted at the root node and traverses the tree again to check whether it is possible to perform additional simplifi- cations. The procedure stops when both the entire expression tree is traversed, and modification is performed. To the best of our knowledge, this kind of pruning approach for GP has not been applied before.
3.3 SEARCH FOR WINNING TREES
We define winning trees for GP as parts (subtrees) of solution (tree) that can be formed into larger, more fit components through the use of genetic operators. Differing from building blocks, winning trees have:
constraints on the fitness value- as they are formed as subtrees of highly fit solutions (trees),
and
constraints on the size - as they cannot be arbitrarily small or large.
Note that winning trees are actually subtrees, but we denote them trees for simplicity.
The candidates for the winning trees will be obtained by first identifying highly fit simplified ex- pressions in the following procedure. A full GP evolution will be executed times, and the best individual from each run on the training set will be stored. When n individuals are obtained, each of them is simplified by the previously outlined methods in the following way. First, the exact simplifi- cation is performed, followed by the heuristic pruning, and then again the exact simplification. The goal of the first exact simplification is to reduce the complexity of the original expression if possi- ble. Since the heuristic pruning needs to evaluate the expression after each change, it is beneficial to start with an already simplified expression to reduce the number of possible evaluations (espe- cially in cases where the fitness function is more complex). After pruning, the exact simplification again invoked to remove possible redundant elements introduced by the heuristic simplification (for example, when introducing neutral elements in the expression).
After the process mentioned above, the n obtained expressions are considered simplified. Therefore, in our approach, the simplification is performed offline after the GP run has finished. The simplified expressions can then be used as the basis to create subtrees that will be used for the initialization of the initial population of a new GP run. However, using only the complete expressions would not make sense as it would mean that GP would be starting from the best solutions and trying to improve them further (emulating setting with longer evolution process). Therefore, smaller subexpres- sions (winning trees) that are part of the original ones are inserted into the initial population. This is performed by selecting random subtrees (with defined depth) from the available expressions. These selected subtrees are then used as individuals in the starting population of a new GP run.
A depth limit for the selected expressions is additionally imposed. If the GP is allowed to evolve expression trees of depth d, then the maximum depth of the randomly selected subtrees is equal to g. In that way, we wish to include smaller subtrees (relative the maximal depth of the tree) but also ensure that not only small subtrees are included in the new population. Note that we limit the minimal tree depth to for all settings. What is more, the limit on & represents an upper bound, which means we also use smaller winning trees. The value was selected arbitrarily, and we leave further investigation on various depths for winning trees for future work.
4

---

Under review as a conference paper at ICLR 2022
4 EXPERIMENTAL SETUP
4.1 DATASETS
To test our hypothesis, we use two symbolic regression benchmark sets. One set based on existing synthetic benchmark functions whose exact target expressions are known and, as such, can be fitted without error. The second benchmark set consists of several wealdworld regression datasets for which the exact solution is not known.
Table 8 in Appendix A shows a selected set of ten synthetic symbolic regression problems (Oliveira al., 2018). This set was selected to include functions of different forms and complexities. All selected functions are either one or two-dimensional. A training set consisting of 10.000 instances and test set of 000 instances were generated for all functions. Both sets contain instances sampled uniformly from the interval [-5, 5]. Table 9 in Appendix A denotes the properties of the datasets for the five real-world regression problems (Dua & Graff, 2017). These sets were divided into the training set containing 70% of instances and the test set containing 30% of instances. Compared to the synthetic benchmark problems, these problems have fewer instances that can be used for training and contain more input variables.
4.2 GENETIC PROGRAMMING
The applied GP uses the steady-state tournament selection with tournament consisting of three individuals. The population size of the algorithm was set to 500 individuals and the mutation prob- ability to 0.3. The tree depths of 6, 8, and 10 will be used in experiments to test the hypothesis with different expression sizes. The crossover operators included the subtree, context preserving, one point, size fair, and uniform operators, whereas the set of mutation operators contains the subtree, shrink, permutation, node replacement, node complement, hoist, and Gauss mutation operators (Poli al., 2008). Each time individuals are crossed over or mutated, the operators that will be applied are randomly selected from the set of crossover and mutation operators. The function set contains the addition, subtraction, multiplication, and division operator, as well as the sine, cosine, and square root. In addition to the input variables, the set of terminal nodes also includes numerical constants generated from the interval 1_. Two stopping criteria were used, the maximum number of eval- uations and the maximum number of evaluations without improvement in the best individual. The maximum number of evaluations was set to 500, whereas the number evaluations without improvement was set to 25 000. The fitness function being minimized is the mean squared error between the expected outputs and the output values obtained by the evolved expression for all input values. Each experiment executed 50 times to obtain statistically significant results.
EXPERIMENTAL RESULTS
5.1 RESULTS FOR SYNTHETIC BENCHMARKS
In the first set of experiments, GP is tasked with finding the expression for ten synthetic benchmark functions, using the three specified maximum tree depths (6, 8, and 10). In every experiment, the fitness of original expressions denoted original, whereas the fitness of simplified expressions is denoted as final. Three scenarios were conducted in the experiments. The first scenario, where GP was executed with random initial population find the symbolic expression for the given data, is denoted as Random. The expressions obtained from this run are then used as the seeds for the initial population of a second GP execution denoted as Subtreelnit. Since the comparison between those two approaches could be considered unfair, we include an additional experiment in which GP was given twice the number of evaluations than the Random variant to compensate for the additional time that is used when rerunning the GP with new initial population. This scenario is denoted as Random2x.
Table gives the results for the test set. The experiments demonstrate that the obtained results depend quite heavily on the maximum tree depth. Indeed, for expressions of depth 6, the results demonstrate that the initialization with the winning trees did not improve the results in most cases. However, as the depth of the expressions increases, the results of the SubtreeInit approach improve. This is most evident when using a tree depth of size 10. For the tree depth of 10, the results obtained
5

---

Under review as a conference paper at ICLR 2022
by Subtreelnit equally good or better than the results obtained by both Random or Random2x for all the tested functions. Another interesting result is that the method initialized with winning trees outperformed GP with the random initialization, which was given twice the number of evaluations. This shows that the improvement in the results is not a consequence of the extra time that GP was given. Rather, the good solutions obtained seem to be direct consequence of the winning trees inserted in the starting population.
Such behavior can be explained so that the winning trees obtained for tree depth six will be quite small and thus very general. Therefore, GP will still struggle to combine such subtrees in a mean- ingful way. However, for the larger tree depths, a larger portion of the solution will be transferred. Naturally, this subtree does not have good fitness by itself since it represents only a part of the expression. However, it more "specialized" for the considered problem.
Table 1: Test set results.
depth
10 final
original
final
original
final
original
Keijzer 4
Random
0, 0,364598
0.389749
0,323364
0.349782
0.34916
0.389907
Random2x
0,369
0.391
0,323
0.351
0.303
0.337
SubtreeInit
0.404064
0,404064
0.296285
0.314635
0,307674
0.330624
Keijzer
Random
0.6998565
0,700004
0,6735125
0,700004
0,6719495
0.700004
Random2x
0.697
0,700
0.674
0.700
0.659
0.700
Subtrceloit
0,700004
0,700004
0,700004
0,700004
0,700004
0,700004
Keijzer 16
Random
2.59087
2.86844
1,336335
1.51365
1,2123
1,22722
Random2x
2,840
3,082
1.252
1.420
1,158
1,230
Subtreclnit
3.74226
3.99701
0,987748
1,08079
0.894961
0.982344
Korns 4
Random
0,020706
0.020706
0.009821
0.009821
0.008658
0.00921
Random2x
0.013
0.013
0,012
0.012
0.011
0.011
SubireeInit
0,040262
0,040262
0,031405
0.031405
0.011096
0.011096
Korus
Random 1.01063
L00063
1.00446
L01892
0,986981
1.01063
Random2x
1.010
1.098
0.995
1.011
0
1.011
SubtreeInit
1.01063
1.01063
1.008765
0.998089
1.01063
Nguyen
Randorn
9.72E-05
9,77E-05
0,082576
0.082576
0.135774
0.137373
Random2x
0.000
0.000
0.018
0.018
0.103
0.130
Subtreelnit
4.97E-15
5.74E-15
4.971:11
5.74
4.97E-15
5.74
Nguyen
Random
59.94085
59,94105
63.46775
69.0745
48.5
$1.867
Random2x
15.998
15.998
$7,950
65.081
28.058
30,807
SubtreeInit
3,20736
3,24277
1.079874
1.079875
2,27039
2.298855
Nguyen
Random
0.196108
0.196108
0,209633
0.213252
0.167364
0.195794
Random2x
0,122
0.122
0,075
0
0,226
0.237
Subtreelnit
0.359085
0.395686
0.240072
0.244396
7.02F-17
7.02F- 17
Nguyen
Randorn
0,294081
0.294081
0.371099
0.403021
0.353553
0,40881
Randem2x
0,258
0.426
SubtreeInit
0.425501
0.442081
0,481001
0.524147
0
5.72B-16
Nguyen 12
Random
3,678065
3.892595
3.65844
4.038375
3,89702
4.29179
Randorn2x
4.385
4.398
4,367
4.881
5.006
4.892
SubtreeInit
5.40213
5,40213
4.907745
5.39591
0.712049
0.706132 32
UNIVERSALITY OF WINNING TREES
After the initial results, we can investigate whether the winning trees for one problem are universal, iee, can they also be used to initialize the population when applying GP for a different problem. To test this hypothesis. we selected five function pairs and used the obtained individuals for one function to initialize the population of GP when optimizing the second function. The functions were selected so that in certain cases, similar functions are paired together (Nguyen 12 and Keijzer 16) while, in other cases, functtons with completely different behavior are paired together (Nguyen 4 and Keijzer 4). Table shows the results for this experiment. The first function represents the optimized function, while the second represents the one from which the subtrees were used for initialization (e.g., Keijzerf12 wttperff2luuubreeeeee subtree_Kornsf11 Kornsf12 denotes that we optimize function Keijzer 12, and use subtrees from Korns 12).
The results generally suggest that the winning trees are not universal, since in most cases, the results obtained by the unmatched initialization procedure were worse than those obtained by either the ran-

---

Under review as a conference paper at ICLR 2022
Table 2: Test set results with the wrong subtree initialization.
depth
mis
med
mB2
min
maal
min
musl
Neljerf12_subrree Korus11
original
lical
0.572146
0.572146
0.700004
0,700004
0,701605
0,0004998666
0,700004
0.700004
0,701212
1,42152
0.700004
0.700004
0,705602
3.10611
Xelperff6.ssubrre saterrtto_uurree-nuuuatt
final
original
1.1334
1.3541
2
2844835
160473
1S9416
D.4865S
0.561838
1211877
108006
5.37345
3.76721
0,478139
0.407764
0.9726
1
5,0/995
5,58704
Nguyeaf4 jubteee, Keijazr44
final
criginal
999245-13
695766-13
1857375
1997375
118964
123.222
4.31668-11
4.4942F-
7.36-13
7.54-133
45,4089
4944
4.536-13
4.53F-13
0.589004
0.337755
41.3374
41,3574
NguyentE subtree Nguycaft
ociginal
70021678-17
0.354029
0.345687
0.440514
0,428466
7,02167E.17
7,021678-17
0.348264
0.394857
0.440291
0.428484
7,02E-17
7.02E
0.20222
0.23388
0.433465
0.428465
Nguveaff sultree Karnst4
original
Rinal
0.55077845
0.5817115
0,647055
0,655615
0
0,502357
0.551956
0.647085
0.647065
0.416604
0.465653
0.647155
0.6470855
Table 3: Test set results with random initialization, real-world datasets.
depth
6
10
function
min
med
min
medd
min
med
airfoll
original final
5.396
6.934
14.975
4.538
5.966
15.640
3.948
5.783
77.790
5.455
7.487
17.482
5.223
6.150
16.583
4.799
5.923
8.507
ccpp
original final
4.771
7.433
33.544
4.524
6.125
16.189
4.126
5.194
45,341
5.059
7,668
35.548
4.827
6.710
16.824
4.741
5.946
51.875
concrete
original final
8.024
11.972
19,390
9.887
12.109
175.524
10.123
13.027
20.201
7,856
12.006
18.627
9.185
12.462
19.769
9.304
12.594
22.162
wine red
original final
0.637
0.678
0.733
0.639
0.675
0.966
0.653
0.684
0.835
0.647
0.727
0.850
0.653
0.722
0.834
0.690
0.739
0.847
original final
0.720
0.994
0.715
0.809
0.667
0.709
0.793
0.702
0.775
0.883
0.711
0.776
0.895
0.720
0.760
0.883
dom or subtree initialization procedures. Therefore, winning trees seem exclusive to the considered problem and cannot be reused across different problems. As such, this is an indication that winning trees represent a specialization of building blocks in GP.
5.2 RESULTS FOR THE REAL-WORLL DATASETS
Table 3 gives the results obtained by GP when using random initialization, whereas Table 4 presents the results obtained when the population is initialized by winning trees obtained from the initial run. For the first two test problems, namely AFN and CCP, it is evident that initializing the population with winning trees improves the overall results. For the other three, the results are more evenly matched. This is especially true for the WIR and WIW problems, where both methods achieved an almost equal performance.
Table 4: Test set results with subtree initialization, real-world datasets.
depth
function
min
med
max
min
med
max
min
med
max
airfoil
original
5.182
5.795
138.921
4.483
5.495
8.952
4.405
5.407
64,376
final
5.536
5.994
139.233
4,964
5.729
7.469
4.557
5.670
64.429
ccpp
original
4.635
5,561
15,990
4.411
5,330
17.331
4.137
4.707
15.980
linal
4.637
6.058
15,990
4.972
5.967
17.351
4.701
5,390
15,980
concrete
original
9.489
13:025
20.428
9.535
11.953
19,549
8.329
12.934
96,710
final
12.145
19.095
11.856
19.152
12.634
25.108
wine
original
0.644
0.675
0.778
0.645
0.671
0.698
0.632
0.676
0.882
Hinal
0.662
0.717
0.832
0.652
0,727
0.834
0.652
0.717
0.825
wine_white
original
0.695
0.728
0.857
0.688
0.712
2.780
0.687
0.705
20.870
final
0.720
0.770
0.951
0.726
0,771
0.892
0.712
0.769
0.904
7

---

Under review as a conference paper at ICLR 2022
5.3 EXPRESSION COMPLEXITY ANALYSIS
Besides the test performance, another perspective worth considering is their complexity, iee, the sizes of the obtained expressions. Table 5 shows the median of expression sizes for all synthetic test functions. First, can be noticed that the applied simplification and pruning methods were effective in reducing the complexity of the expressions. On average, reduction of 40% was achieved across all the experiments after both simplification methods were applied. Although for some functions, like Korns 12, the method simplifies the expression to only single node, this result is not indicative of simplification only. The reason is that GP was, this case, actually unable to fit this function well, and the expression it obtained does not perform better than only single constant node that is obtained after simplification.
The second important observation is that the expressions that evolved when initializing the popu- lation with winning trees are, in most cases, significantly smaller than when using random initializa- tion. On average, when considering all the experiments, initialization with winning trees reduces the size of the evolved expressions by around 50%. This demonstrates that a good initialization leads smaller occurrence of bloat. Still, it should be noted that does not eliminate bloat completely since the obtained solutions could be simplified further.
Table Synthetic problems, solution sizes with random init, random init with twice the evaluations, and subtree init, size median. The first occurrence of the smallest solution is denoted in bold style.
Random
Raudom2x
Subtree
depth
10
8
6
10
Keijzer 4
original simplify
29.5
62
123
28
69.5
135.5
8
52
67
27
prune
22,5
41.5
62
21
43
87
8
34
42
simplity
21
39
54
38.5
8
33
36
Keijzer 12
original simplify
17.5
32
51.5
17
36.5
52
3
3
prune simplify
5
7
8
3
3
Keijzer 16
original simplify
53
106
142.5
59.5
110
153.5 5
53
66
158.25
51
144
prune
47
92
121
$4.5
103.5
130.5
48.5
$9.25
140.75
simplify
125.5
57.5
Korns
original simplify
22
28
43.5
23
14
33
12
20
31.5
12
21.5
8.5
11
24
prune
11.5
19.5
30.5
11.5
21.5
26
8.5
1I
21.55
simplify
11.5
Korns 12
original simplify
35
66.5
98.5
36
7
44
96.5
25.5
57.5
90
31
87.5
I
36.5
83
prune
8
8
8
simplify
Nguyen
original simplify
20.5
32.5
72
13
23
56.5
15
32.5
43
9
prune
13.
23
51.5
9
simplify
13
23
50
13
9
Nguyen
original simplify
54.5
46.5
49
95.5
165
47
104
217
23
27.5
39
prune
47
91.5
154
45.5
193
27
39
simplify
47
89.5
144
44.5
188
26.5
39
Nguyen
original simplify
25
46.5
24
21.5
37.5
86.5
20
32
72
9
16.5
prune
17.5
233
simplify
17
16.5
59.5
13
28
37.5
7.5
12
Nguyen 6
original
17.5
31
58
19
17
simplify
14
29.5
55
17.5
27
49.5
10.5
16.5
prune
11.5
simplify
9.5
22.5
31.5
15
17
29.5
9
10.5
Nguyen 12
original
37.5
77
105.5
43
111.5
23
56
simplify
33
72.5
97
39.5
79.5
103.5
20
51.5
prune
31
66.5
86
38.5
42.5
simplify
30
65
81.5
38
70
92
11
18
38.5
8

---

Under review as a conference paper at ICLR 2022
Table 6 shows the summary of the obtained expression sizes for real-world problems after the cution of the simplification and pruning methods. The expressions obtained using the winning trees for initialization did not always lead to smaller expressions for these problems. This happens for the WIW and WIR datasets, in which the expressions obtained with the initialization by winning trees larger than those obtained with random initialization. A probable cause for this is that the algorithm quickly converged to a good region of solutions and simply started to bloat and overfit on the training set. On the WIW dataset, we observe some spikes on the (random initialization with the tree depth of and subtree initialization with the three depth of 8). At this point, it seems that the method started overfit, but nevertheless, in the next iterations, solu- tions that performed well on the test set were evolved. For CST, the expressions are of similar size, whereas initialization with winning trees resulted in smaller expressions being evolved for the other two problems. In those cases, the algorithm converged more slowly, and as such, it seems that they did not have the chance to overfit the training set.
for experiments
Table 6: Real-world datasets, solution sizes with random and subtree initialization, size median. The first occurrence of the smallest solution is denoted in bold style.
Random
Subtree
depth
Airfoll
original simplaty
154
233.5
53.5
77.5
201
143.5
230
49.5
73.5
191.5
prune
54
114
169
34,5
44.5
141
simplity
28
37.5
134.5
Cepp
original
45.5
107
180.5
39.5
72.5
simplaty
44.5
104.5
171.5
38.5
72
138
prune
77
101
33
58
simplify
72.5
86
29.5
51
55.5
Concrete
original
77
156.5
simplify
43.5
79.5
152.5
40.5
76.5
154
prune
52.5
77
29
simplify
45.5
64
24
42
72
Red
original simplify
64
45
29
50.5
64
20
44.5
82
prune simplify
21.5
19
17.5
14
11.5
13,5
12
White wine
original simplify
50
84,5
18.5
42
96
31
49.5
83
18.5
41.5
95.5
prune
22.5
15
simplify
11.5
13.5
14
10
CONCLUSIONS AND FUTURE WORK
This paper analyses the influence of simplification in GP for regression problems. First, we inves- tigate how various simplification procedures can result in smaller, yet fit solutions. Afterward, we use the parts of the obtained solutions (denoted winning trees) seed the population for new runs. Our results indicate that winning trees can help reach better solutions in a smaller number of evaluations. This approach works especially well for cases where solutions have larger depth as then, winning trees have sufficient "space" to be properly adapted, and where the tree depth size makes more challenging for the GP process to evolve highly fit solutions.
As this paper proposes a new concept winning trees, there are multiple possible future research directions. It is possible to look at winning trees as a building block specialization with constraints on size and fitness. Still, one could question our design choices in several places. For instance, why considering the problems we consider, why not tune more or the GP's parameters, why go for subtrees (winning trees) of depth half the maximum tree depth. Furthermore, the insertion and application of subtrees in the new population can also be performed to provide more influence to the evolutionary process. We consider the investigation of those alternatives natural next step.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Lee Altenberg. The Evolution of Evolvability in Genetic Programming, pp. 47-74. MIT Press, Cambridge, MA, USA, 1994. ISBN 0262111888
Peter J. Angeline and Kenneth E. Kinnear. Extending Genetic Programming with Recombinative Guidance, pp. 69 88. MIT Press, 1996.
Tobias Blickle, Lothar Thiele, and Lehrstuhl Fur Mikroelektronik. Genetic programming and re- dundancy, 1994.
Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Zhangyang Wang, and Michael Carbin. The lottery ticket hypothesis for pre-trained BERT networks. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin (eds.), Advances in Neural Information Processing Systems 33: Annual Con- ference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL /ttpa/////../tt////////oaaaaaaa. neuripss....ssns...p.p....s.ssss ct/ wwwpppppee//////aaaeeeeeeeeeeeee b6a (o6ff2c970322000 (eoe222794be00d f2e3 ateee-btbbttttt.thee...
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL ics. uci. pecimeddm/l..
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neu- ral networks. In 7th International Conference Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. URL / met/forunm d=r11
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M. Roy, and Michael Carbin. Linear mode connectivity and the lottery ticket hypothesis. In Proceedings the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pp. 3259-3269, PMLR, 2020. URL http: http://peoccc......//// mlr. mlr. www.ppressvlll.. v / Saraakke2200 html.
A.L. Garcia-Almann and E.P.K. Tsang. Simplifying decision trees learned by genetic program- ming. In 2006 IEEE International Conference on Evolutionary Computation, pp. 2142-2143 2006. doi: 10. 10..1099/CC..206168555555
David E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Addison- Wesley Longman Publishing Co., Inc., USA, 1st edition, 1989. ISBN 0201 157675.
Dale C. Hooper and Nicholas S. Flann. Improving the accuracy and robustness of genetic program- ming through expression simplification. In Proceedings of the 1st Annual Conference on Genetic Programming, pp. 428, Cambridge, MA, USA, 1996. MIT Press. ISBN 026261 1279.
David Kinzett, Mengjie Zhang, and Mark Johnston. Using numerical simplification to control bloat in genetic programming. In Xiaodong Li, Michael Kirley, Mengjie Zhang, David Green, Vic Ciesielski, Hussein Abbass, Zbigniew Michalewiez, Tim Hendtlass, Kalyanmoy Deb, Kay Chen Tan, Jürgen Branke, and Yuhui Shi (eds.), Simulated Evolution and Learning, pp. 493-502, Berlin, Heidelberg, 2008 Springer Berlin Heidelberg. ISBN 100-3-5500-969444
David Kinzett, Mengjie Zhang, and Mark Johnston. Investigation of simplification threshold and noise level of input data in numerical simplification genetic programs. In IEEE Congress on Evolutionary Computation, pp. 1-8, 2010. doi: 10. 10110/CC.2200005586188
John R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA, 1992. ISBN 026211 1705.
William B. Langdon and Riccardo Poli. Foundations of Genetic Programming. Springer- Springer-Verlag Verlag,
Berlin, Heidelberg, 2002. ISBN 3540424512.
Sean Luke and Liviu Panait. A comparison of bloat control methods for genetic programming. Evolutionary computation, 14:309 44, 02 2006. doi: 10. 1.211666c...20..112 14..3.3.33001....0....
10

---

Under review as a conference paper at ICLR 2022
Su Nguyen, Yi Mei, and Mengjie Zhang. Genetic programming for production scheduling: survey with a unified framework. Complex & Intelligent Systems, 3(1):41-66, February 2017. doi: 10.10077/-40777007-00033 x.
URL https:
Luiz Otavio V. B. Oliveira, Joao Francisco B. S. Martins, Luis F. Miranda, and Gisele L. Pappa. Analysing symbolic regression benchmarks under a meta-learning approach. Proceedings of the Genetic and Evolutionary Computation Conference Companion, Jul 2018. doi: 10. 10.1145/3205651. 3208293. URL http::/tp//... dx. doi. wwt.:odi...o....o 1111/ 02055/325555111 32082933.
Damien O'Neill, Harith Al-Sahaf, Bing Xue, and Mengjie Zhang. Common subtrees in related problems: A novel transfer learning approach for genetic programming- In 2017 IEEE Congress Evolutionary Computation (CEC), pp. 1287-1294, 2017. doi: 10.1 1111/CCC22017.7999455
Stjepan Picek, Erik Hemberg, Domagoj Jakobovic, and Una-May O' D'Reilly. One-class classification of low volume dos attacks with genetic programming. In Wolfgang Banzhaf, Randal S. Olson, William Tozier, and Rick Riolo (eds.), Genetic Programming Theory and Practice XV, pp. 149- 168, Cham, 2018. Springer International Publishing. ISBN 978-3-319-90512-9)
Riccardo Poli, William B. Langdon, and Nicholas Freitag McPhee.
field guide to genetic programming. Published via Attp://lulu. com and freely available http:/ /ttp//wwwwwww/// wow-gp--ieee field- ffied-guidddeeeee guide. org. uk, 2008. URL http:/ http://www.ppffleldd field- guide. org.rrg... uk. (With contributions by R. Koza).
P.I. Rockett. Pruning of genetic programming trees using permutation tests. Evolutionary Intelli- gence, 13, 12 2020. doi: 10. 10.1007/s 10007//122055000000077733
Justinian P. Rosca. Analysis of complexity drift in genetic programming. Genetic Programming 1997: Proceedings of the Second Anmual Conference, pp. 286-288299 286-294. Morgan Kaufmann, 1997.
Andy Song, Dunhai Chen, and Mengjie Zhang. Bloat control in genetic programming by eval- uating contribution of nodes. In Proceedings of the 11th Annual Conference Genetic and Evolutionary Computation, GECCO '09, pp. 1894, New York, NY, USA, 2009. Associa- tion for Computing Machinery. ISBN 9781 9781605583255 doi: 10.1145/1569901.11 1570221. URL https: //w.:///o../// http://i..org///g//// /wwoo/og//oooooooo/oooo w1w.1/11119991.1..1 117.922211.11..11....
Jean-Mare Steyaert and Philippe Flajolet. Patterns and snttem-matching in trees: An analy- sis. Information and Control, 58(1):19-58, 1983. ISSN 0019-9958. doi: https://doi.og org//1. 1016/S00099-955883)8888880 art arricieep111/001199588833
URL https:/ /ttp://wwww.///. sci encedi rect. com/sci com/science ence/
Mahsa Shokri Varniab, Chih-Cheng Hung, and Vahid Khalilzad Sharghi. Data mining and image analysis using genetic programming. SIGAPP Appl. Comput. Rev. 19(4):40-9, January 2020.
ISSN 1559-6915. doi: 02.1145/381130.33881111 URL hitps: /tt::///iii http//ii.ooooo.ooo http///ci.orrrr////// wwwooor/.............oo//..../.o 1145/ 3381307. 3381311.
Phillip Wong and Mengjie Zhang. Algebraic simplification of gp programs during evolution. In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, GECCO '06, pp. 927-934, New York, NY, USA, 2006. Association for Computing Machinery, ISBN 1595931864. doi: 141144//149997.11444 1143997. 1144156.
URL https: https:////// //tcc///dcciiieo orrei.orrg1ie 10..//10111/////111
Phillip Wong and Mengjie Zhang. Effects of program simplification on simple building blocks in genetic programming. In 2007 IEEE Congress on Evolutionary Computation. IEEE, September 2007. doi: 10.1 (0.11099cc.2200.44446666 URL https: httpp/:://d...gg/...111.... http:/10..19//eeee 2007. 4424660.
Mengjie Zhang, Phillip Wong, and Dongping Qian. Online program simplification in genetic pro- gramming. Tzai-Der Wang, Xiaodong Li, Shu-Heng Chen, Xufa Wang, Hussein Abbass, Hi- toshi Iba, Guo-Liang Chen, and Xin Yao (eds.), Simulated Evolution and Leurning, pp. 592-600, Berlin, Heidelherg, 2006. Springer Berlin Heidelberg. ISBN 978-3-540-47332-9;
11

---

Under review as a conference paper at ICLR 2022
Table Mapping rules for simplification.
+X1 + X
-XX -XX-0 -0
+X+YX - + 1YX
+ +
*1 +X
-X
+X*xy 4x-17 1YX
+*YX +
+X0
1XI x
++YXX 1YX
A B sin AB
+0X +0
XVY +x
++XYX
1YX
-+ Acss cos
+UX 7x
4/XV8 -X
-X -1---+++11 +XX
-
008 +AB
0in0
00s AAB
1XX
+x --I11 -XY
sin -0n -Usin
*D2 Acos a
000
Table 8: Synthetic benchmark functions.
Name
Definition
Keijzer 4
f(z) 0.3 2
Keijzer
f(x,0) 2y =i(ssn((2 1)(y 1))
Keijzer 16
f(2.
Korns
f(x) (0.1(0.1++si(()))
Korns 12
f(z. н) 2.0 -2.1-2.1 =
Nguyen
[(z] x² +x +
Nguyen
f(x)
+x +x* - -
Nguyen
f(x] sin(ar") coa(z)
Nguyen
f(x) sin(æ)) sin(# 22)
Nguyen 12
f(x.9) x² 3
A ADDITIONAL RESULTS
The mapping rules for simplification in experiments given in Table 7, defined using the prefix notation. The left side of each line denotes the original pattern that the Compare-Match algorithm searches for in the expression. On the other hand, the right side represents the expression by which the pattern in the original expression will be replaced.
Algorithm Compare- Match procedure
Input: P- pattern (left side the rule). expression
Output: Boolean: true if the rule has changed, fal otherwise.
Function Compare
root(P) wall root(T) wall then return frue
end
MM then
return false
for (i == 0 < degree(P); i do CoooprrrrPP sehhilddi,, T-gchildfi)) then return false
end If
return true
Function Match
Compare(PP. 'I then
Replace paltern in T with the simplified expression return true
Boolean matched :s false RTT
for (i = 0: degree(T); 8 do
matched == MatchiP, Tegchildji)) end for
mutched
end
matched
CONVERGENCE
Figure shows the GP convergence results for real-world problems. The plots represent the median of the best individuals from the 50 performed runs. The convergence is shown both on the training
12

---

Under review as a conference paper at ICLR 2022
Table 9: Real-world datasets.
Abbr.
Datasct
of instances
# of features
AFN
Airfoil self-noise
503
6
CCP
Combined cycle power plant
566
CST
Concrete strength
1030
9
WIR
Wine quality, red wine
1599
12
WIW
Wine quality. white
4889
set and on the test set, where in each iteration, the best individual from the training set was selected and evaluated on the test set.
The problems can be roughly grouped into two categories by their behavior. For the first three problems, we observed that some of the methods still did not converge in the given time and were improving the solutions. For the final two problems, namely WIR and WIW, the algorithms con- verged quite quickly, and for most of the run, the solutions did not improve significantly. The best convergence was achieved on the training set by GP initialized with winning trees and with the max- imum tree depth of 10. The convergence also improves when using winning trees for the other tree depths, although not as consistently. On the test set, it is evident that these methods reach good solutions faster than random initialization. This means that inserting existing genetic material into the initial population did not lead to overfitting but rather helped speed up the convergence.
STABILITY AND DIVERSITY OF THE SYNTHETIC SOLUTIONS
Figure shows the boxplot results for the synthetic benchmark datasets. This figure aims to deter- mine the stability and dissipation of the results between the tested methods. For the smallest depth 6f 6, the initialization with winning trees did not improve the stability of the results. In general, the results obtained by this method were, in several cases, even more dispersed than with random ini- tialization (for example, in cases of the Korns 4 and Keijzer 16 functions). In cases where the results had small dissipation, they were generally worse than the results obtained by random initialization. For tree depth of 8, the results tend to improve in some cases, but still, the initialization with winging trees does not demonstrate a clear dominance over the GP results obtained by random initialization. However, the situation largely improves with the tree depth of 10. In this case, the initialization with winning trees leads significantly less dispersed results than all the other experiments. This is es- pecially evident in the Nguyen type functions, in which the dispersion is almost negligible compared to the other experiments. This suggests that for the depths of and 8, the extracted winning trees were too small to provide useful information that could more efficiently guide GP towards better solutions.
To evaluate the diversity of solutions, we can compare the obtained solutions semantically (i.e., if the resulting trees "look" the same) and functionally (if the trees give the same fitness value as output). For ten synthetic benchmarks, for 21 out of 30 cases, initialization with winning tress gives less semantically diverse solutions. Additionally, for 21 out of 30 cases, initialization with winning trees gives less functionally diverse solutions.
STABILITY AND DIVERSITY OF THE REAL-WORLD SOLUTIONS
Figure 3 shows the boxplot results for the real-world problems. These plots suggest that for these problems, the initialization with winning trees again provides several benefits. However, this again becomes evident only for the two larger tree sizes, as for the tree depth of 6 initialization with winning trees did not always perform better. The initialization with winning trees resulted in less dispersed and more stable results for the other two tree depths, confirming the results obtained for the synthetic benchmarks.
Finally, for 4 out of 15 cases, initialization with winning tress gives less semantically diverse solu- tions. For 6 out of 15 cases, initialization with winning trees gives less functionally diverse solutions.
13

---

Under review as a conference paper at ICLR 2022
Convergence on trair sot Airfll
Convargence on test set Airfol
Convengunsa
F
Sabowerr CL)
Vedlan
modiettoon
Mumber of evaluatirs
(a) Training set
(b) Test set
(c) Training set
Convergence on test Ccno
Curnerreent train Contrete
Consreeeence Corecnele
vaseeeiic Sabesirr 2,00
x
Foaree 3
Number eval adorrs
Number of com
Namber axaluntione
(d) Test set
(e) Training set
(f) Test set
Convergerse
Convergence on train set White wine
1.43
Number evaMattons
Number evoluations
Mamber avaluatern
(g) Training set
(h) Test set
ii) Training set
Convergence
1.23
1.55
0.22
0.63
(j) Test set
Figure 1: Algorithm convergence comparison for the real-world problems.
14

---

Under review as a conference paper at ICLR 2022
No 4
Cojpe
Origial
+
Radeen
Aeddin
Koms 12
Nauyon
Origer Siveds
kcs
10
dercoie All
Neuven
Ngupen 6
Original toress
Aweday
Npuyon 12
Grag1e Rlvees
Aechord
Figure 2: Synthetic problems, boxplot results.
15

---

Under review as a conference paper at ICLR 2022
Arfil
Orginammee
Orginaa
100
+
Bestee_c
detrenng
Besken
Concrcte
Red
Orggn etrest
D3
Orgina Tovess
45
Besden
Sendon,
Redday
Algorthr
Ago the
White wire
12
Anndons
Betmesst
Asaion
Sandee 10
30
Agr the
Figure 3: Real-world problems, boxplot results.
16


Reviews:
[{"review_id": "XhkuHYuYRkO", "reviewer": "Reviewer_Q7WW", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper presents several deficiencies in many aspects  -scientific, experimental, presentation- that render it unsuitable for publication. I will mention some of them that, in my opinion, are the most critical:\n\n- Main hypothesis. Authors attempt to draw an analogy between GP and DL frameworks, in regard to the LTH[1], such that they claim that a similar phenomenon might exists as well in GP. However, authors have a misconception of what the LTH is really about: The LTH is an attempt of DL researchers at explaining why gradient optimization methods work so well at tuning deep networks parameters. It is not that the solution is already embedded in the deep network, as authors of this paper seem to put forward, but rather that such dense networks create pathways for a gradient to move around harsh search landscapes, escaping local minima, and ultimately reach very good solutions. \n\n- Setting, related work and background. Authors set their contribution mostly around techniques aimed at tackling _bloat_ in GP trees, i.e. the phenomenon where GP trees being to grow in size, taking heavy tolls in evaluation costs, with minimal or null performance increase; and while it is true that authors present some pruning techniques, their method is also equally related to _restarting_ techniques and _multilayer_ GP models, where GP runs are executed serially with some modifications to initial populations. Multilayer GP is specially common in the area of feature extraction through GP; I suggest authors to review some works in the area [2,3], to attempt to draw a clear differentiation between their serialized GP model, and others already existing in the literature.\n\n- Experimental assessment. Authors carried several experiments in order to test their approach, both in artificial, as well as real world, datasets. However, the results they present are difficult to read and/or incomplete. Table I, for example, it is not clear what exactly those values are... the average of the MSE of the 50 runs... ? presumably. There is no indication neither in table title, footnote, nor in the main text body, of what are those values, if higher or lower is better, etc. Even if it is MSE, those values alone do not provide any information regarding the performance of each method compared, because there is no standard deviation reported. The table is also difficult to read, because there is no indication (typically with a bold font) which one of the approaches performed better. Similar issues are present in all other result tables presented.\n\n\n1. Frankle, J., & Carbin, M. (2018, September). The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks. In International Conference on Learning Representations.\n2. Lin, J. Y., Ke, H. R., Chien, B. C., & Yang, W. P. (2007). Designing a classifier by a layered multi-population genetic programming approach. Pattern Recognition, 40(8), 2211-2225.\n3. Lin, J. Y., Ke, H. R., Chien, B. C., & Yang, W. P. (2008). Classifier design with feature selection and feature extraction using layered genetic programming. Expert Systems with Applications, 34(2), 1384-1393.", "summary_of_the_paper": "On a technical level, the paper proposes two methods for Genetic Programming (GP) tree pruning, as well as a method for a population _restart_ that relies on both pruning methods. The aim of such approach is that in the second, or subsequent, GP runs, the GP algorithm starts from with an already-somewhat-good initial population of individuals that would allow GP to reach better solutions. On a scientific level, authors try to draw analogies between their approach, and recent advances in the deep learning (DL) community, regarding the Lottery Ticket Hypothesis (LTH). The authors complement their draft with a set of experimental evaluations on different standard datasets.", "summary_of_the_review": "The work is insufficient in many aspects in order to be considered for acceptance.\n- The main motivation behind the work seems unfounded due to a misunderstood concept from the deep learning area.\n- Related work discussion is lacking in regard to some relevant works to the method presented.\n- Experimental evidence is incomplete.\n\nMy recommendation is a clear reject-", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "TtNceR_H2RP", "reviewer": "Reviewer_W75E", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n- The paper is easy to follow.\n- The link with the lottery ticket hypothesis (LTH) is intriguing.\n- The improvement of the proposed idea for depth $\\geq 8$ is positive.\n\nWeaknesses\n- The paper doesn't seem to find the proposed winning trees very promising. Apart from the results in Table 1, the evidence seems to suggest the winning tree idea is not good?\n  - In particular, although it's interesting to link to the LTH, I feel the link is very weak.\n- Apart from the empirically study, the novelty on the method itself is limited: Only the pruning method is novel.\n- Presentation can be improved.\n  - All table titles should be more descriptive. E.g. You should describe what does the value in Table 1 mean.\n- A paper would be good to cite: DreamCoder: Growing generalizable, interpretable knowledge with wake-sleep Bayesian program learning\n  - It also has the idea of iterative learning of useful sub-expressions.", "summary_of_the_paper": "Inspired by (Frankle & Carbin, 2019), the paper proposes to find winning trees from a set of GP solutions as initialisation for another GP procedure.\nWinning tress are random sub-trees from GP solutions after simplification and a novel pruning strategy.\nResults show that such procedure can lead to better regression performance when the expression depth is larger or equal to 8.\nHowever, results also suggest that the discovered winning trees are specialised to specific tasks (i.e. fail to transfer) and cannot in general produce smaller trees.", "summary_of_the_review": "I found the motivation of this paper is weak as its link to the LTH is not clear.\nFurther, results don't seem to suggest the idea of winning tree is very useful.\nTherefore I suggest not accept this paper.\nIt would be interesting see if the author(s) can push this idea further (or implement in another manner) and show its usefulness - I'm looking forward to see more research on symbolic methods in the ML community.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IsihpgDCLMN", "reviewer": "Reviewer_77nm", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper presents good writing style and is easy to follow. It devotes however the whole 9 pages to written explanations and a few numeric tables of results, relegating fundamental information such as part of the algorithm and the entire results plots to the appendix. That is right, there is not a single figure in the paper. This is exacerbated by the experimental results being presented as 6 (six!) purely numerical tables accounting for roughly 3 full pages, with minimal discussion and almost absent captioning, which makes the experimental evaluation unnecessarily hard to assess. The contributions presented are themselves limited, which does not support this choice of presentation. Before I can vouch for its publication, I would require the authors to present the results in a more readable way which does not rely on Appendix material for interpretation or reproducibility.\nFrom a more technical perspective, the paper offers limited support for its arguments. Its main contributions are (i) a rule-based tree simplification method including both algebraic and pruning techniques, and (ii) an archive-based restart strategy.\nHowever, neither contribution is compared in the experimental results against the current state of the art, but only against standard GP. This offers a limited insight on its relative advantage, but no clear perspective to the method's actual applicability and utility.\n\nMain questions that need to be addressed by the authors (in the paper and with experimental results) prior to considering this work ready for publication:\n- What is the practical, empirical difference between the literature method of simplification with removal and the proposed substitution with an operation-neutral constant? I.e., what is the difference between removing a sub-tree from a node with e.g. a multiplication operator, and substituting it with a constant-one (1) leaf?\n- The pruning procedure accepts an arbitrary 15% degradation in fitness on the simplified tree, before looping on itself. In your experiments, is the 15% degradation a global budget over successive loops (i.e. the final simplified tree cannot be worse than 15% on the original tree) or a per-loop limit (which leads to a compounding effect as the solution can worsen by 15% per iteration)?\n- Can you highlight and discuss the performance degradation as depicted above across the Results tables? How did you come up with 15%? Is this hyperparameter robust to small variations?\n- Only aggregated final performance is presented, which limits our understanding of the learning process over time. Please include a standard plot of performance improvement over time for all methods.\n- A budget of 500'000 individuals is significant, especially on a low-dimensional benchmark of limited complexity, and with a mutation rate of 30%. How do the standard GP and your contribution fare against random guessing? I would expect a baseline of generating 500'000 individuals, and include the performance of the best-so-far over time in the comparison.\n- Figures 1 and 2 (Appendix) lack any discussion or interpretation. For example, what is happening with Nguyen 5 and 6 in Figure 2? Why the high variance for everyone but 0 for SubTreeInit? The paper lacks a proper discussion at this stage.\n- How does this technique stand against standard restart strategies? What about niching, as each run could be considered as a niche for the final restarted run? They are entirely missing from the literature review. Moreover, the global consensus on evaluating restart strategies is to maintain a standard useful budget of individual evaluation constant for all method, with the restart being able to reset as many times as seen fit. Instead the current experiments only restart once, and for \"fairness\" doubles the available fitness evaluations from 500'000 to 1'000'000 evaluations. What if the standard GP reaches convergence by 400'000? How would this be fair?\n- Building on that, it is clearly stated (Section 4.2) that the limit for convergence is 25'000 evaluations without improvement: assuming this means early termination if convergence is detected (as usual), what is the budget actually used by GP vs. the proposed contribution over the 50 runs?\n\nMinor points:\n- It is part of the authors' responsibilities to recognize which results are most compelling for their arguments and present those in a more digestible form. The corresponding plots from the Appendix should be moved to the main text. The full results tables could instead be moved to the Appendix.\n- In Section 5.2, I would relax the claim of \"it is evident that [...] improves the overall results\" from a qualitative statement to a quantitative statement (measured performance increase).\n- In Section 5.3 you mention \"a single constant node that is obtained after simplification\". Section 3.3 however states the minimal heights for trees being 2 after simplification. I believe this may be a misunderstanding, but it shows how the exposition is perceived as unnecessarily complicate, and a requirement for all data required for reproducibility to be found in a single place in a clear format (which I propose being another requirement for acceptance).", "summary_of_the_paper": "This paper presents two optimizations to standard GP: a tree pruning with introduction of operation-neutral nodes, and a restart strategy reusing a population of best trees from past runs. It presents results on a broad set of very simple regression problems.", "summary_of_the_review": "Let me state first that I fully support further research in evolutionary computation and especially genetic programming, which I believe could develop in a feasible alternative (even extension) to neural networks in real-world scenarios where access to labeled data is insufficient. This paper proposes an optimization to GP that could improve its performance, which is its main limiting factor to a broader application. Nonetheless I feel the present contributions to be (i) relatively minor (just simplification and restart), (ii) not particularly novel (again, just simplification and restart), and (iii) insufficiently supported by the experimental section (no baselines, no state of the art comparison, no clear exposition of the relevance of the datasets, extremely hard to read presentation). Overall the sensation is that of a work in progress, which may very possibly lead to a crucial contribution down the line, but is not yet ready for publication especially at a major conference.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "DI3Zy6zOkdQ", "reviewer": "Reviewer_mNLH", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The concept of winning trees in GP seems interesting, but this paper still suffers from the issues of 1) insufficient/unclear presentation and 2) limited experiments. My concerns include:\n1.\tIn section 3.2, the authors propose a novel pruning method for GP. But the effectiveness of this pruning method has not been verified via experiments. Especially, their approach allows pruning even if it reduces the fitness compared to the original expression. By doing so, although the obtained expression can be further simplified, the fitness of the expression might be dramatically deteriorated. In most cases, the solution accuracy, i.e., the fitness, is the main objective of method.\n2.\tIn the pruning method, the degraded limit is set to be 15%. It seems that this value is very larger, which will make the fitness of solutions deteriorate quickly. Is there any adaptive method to set this value, e.g., a simulated annealing way?\n3.\tThe winning tress should be strictly defined, rather than just giving its conceptual definition. Without a strict mathematical definition together with some theoretical analysis, it is difficult to fully understand this new concept. For example, it is unclear how many winning trees can be obtained by GP for a specific problem, and the existence of the winning tree can be guaranteed?  \n4.\tIt is also not very clear how to obtain a winning tree, and how a winning tree constrains on the fitness value and the tree size.\n5.\tThe proposed approach seems like the building blocks with restart search strategy. The advantages of the proposed approach comparing to other previous ones should be further highlighted.\n6.\tThe parameter settings in the experiments should be further clarified. Especially, it seems that the influence of winning trees on the performance of GP relies on the tree depths. Thus, it is better to give more experimental results by setting tree depths with more values, e.g., 12, 15, 20, etc.\n7.\tWhat kind of results in Tables are? Are they the fitness values (i.e., the mean squared errors) of the best solution?\n8.\tFrom the experimental results, e.g., those of Korns 12, it is hard to say winning trees can enable GP to find better expressions for regression problems, which significantly limit its practicability.\n9.\tSome minor revisions are needed, e.g., what’re WIW, WIR, WIW? In Algorithm 1, “P-?child” should be “P->child”.", "summary_of_the_paper": "This paper discusses the influence of simplification and pruning in GP for regression problems. A novel pruning method is presented, and a new concept termed as winning trees is proposed. Experiments are conducted based on ten one or two-dimensional synthetic symbolic regression problems and five real-world regression problems. Comparative results show that winning trees can help GP find better solutions in a smaller number of evaluations. ", "summary_of_the_review": "Although the idea seems interesting, this paper is not technically sound. Experimental results cannot fully support the main conclusion of this paper. Without a strict mathematical definition together with some theoretical analysis, it is difficult to fully understand the new concept of “winning trees” in GP.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper explores the hypothesis that bloat can be prevented in Genetic Programming by identifying "winning subtrees" from simplified solutions, and use these to seed new GP runs. This idea is connected with the lottery ticket hypothesis in deep learning.

Reviewer are unanimous that the paper as it stands is not ready to publish. One big issue is that the empirical results are not particularly good. Another is that the conceptual foundations of the paper, in particular the parallell to the lottery ticket hypothesis, might be flawed. Nevertheless, there is much interesting research to do in this direction.
Decision: Reject