With the demand for machine learning increasing, so does the demand for tools which make it easier to use. Automated machine learning (AutoML) tools have been developed to address this need, such as the Tree-Based Pipeline Optimization Tool (TPOT) which uses genetic programming to build optimal pipelines. We introduce Layered TPOT, a modi cation to TPOT which aims to create pipelines equally good as the original, but in signi cantly less time. This approach evaluates candidate pipelines on increasingly large subsets of the data according to their tness, using a modi ed evolutionary algorithm to allow for separate competition between pipelines trained on di erent sample sizes. Empirical evaluation shows that, on su ciently large datasets, Layered TPOT indeed nds better models faster.
The eld of Automated Machine Learning (AutoML) aims to automate many
of the tasks required to construct machine learning models, hence lowering the
barrier to entry and yielding better models, faster. AutoML methods typically
automate one or more steps in the creation of useful machine learning pipelines,
such as the selection of preprocessing or learning algorithms, hyperparameter
optimization, or a combination of them. A few methods even construct and
optimize entire pipelines, such as the Tree-based Pipeline Optimization Tool
(TPOT)[
In this paper, we introduce a novel improvement of TPOT, aimed at reducing the time needed to evaluate pipelines, without reducing the quality of the nal pipeline. Indeed, the most time-consuming part in the optimization process is evaluating the performance of candidate machine learning pipelines. In our modi cation, this time is reduced by initially evaluating the pipelines on a small subset of the data, and only allowing promising pipelines to be evaluated on the full dataset. In order to do this in a fair manner, modi cations to the evolutionary algorithm are implemented to prevent direct comparison between pipelines which are evaluated on di erent subsets of the data. As such, we aim to nd pipelines of similar quality in much less time, making the tool more accessible and practical by requiring less computational time. We call this improvement Layered TPOT (LTPOT).
This paper is organized as follows. First, we review related work in Sect. 2. Then, in Sect. 3, we discuss the proposed modi cation to TPOT in detail. Next, in Sect. 4, we lay out how LTPOT will be evaluated, discuss the results of these evaluations, and propose aspects of LTPOT which can be researched in future work. Finally, we conclude the study in Sect. 5. 2
The eld of AutoML is a culmination of work in the elds of algorithm selection, hyperparameter optimization and machine learning. Several AutoML systems support at least some form of automatic pipeline construction.
Auto-WEKA [
Auto-sklearn [
TPOT di ers from Auto-sklearn and Auto-WEKA by using an evolutionary algorithm instead of SMAC. Additionally, TPOT uses a tree-based structure to represent pipelines, and considers pipelines with any number of preprocessing steps. Hence, TPOT is not constrained in the number nor the order of preprocessing steps.
The main idea of LTPOT is to rst evaluate pipelines on a subset of the
data, to get an indication of whether or not the pipeline is promising relative
to other pipelines. This idea has been explored before, for example in
Samplebased Active Testing [
The use of subsets to evaluate machine learning con gurations is also used
in Hyperband [
To the best of our knowledge, however, it was never before used in combination with evolutionary algorithms for pipeline construction. 3
In this section, we describe the modi cations made to TPOT. First, we give a brief description of how TPOT constructs and optimizes machine learning pipelines. Then, we describe the Layered TPOT (LTPOT) structure and motivate its design. 3.1
To construct and optimize machine learning pipelines, TPOT uses tree-based
genetic programming [
Bernoulli
Naive Bayes Standard Scaler Dataset
Alpha = 1.0
The evolutionary algorithm then works by using these machine learning pipelines as their individuals. It will perform mutation, for example changing a hyperparameter or adding a preprocessing step, as well as crossover, by selecting two pipelines which share a primitive, which allows them to exchange subtrees or leaves. Finally, pipelines are evaluated and assigned a tness score, so that a selection procedure can determine which individuals should be in the next generation.
As mentioned earlier, in theory these pipeline trees could be arbitrarily large. However, very extensive machine learning pipelines are often undesirable. With more hyperparameters, long pipelines can be harder to tune, be more prone to over tting, hinder understanding of the nal model, and require more time to be evaluated, slowing down the optimization process.
Because of these reasons, we use a multiobjective optimization technique,
NSGA-II[
During the TPOT optimization process, most time is spent on evaluating machine learning pipelines. Every machine learning pipeline is evaluated on the full dataset, which can take a lot of time. Layered TPOT (LTPOT) aims to reduce the amount of pipelines evaluated on the entire dataset by doing a selection process, so that only the most promising pipelines need to be evaluated on the full dataset. It achieves this by evaluating pipelines on a small subset of the data, and only if a pipeline exhibits good performance on that subset it will be evaluated on more data.
Age-Layered Population To incorporate a fair evaluation of pipelines on
subsets gradually increasing in size, we designed a layered structure to separate
competition among individuals. In this, we were inspired by the Age-Layered
Population Structure (ALPS) [
Layers in LTPOT In LTPOT, we wish to evaluate pipelines on subsets of the data. However, the performance of a machine learning pipeline is in uenced by the amount of training data it receives. This means that when evaluating individuals on di erent subsets of the data, their performance cannot directly be compared to one another. Therefore, the individuals are segregated into layers.
At each layer, individuals will be evaluated on a subset of di erent size. The layers are ordered, such that in the rst layer the subset used to evaluate the individuals is the smallest, and every layer above that will increase the subset size. When an individual performs well in one layer, it will eventually be transferred to the next. This way, only the best pipelines will be evaluated on the entire dataset in the last layer. A visual overview of the structure and ow of LTPOT is given in Fig.2.
new population new new new
N samples top k rest rest top k rest top k Correlation of performance between layers In the extreme, the selection procedure implicitly assumes that the relative performance of two pipelines is the same when evaluated on a subset of the dataset as it is on the entire dataset. However, this assumption does not always hold. The learning curves for two pipelines may cross, meaning that one pipeline performs better after being trained on a small subset of the data, while the other performs better when trained on the full dataset. Generally speaking, as the pipelines are evaluated on more data, the relative performance correlates more strongly with the relative performance obtained when they are trained on the entire dataset. This is why our design will evaluate the pipelines on gradually larger subsets of data, so that when a pipeline performs worse than expected as the dataset increases, it need not be evaluated on bigger datasets. Unfortunately, in the case where a pipeline has poor performance on a small subset, but good performance on the entire dataset, LTPOT will not pick up this pipeline.
We set up an experiment to verify whether or not there is indeed a correlation
between the performance of a pipeline on a sample of the dataset and its
performance on the entire dataset. In this experiment, we evaluated 50 pipelines
on 12 datasets with ten times 10-fold cross-validation, with various samples
sizes of the dataset as well as the entire dataset. All datasets were part of the
Penn Machine Learning Benchmark (PMLB) [
dataset satimage clean2 ann-thyroid twonorm mushroom agaricus-lepiota coil2000 pendigits nursery magic letter krkopt instances features
In Table 1 the Spearman -values are displayed, that signify the correlation between the ranking of pipelines trained on a sample of the dataset, and the ranking of pipelines when trained on the entire dataset. The p-values are omitted because in all cases they are smaller than 0:0001 and all correlations are thus signi cant. From Table 1 we see that that there is a positive correlation between the rankings for all sample sizes and datasets, and the correlation gets stronger as the sample size gets closer to the full dataset size.
We experimented with various curve tting methods to extrapolate the
learning curves of pipelines so that crossing learning curves might be predicted earlier,
but they did not improve the results. In future work the use of meta-learning for
learning curve extrapolation, such as in [
We will now give a more in-depth break down of the algorithm used in LTPOT. Algorithm 1 shows the core of the layered algorithm LayeredEA, and Algorithm 2 gives descriptions of the subroutines called from LayeredEA. Algorithm 1 Layered Evolutionary Algorithm . Denote the number of layers.
. Denote population size.
Selecting parameter values Before calling LayeredEA, the number of layers as well as their sample size is de ned. The sample size of a layer dictates how many instances are sampled from the dataset, to create the subset that the pipelines in that layer will be evaluated on. The subset is created by strati ed Algorithm 2 Functions called in Layered EA 1: function VarOr(P opulation; N )
Performs mutation and crossover on the individuals in P opulation, creating N new individuals.
end function 2: function Evaluate(P opulation; s; D)
Evaluates each individual on a subset of dataset D, created by taking s instances by strati ed sampling. Individuals are evaluated based on 3-fold CV accuracy and number of components in the pipeline. Results are saved as attributes of individuals.3 end function 3: function Selection(P opulation; p)
Creates pareto-fronts based on the accuracy-pipeline complexity trade-o . Then takes the rst p individuals after ordering the population by which pareto-front they are in (individuals in the rst front come rst).
end function 4: function Top(P opulation; k)
Returns the k best individuals of the population, by constructing a pareto-front based on the accuracy-pipeline complexity trade-o .
end function 5: function NewPopulation(P )
Creates a new population of P individuals.
end function uniform random sampling without replacement, and pipelines will be evaluated on this subset with 5-fold cross-validation. In this study, the sample sizes used in each layer are dictated by the size of the dataset. Let the dataset contain N instances, then the nal layer will always train on the entire dataset, and each subsequent layer will use half of the data the layer above did. In this study, the number of layers used is 4, for every dataset. The respective sample sizes used at each layer are thus N8 , N4 , N2 and N . In this paper we use the term higher layer loosely to denote layers which sample more of the entire dataset (i.e. the layer with sample size N2 is higher than the layer with sample size N4 ).
There are two ways to specify for how long the main loop of lines 7 through 20 should run: a set amount of generations G, or an amount of time. We chose not to work with a speci c number of generations G, but instead let the main loop in lines 7 through 20 run for eight hours. For parameter g, the amount of generations between transfer, we experimented with values 2 and 16. With a g value of 2, LTPOT acts almost as a lter, allowing only very little optimization in early layers. A value of 16, however, allows many generations of early optimization, before passing individuals through to the next layer.
For the nal part of the initialization, a population of size P is generated randomly.
LayeredEA When calling LayeredEA, as shown in Algorithm 1, the rst step is to denote constants based on the input, speci cally the number of layers M (line 1) and the size of the population P (line 2), as well assigning the initial population to the rst layer (line 4) and marking all other layers as empty (line 5).
Then, the evolutionary algorithm will start iterating through the generations (line 6-20), at each generation again progressing the evolutionary algorithm in each layer (line 7-13) and then if required transferring individuals from one layer to the next (line 14-19).
Progressing the evolutionary algorithm in each layer (line 7-13), only happens for layers which are active. This means that there must be a population in the layer ( rst clause on line 8), which it may not yet have if not enough transfers have taken place yet. Additionally, layers which evaluate on more data are not active every generation (second clause on line 8), this is motivated below.
When progressing the evolutionary algorithm, it executes the same steps as TPOT would. First, a new population is created from the individuals evaluated during the last generation in the same layer, by performing mutation and crossover (line 9). However, every time a layer is passed new individuals from a previous layer, as well as in the very rst generation, the provided population is taken as is without creating o spring.4 The new individuals are then evaluated based on the sample of the data as de ned by their layer (line 10). Finally, based on the Pareto-front of the trade-o between the performance score of the pipeline as well as the pipeline length, the best individuals are picked among the new 4 This is not incorporated in the pseudo-code of algorithm 1, to keep the general structure clear. individuals as well as last generation's (line 11). Then, every g generations, the best individuals from each layer get passed to the next one. In our con guration we chose to transfer half of the layer's population.
The nal pipeline chosen by LTPOT is the pipeline which has the best score in the highest layer (line 21).
Optimizations There are a few scenario's that either require some additional clari cation, or deviate from the above algorithm:
The rst time a layer receives individuals from the layer before it, the selection procedure will oversample from this population so that the population in the layer will also grow to size P (line 11). This is done so that in subsequent generations, more variations of the original pipelines will exist, allowing for a better search for optimal pipelines.
Secondly, if LTPOT runs for a speci ed amount of generations, layers will be turned o whenever their population can no longer reach the highest layer. For example, let LTPOT be con gured with 4 layers. When LTPOT is less than 3 g generations away from completion, any individual in the lowest layer will never reach the highest layer, thus rendering any results obtained in this layer useless. Whenever this happens, the respective layer will no longer have their individuals evaluated or transferred to a next layer.
Next, there is the earlier mentioned restriction on activating layers as shown in the second clause on line 8. LTPOT has a selection process in place for which pipelines will be evaluated on the entire dataset. This means that at higher layers, the pipelines in the population are likely already quite good. Because of these two factors, we want to limit the exploration in higher layers. To do this, instead of running the evolutionary algorithm in each layer every generation, higher layers can be turned o for some generations. In this study, for a layered structure with M layers, layer l is progressed for min(2(M l+1); g) generations every g generations, with l 2 f1; ; M g. This is demonstrated with g = 12 and M = 4 in Fig.3, and checked in the second clause on line 8. We have not yet evaluated if this leads to signi cant improvements.
Finally, to prevent any one pipeline from halting the algorithm, a pipeline's evaluation is automatically stopped if it exceeds a given time limit. If the evaluation is stopped this way, the pipeline is marked as failure and will not be considered as parent for the next generation. This behavior is present in the original TPOT, and adopted to LTPOT by further decreasing the time limit by layer. In the top layer, each individual is allowed the same evaluation time as it would in TPOT. However, for lower layers, the time allowed is decreased quadratically proportional to the sample size (a layer with half the data gets a fourth of the time per individual).
Layer 1
Layer 2
Layer 3
Layer 4
On Off
The goal of LTPOT is to nd pipelines at least as good as TPOT's, but in less time. This also means that, given the same amount of time, LTPOT could very well nd better pipelines. To assess whether or not this is achieved, we will evaluate LTPOT in three ways.
First, we want to evaluate if, given the same amount of time, LTPOT will
outperform TPOT when their best found pipelines are compared. To do this, a
ranking is constructed between TPOT and LTPOT for each dataset over time,
by ranking the performance of the best pipeline found so far at regular time
intervals. We omit a comparison to Random Search, as TPOT compared favorably
to Random Search in earlier work [
Secondly, to quantify how much faster LTPOT is, we compare the time needed for LTPOT to nd a pipeline at least as good as the best pipeline found by TPOT. We then compare it to the time TPOT needs to nd this pipeline.
Finally, we will also compare the Area Under the Receiver Operating Characteristic curve (AUROC) of the nal pipelines found by each method, so we can quantify the di erence in model quality between the methods. 4.2
We compare LTPOT to the original TPOT by evaluating both on a selection of
18 large datasets. We speci cally chose larger datasets so that there will be a
distinct di erence in time needed to evaluate individuals on the entire dataset
versus just a subset. All datasets in the selection contain at least one hundred
thousand instances, though most contain exactly one million. The selection
includes pseudo-arti cial datasets described in [
As described earlier, there are many hyperparameters with which to tune LTPOT. In this study, we only experiment with g, the amount of generations between transfer. The choices for g will be 2 and 16, and these con gurations will be referred to as LTPOT-2 and LTPOT-16, respectively. This is meant to give insight in the e ectiveness of two functions of LTPOT: ltering and early optimization. For LTPOT-2, layers act almost solely as a lter, by passing the best individuals to the next layer every other iteration, not much optimization takes place in lower layers, but it does allow for the early discarding of pipelines which seem to perform poorly. With LTPOT-16, we instead see that a lot of optimization can take place based on results found in lower layers, as relatively more time is spent evaluating and improving individuals in lower layers compared to LTPOT-2. In other words, LTPOT-2's rst layer allows for more early exploration, while LTPOT-16's rst layer is more focused on exploitation.
The amount of individuals transferred, k, will be set to 15, which is half of the total population size P = 30. Each LTPOT con guration, as well as TPOT, is run nine times per dataset, each time with a di erent random seed, guaranteeing a di erent initial population and subsequent choices for crossover and mutation. Each run set to last 8 hours, but each individual pipeline may only be evaluated for at most 10 minutes. We explored di erent values for P and di erent amounts of evaluation time per individual, while keeping the total run time constant at 8 hours, and found that for the chosen datasets these values strike a balance between having a diverse enough population and being able to evaluate enough generations. 4.3
First, we compare the various con gurations by their average rank over time,
which can be seen in Fig. 4. In this gure, for each con guration, for every
dataset and seed, the best found pipelines so far are ranked against each other
every minute. For each method, the average Friedman rank [
In Fig. 4, we see that LTPOT on average achieves the best scores throughout the entire 8 hour period. LTPOT-16 starts by outperforming LTPOT-2 slightly, but as time goes on its relative performance drops, even being surpassed by TPOT. From this, it seems that while LTPOT works well as a lter, optimization in early layers does not pay o beyond the early stages. Thus, a lower value for g is better based on these results. Furthermore, we see that towards the end TPOT is decisively improving over LTPOT-16, but only very slowly over LTPOT-2, as the average rank of LTPOT-2 increases only very slowly.
A di erent rank does not necessarily mean the found model performance di ers a lot. To clarify this, we look at the di erence in AUROC by dataset per con guration, as seen for 9 of 18 datasets in Fig. 5.6
In Fig. 5 we show a boxplot that describes the distribution of AUROC scores of the nal pipelines by each method. No single method is dominant over the others, and di erences in AUROC scores are small for almost all datasets. Using a student t-test, we determined that there is no statistically signi cant di erence (p < 0:05) between the nal pipelines (after the full 8 hour time budget).
However, looking at the average ranking by con guration in Fig. 4, we see that under smaller time budgets LTPOT-2 often nds pipelines which are better than TPOT. In this scenario, it is interesting to see how much time LTPOT needs to nd a pipeline at least as good as the best pipeline TPOT found. We compared LTPOT-2 to TPOT for each dataset and seed, and looked at how long it took for the method which found the best pipeline to nd a pipeline at least as good as the best found pipeline by the other method. Figure 6 shows the time di erence (in minutes) between nding these equally good pipelines. Positive values indicate that LTPOT is faster. Yellow distributions correspond to seeds where LTPOT eventually found the best pipeline, and show how much sooner LTPOT found a pipeline at least as good as the best pipeline of TPOT. 6 A similar gure for the other 9 datasets can be found in Appendix A.
Blue distributions correspond to cases where TPOT eventually found the best pipeline, and show how much later TPOT found a pipeline at least as good as LTPOT's best.
In general, when LTPOT nds the best pipeline, it nds a pipeline at least as good as TPOT's best pipeline much sooner. In particular for LTPOT-16 we see that it often is at least 200 minutes faster. Even in the cases where TPOT eventually nds the best pipelines, we see that it often nds a pipeline at least as good as LTPOT's best only after LTPOT already found it. This again is especially true for LTPOT-16, where almost all yellow distributions are entirely positive.
However, even when one method nds a pipeline at least as good as the other method's eventual best pipeline, it can still be the case that the eventual worst method at that same time already has quite a good pipeline. Therefore, we compare the performance of the best pipeline of each method found at time t, where time t is the time where the best method nds a pipeline at least as good as the eventual best pipeline of the worst method. Between 18 datasets and 9 seeds, there are 162 comparisons between TPOT and LTPOT-2 or LTPOT-16. The comparison in AUROC at time t is shown in Figure 7.
We see that when TPOT nds a pipeline at least as good as LTPOT's best, in most cases it does so when LTPOT already has found a pipeline at most 11a6ir9lines BN1G1 s8p0ect_test B1N18G2 adult BNG1 2m0ushroComlick_p1r2e1d7iction_smaBlN1G24 credita BN1G26 creditg B1N31G sick B1N3G2 sonar BNG1 3s5pambase B1N3G9 trains Fig. 7: Shows the AUROC di erence at time t, which is the time the best method (color coded) nds a pipeline at least as good as the other method will nd. 0.01 AUROC worse. However, when LTPOT nds a pipeline at least as good as TPOT's best, TPOT has relatively worse pipelines more often, and in some cases as much as over 0.2 AUROC worse.
From this we conclude that in many cases LTPOT nds good pipelines faster. While LTPOT-2 does not always nd the best pipeline, when it doesn't, it nds comparable pipelines at least as quickly as TPOT. LTPOT-16 nds comparable pipelines even quicker, although it becomes less competitive under larger time budgets. The structure of Layered TPOT allows for more hyperparameters to be tuned, and their e ect remains unexplored at this point. The number of layers as well as the e ect of their granularity could possibly be tuned to the dataset. Whether or not to turn o higher layers, and with which frequency, should be explored as well. The amount of individuals to transfer between layers may also change how quickly higher layers can optimize pipelines. The choice of the amount of generations before transfer, g, will in uence how much optimization will be done in the lower layers. Perhaps these parameters should change over time in a single run. All of these choices come in addition to the hyperparameters already available for TPOT, such as the population size, mutation rate and crossover rate.
Finally, there are possible changes not yet captured in hyperparameters. For instance, it might be better to favor crossover over mutation in higher layers, so that the focus of exploration shifts to combining promising pipelines in higher layers. It could be that having a big population in the higher layers is unnecessary, and shrinking population size there might yield similar results in a faster time frame. Currently, the way to evaluate individuals quickly is to sample a number of instances of the data. Instead, one could create a subset by selecting features, or apply compression techniques to represent the data. We will explore these aspects in subsequent work.
Results of this study will be made available on OpenML7, and the code for Layered TPOT can be found on Github8. 5
In this paper we presented an extension to TPOT called Layered TPOT. In the extension, instead of evaluating each pipeline on all data, only pipelines which have shown good results on subsets of the data are evaluated on all data. It does this by introducing layers. In each layer a distinct group of individuals is subject to the evolutionary algorithm, but individuals are only evaluated on a subset of the data as de ned by the layer. Each subsequent layer will evaluate 7 www.openml.org 8 https://github.com/PG-TUe/tpot/tree/layered the individuals on more data, and if an individual performs well in one layer, it will be transferred to the next, to be trained on more data and compete with other promising pipelines trained on the same subset size.
To determine the usefulness of LTPOT, two con gurations have been compared to TPOT, on a selection of 18 large datasets. The results showed that LTPOT is not strictly better than TPOT, but it often nds good pipelines much faster, and under smaller time budgets, it outperforms TPOT on average. Moreover, LTPOT allows for a lot of exibility in the con guration of its structure, and the e ects of changes to these con gurations remain to be explored.
Below is a gure similar to Figure5 for the other 9 datasets in the benchmark. 126 77 1502 140 0.296 0.294 C0.292 RO0.290 U0.288 A 0.286 1 0.284 0.282 0.125 C O0.120 R U A0.115 10.110 0.105 0.0085 C0.0080 RO0.0075 U0.0070 A 10.0065 0.0060 0.0055 0 50 100 150 200 250 300 350 400 450 time (minutes) 0 100 400
500 0 100 400
500 0 100 400
500 CO0.090 R U A0.085 1 0.054 0.053 C0.052 RO0.051 U0.050 A 0.049 1 0.048 0.047 CO0.06 RU0.05 0.0042 C O0.0041 R U A0.0040 10.0039 0.328 0 100 400
500 0 100 400
500 0 100 400
500 Fig. 10: Shows per dataset per seed per method when the best pipeline was found, and its '1-AUROC' score.