Hmida Hmida

Sana Ben Hamida

Amel Borgi

Marta Rukoz

Sampling Methods in Genetic Programming Learners from Large Datasets: A Comparative Study

The amount of available data for data mining and knowledge discovery continue to grow very fast with the era of Big Data. Genetic Programming algorithms, that are efficient machine learning techniques, are face up to a new challenge that is to deal with the mass of the provided data. Active Sampling, already used for Active Learning, might be a good solution to improve the EA training from very big data sets. This paper present a review of sampling techniques already used with active GP learner and discuss their ability to improve the GP training from very big data sets. A method in each sampling strategy is implemented and applied on the KDD problem using very close parameters. Experimental results show that sampling methods outperforms results obtained with full dataset but some of them cannot be scaled to large datasets.

Introduction

Genetic Programming GP [START_REF] Koza | Genetic programming: On the programming of computers by means of natural selection[END_REF] is an Evolutionary algorithm considered as a universal solving problem method. This paradigm have shown its potential by reinventing previously invented patents and by creating new patentable inventions.

Applied to supervised learning and classification problems, GP generates a population of classifiers (genetic programs) by means of genetic operators. The performance of each classifier is measured by a fitness function that needs the evaluation (execution) of every program against the complete training dataset. This leads to a computational overhead increased specially with large datasets and proportional to the product of the number of instances in the dataset, the population size and the number of generations that will be carried out during the evolution process. Otherwise, using the full learning data might be impossible when the input data doesn't fit within the main memory which is often the case with Big Datasets.

The problem of reducing this calculation cost can be addressed mainly with two approaches:

-Speeding evaluation by means of hardware acceleration and parallelization.

-Reducing the number of evaluations by selecting a training subset much smaller than the entire dataset: training set sampling.

A large variety of sampling methods was investigated in many classification problems using GP and demonstrated a success comparing to the use of entire training set [START_REF] Curry | Scaling genetic programming to large datasets using hierarchical dynamic subset selection[END_REF][START_REF] Gathercole | An Investigation of Supervised Learning in Genetic Programming[END_REF][START_REF] Iba | Bagging, boosting, and bloating in genetic programming[END_REF][START_REF] Zhang | Genetic programming with incremental data inheritance[END_REF][START_REF] Lasarczyk | Dynamic subset selection based on a fitness case topology[END_REF]. However, the results obtained from the earlier experiments cannot be cross-compared since they are based on different GP variants (Linear GP, Standard GP, Cartesian GP), different datasets and different GP parameters.

Large datasets are nowadays abundant, they are needed to reach an accurate classifier. Nevertheless, the increasing size heightens the calculation time problem of GP algorithms.

In this paper, we will try to put a representative set of sampling methods in very close experimental conditions, in order to show their impact on learning speed and accuracy.

Sampling Methods: a Review

The main objective of the studied sampling methods, in this paper, is to reduce the original training dataset size by substituting it with a representative subset much smaller and hence the evaluation cost of GP algorithm. Two major classes of sampling techniques can be layed out : static sampling and dynamic sampling.

Static Sampling Methods

With static sampling, the learner obtains all the input training set at once and stills unmodified across the learning process. This type of sampling creates a subset of patterns with a given size from the training dataset. These patterns are selected independently from the training process in which they will be used. Some methods use a unique subset during all GP runs. Other ones can assign different subsets for each run. Hereafter, some techniques used to build this subset.

Fixed Sampling

The Historical Subset Selection HSS (Gathercole and Ross 1994) [START_REF] Gathercole | Dynamic training subset selection for supervised learning in genetic programming[END_REF] gathers misclassified instances from previous GP runs (seven for example) at each generation using the best individual of population. The subset contains not only difficult cases but also easy ones that are collected at earlier generations. These preliminary runs are conducted using the full dataset.

Boosting This machine learning technique was applied to GP in [START_REF] Iba | Bagging, boosting, and bloating in genetic programming[END_REF][START_REF] Paris | Artificial Evolution: 5th International Conference, Evolution Artificielle[END_REF] but not as a speeding method but rather to improve GP quality by evolving several subpopulations with different training sets generated by selecting the base dataset with replacement. Each training pattern has a weight reflecting his difficulty and most difficult cases may appear more often since the target size is equal to the original dataset size.

Dynamic Sampling Methods

Dynamic sampling methods are also referred to as active data selection methods as derived from Active Learning [START_REF] Cohn | Improving generalization with active learning[END_REF]. The underlying sampling techniques are tightly related to the learning process evolution. Generally, it depends on a particular feature like unresolved or difficult cases, the number of generations carried out, the fitness...

Random Sampling

The selection of fitness cases is based on a uniform probability among the training subset. This stochastic selection helps to reduce any bias within the full dataset on evolution. In Random Subset Selection RSS [START_REF] Gathercole | Dynamic training subset selection for supervised learning in genetic programming[END_REF], at each generation g, the probability of selecting any case i is equal to P i (g) such that :

∀i

: 1 ≤ i ≤ T, P i (g) = S T . ( 1
)
where T is the size of the full dataset and S is the target subset size. The sampled subset have a fluctuating size around S. Fixed Random Selection (FRS) [START_REF] Zhang | Genetic programming with incremental data inheritance[END_REF] is a very similar method with a fixed number of cases selected at every generation. Stochastic Sampling SS (Nordin and Banzhaf 1997) [START_REF] Nordin | An on-line method to evolve behavior and to control a miniature robot in real time with genetic programming[END_REF] is another method using the same probabilistic selection to construct subsets for each individual per generation.

The single parameter of this category of sampling is the subset size, whether a crisp or flexible target, is set like other GP parameters (population size, crossover probability, . . . ) and most likely by several GP runs.

Weighted Sampling. The selection of fitness cases that will be added to the subset is based on a calculated weight which is a non uniform probability that measures how much a pattern is worthy and can help to sharpen the population quality. It is highly inspired by boosting technique in machine learning field, originally used to improve accuracy of weak learners. The very first algorithm in this category is Dynamic Subset Selection DSS [START_REF] Gathercole | Dynamic training subset selection for supervised learning in genetic programming[END_REF][START_REF] Gathercole | Small populations over many generations can beat large populations over few generations in genetic programming[END_REF][START_REF] Gathercole | An Investigation of Supervised Learning in Genetic Programming[END_REF]. This algorithm is intended to preserve training set consistency while alleviating its size by keeping only the d ifficult cases with ones not selected for several generations. Each dataset record is assigned a difficulty degree D i (g) and an age A i (g) starting with 0 at first generation and updated at every generation. The difficulty is incremented per one individual misclassification and reset to 0 if the fitness case is selected. The age is equal to the number of generations since last selection, so it is incremented when the fitness case has not been selected and reset to 0 otherwise. The resulting weight W of the i th case is calculated with this sum:

∀i : 1 ≤ i ≤ T, W i (g) = D i (g) d + A i (g) a .
(

) 2
where d is the difficulty exponent and a is the age exponent. The selection probability is biased by fitness case difficulty and age:

∀i : 1 ≤ i ≤ T, P i (g) = P i (g) * S T j=1 W j (g) . (3)
DSS needs three parameters to be tuned: difficulty exponent, age exponent and target size. Gathercole [START_REF] Gathercole | Dynamic training subset selection for supervised learning in genetic programming[END_REF] tried different subset sizes, and different population sizes with The thyroid classification problem3 using a full training set size of 3772 . With 10000 individuals DSS realizes better results than neural networks. DSS reduced evaluations by 20% whilst obtained similar classifiers.

Hierarchical Sampling. This kind of sampling is based on multiple levels of sampling methods inspired by the concept of a memory hierarchy. It combines several sampling algorithms that are applied in different levels.

RSS-DSS and DSS-DSS. Robert Curry and Malcom Heywood conceived an extension to DSS algorithm into a 3 levels hierarchy [START_REF] Curry | Towards efficient training on large datasets for genetic programming[END_REF]. At level 0, the dataset was first partitioned into blocks that were sufficiently small to reside within RAM alone. Then, at level 1, blocks were then chosen from this partition based on RSS or DSS. Finally, at level 2, the selected block is considered as the full datset on which DSS was applied for several rounds. Depending on the level BB-DSS. An extension to this work is made in [START_REF] Curry | Scaling genetic programming to large datasets using hierarchical dynamic subset selection[END_REF] with the Balanced Block DSS by altering mainly the level 0 block selection with the goal of obtaining a balanced block in level 1. A balanced block which does not reflect the original datset classes' distribution but a fixed ratio for each class regardless of their original ratios. At level 0, the full dataset is sorted and divided into separate class partitions. To create a level 1 block, one partition per class will be used.

I b (i) = I max * E b (i -1). (4)
The size of class partition depends on the level 1 block size and the class ratio.

For a block size equal to 1000 with 2 classes having respectively 25% and 75% ratios, class partition sizes will be respectively 250 and 750. To apply DSS on partitions, partition difficulty and age are defined to calculate partition weight and selection probability [START_REF] Curry | Scaling genetic programming to large datasets using hierarchical dynamic subset selection[END_REF]. BB-DSS was compared to RSS-DSS and CasGP4 against different datasets : Adult, Census, Shuttle and KDD'99 3 . Experimental results showed that Balanced Block algorithm is able to approach the classification performance of the CasGP algorithm, whilst retaining the computational speedup of the original RSS-DSS algorithm.

Incremental Sampling. The training subset starts with a few cases and acquires more cases at every generation to reach the full subset size.

Zhang [START_REF] Zhang | Genetic programming with incremental data inheritance[END_REF][START_REF] Zhang | Genetic Programming with Active Data Selection[END_REF] proposes to perform a uniform data crossover simultaneously with genetic programs evolution. Data crossover means that when crossover operation is applied to genetic programs to produce new programs, their subsets are crossed to obtain new offspring subsets inducing data inheritance through generations. This helps to preserve the knowledge acquired by the parents. This method called Incremental Data Inheritance IDI starts with n 0 sized subsets, and increases by λ at every generation with respect to an import rate depending on a third parameter ρ. In addition to that Zhang uses an Adaptive Fitness Function varying from an individual to another [START_REF] Zhang | Genetic programming with incremental data inheritance[END_REF]. This method is applied to the evolution of collective behaviors for multiple robotic agents [START_REF] Zhang | Genetic Programming with Active Data Selection[END_REF] and was compared to the standard GP and GP with Incremental Random Selection (IRS) [START_REF] Zhang | Genetic Programming with Active Data Selection[END_REF] with 100 training cases. In a second study [START_REF] Zhang | Genetic programming with incremental data inheritance[END_REF], IDI was faced to full dataset and FRS in a context of time series prediction problem. Experimental evidence supports that evolving programs on an incrementally selected subset of fitness cases can significantly reduce the fitness evaluation time without sacrificing generalization accuracy of the evolved programs.

Topology Based Sampling. Inspired by the idea that structure influences the efficiency of heuristics working on it [START_REF] Hogg | Refining the phase transition in combinatorial search[END_REF][START_REF] Walsh | Search in a small world[END_REF], this method consists at building a topology of the problem from the knowledge acquired by individuals about fitness cases. Lazarczyk [START_REF] Lasarczyk | Dynamic subset selection based on a fitness case topology[END_REF] suggests a Fitness case Topology Based Sampling TBS in which relationship between fitness cases in the training set is represented by an undirected weighted graph. Vertices are fitness cases and edges have a weight measuring a similarity or a distance induced from individuals performance. Then, cases having a tight relationship with respect to a threshold cannot be selected together in the same subset assuming that they have an equivalent difficulty for the population. Edge values start at 0 and are updated after evaluation phase by increasing the weight of all edges between solved cases by each individual and decreasing the weight of all edges by a loss rate λ. This algorithm uses a unique subset for all the individuals renewed each generation after updating the topology graph. The TBS has the following steps:

1. Empty the set of selected fitness cases and initialize the candidate set with all fitness cases. 2. while there are more candidate fitness cases and the target subset size not reached do: (a) Select randomly a fitness case into the subset from the set of candidate fitness cases (b) remove the selected case and all fitness cases connected to it with an edge weight exceeding the threshold.

The threshold is calculated during evolution process to have a value adapted to the current topology. The threshold must not be too high or too low. In the first case, there is no exclusion and TBS is equivalent to Stochastic Sampling. In the second case, very few cases are selected and the target size could not be reached. Threshold is calcultaed using a binary-search type algorithm. Experimental results on classification problems (intertwined spirals [START_REF] Lang | Learning to tell two spirals apart[END_REF] and the Thyroid problems) demonstrated improvements in mean fitness value through generations compared to DSS and SSS. However, the additional computational cost of TBS caused by the threshold calculation algorithm and the topology update has not been measured. Moreover, this method has not been tested on a large dataset.

Other Sampling Techniques. Rational Allocation of Trials RAT is an algorithm that allocates fitness cases only to those individuals for which the cost of evaluating another fitness case is out weighed by the expected utility that the new information will provide. Although, it is a proven speed up mechanism and leads to a reduced and varying number of fitness cases per individual, it's not a training subset selection method -in my opinion-since it does not select cases according to a certain probability but use a minimal set of fitness cases for evaluation and then decides for each individual whether to carry on evaluation with the next fitness case according to the probability that they might win some tournament that they are losing or lose some tournament they are winning.

Balanced sampling [START_REF] Hunt | Sampling methods in genetic programming for classification with unbalanced data[END_REF] is a method aiming to improve classifiers accuracy by correcting the original dataset imbalance within majority and minority class instances. It has some methods based on the minority class size and thus reduce the number of instances like the methods studied in this paper. The following sampling methods are used with GP:

-Static Balanced Sampling: selects cases with uniform probability from each class without replacement until obtaining a balanced subset with equal number of majority and minority class instances of the desired size at every generation. -Basic Under-sampling: select all minority class instances and then an equal number from majority class randomly. -Basic Over-sampling: select all majority class instances and then an equal number from minority class randomly with replacement. -Under-sampling A/B: Multiple balanced samples are created at each generation with Basic under-sampling method. At every generation, all individuals are evaluated against all of the sample sets and are attributed the average fitness across all the sample sets (and the minimum fitness for version B). -Over-sampling A/B: Creates several balanced samples using Basic Oversampling. The final fitness is the average on all subsets (and the minimum fitness for version B).

3 Design Issues for the Comparative Study

3.1 Cartesian GP.
CGP is a form of GP, proposed by Julian Miller [START_REF] Miller | Cartesian genetic programming[END_REF], that represent genetic programs as directed acyclic graphs and mostly inspired by digital circuits called FPGA. In this graph, nodes representing functions many inputs and one output, and are layed into two dimensional matrix very similar to neural networks. This form of GP has the following advantages:

-Unlike trees, it allows more than one path between any pair of nodes permitting the reuse of previous results. -Highly competitive with other GP methods.

-Does not bloat.

-Is easy to implement.

-Can have multiple outputs and then solve many types of problems (eg. classification problems).

CGP parameters. The implementation of CGP involves different parameters that determine its efficiency. A common approach in tuning GP is to undertake a series of trials to make parameter choices for the final GP runs. Since the main objective is to compare sampling methods in closely context, this tuning procedure is not fully investigated.s The final design of CGP parameters used in this work is summarized in Table 1.

Implemented Sampling Methods

RSS and DSS were implemented identically to their author's description. The remaining methods have been altered as described hereafter.

BRSS. This method is Balanced RSS in which the subset generated by RSS reflects the original dataset classes' frequencies. The number of each class patterns is calculated with respect to the target size. IDI. Since we use a fixed subset grow increment, the full dataset size is not reached at the last generation.

TBS. We calculated the threshold applying a more simpler steps:

1. Use the lowest edge weight as the initial threshold to have the smallest possible subset. 2. Repeat until target size reached.

T P R = T rue P ositives T rue P ositives + F alse N egatives .

F P R = F alse P ositives F alse P ositives + T rue N egatives .

The training time is the amount of elapsed seconds between the first and the last generation (see Table 1 for the number of generations ).

Experimental Design

4.1 Evolutionary Framework ECJ. Among several evolutionary computation frameworks, Sean Luke's ECJ [START_REF] Luke | Ecj, a java-based evolutionary computation research system[END_REF] was used in this work to implement and test the sampling algorithms. ECJ implements evolutionary algorithms like GP, Evolution Strategies, Genetic Algorithms... It's an open source framework written in Java, offering the most complete range of GP representations (Koza, linear, grammatical, ...). This framework provides a very flexible API using parameter files well documented in the ECJ owner's manual. ECJ is an active project at George Mason University's Evolutionary Computation Laboratory having frequent releases 5 and benefit of many contribution packages as the one used here for implementing Cartesian GP developed by David Oranchak [START_REF]CGP: Cartesian gp website[END_REF].

Learning Data

We used here a large dataset, which was firstly created for the competition held at the Fifth International Conference on Knowledge Discovery and Data Mining KDD-99 and is about intrusion detection problem. The original training dataset contains 5 million lines conveying data about connections from the simulated traffic and their labels. Another set was called corrected set, constructed with the same way is used as test dataset. The training process is run on the derived 10% KDD-99 dataset to learn how to classify normal connections and attacks. The best individual of each run is then tested on the test set. Both datasets are presented in Table 2.

GP Design

The EA used for the experimental study is the Cartesian GP (CGP). With CGP, programs are coded with integer linear chromosome divided into groups. Each group corresponds to a position in a 2-D array.

  (a) Apply TBS selection using current threshold on the remaining patterns. (b) remove the selected patterns. (c) If the subset size is too small, the new threshold value is the next edge weight and the previsouly excluded patterns are added to the candidate ones.

Table 1 .

 1 CGP parameters. The implemented RSS-DSS here does not use the same fitness as proposed by authors. It uses the same fitness function as the other implemented methods. The effect of this transformation will discussed in Section 5. Two configurations was tested as shown on the Table4changing target size, RSS and DSS iterations simultaneously. The second configuration is referred to with RSS-DSS2.

	Parameter	Value
	Population size	512 for RSS, DSS, BUSS BRSS
		and RSS-DSS
		128 for IDS, TBS and Full Subset
	Subpopuations number	1
	Number of generations	500 for RSS, DSS, BUSS and BRSS
		100 for IDS, TBS
		depending on the RSS iteration for RSS-DSS
	CGP nodes	300
	Inputs/Outputs	49/1
	Tournament size	4
	Crossover/Mutation probability	0.9/0.04
	Fitness	Minimize classification errors
	RSS-DSS.

  Performance MetricsBy the end of each run, the best individual based on the fitness function is tested on the whole dataset and then the test dataset. Results are recorded in a confusion matrix from which accuracy, True Positive Rate (TPR) and False Positive Rate (FPR) are calculated.

	3.3 Accuracy =	T rue P ositives + T rue N egatives T otal patterns	.
	BUSS. KDD-99 have a normal class and 4 attack classes. The subset selection
	uses the U2R attack (52 patterns) class as minority class and then randomly
	selects an equal number of patterns from the remaining 3 attacks to obtain 208
	attack patterns. In a first experiment, 52 normal were added obtaining a subset
	of 260 patterns. In the second experiment (referred to as BUSS2), 208 normal
	patterns were chosen to get a final subset of 416 patterns. Sampled subsets are
	renewed each generation.

Table 2 .

 2 KDD-99 datasets composition.

	Class	Number of Patterns 10% Training Set Test Set
	Normal	97278	60593
	Dos	391458	229853
	probe	4107	4166
	R2L	1126	16347
	U2R	52	70
	Total Attacks	396743	250436
	Total Patterns	494021	311029

See UCI Machine Learning Repository at http://archive.ics.uci.edu/ml/

Cascaded GP: uses the RSS-DSS algorithm to provide the basis for building cascades of GP classifiers, up to a predefined number of layers

Terminal and function sets. The terminal set includes input variables which are the 41 KDD-99 features set with 8 randomly generated constants. The function set includes basic arithmetic, comparison and logical operators reaching 17 functions.

Specific Parameters for Sampling Methods

The values of additional parameters brought by each sampling method are assigned with respect to original method paper. Some of theses methods have been modified in a order to fit in a comparable context. The Table 4 below shows each method configuration.

Experimental Results

Experiments are performed on an Intel i7-4810MQ (2.8GHZ) workstation with 8 GB RAM running under Windows 8.1 64-bit Operating System. GP programs are trained to distinguish between normal and attack patterns. To compare the performance of the implemented sampling methods, six measures are recorded cross the 21 runs performed for each technique: the best and the mean values for the accuracy, TPR and FPR metrics. The best measures are illustrated by the Figure 3 whereas the mean values are presented in the figures 1 and 2. Otherwise, to compare the methods according to the computational cost, the spent time to complete each run and to find the best of run individual for all the trials are GP trained on the whole data set (FSS), and this is according to the three performance metrics (Figure 2.

From Figures 1 and2, we can make the following observations. Except for the basic version of RSS-DSS technique, all the implemented sampling techniques have given satisfactory results. As shown in the Figure 3, the accuracy and the True Positive Rate of the best solutions given by all the methods are quite similar. However, this finding is not available for the best FPR values. Indeed, according to the Accuracy and TPR metrics of the best solutions, BUSS method performed better than all the other sampling approach, but it has the 2 nd worst TPR value (after the RSS-DSS method).

For the two methods BUSS and RSS-DSS, we tried a second configuration mentioned as BUSS2 and RSS-DSS2 (see Section 3.2). BUSS2, while using a larger subset (more normal cases than BUSS), has lost accuracy and TPR but realizes a much better FPR. With RSS-DSS2 settings, this method enhances its performance but FPR remains very high. TBS, IDI and FSS have been tested with a reduced number of generations, population size, and target subset size due to the huge amount of time needed for each generation. Nevertheless, TBS and IDI reached a comparable performance level. All 3 methods have a very increased run time. Moreover, both IDI and TBS spent more time than using the full dataset assuming that the computing time needed for training set sampling is very high compared with the evaluation time. From Figure 4, we can see that RSS-DSS in both settings finds the best individual of run in the very first generations. BUSS makes the fastest runs because it uses the smallest subset size but this result depends on the classification problem itself and classes of the learning data.

Conclusion

The aim of this study was to compare dynamic sampling methods and their behavior when faced with large datasets under fixed parameters. Those parameters (CGP parameters) were not tuned for each sampling method.

IDI and TBS, even though they had shown good results with smaller training sets, they suffer from a very high computing time and cannot be applied to large datasets.

RSS-DSS, in this experimental context has lost its performance. The main change with earlier experiments is the use of a different fitness function.

To deal with run time problem of IDI and TBS, mixing them with other sampling methods in a hierarchical sampling is a promising solution. Fitness function affects the quality of GP results and this needs to be experimented on the sampling methods tested here.


Hmida Hmida

Sana Ben Hamida

Amel Borgi

Marta Rukoz

Genetic Programming over Spark for Higgs Boson Classification

Keywords: Genetic Programming, Machine Learning, Spark, Large Dataset, Higgs Boson Classification

With the growing number of available databases having a very large number of records, existing knowledge discovery tools need to be adapted to this shift and new tools need to be created. Genetic Programming (GP) has been proven as an efficient algorithm in particular for classification problems. Notwithstanding, GP is impaired with its computing cost that is more acute with large datasets. This paper, presents how an existing GP implementation (DEAP) can be adapted by distributing evaluations on a Spark cluster. Then, an additional sampling step is applied to fit tiny clusters. Experiments are accomplished on Higgs Boson classification with different settings. They show the benefits of using Spark as parallelization technology for GP.

Introduction

Digital transformation that we witness in organizations and companies have generated a huge volume of data. High storage capacities facilitated this phenomenon and provided organizations with their own data lakes 3 .

To discover hidden knowledge in this data, many Artificial Intelligence (AI) tools and techniques have been used such as Neural Networks, Decision Trees, etc. Evolutionary Algorithms (EA), and in particular Genetic Programming (GP) [START_REF] Koza | Genetic Programming: On the Programming of Computers by Means of Natural Selection[END_REF], are candidate solutions since they have shown satisfying results for a wide range of problems (classification, time series prediction, etc.). However, GP suffers from an overwhelming computational cost. This becomes more noticeable when the handled problem has a very large dataset as input. In fact, the evaluation step (see figure 1) is the Achilles heel of GP. It is at the origin of the increasing computational time. Therefore, any solution that applies GP to solve a large scale problem, has to focus on reducing the evaluation cost.

Summarily, mitigating this cost could be achieved by either parallelizing evaluations or reducing their number by means of dataset sampling, hardware ac-celeration or distributed computing. Hadoop MapReduce 4 and Apache Spark5 are Big Data tools that implement a new programming model over a distributed data storage architecture. They are de facto tools for data intensive applications. However, according to our knowledge, neither Spark libraries, such as Spark built-in library MLlib, nor existing ad hoc solutions do provide an implementation of GP adapted to Spark, which hinders its use in Big Data frameworks. Moreover, recent machine learning problems more often than not need very high computing power and resources in order to make a solution in a reasonable time. The challenge of running GP on Spark becomes more defying when only Small clusters are available.

This work outlines how we ported an existing GP implementation to Spark context in order to take the most of its proven potential. We apply this solution to the Higgs Boson classification problem (see section 2.4) and study the effect of varying some GP parameters on learning performance and time. Additionally, we include a sampling algorithm to GP and test it in the same environment configuration used with the whole dataset. We discuss the contribution of this sampling method to the learning process and the effect of varying number of generations, population size and sample size on training time and classifier performance.

The remainder of this paper is organized as follows. Section 2 gives an introduction to GP basics. It presents Spark and recent works that combine these two concepts. Section 3, exposes how we adapted an existing GP implementation to comply with Spark environment. Then, we show why and how a sampling phase is added to GP. Details about experimental design followed by the obtained results are discussed respectively in Sections 4 and 5. Finally, we end with some concluding remarks and perspectives.

2 Background and Related works

Genetic Programming (GP)

In the standard GP, the population is composed of tree-based individuals very close to Lisp programs. It performs the common steps of any EA that are:

1. Randomly create a population of individuals where tree nodes are taken from a given function and terminal sets. Then evaluate their fitness value by executing each program tree against the training set. 2. According to a fixed probability, individuals are crossed and/or mutated to create new offspring individuals. 3. New solutions are evaluated and a new population is made up by selecting best individuals from parents and offspring according to their fitnesses. 4. Loop step 2 and 3 until a stop criteria is met.

The evaluation step is at the origin of the increase of the GP computing time. In fact, it executes all programs (individuals) as many times as the size of the training set. In a classification problem, an individual is a program tree that represents a classification model. Figure 1 illustrates the evaluation of an individual against the training set. Its phenotype is (if

(IN 3 > 0.3, IN 3, IN 0+IN 1) < 0.6)
and is represented by the tree in the same figure. It depicts a single iteration in the evaluation of a single individual within the population. The output is translated in a class prediction and is compared to the given value from the training set. The fitness value is computed, after looping on the whole training set, according to the fitness function adopted (error rate, true positive rate, etc.).

Population Evaluation

Training Set

Spark and MapReduce

MapReduce is a parallel programming model introduced by Dean et al. in [START_REF] Dean | Mapreduce: Simplified data processing on large clusters[END_REF] and made popular with its implementation Apache Hadoop. The main idea of this model is that moving computation is cheaper than moving data. On a cluster, data is distributed over nodes and processing instructions are distributed and performed by nodes on local data. This phase is known as the Map phase. Finally, at the Reduce phase, some aggregation is performed to produce the final output. Hadoop Distributed Files System (HDFS) ensures data partitioning and replication for MapReduce. However, it needs many serialization operations and disk accesses. In addition to that, Hadoop MapReduce does not support iterative algorithms which is the case for EA. Apache Spark is one of many frameworks intended to neutralize the limitations of MapReduce while keeping its scalability, data locality and fault tolerance. It is up to 100 times faster than MapReduce owing to in-memory computing. The keystone of Spark is the Resilient Distributed Datasets (RDD) [START_REF] Zaharia | Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing[END_REF]. An RDD is a typed cacheable and immutable parallel data structure. Operations on RDDs are of two types: transformations (map. filter, join, . . . ) and actions (count, reduce, reduceByKey, . . . ). Spark DAGScheduler, computes an optimized Directed Acyclic Graph exploiting lazy evaluation and data locality. Spark is compatible with different cluster managers (Built-in Standalone, Hadoop YARN, Mesos and Kubernetes) [START_REF] Kienzler | Mastering Apache Spark 2[END_REF].

Previous works

Recently, several works deal with parallelizing EA in distributed environments. Rong-Zhi Qi et al. [START_REF] Qi | A parallel genetic algorithm based on spark for pairwise test suite generation[END_REF] and Padaruru et al. [START_REF] Paduraru | A distributed implementation using apache spark of a genetic algorithm applied to test data generation[END_REF] apply Genetic Algorithms (GA) on software test suite generation where input data is a binary code. Both give a Spark based implementation that parallelizes fitness evaluation and genetic operators. In Chávez et al. [START_REF] Chávez | ECJ+HADOOP: an easy way to deploy massive runs of evolutionary algorithms[END_REF], the well-known EA library ECJ is modified in order to use MapReduce for fitness evaluations. This new tool is tested using GA to resolve a face recognition problem over around 50MB of data. Only time measure was considered in this work. In Peralta et al. [START_REF] Peralta | Evolutionary Feature Selection for Big Data Classification: A MapReduce Approach[END_REF], the MapReduce model is applied to implement a GA that preprocesses big datasets (up to 67 millions instances). It applies an evolutionary feature selection, in a map phase, to create a vector per mapper on top of disjoint subsets from the original dataset. The reducer aggregates the previously created vectors. Funika et al. [START_REF] Funika | Scaling evolutionary programming with the use of apache spark[END_REF] implement an 'Evaluation Service' that can be solicited through a REST API. It is not an implementation of a specific EA algorithm but rather an outsourcing of the evaluation. This service can be used by any algorithm that requires the evaluation of an expression over a given dataset. They tested this service for 3 different expressions on datasets varying from 1MB to 1024MB. Al-Madi et al. [START_REF] Al-Madi | Scaling genetic programming for data classification using mapreduce methodology[END_REF] present a full GP implementation based on MapReduce. It relies on creating a mapper for each individual by storing the population on HDFS. Each mapper, calculates the fitness value for the involved individual. Then, the reducer collects the population and performs selection, crossover and mutation to create the new population. The focus is on increasing population size (until 50000) and only with small datasets classification problems.

Our proposal is inspired by all these works and mostly by Chávez et al. [START_REF] Chávez | ECJ+HADOOP: an easy way to deploy massive runs of evolutionary algorithms[END_REF] where the authors have integrated the MapReduce model to the ECJ library in order to run EA on a hadoop cluster. Their goal was to evolve very large populations (up to 3 million individuals), which was achieved by using the checkpointing feature and serializing individuals in an HDFS file. This work is focused on population and did not study the use of massive datasets. Our proposal is rather concerned with training dataset. We both give a transformation of an existing tool, but our solution uses a different underlying infrastructure which is Spark engine and handles a big dataset to assess the advantages of distributing GP evaluation. Another difference is the EA algorithm applied. While Chávez used GA, we use standard tree-based GP. Finally, we extend this solution with a sampling technique.

HIGGS dataset

A Higgs or Z Boson is a heavy state of matter resulting from a small fraction of the proton collisions at the Large Hadron Collider [START_REF] Baldi | Enhanced higgs boson to τ + τ -search with deep learning[END_REF].

From the machine learning point of view, the problem can be formally cast into a binary classification problem. The task is to classify events as a signal (event of interest) or a background. Baldi et al. [START_REF] Baldi | Searching for exotic particles in high-energy physics with deep learning[END_REF] published for benchmarking machine-learning classification algorithms a big dataset of simulated Higgs Bosons that contains 11 million simulated collision events [START_REF]Higgs[END_REF].

In this work, we propose to handle the whole dataset, which is a big challenge when using EA. Table 1 summarizes the main characteristics of the dataset. To adapt DEAP for a parallel computing engine, the usual method is to replace the map method, of the Toolbox class, by a code that calls the desired parallelized operation. Unfortunately, Spark has a constraint that prohibits nesting RDDs. To evaluate an individual, we need to access our dataset stored in an RDD. Consequently, this solution is not feasible. The following paragraph shows how we transformed DEAP to benefit from Spark RDDs.

Implementation model

From recent works described in 2.3, two main scenarios for distributing any EA, and in particular GP, can be laid out:

1. Distribute the whole GP process: each mapper is an independent run that uses local data. It is very close to the co-evolution scheme or island model. By the end of this scenario, an aggregation is required to obtain the final solution. This aggregation is run on the driver program. For example, aggregation can be made through a voting using the best individual of each population in a classification problem. Another way is to take the best individual after a test on the whole training set. This solution needs more resources on the cluster.

2. Distribute population: this is suitable when a single population is evolved. Parallelization can be reached by partitioning the population using RDDs. Therefore, individuals are distributed on nodes, and each node processes the local individuals in spite of the total population. To proceed the following phase of the GP (see 2.1), the output of the previous phase is collected as a new RDD. It is composed of the modified individuals (RDDs are immutable).

The evaluation represents more than 80% of the total time cost in EA [START_REF] Giráldez | An approach to reduce the cost of evaluation in evolutionary learning[END_REF][START_REF] Funika | Scaling evolutionary programming with the use of apache spark[END_REF]. We suggest to focus on evaluation which can be easily distributed on Spark cluster even with limited resources seeing that we do not need independent populations. Besides, for machine learning problems involving big training sets, data must be parallelized and then we cannot parallelize population. The fitness function considered in this problem is to maximize correct predictions. To adapt fitness computing to Spark, a first alternative is to replace the default evaluation function used in DEAP. Map operation on TrainingRDD does not use the individual but a function (func) representing the Genetic Program. This alternative makes as many reduce operations as the size of population. This generates an important cost even for small populations. A key rule in Spark optimization is to reduce the number of action operations with regard to transformations. Thus, we altered DEAP evaluation so it maps all the population on the TrainingRDD. This diminishes action calls to one call per generation. Figure 2 gives the global flowchart of the modified DEAP evaluation algorithm. First, training set is transformed into an RDD (TrainingRDD) from a file stored on HDFS and is cached (Figure 3, line 3). Then, at each generation, the population is evaluated against the training set by mapping their functions on TrainingRDD partitioned over worker nodes (Figure 3, line 9). To get fitness values, a reduce operation is performed (Figure 3, line 12). After, offspring can be generated on the driver node by applying mutation and crossover. The offspring replaces the old population and program loops until maximum generation number is reached.

Data sampling

GP is a costly algorithm and this is intensified with big datasets like HIGGS. For clusters with a small number of nodes, running GP for such problems remains of high-cost. Furthermore, in these datasets, redundancy is inescapable. Sampling is a very suitable technique to deal with this situation. Additionally, depending on the underlying algorithm, sampling may counter overfitting, enhance learning quality and allow large population or more generations per run. For these reasons, we investigated the use of sampling with the previous implementation. In this work, we started by a simple sampling method which is Random Subset Selection (RSS) [START_REF] Gathercole | Dynamic training subset selection for supervised learning in genetic programming[END_REF]. RSS combines simplicity with efficiency. Spark makes available two operations: sample and takeSample. They produce samples with an oscillating size around the specified target. For efficiency, we used sample which is an RDD transformation. takeSample is an action and cannot be optimized by Spark DAG Scheduler. The training sample is renewed at each generation before evaluating the population. The commented code snippet in Figure 3 outlines the steps we made to adapt the DEAP standard GP.

Spark cluster

We used a tiny cluster composed of 4 worker nodes. Each node has a 16 core Intel Core processor at 2.397GHZ, 45GB of RAM and 1TB of HDFS storage space.

In the following experiments, Spark application is submitted to the cluster via spark-submit script. We used the same YARN directives that are optimized for the cluster size and the used dataset accordingly to guidelines in [START_REF] Karau | High Performance Spark. O'reilly[END_REF] for all the GP runs in order to neutralize the effect of this configuration on results.

On this cluster, 4 Spark executors are deployed per node. The number of available nodes does not allow us further investigation of hardware effect on GP performance.

GP settings

General settings Based on few runs, we set parameter values (Table 2) for GP. The process of tuning GP settings is beyond the scope of this work and have not been thoroughly studied. Terminal and function sets The terminal set includes 28 features of the benchmark Higgs dataset with a random constant. The function set includes basic arithmetic, comparison and logical operators reaching 11 functions (Table 3).

Results and discussion

Since the main objective is to tackle computation cost of GP in supervised learning problems, the first recorded measure is learning time. It comprises the elapsed time from the initialization of the first population until the last generation. It does not include the time for evaluation against the test set. Reducing time must not be at the expense of learning quality. Then, by the end of each run, the best individual based on the fitness function is evaluated on the test dataset. Results are recorded in a confusion matrix from which accuracy, True Positive Rate (TPR) and False Positive Rate (FPR) are calculated. The objective function used with GP is the classification accuracy:

Accuracy = T rue P ositives + T rue N egatives T otal patterns (1)
We tried 61 different configurations obtained by varying population size, generation number and sample size. Each configuration is run 11 times. Then we compute the average learning time and the overall best individual performance metrics. By these experiments, we intend to trace the speed gain in learning time and how it reacts to population size and generations number changing. The results are reported in Figure 4 in which 3 population sizes are tested (32, 64 and 128 with 30 generations) and 3 generations numbers (30, 50 and 70 with 32 individuals per population) with full dataset (FSS). It is noticeable that parallelizing GP on Spark, facilitates its use for solving large classification problem like Higgs Boson classification. With only 4 nodes, a GP run takes on average 4864.541 seconds in 70 generation with 32 individuals and 9779.379 seconds in 30 generations with 128 individuals. A serial execution of GP on a single node takes more than 20 seconds to evaluate one individual against the total dataset which could take more than 44800 seconds for 70 generations with 32 individuals. Parallelizing evaluations under Spark achieves a speedup over nine times. This can be boosted by deploying more nodes on the cluster. Otherwise, learning time increases linearly with respect to the population size and generations number when using the same Spark settings.

Then, to allow using large populations and more generations without adding nodes, we injected RSS to the modified GP. We used the same settings but more population size values (from 32 to 8192) and generation numbers (from 30 to 1500) with a sample size fixed at 10000 instances. Results are exposed in Figure 5. The mean learning time for 1500 generations evolving 128 individuals is 3116.744 seconds and for 30 generations with 8192 individuals is 763.9 seconds. The two curves have the same pace. This is owing to the fact that evaluation is the predominant phase in GP. Also, with low values of population size and generations number, time curve is almost flat or with slight slope. It means that time is affected mainly by Spark scheduling delays. This is tightly related to the cluster use tuning. This remains valid for target sample size (Table 4).

We tried the values: 1000, 5000, 10000, 50000 and 100000 instances per sample. While population size and generations number are set to 128 and 300. To weigh the differences between using the whole dataset and a sampled subset for training, we juxtapose the results of full dataset (FSS) with those obtained by RSS with the same number of generations and population size in Figure 6. Also, we keep an eye on learning performance in Figure 7. Undoubtedly, RSS outper- forms GP without sampling for the 5 different target sizes. As regards learning performance, in terms of accuracy, experiments using RSS are less efficient with low number of generations or population size. It surpasses using the full dataset with large populations or more generations. On the one hand, in Figure 7(a), it's for more than 50 generations that all RSS variants have best accuracy. On the other hand, Figure 7 do not focus on enhancing learning performance and do not use any enhancing technique (e.g. feature engineering). Nevertheless, the best accuracy obtained is 66.93% with RSS (popultaion: 128, generations: 1500, sample: 10000) in 3190.02 seconds. The best result in [START_REF] Shashidhara | Evaluation of machine learning frameworks on bank marketing and higgs datasets[END_REF] is 60.76% realized with logistic regression.

Conclusion

We presented, in this paper, details about reshaping DEAP library by parallelizing evaluation on Spark cluster. We obtained encouraging results that proclaim Spark as an efficient environment and is suitable for distributing GP evaluations. Then, we integrate a simple sampling technique that preserves learning performance while providing the possibility to probe GP with large populations or for a high number of generations. We studied experimentally the effect of varying 3 parameters: population size, generations number and sample size. This work provides a Spark compliant GP implementation without the need to code it from scratch. Thus, it can be used in resolving different machine learning problems. Although it has been successfully tested on a small cluster, the size of the underlying cluster on the overall performance has to be investigated.

A logical extension is to study the impact of different Spark configurations (number of nodes, RDD partitioning, partition sizes, etc.). This will help to find the most suitable execution settings. A second path is to check the feasibility of adding other sampling techniques and in particular active sampling that prove to be advantageous in the context of machine learning. Hierarchical sampling, that we used in [START_REF] Hmida | Scale genetic programming for large data sets: Case of higgs bosons classification[END_REF], is a promising candidate.

1 Fig. 1 .

 11 Fig. 1. GP Evaluation.

Fig. 2 .

 2 Fig. 2. Flowchart of the modified evaluation.

1 Framework

 1 Software frameworkThe details of used software are as follows: Spark version: 2.1.0, Hadoop version: 2.9.1, Resource Manager: YARN, Operating System: SMP Debian 4.9.130 and DEAP version: 1.2.2.

1 from pyspark import SparkContext 2 sc 6 # 9 [ 10 # 14 # 16 #Fig. 3 .

 12691014163 Fig. 3. Modified DEAP GP loop.

Fig. 4 .

 4 Fig. 4. FSS Mean Time.

Fig. 5 .

 5 Fig. 5. RSS Mean Time.

Fig. 6 .

 6 Fig. 6. RSS vs FSS mean learning time.

Fig. 7 .

 7 Fig. 7. RSS vs FSS Best individual accuracy.

Table 1 .

 1 Higgs dataset composition.

	Total of events	11 millions
	Number of Attributes 28 real-valued (21 low-level and 7 high-level variables)
	Percentage of signals 53%
	Training set size	10.5 millions events
	Test set size	500K events
	3 Porting DEAP to Spark

DEAP (Distributed Evolutionary Algorithms in Python)

[START_REF] Fortin | DEAP: Evolutionary algorithms made easy[END_REF]

is presented as a rapid prototyping and testing framework that supports parallelization and multiprocessing. It implements several EA: GA, Evolution Strategies (ES) and GP. We decided to use this framework for the following reasons: (1) it is a Python package which is one of the 3 languages supported by Spark, (2) it implements standard GP with tree based representation and (3) it is distributed ready. The third point means that DEAP is structured in a way that facilitates distribution of computing tasks. DEAP is not natively compliant with Spark and do not use any of its parallel data structures (RDDs, DataFrames or DataSets).

Table 2 .

 2 GP settings.

	Parameter	Value
	Initialization	Ramped half
		and half
	Tournament size	4
	Tree limit	17
	Crossover probability	0.9
	Mutation probability	0.04
	Generations and	61 different
	population size	combinations

Table 3 .

 3 GP terminal and function sets.

	Function (node) set
	Arithmetic operators	+, -, * , /
	Comparison operators	<, >, =
	Logic operators	AND, OR, NOT
	Other	IF (IF THEN ELSE)
	Terminal set
	Higgs Features	28
	Random Constants	1
	Boolean values	True, False

Table 4 .

 4 RSS sample size effect on time.

	Sample size	1000	5000	10000 50000 100000
	Mean time (S) 384.748 411.198 547.839 971.921 1684.747

  (b) shows that RSS outperforms the use of the entire dataset only with a population size of 128. It is important to notice that we

		63%						64%
		62%						63%
	Accuracy	56% 57% 58% 59% 61% 60%					Accuracy	55% 56% 62% 61% 57% 58% 59% 60%
		55%						54%
		54%						53%
			30		50		70		32		64		128
					Generations					Population size
		FSS	RSS-1000	RSS-5000	RSS-10000	RSS-50000	RSS-100000	FSS	RSS-1000	RSS-5000	RSS-10000	RSS-50000	RSS-100000

'A data lake is a collection of storage instances of various data assets additional to the originating data sources.' (Source: Gartner)

https://hadoop.apache.org

https://spark.apache.org


Hmida Hmida

Sana Ben Hamida

Amel Borgi

Marta Rukoz

Hierarchical Data Topology Based Selection for Large Scale Learning

The amount of available data for data mining and knowledge discovery continues to grow very fast with the era of Big Data. Genetic Programming algorithms (GP), that are efficient machine learning techniques, are face up to a new challenge that is to deal with the mass of the provided data. Active Sampling, already used for Active Learning, might be a good solution to improve the Evolutionary Algorithms (EA) training from very big data sets. This paper investigates the adaptation of Topology Based Selection (TBS) to face massive learning datasets by means of Hierarchical Sampling. We propose to combine the Random Subset Selection (RSS) with the TBS to create the RSS-TBS method. Two variants are implemented and applied to solve the KDD intrusion detection problem. They are compared to the original RSS and TBS techniques. The experimental results show that the important computational cost generated by original TBS when applied to large datasets can be lightened with the Hierarchical Sampling.

I. INTRODUCTION

Genetic Programming (GP) [START_REF] Koza | Genetic programming: On the programming of computers by means of natural selection[END_REF] is a meta heuristic that has been used to solve a wide variety of machine learning problems. Applied for many classification problems, it has made a very competitive results with other approaches like Neural Networks, Decision Trees, etc. Nevertheless, this Evolutionary Algorithm (EA) suffers from an increased computational cost induced mainly by the evaluation step.

Applied to supervised learning and classification problems, GP generates a population of classifiers (genetic programs) by means of genetic operators. The performance of each classifier is measured by a fitness function that needs the evaluation (execution) of every program against the complete training dataset. This leads to a computational overhead increased specially with large datasets. It is proportional to the product of the number of instances in the dataset, the population size and the number of generations that will be carried out during the evolution process. Otherwise, using the full learning data might be impossible when the input data doesn't fit within the main memory which is often the case with Big Datasets.

To alleviate the number of evaluations, sampling the training set has been successfully adopted in several works [START_REF] Curry | Scaling genetic programming to large datasets using hierarchical dynamic subset selection[END_REF]- [START_REF] Lasarczyk | Dynamic subset selection based on a fitness case topology[END_REF]. The proposed approaches vary from simple methods based on a random data selection to complex methods using graphs or hierarchical techniques. Topology Based Selection (TBS) [START_REF] Lasarczyk | Dynamic subset selection based on a fitness case topology[END_REF] is an active data selection algorithm 1 that keeps in the sampled subset the cases that are quite different according to a similarity graph constructed during the learning process. It was applied to solve a set of machine learning problems (thyroid problem, function approximation and the two intertwined spirals problem) and compared to the random sampling and the weighted sampling [START_REF] Gathercole | Dynamic training subset selection for supervised learning in genetic programming[END_REF]. It was shown that TBS was able to improve the performance of genetic programming thanks to the data diversity control.

In this paper, we will try to adapt TBS to deal with problems involving large scale datasets using Hierarchical Sampling [START_REF] Curry | Scaling genetic programming to large datasets using hierarchical dynamic subset selection[END_REF]. The aim is to mix TBS with Random Subset Selection (RSS) [START_REF] Gathercole | An investigation of supervised learning in genetic programming[END_REF] in order to reduce the complexity and the computation cost while taking advantage of the strengths of this method. Our purpose is to apply the TBS on reduced samples that are actively selected along evolution using random sampling or balanced sampling on the whole training data. The aim is to reduce the complexity thanks to the hierarchical strategy and, at the same time, allow the GP to maximize its generalization ability thanks to the data diversity enhanced by the TBS method.

This paper is organized as follows. Section II exposes the RSS, TBS and balanced sampling in addition to Hierarchical Sampling that inspired this work. A description of the proposed RSS-TBS method is given in Section III. The last section exposes intrinsic parameters used and discusses the obtained results under these experimental conditions.

II. BACKGROUND

Two major classes of sampling techniques can be layed out: static sampling and dynamic sampling. With static sampling, the learner obtains all the input training set at once and stills unmodified across the learning process. This strategy is not efficient when learning from very large data sets, and it might not be applicable with big data sets. Dynamic sampling techniques are tightly related to the learning process evolution. Generally, it depends on a particular feature like unresolved or difficult cases, the number of generations carried out, among others. The presented methods are part of the dynamic sampling class.They are inspired by four techniques in this category: the Random Subset Selection (RSS), the Topologu Based Selection(TBS), the Hierarchical Selection and the Balanced Sampling. These techniques are presented in details in the following section.

A. Random Subset Selection (RSS)

The selection of fitness cases is based on a uniform probability among the training subset. This stochastic selection helps to reduce any bias within the full dataset on evolution. In Random Subset Selection RSS [START_REF] Gathercole | Dynamic training subset selection for supervised learning in genetic programming[END_REF], at each generation g, the probability of selecting any case i is equal to P i (g):

∀i : 1 ≤ i ≤ T, P i (g) = S T . ( 1
)
where T is the size of the full dataset and S is the target subset size. The sampled subset have a fluctuating size around S. Fixed Random Selection (FRS) [START_REF] Zhang | Genetic programming with incremental data inheritance[END_REF] is a very similar method with a fixed number of cases selected at every generation. Stochastic Sampling SS [START_REF] Nordin | An on-line method to evolve behavior and to control a miniature robot in real time with genetic programming[END_REF] is another method using the same probabilistic selection to construct subsets for each individual per generation.

The single parameter of this category of sampling is the subset size, whether a crisp or flexible target, it is set like other GP parameters (population size, crossover probability, etc.) and most likely by several GP runs.

B. Hierarchical Sampling

This kind of sampling is based on multiple levels of sampling methods inspired by the concept of a memory hierarchy. It combines several sampling algorithms that are applied in different levels.

Robert Curry and Malcom Heywood conceived an extension to Gathercole's Dynamic Subset Selection algorithm (DSS) [START_REF] Gathercole | Dynamic training subset selection for supervised learning in genetic programming[END_REF] into a 3 levels hierarchy [START_REF] Curry | Towards efficient training on large datasets for genetic programming[END_REF]. At level 0, the dataset was first partitioned into blocks that were sufficiently small to reside within RAM alone. Then, at level 1, blocks were then chosen from this partition based on RSS or DSS. Finally, at level 2, the selected block is considered as the full dataset on which DSS was applied for several rounds. Depending on the level 1 algorithm, we have RSS-DSS hierarchy or DSS-DSS hierarchy. Besides DSS parameters, new parameters are added: level 0 block size, level 1 number of iterations, level 2 iterations, maximum level 2 iterations and tournament iterations. Only level 2 iterations is calculated by:

I b (i) = I max * E b (i -1). (2)
I b (i): number of level 2 iterations on block b in i th level 1 iteration.

I max : maximum level 2 iterations. E b (i -1): error rate over block b for the best case at previous iteration.

A modified DSS in level 2 is used where two roulette wheels exist per block, one is used to control the selection of patterns with respect to age and the other to difficulty, the roulette wheels being selected in proportion to the corresponding probability for age and difficulty (2 additional parameters).

For the DSS-DSS hierarchy, block weight and block selection probability are defined in [START_REF] Curry | Towards efficient training on large datasets for genetic programming[END_REF]. Tested against KDD-99 [START_REF]Kdd cup[END_REF] and Adult dataset [START_REF] Curry | Towards efficient training on large datasets for genetic programming[END_REF], both algorithms realize competitive results in very shorter time. DSS-DSS outperforms RSS-DSS in these experiments.

An extension to this work is made in [START_REF] Curry | Scaling genetic programming to large datasets using hierarchical dynamic subset selection[END_REF] with the Balanced Block DSS by altering mainly the level 0 block selection with the goal of obtaining a balanced block in level 1 with respect to a fixed ratio. Experimental results showed that Balanced Block algorithm is able to approach the classification performance of the CasGP2 algorithm, whilst retaining the computational speedup of the original RSS-DSS algorithm.

C. Topology Based Selection

Inspired by the idea that structure influences the efficiency of heuristics working on it, this method consists at building a topology of the problem from the knowledge acquired by individuals about fitness cases. Lazarczyk [START_REF] Lasarczyk | Dynamic subset selection based on a fitness case topology[END_REF] suggests a Fitness case Topology Based Sampling TBS in which relationship between fitness cases in the training set is represented by an undirected weighted graph. Vertices are fitness cases and edges have a weight measuring a similarity or a distance induced from individuals' performance. Then, cases having a tight relationship with respect to a threshold cannot be selected together in the same subset assuming that they have an equivalent difficulty for the population. Edge values start at 0 and are updated after evaluation phase by increasing the weight of all edges between solved cases by each individual and decreasing the weight of all edges by a loss rate λ. This algorithm uses a unique subset for all the individuals renewed each generation after updating the topology graph.This subset is constructed by selecting randomly a case from a candidates set (initially equal to full dataset) until reaching the target size or the candidates set is empty. All fitness cases connected to it with an edge weight exceeding the threshold are removed from candidates. The threshold is calculated during evolution process, using a binary-search like algorithm, to have a value adapted to the current topology: it must not be too high or too low.

Experimental results on classification problems (intertwined spirals [START_REF] Lang | Learning to tell two spirals apart[END_REF] and the thyroid problems) demonstrated improvements in mean fitness value through generations compared to DSS and SSS. However, the additional computational cost of TBS caused by the threshold calculation algorithm and the topology update has not been measured. Moreover, this method has not been tested on a large dataset.

D. Balanced sampling

Balanced sampling [START_REF] Hunt | Sampling methods in genetic programming for classification with unbalanced data[END_REF] is a method aiming to improve classifiers accuracy by correcting the original dataset imbalance within majority and minority class instances. It has some methods based on the minority class size and thus reduce the number of instances like the methods studied in this paper. The following sampling methods are used with GP:

• Static Balanced Sampling: is a static sampling method that selects cases with uniform probability from each class without replacement until obtaining a balanced subset with equal number of majority and minority class instances of the desired size at every generation.

• Basic Under-sampling: select all minority class instances and then an equal number from majority class randomly. This method produces balanced subsets having a reduced size especially when the gap between minority and majority classes is very important. We integrated this method in our approach to take advantage of its contribution to reduce the sample size, while keeping a balanced sample (see Section III-B). • Basic Over-sampling: select all majority class instances and then an equal number from minority class randomly with replacement. • Under-sampling A: Multiple balanced samples are created at each generation with Basic Under-sampling method. At every generation, all individuals are evaluated against all of the sample sets and are attributed the average fitness across all the sample sets. • Under-sampling B: Identical to Under-sampling A but uses the minimum fitness instead of the average. • Over-sampling A: Creates several balanced samples using Basic Over-sampling. The final fitness is the average on all subsets. • Over-sampling B: Uses the same sampling method as Over-sampling A and the minimum fitness.

III. HIERARCHICAL SAMPLING WITH TBS

GP based learning algorithms using TBS are limited to those in the original paper [START_REF] Lasarczyk | Dynamic subset selection based on a fitness case topology[END_REF] where training set does not exceed few thousands of cases. TBS accelerates evolutionary search with a high diversity and good average fitness of the evolved population. This sampling method relies on a complete undirected graph having its edges updated after each evaluation phase. It is expected that the cost of maintaining this topology for a high volume of datasets will be very important. In this section, we propose a method inspired by the Hierarchical Sampling to overcome this additional cost by combining the use of RSS, TBS and Basic Under-Sampling (BUSS). The main idea is to apply TBS on different training sets with reduced size that are selected randomly from a fixed set of blocks. Blocks are created proportionally to the training set (the RSS-TBS method) or balanced according to BUSS (the BUSS-RSS-TBS method). We describe below the two methods in details.

A. RSS-TBS

At level 0, the full training set is first partitioned into blocks with a fixed size and then saved into hard disk. The number of cases per class is proportional to the initial training set. Then, at level 1, RSS is applied to randomly select a block. At the last level, previously selected block is sampled with TBS. The general algorithm is shown below (Algorithm 1).

At step 13, the number of TBS iterations is calculated using Equation 2 in which the error rate is for the actual best individual of the run. We used a modified TBS that calculates the threshold through the steps described by Algorithm 2 if the subset size is too small then

B. BUSS-RSS-TBS

This method differs from the previous one by level 0 block creation. In fact, BUSS is performed at this level and then block size becomes calculated according to minority class. KDD-99 have a normal class and 4 attack classes. The subset selection uses the U2R attack (52 patterns) class as minority class and then randomly selects an equal number of patterns from the remaining 3 attack classes gathering 208 attack patterns. In a first experiment, 52 normal were added obtaining 260 patterns in a single block. In the second experiment, 208 normal patterns were chosen to get a final level 0 block of 416 patterns. RSS and TBS are then applied in the same way as in Section III-A

IV. EXPERIMENTS AND RESULTS

A. Learning Data

We used here a large dataset, which was firstly created for the competition held at the Fifth International Conference on Knowledge Discovery and Data Mining KDD-99 and is about intrusion detection problem. The original training dataset contains 5 million lines conveying data about connections from the simulated traffic and their labels as Normal connections and four attack classes. Another set, called corrected set is constructed with the same way and used as test dataset. The training process is run on the derived 10% KDD-99 dataset to learn how to classify normal connections and attacks. The best individual of each run is then tested on the test set. Both datasets are presented in Table I.

B. Cartesian GP (CGP)

CGP is a form of GP, proposed by Julian Miller [START_REF] Miller | Cartesian genetic programming[END_REF], that represents genetic programs as directed acyclic graphs and mostly inspired by digital circuits called FPGA. In this graph, nodes representing functions have many inputs and one output, and are layed into two dimensional matrix very similar to neural networks. This form of GP has the following advantages [START_REF] Cgp | Cartesian gp website[END_REF]:

• Unlike trees, it allows more than one path between any pair of nodes permitting the reuse of previous results. • Highly competitive with other GP methods.

• Does not bloat.

• Is easy to implement.

• Can have multiple outputs and then solve many types of problems.

We use here a CGP implementation done by David Oranchak [START_REF] Cgp | Cartesian gp website[END_REF] as a contribution package to Sean Luke's ECJ [START_REF] Luke | Ecj homepage[END_REF]. ECJ is an open source evolutionary computation framework implementing evolutionary algorithms like GP, Evolution Strategies, Genetic Algorithms etc., and offering the most complete range of GP representations (Koza, linear, grammatical, etc.).

1) CGP parameters: The implementation of CGP involves different parameters that determine its efficiency. The final design of CGP parameters used in this work is summarized in Table II.

2) Terminal and function sets: The terminal set includes input variables which are the 41 KDD-99 features set with 8 randomly generated constants. The function set includes basic arithmetic, comparison and logical operators reaching 17 functions (see Table III).

C. Performance Metrics

By the end of each run, the best individual based on the fitness function is tested on the whole dataset and then on the test dataset. Results are recorded in a confusion matrix from

T P R = T rue P ositives T rue P ositives + F alse N egatives .

F P R = F alse P ositives F alse P ositives + T rue N egatives .

The training time is the amount of elapsed seconds between the first and the last generation (see Table II for the number of generations ).

D. Specific Parameters for Sampling Methods

The values of additional parameters brought by each sampling method are assigned with respect to the original method paper. Some of theses methods have been modified in order to fit in a comparable context. The Table IV shows each method configuration.

E. Experimental Results

Experiments are performed on an Intel i7 -4810M Q (2.8GHZ) workstation with 8GB RAM running under Windows 8.164 -bit Operating System. GP programs are trained to distinguish between normal and attack patterns.

To compare the performance of the implemented sampling methods, six measures are recorded cross the 21 runs performed for each technique: the best and the mean values of the accuracy, TPR and FPR metrics for both training and test datasets. The best measures are illustrated by the Figures 4, 5 Otherwise, to compare the methods according to the computational cost, the spent time to complete each run and to find the best of run individual for all the trials are recorded. Table V illustrates the corresponding mean values for all implemented techniques.

From Table V, it is obvious that all three hierarchical sampling methods are more faster than TBS while having larger population and performing a greater number of generations due to the two level iterations. These methods also spend less time than RSS. Meanwhile, it's noticeable that the best classifier is found very early according to the whole run. Regarding resulting best classifier quality (Figure 4) in terms of accuracy, RSS-TBS and BUSS-RSS-TBS (2 variants) merely outperforms RSS and TBS. The last two methods have very similar results. At the same time, recall and FPR increased remarkably for the three hierarchical methods. Whenever the second configuration of BUSS is used as in BUSS2 and BUSS-RSS-TBS2 the FPR

V. CONCLUSION

In this paper, we have shown the glaring computational cost of TBS when used within a supervised learning process using GP algorithm. Then we gave a solution to this problem by mounting a cascade of different sampling methods inspired by the RSS-DSS algorithm. In a first scenario, TBS was mixed with RSS and in a second one BUSS is deployed to build first level blocks.

Experimental results demonstrates this speed gain with RSS-TBS whilst reaching a slightly better accuracy than the original TBS and RSS. In addition to that BUSS registers an increase in FPR. Though, the three hierarchical sampling methods suffer from an early convergence and could be handled with using a suitable Fitness Function. Moreover, in this paper we used a topology graph for each level 1 subset generated at each RSS iteration and thus the previous similarity measures is lost. Keeping a full topology graph could save some extra time.

9 :

 9 until target size reached

Fig. 1 .Fig. 2 .

 12 Fig. 1. Mean Accuracy

Fig. 3 .Fig. 5 .

 35 Fig. 3. Mean FPR

Fig. 6 .

 6 Fig. 6. Best Individual FPR

TABLE IV SPECIFIC

 IV METHODS' PARAMETERS

	Method	Parameter	Value
	RSS	Target Size	5000
	TBS	Target Size Loss Rate	1000 0.7
	RSS-TBS	Target Size(level 2 block size) Level 0 block size	2500 then 100 5000
		RSS iterations	200 then 500
		Max TBS iterations	20 then 50
		Individuals evaluated	100
		per TBS iteration	(20% of population size)
	BUSS-	Target Size(level 2 block size)	2500 then 100
	RSS-TBS	Level 0 block size	260 then 416 (calculated)
		RSS iterations	50 then 40
		Max TBS iterations	40 then 50
		Individuals evaluated	100
		per TBS iteration	(20% of population size)

TABLE V

 V Another evidence, based on Figures 1,2 and 3 is that hierarchical sampling obtains the worst mean performance indicators (accuracy, recall and FPR) assuming that results are very divergent.

		TIME MEASURES
	Method	Mean Run Time	Mean 'Best of Run'Time
	BUSS	75.612	20.135
	BUSS2	102.428	43.054
	TBS	11174.507	1494.977
	RSS	1493.788	530.038
	RSS-TBS	714.414	9.524
	BUSS-RSS-TBS	157.485	1.712
	BUSS-RSS-TBS2	236.029	4.687
	falls down.

derived from Active Learning[START_REF] Atlas | Training connectionist networks with queries and selective sampling[END_REF],[START_REF] Cohn | Improving generalization with active learning[END_REF]: 'any form of learning in which the learning program has some control over the inputs on which it trains.'

Cascaded GP: uses the RSS-DSS algorithm to provide the basis for building cascades of GP classifiers, up to a predefined number of layers