Keywords: Dificultad de problemas, Predicci ón de rendimiento esperado, Programaci ón genética, Aprendizaje supervisado Problem difficulty, Prediction of expected performance, Genetic programming, Supervised learning

Resumen

La estimaci ón de la dificultad de problemas es un tema abierto en Programaci ón Genética (GP). El objetivo de este trabajo es generar modelos que puedan predecir el desempe ño esperado de un clasificador basado en GP cuando este es aplicado a tareas de prueba. Los problemas de clasificaci ón son descritos usando características de un dominio específico, algunas de las cuales son propuestas en nuestro trabajo y estas características son dadas como entrada a los modelos predictivos. Nos referimos a estos modelos como predictores de desempe ño esperado (PEPs, por sus siglas en inglés). Extendimos este enfoque usando un ensemble de predictores especializados (SPEPs, por sus siglas en inglés), dividiendo problemas de clasificaci ón en grupos específicos y elegimos su correspondiente SPEP. Los predictores propuestos son entrenados usando problemas de clasificaci ón sintéticos de 2D con conjunto de datos balanceados. Los modelos son entonces usados para predecir el desempe ño de un clasificador de GP en problemas del mundo real antes no vistos los cuales son multidimensionales y desbalanceados. Además, este trabajo es el primero en proveer una predicci ón de rendimiento para un clasificador de GP sobre datos de prueba, mientras en trabajos previos se han enfocado en predecir el rendimiento para datos de entrenamiento. Por lo tanto, planteados como un problema de regresi ón simb ólica son generados modelos predictivos exactos los cuales son resueltos con GP. Estos resultados son alcanzados usando características altamente descriptivas e incluyendo un paso de reducci ón de dimensiones el cual simplifica el proceso de aprendizaje y prueba. El enfoque propuesto podría ser extendido a otros algoritmos de clasificaci ón y usarlo como base de un sistema experto de selecci ón de algoritmos.

To my parents v vi I would like to thank all people who lived this dream with me.

To my dear parents, life is a constant struggle and becomes more comfortable hand of you, I have no words that represent how grateful I am for letting me dream, fly and reach my goals, I love you.

To my brothers, for always supporting me and loving me so much, I love you very much and I am very proud of you.

To my sister in a law, being like a sister, always listening to me, supporting me and giving me the most beautiful gift, my nephews.

To my nephews, they are the most beautiful thing happened to me, the best gift of a brother, thank you for so much love my beautiful boys, Julito and Cesarito.

To my dear grandparents, for their love, patience, so many beautiful moments I hope to have them with me much longer time, I love you.

To my family, aunts, uncles and cousins, thanks for their support all time.

To my friends, those who remain in good and bad times those that endure over time.

To my boyfriend, thanks for your love, support and understanding, just I love you.

I would like to thank my advisor, Dr. Leonardo Trujillo, for all his help and guidance that he has given me over the past six years. Thanks for his patience and for giving me always the best advices.

To Dr. Pierrick Legrand and family, for all your time, patience, advice and support.

To my dear TREE-LAB, the best people! Leonardo, Pierrick, Enrique, Emigdio, Luis, Victor, Perla, Uriel, Angel, Carlos and me. vii To Dr. Francisco Fernández, Dr. Francisco Chávez, Dra. Sara Silva, being witnessed one of the most pleasant experiences I've had, to work with them in their institutions and know that different cultures.

To Dr. Edgar Galván-López, Dr. Victor Díaz-Ramírez, MC Arturo Sotelo, for their valuable comments on work and support.

I would like to express my gratitude to the members of my examination committee.

To the graduate program in Engineering Sciences, specially to the Dr. Luis Nestor Coria, thanks for the support.

To the Department of Electrical and Electronic Engineering at Instituto Tecnológico de Tijuana, for the great support given, MC Carlos Edgar Vázquez and Cinthya López.

I would like to thank to CONACYT for the opportunity to pursue my doctoral studies giving me a scholarship No. 226981. Finally, I would training and amount of overlap for the PGPC. Each row corresponds to each subject (top row is S 1 and bottom row S 4 ) and each column corresponds to a different segment duration; leftmost row is 1 sec., middle row 2 and rightmost 3. . . xii 3.3. Median sensitivity plotted against the day-used for training and the amount of overlap for the SRS-GPC. Each row corresponds to each subject (top row is S 1 and bottom row S 4 ) and each column corresponds to a different segment duration; leftmost row is 1 sec., middle row 2 and rightmost 3. . . 58 3.4. Median specificity plotted against the day used for training and the amount of overlap for the SRS-GPC. Each row corresponds to each subject (top row is S 1 and bottom row S 4 ) and each column corresponds to a different segment duration; leftmost row is 1 sec., middle row 2 and rightmost 3. . . 59 3.5. Median sensitivity plotted against the day used for training and the amount of overlap for the PGPC. Each row corresponds to each subject (top row is S 1 and bottom row S 4 ) and each column corresponds to a different segment duration; leftmost row is 1 sec., middle row 2 and rightmost 3. . . 60 3.6. Median specificity plotted against the day used for training and the amount of overlap for the PGPC. Each row corresponds to each subject (top row is S 1 and bottom row S 4 ) and each column corresponds to a different segment duration; leftmost row is 1 sec., middle row 2 and rightmost 3.

Introduction

Within the field of Evolutionary Computation (EC) [START_REF] Eiben | Introduction to Evolutionary Computing[END_REF] it is not yet clear if a particular algorithm will perform well on a specific problem instance. The "No Free Lunch" (NFL) theorem [START_REF] Wolpert | No free lunch theorems for optimization[END_REF] has provided valuable theoretical and conceptual insights, broadly stating that all search algorithms on average are equivalent when they are evaluated over all possible problems. On the other hand, the NFL theorem does not apply to many common domains of genetic programming (GP) [START_REF] Poli | Free lunches for function and program induction[END_REF], a promising theoretical insight that drives research to develop the best possible GP-based search. Nevertheless, it is by now evident that most GP-based systems tend to perform well on some problem instances while failing on others, with little understanding as to why or when either of those two scenarios will arise (Graff et al., 2013a;[START_REF] Graff | Practical model of genetic programming's performance on rational symbolic regression problems[END_REF][START_REF] Martínez | A comparison of predictive measures of problem difficulty for classification with genetic programming[END_REF]Trujillo et al., 2011a,b).

The above issue can be described as the study of problem difficulty, which has been studied in different ways in EC and GP literature. Some methods focus on analyzing the properties of a problem's fitness landscape [START_REF] Kinnear | Fitness landscapes and difficulty in genetic programming[END_REF]. This can be done, for instance, by defining specific classes of functions [START_REF] He | On the easiest and hardest fitness functions[END_REF], or by extracting high-level features (Graff et al., 2013a;[START_REF] Graff | Practical model of genetic programming's performance on rational symbolic regression problems[END_REF][START_REF] Martínez | A comparison of predictive measures of problem difficulty for classification with genetic programming[END_REF]Trujillo et al., 2011a,b) or statistical properties [START_REF] Clergue | Fitness distance correlation and problem difficulty for genetic programming[END_REF][START_REF] Galván-L Ópez | The effects of constant neutrality on performance and problem hardness in gp[END_REF][START_REF] Galván-L Ópez | Defining locality in genetic programming to predict performance[END_REF][START_REF] Goldberg | Simple genetic algorithms and the minimal, deceptive problem[END_REF][START_REF] Kimura | The neutral theory of molecular evolution[END_REF][START_REF] Rothlauf | Representations for Genetic and Evolutionary Algorithms[END_REF][START_REF] Vanneschi | The k landscapes: A tunably difficult benchmark for genetic programming[END_REF][START_REF] Verel | Where are bottlenecks in NK fitness landscapes[END_REF] of the fitness landscape. In the case of standard tree-based GP, where search operators are applied in syntax space, the concept of a fitness landscape is difficult to define given that there is no clear way of de-introduction termining a general concept of neighborhood for GP representations that are usually highly redundant, which limits the usefulness of such approaches. While some methods have been successfully applied to GP, these are mostly sampling-based techniques that attempt to infer specific types of structures within the underlying fitness landscape, such as: neutrality [START_REF] Galván-L Ópez | The effects of constant neutrality on performance and problem hardness in gp[END_REF]Galván-L ópez and Poli, 2006a,b;[START_REF] Poli | The effects of constant and bitwise neutrality on problem hardness, fitness distance correlation and phenotypic mutation rates[END_REF][START_REF] Yu | Neutrality and the evolvability of boolean function landscape[END_REF]), locality (Galván-L ópez et al., 2010, 2011), ruggedness [START_REF] Vanneschi | The k landscapes: A tunably difficult benchmark for genetic programming[END_REF]), deception (Tomassini et al., 2005), fitness distance correlation (FDC) [START_REF] Clergue | Fitness distance correlation and problem difficulty for genetic programming[END_REF][START_REF] Kaufmann | A study of fitness distance correlation as a difficulty measure in genetic programming[END_REF], fitness clouds [START_REF] Vanneschi | Fitness clouds and problem hardness in genetic programming[END_REF] and negative slope coefficient (NSC) [START_REF] Vanneschi | Negative slope coefficient: A measure to characterize genetic programming fitness landscapes[END_REF][START_REF] Vanneschi | A comprehensive view of fitness landscapes with neutrality and fitness clouds[END_REF]. In this work, we refer to such methods as Evolvability Indicators (EIs), which are extensively reviewed in [START_REF] Malan | A survey of techniques for characterising fitness landscapes and some possible ways forward[END_REF] and discussed in the following section.

One notable shortcoming of EIs is that they require an extensive sampling of the search space in order to compute them [START_REF] Altenberg | Fitness distance correlation analysis: An instructive counterexample[END_REF][START_REF] Quick | Fitness distance correlation and ridge functions[END_REF][START_REF] Vanneschi | Fitness distance correlation in genetic programming: a constructive counterexample[END_REF][START_REF] Vanneschi | Limitations of the fitness-proportional negative slope coefficient as a difficulty measure[END_REF]. This is an important limitation: if we need to know when a particular problem is easy or difficult for an algorithm to solve it may just be easier to run the algorithm and observe its behavior and outcome. Therefore, some researchers have proposed predictive models that take the problem data (or a description of the data) as input, and produce as output a prediction of expected performance, we will refer to such methods as Predictors of Expected Performance (PEPs). Currently, the development of PEPs represents a minority of research devoted to problem difficulty in GP, with only a few recent works. In particular, Graff and Poli (Graff et al., 2013a;[START_REF] Graff | Practical model of genetic programming's performance on rational symbolic regression problems[END_REF][START_REF] Koza | Human-competitive results produced by genetic programming[END_REF], 2011;[START_REF] Graff | Models of performance of evolutionary program induction algorithms based on indicators of problem difficulty[END_REF] have studied the development of such predictive models, for symbolic regression, Boolean and time-series problems. While their original work mostly focused on synthetic benchmarks [START_REF] Graff | Practical model of genetic programming's performance on rational symbolic regression problems[END_REF], more recent contributions extended their approach to performance prediction in real-world problems (Graff et al., 2013a,b). However, in their approach it is necessary to have an extensive knowledge of the realworld problems in advance. Furthermore, their models are intended to predict the performance of the best solution found by GP on the train-1.1 general objective ing set of data, they did not address the prediction of performance on unseen test cases.

This work is an extension of our previous work (Trujillo et al., 2011a,b,c) where PEPs were first proposed for a GP classifier, making several methodological and experimental contributions. First, the PEP models are produced using only simple 2D synthetic datasets that are randomly generated. Second, the PEP models are used to predict the performance of the GP classifier on the test set of data, while previous works mostly focused on predicting performance on the training or learning set (Graff et al., 2013a;[START_REF] Graff | Practical model of genetic programming's performance on rational symbolic regression problems[END_REF][START_REF] Koza | Human-competitive results produced by genetic programming[END_REF], 2011;[START_REF] Graff | Models of performance of evolutionary program induction algorithms based on indicators of problem difficulty[END_REF]. Third, accurate predictions are obtained on unseen real-world problems that are multidimensional and contain imbalanced data. On the other hand, previous works (Graff et al., 2013a;[START_REF] Graff | Practical model of genetic programming's performance on rational symbolic regression problems[END_REF][START_REF] Koza | Human-competitive results produced by genetic programming[END_REF], 2011;[START_REF] Graff | Models of performance of evolutionary program induction algorithms based on indicators of problem difficulty[END_REF]Trujillo et al., 2011a,b,c) used the same type of problems (either synthetic or real) for both training and testing. Fourth, to increase PEP accuracy this work presents an ensemble approach using specialized PEP models called SPEPs. Each SPEP is trained to predict performance within a specific range of classification error. To do so, we use a two-tier approach, where each problem is first classified into a specific group, and then prediction is obtained from the corresponding SPEP which was trained for that group of problems. Finally, it is reasonable to state that the proposed approach could be applied to predict the performance of GP on other learning problems.

General Objective

Build models to predict the expected performance and categorize its difficulty into classification problems using Genetic Programming.

Particular Objectives

1. Characterize the classification problems using descriptive measures.

introduction 2. Build models to predict the expected performance using synthetic classification problems.

3. Categorize the classification problems (in easy or hard).

4. Evaluate the methodology on real-world classification problems, a more interesting and realistic scenario.

Thesis Organization

The remainder of this thesis proceeds as follows.

Chapter 2 shows an overview about Genetic Programming.

Chapter 3 provides a short survey of GP-based classification and presents two implementations of GP classifiers on real-world scenarios.

Chapter 4 reviews the state of art both Evolvability Indicators and Predictors of Expected Performance.

The basic PEP strategy is outlined and evaluated in Chapter 5. Afterwards, Chapter 6 introduces the proposed ensemble strategy based on SPEPs and provides experimental results.

Chapter 7 presents a discussion related to results and contributions. Finally, Chapter 8 contains conclusions and future work.

2

Genetic Programming

The goal of having computers automatically solve problems is central to artificial intelligence, machine learning and the broad area encompassed by what Turing called "machine intelligence" [START_REF] Turing | Computing machinery and intelligence[END_REF]. Machine learning pioneer Arthur Samuel, in his 1983 talk entitled "AI: Where It Has Been and Where It Is Going" [START_REF] Samuel | Ai: Where it has been and where it is going[END_REF], stated that the main goal of the fields of machine learning and artificial intelligence is:

"to get machines to exhibit behaviour, which if done by humans, would be assumed to involve the use of intelligence."

Genetic Programming (GP) is an extension of Genetic Algorithms (GA's) and owes its origin to the work of John Koza [START_REF] Koza | Genetic Programming: On the Programming of Computers by Means of Natural Selection[END_REF]. It basically works as GA's, with the major difference that individuals to be evolved are not fixed length strings of characters, but, generally speaking, computer programs. GP is an evolutionary computation (EC) technique that automatically solves problems without requiring the user to know or specify the form or structure of the solution in advance [START_REF] Poli | Parsimony pressure made easy[END_REF]. At the most abstract level GP is a systematic, domain-independent method for getting computers to solve problems automatically starting from a high-level statement of what needs to be done.

Representation, Initialization and Operators

In GP, programs are usually expressed as syntax trees rather than as lines of code. For example Figure 2.1 shows the tree representation genetic programming of the program max(x + x, x + 3 * y). The variables and constants in the program (x, y and 3) are leaves of the tree. In GP they are called terminals, whilst the arithmetic operations (+, * and max) are internal nodes called functions. The sets of allowed functions and terminals together form the primitive set of a GP system. In more advanced forms of GP, programs can be composed of multiple components (e.g., subroutines). In this case the representation used in GP is a set of trees (one for each component) grouped together under a special root node that acts as glue, as illustrated in Figure 2.2 we will call these (sub)trees branches. The number and type of the branches in a program, together with certain other features of their structure, form the architecture of the program.

Like in other evolutionary algorithms, in GP the individuals in the initial population are typically randomly generated. There are a number of different approaches to generating this random initial popula- tion. Here we will describe two of the simplest (and earliest) methods (the full and grow methods), and a widely used combination of the two known as Ramped half-and-half.

In both the full and grow methods, the initial individuals are generated so that they do not exceed a user specified maximum depth. The depth of a node is the number of edges that need to be traversed to reach the node starting from the tree's root node (which is assumed to be at depth 0). The depth of a tree is the depth of its deepest leaf (e.g., the tree in Figure 2.1 has a depth of 3). In the full method (so named because it generates full trees, i.e. all leaves are at the same depth) nodes are taken at random from the function set until the maximum tree depth is reached. Figure 2.3 shows a series of snapshots of the construction of a full tree of depth 2. The children of the * and / nodes must be leaves or otherwise the tree would be too deep. Thus, at both steps t = 3, t = 4, t = 6 and t = 7 a terminal must be chosen (x, y, 1 and 0, respectively). Although, the full method generates trees where all the leaves are at the same depth, this does not necessarily mean that all initial trees will have an identical number of nodes (often referred to as the size of a tree) or the same shape. This only happens, in fact, when genetic programming all the functions in the primitive set have an equal arity. Nonetheless, even when mixed-arity primitive sets are used, the range of program sizes and shapes produced by the full method may be rather limited. The grow method, on the contrary, allows for the creation of trees of more varied sizes and shapes. Nodes are selected from the whole primitive set (i.e., functions and terminals) until the depth limit is reached. Once the depth limit is reached only terminals may be chosen (just as in the full method). Figure 2.4 illustrates this process for the construction of a tree with depth limit 2. Here the first argument of the + root node happens to be a terminal. This closes off that branch preventing it from growing any more before it reached the depth limit. The other argument is a function (-), but its arguments are forced to be terminals to ensure that the resulting tree does not exceed the depth limit.

GP departs significantly from other evolutionary algorithms in the implementation of the operators of crossover and mutation. The most commonly used form of crossover is subtree crossover. Given two parents, subtree crossover randomly (and independently) selects a crossover point (a node) in each parent tree. Then, it creates the offspring by replacing the subtree rooted at the crossover point in a copy of the first parent with a copy of the subtree rooted at the crossover Figure 2.4: Creation of a five node tree using the grow initialization method with a maximum depth of 2 (t = time). A terminal is chosen at t = 2, causing the left branch of the root to be closed at that point even though the maximum depth had not been reached. point in the second parent, as illustrated in Figure 2.5 Copies are used to avoid disrupting the original individuals. This way, if selected multiple times, they can take part in the creation of multiple offspring programs. Note that it is also possible to define a version of crossover that returns two offspring, but this is not commonly used. Often crossover points are not selected with uniform probability. Typical GP primitive sets lead to trees with an average branching factor (the number of children of each node) of at least two, so the majority of the nodes will be leaves. Consequently the uniform selection of crossover points leads to crossover operations frequently exchanging only very small amounts of genetic material (i.e., small subtrees); many crossovers may in fact reduce to simply swapping two leaves. To counter this, [START_REF] Koza | Genetic Programming: On the Programming of Computers by Means of Natural Selection[END_REF] suggested the widely used approach of choosing functions 90% of the time and leaves 10% of the time. Many other types of crossover and mutation of GP trees are possible.

The most commonly used form of mutation in GP (which we will call subtree mutation) randomly selects a mutation point in a tree and genetic programming substitutes the subtree rooted there with a randomly generated subtree. This is illustrated in Figure 2.6. Subtree mutation is sometimes imple-2.2 selection mented as crossover between a program and a newly generated random program; this operation is also known as "headless chicken" crossover [START_REF] Angeline | Subtree crossover: Building block engine or macromutation[END_REF]. Another common form of mutation is point mutation, which is GP's rough equivalent of the bit-flip mutation used in genetic algorithms [START_REF] Goldberg | Genetic Algorithms in Search, Optimization and Machine Learning[END_REF]. In point mutation, a random node is selected and the primitive stored there is replaced with a different random primitive of the same arity taken from the primitive set. If no other primitives with that arity exist, nothing happens to that node (but other nodes may still be mutated). When subtree mutation is applied, this involves the modification of exactly one subtree. Point mutation, on the other hand, is typically applied on a per-node basis. That is, each node is considered in turn and, with a certain probability, it is altered as explained above. This allows multiple nodes to be mutated independently in one application of point mutation. The choice of which of the operators described above should be used to create an offspring is probabilistic. Operators in GP are normally mutually exclusive (unlike other evolutionary algorithms where offspring are sometimes obtained via a composition of operators). Their probability of application are called operator rates. Typically, crossover is applied with the highest probability, the crossover rate often being 90% or higher. On the contrary, the mutation rate is much smaller, typically being in the region of 1%. When the rates of crossover and mutation add up to a value of probability (τ) which is less than 100%, an operator called reproduction is also used, with a rate of 1τ. Reproduction simply involves the selection of an individual based on fitness and the insertion of a copy of it in the next generation.

Selection

As with most evolutionary algorithms, genetic operators in GP are applied to individuals that are probabilistically selected based on fitness. That is, better individuals are more likely to have more child programs than inferior individuals. The most commonly employed method for selecting individuals in GP is tournament selection, which genetic programming is discussed below, followed by fitness-proportionate selection, but any standard evolutionary algorithm selection mechanism can be used. In tournament selection a number of individuals are chosen at random from the population. These are compared with each other and the best of them is chosen to be the parent. When doing crossover, two parents are needed and, so, two selection tournaments are made. Note that tournament selection only looks at which program is better than another. It does not need to know how much better. This effectively automatically rescales fitness, so that the selection pressure on the population remains constant. Thus, a single extraordinarily good program cannot immediately swamp the next generation with its children; if it did, this would lead to a rapid loss of diversity with potentially disastrous consequences for a run. Conversely, tournament selection amplifies small differences in fitness to prefer the better program even if it is only marginally superior to the other individuals in a tournament. An element of noise is inherent in tournament selection due to the random selection of candidates for tournaments. So, while preferring the best, tournament selection does ensure that even average-quality programs have some chance of having children. Since tournament selection is easy to implement and provides automatic fitness rescaling, it is commonly used in GP. Considering that selection has been described many times in the evolutionary algorithms literature, we will not provide details of the numerous other mechanisms that have been proposed. [START_REF] Goldberg | Genetic Algorithms in Search, Optimization and Machine Learning[END_REF], for example, describes fitness-proportionate selection, stochastic universal sampling and several others.

Terminals and Functions

While it is common to describe GP as evolving programs, GP is not typically used to evolve programs in the familiar Turing-complete languages humans normally use for software development. It is instead more common to evolve programs (or expressions or formulae) in a more constrained and often domain-specific language. The first two preparatory steps, the definition of the terminal and function sets, spec-2.3 terminals and functions functions with no arguments. These may be included because they return different values each time they are used, such as the function rand() which returns random numbers, or a function dist to wall() that returns the distance to an obstacle from a robot that GP is controlling. Another possible reason is because the function produces side effects. Functions with side effects do more than just return a value: they may change some global data structures, print or draw something on the screen, control the motors of a robot, etc.

constants. These can be pre-specified, randomly generated as part of the tree creation process, or created by mutation.

Using a primitive such as rand can cause the behaviour of an individual program to vary every time it is called, even if it is given the same inputs. This is desirable in some applications. However, we more often want a set of fixed random constants that are generated as part of the process of initializing the population. This is typically accomplished by introducing a terminal that represents an ephemeral random constant. Every time this terminal is chosen in the construction of an initial tree (or a new subtree to use in an operation like mutation), a genetic programming

Fitness Function

The first two preparatory steps define the primitive set for GP, and therefore indirectly define the search space GP will explore. This includes all the programs that can be constructed by composing the primitives in all possible ways. However, at this stage, we still do not know which elements or regions of this search space are good. I.e., which regions of the search space include programs that solve, or approximately solve, the problem. This is the task of the fitness measure, which is our primary (and often sole) mechanism for giving a high-level statement 2.5 gp parameters of the problem's requirements to the GP system. For example, suppose the goal is to get GP to synthesize an amplifier automatically. Then the fitness function is the mechanism which tells GP to synthesize a circuit that amplifies an incoming signal. (As opposed to evolving a circuit that suppresses the low frequencies of an incoming signal, or computes its square root, etc. etc.) Fitness can be measured in many ways. For example, in terms of: the amount of error between its output and the desired output; the amount of time (fuel, money, etc.) required to bring a system to a desired target state; the accuracy of the program in recognising patterns or classifying objects; the payoff that a game-playing program produces; the compliance of a structure with user-specified design criteria.

GP Parameters

The most important control parameter is the population size. Other control parameters include the probabilities of performing the genetic operations, the maximum size for programs and other details of the run. It is impossible to make general recommendations for setting optimal parameter values, as these depend too much on the details of the application. However, genetic programming is in practice robust, and it is likely that many different parameter values will work. As a consequence, one need not typically spend a long time tuning GP for it to work adequately. It is common to create the initial population randomly using ramped half-and-half with a depth range of 2-6. The initial tree sizes will depend upon the number of the functions, the number of terminals and the arities of the functions. However, evolution will quickly move the population away from its initial distribution. Traditionally, 90% of children are created by subtree crossover. However, the use of a 50 -50 mixture of crossover and a variety of mutations also appears to work well.

genetic programming

Training Set: fitness-cases

GP is widely used to generate mathematical functions, or operators, that solve symbolic regression and classification problems, which can be stated as follows. The goal is to search for the symbolic expression K : R p → R that best fits a particular training set T = {I 1 , I 2 , . . . , I n }, where

I i = (υ i , ν i ) of n input-output pairs with υ i ∈ R p and ν i ∈ R, stated as K ← arg min K∈G f (K(υ i ), ν i ) with i = 1, . . . , n , (2.1)
where G is the solution or syntactic space defined by the primitive set P of functions and terminals, f is the fitness function which is based on the difference between a program's output K(υ i ) and the desired output ν i . Each input-output pair (υ i , ν i ) is referred to as a fitness-case. As stated above, GP traditionally uses the entire set of fitness-cases T to determine a program's fitness. Recent works, however, have focused on evolving solutions by only using a subset of fitness-cases S G ⊆ T to determine the fitness of each candidate solution K at a given generation G; in some cases reducing the number of considered fitness-cases to a single one. This, of course, can produce one obvious benefit, a reduction in computational cost during fitness evaluation, which is usually the main computational bottleneck in a GP system. However, the motivation for most approaches has been varied. For instance, some methods focus on reducing computational costs during fitness evaluation (Gathercole and Ross, 1994a,b) or reducing overfitting and improving generalization (Gonc ¸alves and Silva, 2013), others have addressed the issue of problem modality [START_REF] Spector | Assessment of problem modality by differential performance of lexicase selection in genetic programming: a preliminary report[END_REF] or attempted to promote novel solutions that can solve every fitness case [START_REF] Martínez | Searching for novel regression functions[END_REF], particularly the most difficult ones (Gathercole and Ross, 1994a,b;[START_REF] Martínez | A comparison of fitness-case sampling methods for symbolic regression with genetic programming[END_REF]. GP traditionally uses the Entire Training Set (ETS) of fitness-cases T to determine a program's fitness. Recent works, however, have focused on evolving solutions by only using a subset of fitness-cases S G ⊆ T to determine the fitness of each candidate solution K at a given generation G; in some cases reducing the number of considered fitness-cases to a single one. This, of course, can produce one obvious benefit, a reduction in computational cost during fitness evaluation, which is usually the main computational bottleneck in a GP system. However, the motivation for most approaches has been varied. For instance, some methods focus on reducing computational costs during fitness evaluation (Gathercole and Ross, 1994a,b) or reducing overfitting and improving generalization (Gonc ¸alves and [START_REF] Gonc ¸alves | Balancing learning and overfitting in genetic programming with interleaved sampling of training data[END_REF], others have addressed the issue of problem modality [START_REF] Spector | Assessment of problem modality by differential performance of lexicase selection in genetic programming: a preliminary report[END_REF] or attempted to promote novel solutions that can solve every fitness case [START_REF] Martínez | Searching for novel regression functions[END_REF], particularly the most difficult ones (Gathercole and Ross, 1994a,b;[START_REF] Martínez | A comparison of fitness-case sampling methods for symbolic regression with genetic programming[END_REF]. In what follows, we review these methods and describe their main details.

Dynamic Training Subset Selection (DTSS) was proposed in Gathercole and Ross (1994a,b), and probably should be considered as the first fitness-case sampling method proposed in GP literature. In their original work, Gathercole and Ross (1994a,b) developed their method for classification problems, outperforming the basic GP approach, but it was only tested on a single problem instance. In each generation G DTSS performs two passes through the entire training set of fitnesscases. It assigns a weight w i to each fitness-case I i computed by

w i (G) = D i (G) d + A i (G) a (2.2)
where D is a function that measures the difficulty of I i , A is an age factor that measures the number of generations G since I i was last selected (D and A are reset to zero once I i is selected), while a and d are parameters that need to be set by the user. Afterwards a total of F fitness are selected using a probability that is proportional to its associated weight, given by Φ = w i n j=1 w j with n the total number of fitnesscases. In their original work, D i represented the total number of times that a particular fitness case was misclassified by the individuals in the population. While the authors reported strong results on some tests, DTSS has not been extensively benchmarked on a variety of problems. Moreover, there are several shortcomings with DTSS. In particular, it requires several parameters to be tuned; the difficulty score is not triv-

genetic programming

Algorithm 1: Interleaved Sampling (IS) Deterministically interleaving between using a single or all training fitness cases at each generation:

(1) Initialize:

(a) Entire training set T = {I 1 , I 2 ...I n }.

(2) First generation:

(a) Evaluate population using T.

(3) Loop on the remaining generations:

(a) Odd generations:

-Generate an integer random number r, where r ∈ [1, n]. -Evaluate population using I r .

(b) Even generations:

-Evaluate population using T.

ially extrapolated to other problems, particularly symbolic regression; and, it is more computationally costly than standard GP since at every generation the algorithm requires two passes over the entire training set of fitness-cases.

Interleaved Sampling and related methods

Interleaved Sampling (IS) (Gonc ¸alves and Silva, 2011) is a deterministic-based sampling method, which uses the entire training set to compute fitness in some generations and uses a single fitnesscase in others. This approach was motivated by the idea of balancing learning and overfitting through the interleaving of fitness-cases, attempting to elude local optima. Determining in which generation to 2.6 training set: fitness-cases Algorithm 2: Random Interleaved Sampling (RIS) Probabilistically interleaving between using a single or all training fitness cases at each generation:

(1) Initialize: (2) Loop for every generation: use a single fitness-case, and in which one to use all of them, is an integral part of the algorithm design. In Gonc ¸alves and [START_REF] Gonc ¸alves | Balancing learning and overfitting in genetic programming with interleaved sampling of training data[END_REF], the authors present two variants that achieved the best results, IS and Random IS or RIS with the probability value of 75%. IS uses the entire training set in odd numbered generations, and uses a single randomly chosen fitness-case on even numbered generations, see the Algorithm 1. RIS, on the other hand, uses a probabilistic decision at the beginning of each generation to determine if all of the fitness-cases are used or a single randomly chosen fitness-case, see the Algorithm 2. In Gonc ¸alves and [START_REF] Gonc ¸alves | Balancing learning and overfitting in genetic programming with interleaved sampling of training data[END_REF], RIS exhibited the best performance with the probability of using a single fitness case set to δ = 0.75. These methods are related to the approach presented in [START_REF] Lasarczyk | Dynamic subset selection based on a fitness case topology[END_REF], that also selects a different subset of fitness-cases at each generation.

genetic programming

Algorithm 3: Lexicase Selection (LEX)

For parent selection:

(1) Initialize:

(a) Set candidates to be the entire population.

(b) Set cases to be a list of all of the fitness cases in random order.

(2) Loop:

(a) Set candidates to be the subset of the current candidates that have exactly the best fitness of any individual currently in candidates for the first case in cases.

(b) If candidates or cases contains just a single element then return the first individual in candidates.

(c) Otherwise remove the first case from cases and go to Loop.

Lexicase Selection

Spector (2012) proposed the concept of modality to describe problems for which an optimal solution must exhibit different modes of operations; i.e., solutions must exhibit distinct behaviors based on contextual information that is provided implicitly by the input data [START_REF] Trujillo | A behaviorbased analysis of modal problems[END_REF]. [START_REF] Spector | Assessment of problem modality by differential performance of lexicase selection in genetic programming: a preliminary report[END_REF] points out that, in general, GP systems are generally limited to problems for which solution programs perform similar actions for all possible inputs, but real-world problems will normally require more complex solutions, that change their behavior depending on context.

To solve such problems, [START_REF] Spector | Assessment of problem modality by differential performance of lexicase selection in genetic programming: a preliminary report[END_REF] presents the Lexicase Selection (LEX) method for parent selection, which allows each fitness case to possibly be the main source of selective pressure at any given parent selection event. During evolution, LEX selects parents by starting Algorithm 4: Keep-Worst Interleaved Sampling (KW-IS)

Deterministically interleaving between using a subset of the most difficult or all fitness cases at each generation:

(1) Initialize: (2) First generation:

(a) Evaluate population using T.

(b) Construct the subset ϕ of the most difficult fitness cases using the ρ value.

(3) Loop on the remaining generations:

(a) Odd generations:

-Evaluate population using ϕ.

(b) Even generations:

(a) Evaluate population using T.

(b) Construct the subset ϕ of the most difficult fitness cases using the ρ value.

with a pool of candidate parents, and removing candidates based on the performance achieved on a single fitness-case. LEX is elitist, all of the individuals that do not achieve the best performance are removed. This process is repeated using another fitness-case, until only one individual remains, which is then returned as the selected parent. In the basic implementation, the initial pool of candidates is composed by the entire population and the fitness-cases are ordered randomly each time a parent is selected. LEX resembles a lexicographic ordering of a character string, where the first fitness-case has the largest effect in choosing the parent, then the next fitness-case acts as tie-breaker, and genetic programming so on. This means that each fitness-case has a chance to be deciding factor in determining which individuals are used to produce offspring at any given parent selection event, see Algorithm 3.

Keep-Worst Interleaved Sampling

Based on [START_REF] Martínez | Searching for novel regression functions[END_REF] and Gonc ¸alves and Silva (2013) we proposed a new fitness-case sampling method called Keep-Worst Interleaved Sampling (KW-IS) [START_REF] Martínez | A comparison of fitness-case sampling methods for symbolic regression with genetic programming[END_REF]. This proposed method is based on the general methodology of the Novelty Searchbaseddescriptor proposed in [START_REF] Martínez | Searching for novel regression functions[END_REF] but it is also common in other learning paradigms such as AdaBoost, for example, where solution design is adjusted based on the most difficult training data samples. KW-IS is similar to IS, using the entire set of fitness-cases in some generations, just like IS would. However, in the remaining generations, fitness-cases are not chosen randomly. Instead, the goal is to bias selective pressure towards individuals that exhibit good performance on the most difficult fitness-cases. Therefore, the fitness-cases are ordered based on difficulty. Afterwards, the ρ value show the percentage of most difficult fitness-cases are used to determine fitness in the next generation, see Algorithm 4. The best performance of this parameter was achieved with ρ = 90. For symbolic regression problems the difficulty of a single fitness case is given by the average absolute error of the entire population in a given generation. Where we take the fitness-cases that have a larger error than the error found in the percentile given the value of ρ. On the other hand, for classification the difficulty of a fitness-case is computed as done in DTSS, by the total number of individuals in the population that misclassified it. Therefore, in the same way we will take the fitness-cases that have been misclassified by ρ percent of the population. KW-IS is closely related to DTSS, since it also focuses on reducing the size of the training set used in each generation by concentrating on a small subset of the most difficult fitness-cases. However, KW-IS requires less parameters to tune, it only performs a single pass of the training set T at each generation G by relying on the estimated difficulty given in generation G -1, and it can be used directly on symbolic regression problems.

Comparison of Fitness-Case Sampling Methods

In order to provide a comprehensive evaluation of the fitness case sampling methods described above we perform experiments using a tree-based GP algorithm with standard subtree crossover and subtree mutation, as originally proposed by [START_REF] Koza | Human-competitive results produced by genetic programming[END_REF]. With this GP system, we test IS, RIS, LEX and KW-IS on two of the most common problems on which GP is used, symbolic regression and classification, using benchmark and real-world problems. Moreover, a standard GP search (GP-STD) is included as the control method.

None of the algorithms have been extensively studied or compared besides our previous study reported in [START_REF] Martínez | A comparison of fitness-case sampling methods for symbolic regression with genetic programming[END_REF], however that work only performed an informal comparison and only considered symbolic regression problems. The algorithms are compared based on the following criteria. First, performance of the best solution found during training evaluated on the test set, a standard evaluation measure. Second is overfitting, here measured by the difference between the training error of the best solutions and its respective test error. Finally, one of the most important open issues with GP is the bloat phenomenon, where the average size of the population increases disproportionately relative to the improvements achieved in terms of fitness [START_REF] Silva | Dynamic limits for bloat control in genetic programming and a review of past and current bloat theories[END_REF]. Therefore, we also compare the methods based on the average size of the population in the final generation, given by the number of nodes of each tree.

In all problems a total of thirty independent runs are performed, with different, and randomly chosen, training and testing sets. Results are analyzed using rank statistics and nonparametric tests, since machine learning algorithms do not tend to produce normally distributed samples [START_REF] Trawinski | Nonparametric statistical analysis for multiple comparison of machine learning regression algorithms[END_REF][START_REF] Derrac | A practical tutorial on the use of nonparametric statistical tests as a methodology for comparing evolutionary and swarm intelligence algorithms[END_REF]. Therefore, the Friedman test multiple comparison [START_REF] Friedman | The Use of Ranks to Avoid the Assumption of Normality Implicit in the Analysis of Variance[END_REF] is used to com-genetic programming pare all of the algorithms on each problem, with the null hypothesis that the mean rank of all methods is the same; the p-value of each test is reported and the significance level is set at α = 0.05. Afterwards, a post-hoc procedure is used, performing pairwise comparisons between all methods using the Friedman test with the Bonferroni-Holm correction [START_REF] Holm | A simple sequentially rejective multiple test procedure[END_REF] of the p-value (considering six methods), under the null hypothesis that each pair of samples share equal medians. The results of all tests are presented in tables with the corresponding pvalues. Moreover, a summary of the medians of each measure (test fitness, average size and overfitting) are presented, using bold to indicate that a given method achieved the best performance on a given problem. For instance, if the performance of all methods are presented in bold, this means that no statistical difference was detected. Similarly, if one (or several) result(s) is (are) in bold, this means that the method(s) achieved significantly different performance compared to the other (non-bold) methods. Box plots are used to graphically illustrate the behavior of each method. Finally, all algorithms were implemented using the GPLab Matlab toolbox [START_REF] Silva | GPLAB -A Genetic Programming Toolbox for MATLAB[END_REF]) and all statistical test were performed using the Matlab statistical toolbox.

Symbolic Regression Problems

Five benchmark problems are used for symbolic regression, originally published in [START_REF] Uy | Semantically-based crossover in genetic programming: application to real-valued symbolic regression[END_REF]suggested in McDermott et al. (2012) and [START_REF] Martínez | Searching for novel regression functions[END_REF]; these problems are summarized in Table 2.3. The experimental parameters used with these problems are given in Table 2.4, and fitness is calculated as the root mean square error between predicted and expected outputs specified in the training set.

Moreover, to get a better assessment of each method in more difficult scenarios, six problems are used to evaluate the algorithms; these are: Toxicity, Plasma Protein Binding, Bioavailability, Concrete, Housing and Yacht. The first three problems are described in Gonc ¸alves and [START_REF] Gonc ¸alves | Balancing learning and overfitting in genetic programming with interleaved sampling of training data[END_REF] and the remaining three from the University of California, Irvine (UCI) machine learning repository [START_REF] Lichman | UCI machine learning repository[END_REF], which Table 2.3: Five symbolic regression problems, originally published in [START_REF] Uy | Semantically-based crossover in genetic programming: application to real-valued symbolic regression[END_REF], and suggested as benchmark regression problems in [START_REF] Mcdermott | Genetic programming needs better benchmarks[END_REF] and [START_REF] Martínez | Searching for novel regression functions[END_REF]. are characterized by a high-dimensionality and a difficult to model behavior. The experimental parameters used are the same as those in Gonc ¸alves and [START_REF] Gonc ¸alves | Balancing learning and overfitting in genetic programming with interleaved sampling of training data[END_REF], summarized in Table 2.5. Fitness is calculated as the root mean square error between predicted and expected outputs, and the data set is randomly divided before each run, using 50% for training and 50% for testing.

Problem Function Fitness/Test cases f 1 -Benchmark x 4 + x 3 + x 2 + x 20 random points ⊆ [-1, 1] f 2 -Benchmark x 5 + x 4 + x 3 + x 2 + x 20 random points ⊆ [-1, 1] f 3 -Benchmark sin(x 2 ) * cos(x) -1 20 random points ⊆ [-1, 1] f 4 -Benchmark log(x+1)+log(x 2 +1) 20 random points ⊆ [0, 2] f 5 -Benchmark 2sin(x) * cos(y) 100 random points ⊆ [-1, 1] × [-1, 1]
For the benchmark problems, the five box plots in Figure 2.7 show the performance of of the best individual from each run evaluated with the test set. and 2.12, for test performance, overfitting and average population size respectively.

To summarize these results a numerical comparison of the methods is provided in Table 2.6 the null hypothesis is rejected at the α = 0.05 significance level. The results on symbolic regression reveal several interesting trends.

First, considering test performance the following can be observed. For all benchmark problems none of the fitness-case sampling methods outperform GP-STD. In fact, only LEX can compare on test performance, while RIS achieves the worst results of all methods. On the other hand, for the real-world problems GP-STD is outperformed by at least 2 fitness-case sampling methods, and in two problems by six of them. In these problems, LEX and KW-IS clearly show the best performance, while IS outperforms GP-STD on two of the six problems (Toxicity and Plasma). Again, RIS clearly is the worst of all fitness-case sampling methods.

Based on overfitting, IS shows the best performance, on both the synthetic benchmarks and the real-world problems. Similarly, RIS shows strong performance on the real-world cases. The performance of IS and RIS is consistent with those reported in Gonc ¸alves and [START_REF] Gonc ¸alves | Balancing learning and overfitting in genetic programming with interleaved sampling of training data[END_REF]. On the other hand, GP-STD and LEX do not seem to overfit on synthetic problems, but clearly do so on the real-world cases. In particular, GP-STD clearly shows the worst performance among all methods genetic programming on the real-world problems. KW-IS shows the weakest performance among all fitness-case sampling methods.

Finally if we consider size, some interesting results can be seen. On synthetic problems there appears to be small differences between the terminal (variable) in three of the six cases. Second, GP-STD consistently produces the larger trees, in some cases one order of magnitude larger than the fitness-case sampling methods. Third, if we consider size and test fitness, then we can say that IS, LEX and KW-IS produce smaller trees with better performance than GP-STD. Afterwards, five problem were chosen, showed in Figure 2.13, that are used to evaluate the algorithms tested here. Additionally, six realworld problems from the University of California, Irvine (UCI) machine learning repository were chosen [START_REF] Lichman | UCI machine learning repository[END_REF], summarized in Table 5.5. These problems have a more complex nature and therefore will be interesting test cases for the sampling methods In this work, was used a GP classifier called static range selection (SRS) [START_REF] Zhang | Using gaussian distribution to construct fitness functions in genetic programming for multiclass object classification[END_REF]. For a two class problem and realvalued GP outputs, the SRS decision rule is simple: if the program output for input pattern υ is greater than zero then the pattern is labeled as belonging to class A, otherwise its labeled as a class B pattern. The experimental parameters are given in Table 2.9, and fitness is given by the classification error.

For the synthetic problems, Figures 2.14, 2.15 and 2.16 illustrate the performance of each method on test fitness, overfitting and average size. Similarly, Figures 2.17 To summarize these results a numerical comparison of the methods is provided in Table 2.10, showing the median values of each method, on each problem and for each measure. Here, bold indicates statistically different results with respect to the other (non-bold) values. Table Table 2 Synthetic). Therefore, these results suggest that no performance improvement is obtained by using fitness-case sampling methods. Based on overfitting, again IS and RIS show the best results, however given their worse performance based on test fitness, they should not be preferred. Among the other methods, the best overfitting performance was exhibited by KW-IS, while GP-STD showed the worst. Finally, based on size, again IS and RIS evolve the smaller trees, but the improvement in program size is not justified by their poor performance. On the other hand, LEX and KW-IS sometimes evolve smaller trees than GP-STD, but in other cases their performance is similar or a bit worse. Given these results, it can be stated that the LEX and KW-IS do not improve upon GP-STD, but they do not compromise performance either, while IS and RIS negatively effect classifier performance.

genetic programming The algorithms were compared using three performance measures: test error, overfitting and average program size. Statistical comparisons were carried out using a non-parametric multigroup test, and a post hoc non-parametric pairwise testing, in both cases at the 95% confidence level.

genetic programming

The results are illustrative and can be summarized as follows. For symbolic regression the conclusions are dependent on the type of problem. For the simpler benchmark problems, none of the sampling methods outperform standard GP, and only LEX achieves equal performance on all problems. However, when we increase difficulty and consider the real-world problems, then we see the added benefit of the sampling approaches, with three of the methods (LEX, KW-IS and IS) significantly improving upon the standard GP approach. The sampling techniques also exhibit substantially smaller amounts of overfitting and also tend to produce smaller trees than standard GP. Based on these results, it is clear that for difficult real-world symbolic regression fitness-case sampling can help improve performance, reduce overfitting and reduce code growth. Furthermore, based on the presented experimental work, the best methods to use are LEX and KW-IS, with IS also exhibiting strong results, and RIS clearly showing the worst performance.

On the other hand, when we consider classification problems, the results are not convincing in favor of the fitness-case sampling methods. In all problems, either synthetic or real-world, none of the tested algorithms could improve upon the performance of standard GP. In fact only two methods achieved the same performance, with LEX and KW-IS never producing worse results. Moreover, while IS and RIS exhibited the smallest amount of overfitting, this result was not satisfactory since their test performance was significantly worse than GP, LEX and KW-IS on most problems. Finally, an unexpected result was that the fitness-case sampling methods showed the same amount of code growth than standard GP, except for IS and RIS, an improvement that is not desirable due to their low test performance.

In conclusion, the main recommendations that can be drawn from these results are the following. First, LEX and KW-IS are useful fitnesscase sampling methods that can improve GP performance on difficult real-world symbolic regression problems. Second, while IS and RIS tend to reduce overfitting and bloat, this comes at the cost of worse test performance, therefore they are not recommended for real-world use. Third, for classification tasks standard GP is still recommended, LEX and KW-IS will not degrade or improve performance in this do-3

Classification with GP

In machine learning one of the most common tasks is supervised classification [START_REF] Kotsiantis | Machine learning: A review of classification and combining techniques[END_REF]. The general task can be stated as follows. Given a pattern υ ∈ R P , assign the correct class label among C distinct classes ω 1 , ..., ω C , using a training set T of P-dimensional patterns with a known label. The idea is to build a mapping g(υ) : R P → C, that assigns each pattern υ to a corresponding class ω i , where g is derived based on the evidence provided by T. GP has been widely used to address this problem [START_REF] Mu Ñoz | M3GP -multiclass classification with GP[END_REF][START_REF] Sotelo | Identification of epilepsy stages from ecog using genetic programming classifiers[END_REF]Trujillo et al., 2011a;[START_REF] Z-Flores | A local search approach to genetic programming for binary classification[END_REF]Zhang andSmart, 2004, 2006). In general, GP can be applied to classification following three general approaches:

1. Feature selection and construction [START_REF] Muharram | Evolutionary constructive induction[END_REF][START_REF] Mu Ñoz | M3GP -multiclass classification with GP[END_REF][START_REF] Sherrah | The evolutionary pre-processor: Automatic feature extraction for supervised classification using genetic programming[END_REF]Trujillo et al., 2011a;[START_REF] Zhang | Using gaussian distribution to construct fitness functions in genetic programming for multiclass object classification[END_REF].

2. Model extraction [START_REF] Bentley | Evolutionary, my dear Watson" Investigating Committee-based Evolution of Fuzzy Rules for the Detection of Suspicious Insurance Claims[END_REF][START_REF] Tanigawa | A study on efficient generation of decision trees using genetic programming[END_REF][START_REF] Tsakonas | A comparison of classification accuracy of four genetic programming-evolved intelligent structures[END_REF][START_REF] Z-Flores | A local search approach to genetic programming for binary classification[END_REF][START_REF] Zhang | Multiclass object classification using genetic programming[END_REF].

3. Learning ensemble classifiers [START_REF] Hengpraprohm | A genetic programming ensemble approach to cancer microarray data classification[END_REF][START_REF] Imamura | Behavioral diversity and a probabilistically optimal gp ensemble[END_REF][START_REF] Langdon | Foundations of genetic programming[END_REF].

Feature selection and construction is also known as preprocessing of the problem data. These approaches use GP to either select the most interesting problem features or to construct new features that simplify the classification problem. These techniques are often described as either filter [START_REF] Guo | Feature generation using genetic programming with application to fault classification[END_REF][START_REF] Muharram | Evolutionary constructive induction[END_REF]Trujillo et al., classification with gp 2011a; [START_REF] Zhang | Using gaussian distribution to construct fitness functions in genetic programming for multiclass object classification[END_REF] or wrapper approaches [START_REF] Mu Ñoz | M3GP -multiclass classification with GP[END_REF][START_REF] Sherrah | The evolutionary pre-processor: Automatic feature extraction for supervised classification using genetic programming[END_REF][START_REF] Smith | Genetic programming with a genetic algorithm for feature construction and selection[END_REF]. In the former, feature construction is done independently of the model used to build the classifier, while in the latter fitness assignment is based on the performance of a classifier. On the other hand, model extraction with GP is used to build specific types of classifiers, such as decision trees [START_REF] Tanigawa | A study on efficient generation of decision trees using genetic programming[END_REF][START_REF] Tsakonas | A comparison of classification accuracy of four genetic programming-evolved intelligent structures[END_REF], classification rules [START_REF] Bentley | Evolutionary, my dear Watson" Investigating Committee-based Evolution of Fuzzy Rules for the Detection of Suspicious Insurance Claims[END_REF][START_REF] Qing-Shan | A modified genetic programming for behavior scoring problem[END_REF] and discriminant functions [START_REF] Zhang | Multiclass object classification using genetic programming[END_REF]. Finally, ensemble classifiers are used to improve the quality of the classification task by using not only a single classifier, but a group of them, each one providing a different output [START_REF] Hengpraprohm | A genetic programming ensemble approach to cancer microarray data classification[END_REF][START_REF] Imamura | Behavioral diversity and a probabilistically optimal gp ensemble[END_REF][START_REF] Langdon | Foundations of genetic programming[END_REF].

Real-World Applications of GP Classifiers

In order to improve understanding of the relevance of the GP classifiers, we present a experimental work about two different approaches, feature construction and model extraction. These experimental work has been over the most interesting problems, real-world scenarios. The goal is to detect the three main stages of an epileptic seizure (Pre-Ictal, Ictal and Post-Ictal) given a short segment of a ECoG signal. This is posed as a classification problem, where the signal segment represents a pattern κ ∈ R n , with n the total number of sample points which is dependent on the sampling rate and the signal duration. For instance, since the sampling rate during recording is 256 Hz, if we take a 2 second signal then n = 512. Then, this can be defined as a supervised learning problem where a training set T of n-dimensional patterns with a known classification are used to derive a mapping function g(υ) : R P → C, where C are the three distinct epilepsy stages.

The proposal is to solve this problem using GP to derive the mapping function g. GP can be used in different ways to solve a supervised classification tasks such as the one presented here, see for instance [START_REF] Koza | Genetic programming II: automatic discovery of reusable programs[END_REF][START_REF] Eggermont | Genetic programming for data classification: partitioning the search space[END_REF]. However, in this work we test 50 3.1 real-world applications of gp classifiers two GP classifiers that have achieved good results in difficult real-world problems, proposed by [START_REF] Zhang | Using gaussian distribution to construct fitness functions in genetic programming for multiclass object classification[END_REF].

Static Range Selection GP Classifier (SRS-GPC)

The first approach is called the Static Range Selection GP Classifier or SRS-GPC a model extraction approach. In this approach, R is divided into C non-overlapping regions, one for each class. Then, GP evolves a mapping g(υ) : R P → R, such that the region in R where pattern υ is mapped to, determines the class to which it belongs. The fitness function is simple, it consists on maximizing the total classification accuracy of g. For the present problem, since there are three classes (the three seizure stages), R is divided into the following three ranges for each stage: Pre-Ictal (inf, -1], Ictal [-1, 1] and Post-Ictal [1, inf). This is a very simple and straightforward GP implementation, that is easy to setup and use. However, an obvious shortcoming is that it requires an a priori definition of the order and size of the region boundaries.

Probabilistic GP Classifier (PGPC)

We refer to the second approach as the Probabilistic GP Classifier, or PGPC (Trujillo et al., 2011a;[START_REF] Zhang | Using gaussian distribution to construct fitness functions in genetic programming for multiclass object classification[END_REF]) a feature construction approach. In PGPC, it is assumed that the behavior of h can be modeled using multiple Gaussian distributions, each corresponding to a single class [START_REF] Zhang | Using gaussian distribution to construct fitness functions in genetic programming for multiclass object classification[END_REF]. The distribution of each class N (µ, σ ) is derived from the examples provided for it in set Υ , by computing the mean µ and standard deviation σ of the outputs obtained from h on these patterns. Then, from the distribution N of each class a fitness measure can be derived using Fisher's linear discriminant; for a two class problem it proceeds as follows. After the Gaussian distribution N for each class are derived, a distance is required. In Zhang and

classification with gp

d = 2 * |µ 1 -µ 2 | σ 1 + σ 2 , (3.3)
where µ 1 and µ 2 are the means of the Gaussian distribution of each class, and σ 1 and σ 2 their standard deviations. When this measure tends to 0, it is the worst case scenario because the mapping of both classes overlap completely, and when it tends to ∞, it represents the optimal case with maximum separation. In order to rescale the above measure, the fitness for an individual mapping h is given by

f d = 1 1 + d . (3.4)
After executing the GP, the best individual found determines the parameters for the Gaussian distribution N i associated to each class. Then, a new test pattern υ is assigned to class i when N i gives the maximum probability.

In summary, we use two different GP classifiers, SRS-GPC and PGPC. Both are trained using the epilepsy signal recorded during a single day, from a total of five different days, and then tested on the remaining days. The signal from each day is divided into segments of equal duration, here we build two different partitions, the first with 1 second signals and the other using 2 second signals. The next section presents the experimental setup and main results.

Experiments and Results

The goal of the experimental work is to evaluate the accuracy of intra-subject classification of epilepsy signals. In other words, to test the performance of classifiers that are trained and tested with signal samples from a single test subject. Keep best elitism a level-5 seizure is elicited and recorded on five consecutive days; call them Day -1, Day -2, Day -3, Day -4 and Day -5. Afterwards, the signal is classified manually by a human expert, who specifies where each epilepsy stage begins and ends. This manual classification establishes the ground-truth for the supervised-learning problem. The signal is divided into C segments, each constituting a sample from the corresponding stage. We test three different segment durations: 1, 2 and 3 seconds. When the signal is divided, we allow for different amounts of overlap between consecutive segments given by a percentage of signal duration. Five different overlaps are tested: 0%, 20%, 40%, 60% and 80%. It is important to state that signal segments that lie on two adjacent stages are removed from the data-sets.

gp implementation Both GP classifiers use a standard Koza style tree based representation, with subtree-crossover and sub-tree mutation. The basic parameters of both systems is presented in Table 3.1.

For both GP classifiers, the terminal elements are basic statistical features computed for each signal segment x that is to be classified. Specifically, the terminal set contains: mean value υ µ , median υ m , standard deviation υ σ , maximum υ max , minimum υ min , skewness υ s and kurtosis υ k . For each experimental configuration, 30 independent runs of the GP system are executed. This is necessary, since GP is a nondeterministic search process.

performance measures To gain a deeper understanding of the GP-based classifiers, a detailed analysis of the results is presented using three standard performance measures computed on the test set of data: classification error, sensitivity and specificity. The first measure is explicit, while the latter two are derived from the confusion matrix (true positives (TP), true negatives (TN), false positives (FP), false negatives (FN)) generated by the classifier with respect to each class; given by:

Sensitivity : S = T P T P + FP . (3.5) Specif icity : Sp = T N FN + T N . (3.6)
intra-subject classification As stated above, the task of automatic epileptic stage identification is posed a supervised learning problem. The training data used consists of all of the signal segments taken from a single recording day. Then, for intra-subject classification the evolved classifiers are tested on the signal segments from each additional recording day. This is done for all subjects (S 1 , S 2 , S 3 and S 4 ) and all possible combinations of training and testing days, as well as for all segment durations (1,2 or 3 seconds) and overlaps (0, 20, 40, 60 and 80%). Figure 3.1 shows the median classification error achieved by the SRS-GPC. The error is plotted with respect to the day used to train the classifier and the amount of overlap. Each row corresponds to each subject (top row is S 1 and so on) and each column corresponds to a classification with gp different segment duration (leftmost row is 1 sec. and so on). Figure 3.2 presents the same for PGPC.

Figures 3.3 and 3.4 present the results for the median sensitivity and specificity respectively, for SRS-GPC. Similarly, figures 3.5 and 3.6 show the same results for PGPC.

discussion The plots shown in Figures 3.1 -3.6 present an extensive empirical evaluation of the proposed approach for stage identification. The best way to read these plots is as follows. In all cases, the flatness of the plotted surfaces is related to the robustness of the proposed approach to the different data configurations. Moreover, for classification error lower values are best, and for sensitivity and specificity the converse is true.

The plots shown above illustrate strong statistical trends regarding the behavior of the system, from which several noticeable implications can be derived. First, overall the best performance is achieved by the simpler SRS-GPC classifier, compared with PGPC. This was slightly unexpected, given the strong assumptions made by the SRS-GPC method. Nonetheless, across all configurations and all test subjects, SRS-GPC is better based on all three performance measures. Second, it appears that the segment length is an important determining factor in classification performance. In particular, smaller segments (1 or 2 seconds) are easier to classify than longer ones (3 s). Also, it appears that a higher amount of overlap between segments can induces better results. A reasonable explanation for both observations can be given based on the machine learning approach followed by the proposal. In particular, shorter segments and a larger overlap produce more training data with which to train the classifier and thus obtain a better supervised learning process.

Third, while the results described above hold for all test subjects, there are still some subtle and important differences among them. The GP classifiers achieve good results for three of the test subjects (S 1 , S 2 and S 3 ), evidenced by all three performance measures. However, the performance is considerably worse for test subject S 4 . This result is coherent with the general observation that different subjects can produce quite different signal patterns, even if all signals appear similar at a classification with gp classification with gp coarser scale. Moreover, the plots show that classifier performance can sometimes vary depending upon which training day is used. In effect, this shows that, of course, the recorded signals should not be expected to be homogenous given the different (even if slight) conditions under which each recording session is done.

Finally, considering results obtained in previous work using GADs [START_REF] Sotelo | Epoch parameterization by gabor atom density in experimental epilepsy[END_REF][START_REF] Sotelo | Epilepsy stages diagnosis by gabor atom density according to their aspect ratio[END_REF], here we find that the ability to identify epilepsy stages are substantivally better with the GP classifiers. The results suggest that the time domain properties used in GP were more efficient for stage classification than the signal complexity computed from the time-frequency domain. Moreover, such features, and the evolved classifiers, are of low computational complexity and could be easily implemented on dedicated hardware.

Here is presented an automatic method for identifying the three main stages of an epileptic seizure from ECoG signals. The proposal is based on posing the problem as a supervised learning problem and solving it with Genetic Programming. The results exhibit strong statistical tendencies of the GP classifiers that suggest that the approach is able to solve the intra-patient classification problem. These results are unique and show substantial improvement when compared with previous methods [START_REF] Sotelo | Epoch parameterization by gabor atom density in experimental epilepsy[END_REF][START_REF] Sotelo | Epilepsy stages diagnosis by gabor atom density according to their aspect ratio[END_REF][START_REF] Sotelo | Epilepsy ictal stage identification by 0-1 test of chaos[END_REF].

4

The estimation of problem difficulty: Related Work

Determining problem difficulty has been an important issue in EC for several years [START_REF] Mcclymont | The lay of the land: a brief survey of problem understanding[END_REF]. From an algorithmic perspective, problem difficulty can be related to the total runtime (or memory) required to find an optimal solution. Recently, [START_REF] He | On the easiest and hardest fitness functions[END_REF] took this view one step further, to analytically define broad classes of fitness functions which allowed them to demonstrate that easy functions define unimodal fitness landscapes, while hard functions define deceptive landscapes for a (1+1) ES. However, it is important to remember that the difficulty of a particular problem depends upon the solution method. Therefore, in what follows we will try to limit our overview to GP-related research.

Evolvability Indicators

The fitness landscape has dominated the way geneticists think about biological evolution and has been adopted by the EC community as a way to visualize evolution dynamics [START_REF] Wright | The roles of mutation, inbreeding, crossbreeding and selection in evolution[END_REF]. Formally, a fitness landscape can be defined as a triplet ( , χ, f ), where is a set of configurations, χ is a notion of neighborhood, distance or accessibility on , and f is a fitness function [START_REF] Stadler | Fitness landscapes[END_REF]. The local and global structure of the fitness landscape describes the underlying difficulty of a search. However, in the case of standard GP [START_REF] Langdon | Foundations of genetic programming[END_REF] the concept of a fitness landscape is not clearly defined [START_REF] Kinnear | Fitness landscapes and difficulty in genetic programming[END_REF]. To overcome this, some works have constructed synthetic the estimation of problem difficulty: related work problems; such as the Royal Tree problem [START_REF] Punch | Advances in genetic programming[END_REF] or the Klandscapes model [START_REF] Vanneschi | The k landscapes: A tunably difficult benchmark for genetic programming[END_REF], where the goal of the search is defined as a particular tree structure with a specific syntax. Unfortunately, such models are not realistic since the space of possible programs is highly redundant [START_REF] Langdon | Foundations of genetic programming[END_REF] in most domains, and the goal is not a particular syntax but a particular expected output, also known as semantics [START_REF] Mcphee | Semantic building blocks in genetic programming[END_REF][START_REF] Vanneschi | A survey of semantic methods in genetic programming[END_REF]. Therefore, some researchers have proposed variants of GP that explicitly account for program semantics. In semantic space the fitness landscape is clearly defined and unimodal. This has lead researchers to develop specialized search operators that modify program syntax while geometrically bounding the semantics of the generated offspring, this is known as geometric semantic GP (GSGP) [START_REF] Moraglio | Geometric semantic genetic programming[END_REF]. Nevertheless, such approaches are still problematic since the size of the evolved programs grows exponentially with every generation, a limitation that is not easily solved [START_REF] Silva | Dynamic limits for bloat control in genetic programming and a review of past and current bloat theories[END_REF]. This work will focus on measures of problem difficulty for standard GP systems [START_REF] Koza | Genetic Programming: On the Programming of Computers by Means of Natural Selection[END_REF], but could be applied to other supervised learning systems including GSGP.

In general, most meta-heuristics work under the assumption that the fitness of a candidate solution, a point on the fitness landscape, is positively correlated with the fitness of its (some) neighbors. Such a property can be defined as the evolvability of a landscape [START_REF] Altenberg | The evolution of evolvability in genetic programming[END_REF]O'Neill et al., 2010). EIs extract a numerical indicator of a specific property of the fitness landscape to provide a measure of the evolvability within the landscape. [START_REF] Malan | A survey of techniques for characterising fitness landscapes and some possible ways forward[END_REF] presents a comprehensive survey of EIs and other forms of fitness landscape analysis. Those that have been studied in GP literature include neutrality [START_REF] Galván-L Ópez | The effects of constant neutrality on performance and problem hardness in gp[END_REF][START_REF] Kimura | The neutral theory of molecular evolution[END_REF]), locality (Galván-L ópez et al., 2010;[START_REF] Rothlauf | Representations for Genetic and Evolutionary Algorithms[END_REF], ruggedness [START_REF] Kauffman | Towards a general theory of adaptive walks on rugged landscapes[END_REF][START_REF] Vanneschi | The k landscapes: A tunably difficult benchmark for genetic programming[END_REF], fitness distance correlation (FDC) [START_REF] Clergue | Fitness distance correlation and problem difficulty for genetic programming[END_REF][START_REF] Jones | Fitness distance correlation as a measure of problem difficulty for genetic algorithms[END_REF][START_REF] Kaufmann | A study of fitness distance correlation as a difficulty measure in genetic programming[END_REF], fitness clouds [START_REF] Verel | Where are bottlenecks in NK fitness landscapes[END_REF] and the negative slope coefficient (NSC) [START_REF] Vanneschi | Fitness clouds and problem hardness in genetic programming[END_REF]. While these approaches can sometimes provide good estimates of problem difficult for GP, they suffer from two practical limitations. First, for each new problem instance they require a large amount of data, by sampling the search space or performing several runs. Second, they cannot estimate the actual quality of the solution found, which can be important if we want to choose the best algorithm to use for a new problem, and if such a choice must be made in realtime. Indeed, [START_REF] Malan | A survey of techniques for characterising fitness landscapes and some possible ways forward[END_REF] point out that a possible way forward is to build a mapping that can estimate algorithm performance based on a set of descriptive features of the problem, an approach that would provide a more practical measure of problem difficulty and allow us to choose the best algorithm for the specific task. [START_REF] Malan | Particle swarm optimisation failure prediction based on fitness landscape characteristics[END_REF] attempted to find a link between EIs and algorithm performance for particle swarm optimization.

Performance Prediction

PEPs predict the performance of a GP search on an unseen problem instance without performing the search or sampling the solution space. These models have been derived using a machine learning approach (Graff et al., 2013a;[START_REF] Graff | Practical model of genetic programming's performance on rational symbolic regression problems[END_REF][START_REF] Martínez | A comparison of predictive measures of problem difficulty for classification with genetic programming[END_REF]Trujillo et al., 2011a,b). The performance of GP on a set of problems and a description of those problems are used to pose a supervised learning task. A promising feature of PEPs is that they are not only useful for GP, they can also be used to predict the performance of other algorithms [START_REF] Graff | Practical performance models of algorithms in evolutionary program induction and other domains[END_REF][START_REF] Trujillo | Estimating classifier performance with genetic programming[END_REF]. [START_REF] Graff | Practical performance models of algorithms in evolutionary program induction and other domains[END_REF] proposed linear predictive models based on a sampling of the fitness landscape, given by

Ψ (ν) ≈ a 0 + ξ∈Ξ a ξ • d(ξ, ν) , (4.7)
where Ψ (ν) is the predicted performance, ν is the target functionality, d(ξ, ν) is a distance measure1 , Ξ is the set of all possible program outputs, also known as semantic space [START_REF] Moraglio | Geometric semantic genetic programming[END_REF], and where the estimation of problem difficulty: related work each ξ represents the vector of program outputs obtained from the set of fitness cases used to define a particular problem, also known as the semantics of the program [START_REF] Mcphee | Semantic building blocks in genetic programming[END_REF]. In other words, [START_REF] Graff | Practical performance models of algorithms in evolutionary program induction and other domains[END_REF] derive PEPs by sampling semantic space Ξ. These models were tested on symbolic regression and 4-input Boolean problems with promising results.

The second and more recent approach towards building a PEP focuses on the problem data (Graff et al., 2013a;[START_REF] Graff | Performance models for evolutionary program induction algorithms based on problem difficulty indicators[END_REF][START_REF] Graff | Models of performance of evolutionary program induction algorithms based on indicators of problem difficulty[END_REF][START_REF] Martínez | A comparison of predictive measures of problem difficulty for classification with genetic programming[END_REF]Trujillo et al., 2011a[START_REF] Trujillo | A comparative study of an evolvability indicator and a predictor of expected performance for genetic programming[END_REF]Trujillo et al., , 2011b,c) ,c) and proceeds as follows. Assume we want to solve a supervised learning problem p with a GP search, where fitness is given by a cost function that must be minimized, such as an error measure. Let us define the performance of the GP algorithm as the associated error of the best solution found during training when it is evaluated on a particular set of fitness cases T , call this quantity F T (p). The goal is to predict F T (p), so first we construct a feature vector β = (β 1 , β 2 , ...β N ) of N distinct features that describe the main properties of p. Then, a PEP is function K such that

F T (p) ≈ K(β) . (4.8)
Notice that the form of K is not a priori restricted in any way. [START_REF] Graff | Performance models for evolutionary program induction algorithms based on problem difficulty indicators[END_REF] use a linear function similar to the one used in their previous work [START_REF] Graff | Practical performance models of algorithms in evolutionary program induction and other domains[END_REF]. Using this approach the feature vector β should be designed specifically for the domain of p. For example, features designed for symbolic regression and Boolean problems are proposed in [START_REF] Graff | Performance models for evolutionary program induction algorithms based on problem difficulty indicators[END_REF], and the results show that the predictive accuracy surpasses that of the fitness-based models proposed in [START_REF] Graff | Practical performance models of algorithms in evolutionary program induction and other domains[END_REF]. However, their work did not scale well to realworld cases. For instance, in Graff et al. (2013a,b) the authors built PEPs to predict performance on real-world problems, but require information obtained from runs performed on similar problem instances, models built with simpler synthetic problems could not be used. It was not trivial to map multidimensional problems to the proposed feature space since the training problems were much simpler with a small number of dimensions. It would be impractical to consider all possi-ble dimensionalities during training. This is an important limitation in building PEPs, since it is not trivial to have all the possible versions of the same problem. Moreover, in the proposals made by Graff et al. (2013a); [START_REF] Graff | Performance models for evolutionary program induction algorithms based on problem difficulty indicators[END_REF]; [START_REF] Graff | Models of performance of evolutionary program induction algorithms based on indicators of problem difficulty[END_REF] the models predicted the performance of the GP system on the training set of fitness cases; i.e., T was the training set. While certainly of importance, performance on the training set may not be useful if the algorithm overfits the training examples, which happens often in real-world scenarios.

In previous work Trujillo et al. (2011a,b,c), we used a similar approach to predict the performance of a GP-classifier using descriptive features that characterize the geometry of the data distribution in feature space. The PEPs where built using quadratic linear models and non-linear GP models, the latter achieving the best performance on synthetic problems. However, it was not clear how well the PEPs generalized to unseen problem instances, particularly to real-world problems with imbalanced datasets and larger feature spaces than those used to train the models, a similar difficulty pointed out in Graff et al. (2013a,b). The current work extends our previous contributions by performing the learning process on 2D synthetic problems and testing on a wide variety of real-world datasets. Moreover, an important contribution of this work is that the PEP models are used to predict the performance of the best solution found by GP when it is evaluated on the test set of data. To achieve improved performance this work also proposes a two-tiered ensemble approach using specialized PEP models and a preprocessing stage for dimensionality reduction.

PEP: Predictor of Expected Performance

The general goal of this work is to build models that can predict the performance of a GP-classifier (PGPC) without executing the search or sampling the problem's search space. The general proposal is depicted in Figure 5.1, where for a given classification problem we do the following. First, apply a preprocessing step to simplify the feature extraction process and deal with multidimensional representations. Second, perform feature extraction to obtain an abstraction of the problem. Third, use a PEP model that takes as input the extracted features and produces as output the predicted classification error (PCE) on the testing set.

Moreover, to derive the PEP models we use a supervised learning methodology, depicted in Figure 5.2. This process takes as input a set of synthetic classification problems Q and produces as output the PEP model as follows:

1. Compute the average classification error (CEµ) on the test data by PGPC for each p ∈ Q.

2. Apply a preprocessing for dimensionality reduction using principal component analysis (PCA), and take the first m principal components to represent the problem data.

3. Perform feature extraction on the transformed data using statistical and complexity measures to build a feature vector β for each p ∈ Q.

pep: predictor of expected performance (2) apply a preprocessing for dimensionality reduction;

(3) extract the feature vector β from the problem data; and (4) learn the predictive model using GP.

4. Finally, using the set of feature vector/performance pairs {(β i ,CEµ i )}, formulate a supervised symbolic regression problem and solve it using GP.

Synthetic Classification Problems

A set of synthetic classification problems was generated to learn our PEP models. Specifically, 500 binary classification problems were generated using Gaussian mixture models (GMMs) with either unimodal or multimodal classes, with different amounts of class overlap. All class samples lie within the closed 2-D interval υ, ν ∈ [-10, 10], and 200 sample points were randomly generated for each class. The parameters for 5.2 pgpc classification error the GMM of each class were randomly chosen using a uniform distribution in the following ranges:

1. Number of Gaussian components: {1, 2, 3}.

PGPC Classification Error

For each problem p ∈ Q we perform 30 runs of PGPC, randomly choosing the training and testing sets in each run. Then, the mean classification error CEµ is computed by the average of the test performance achieved by the best solutions found in each run. The parameters of the PGPC system are given in Table 5.1, a tree-based GP algorithm with dynamic depth bloat control [START_REF] Silva | Dynamic limits for bloat control in genetic programming and a review of past and current bloat theories[END_REF], implemented using Matlab and the GPLAB toolbox [START_REF] Silva | GPLAB -A Genetic Programming Toolbox for MATLAB[END_REF]. Figure 5.3 presents some examples, showing the problem data, the CEµ achieved by PGPC and the standard deviation σ over all runs. The problems are ordered from the lowest CEµ (easiest problem, depict in Fig. 5.3(a)) to the highest, CEµ (hardest problem, depict in Fig. 5.3(f)).

Figure 5.4 summarizes PGPC performance over all 500 synthetic problems in Q. Figure 5.4(a) plots the CEµ for each problem, ordered from the lowest to the highest error. On the other hand, Figure 5.4(b) shows an histogram of PGPC performance, quantifying how many problems are solved with a particular CEµ. We arbitrarily set a threshold such that problems in the range 0 ≤CEµ ≤ 0.15 are considered "easy" and the rest are considered to be "hard". From this perspective the plot reveals that randomly generated problems produce a 71 pep: predictor of expected performance intend to use this set to pose a supervised learning task, this would induce an unwanted bias. Therefore, we subsample Q to get a more balanced distribution over CEµ. The new set consists of 300 problems, and Figure 5.5 summarizes PGPC performance over this new set Q . Notice that the performance plot for Q ⊂ Q is similar to the one obtained for Q (see Figure 5.5(a)), but now the distribution over CEµ is flat (Figure 5.5(b)), providing a more balanced learning set.

Preprocessing

Previous work has found that PEP models can predict GP performance accurately for small scale synthetic problems [START_REF] Graff | Practical model of genetic programming's performance on rational symbolic regression problems[END_REF][START_REF] Koza | Human-competitive results produced by genetic programming[END_REF], 2011;[START_REF] Martínez | A comparison of predictive measures of problem difficulty for classification with genetic programming[END_REF]Trujillo et al., 2011a[START_REF] Trujillo | A comparative study of an evolvability indicator and a predictor of expected performance for genetic programming[END_REF] to take the first m principal components to represent the data of each problem. In particular, we set m = 2 in all experiments reported here. In this way, all problems are reduced to the same number of dimensions used in the synthetic training set.

Feature Extraction

The goal of this step is to extract a set of descriptive measures from each problem. In this work, we use a subset of the features proposed in [START_REF] Sohn | Meta analysis of classification algorithms for pattern recognition[END_REF] and [START_REF] Ho | Complexity measures of supervised classification problems[END_REF]. Those works attempted to develop meta-representations of classification problems. A wider set of features was previously tested in Trujillo et al. (2011a[START_REF] Trujillo | A comparative study of an evolvability indicator and a predictor of expected performance for genetic programming[END_REF]Trujillo et al. ( , 2011b,c),c), but the present work only uses those features that showed the highest correlation with CEµ. We also propose three new descriptors based on the Canberra distance; each measure is presented next. geometric mean (sd) measures the homogeneity of covariances [START_REF] Michie | Machine learning, neural and statistical classification[END_REF][START_REF] Sohn | Meta analysis of classification algorithms for pattern recognition[END_REF]. This quantity is related to a test of the hypothesis that all populations have a common covariance structure; i.e.. to the hypothesis H 0 : 1 = 2 , which can be tested via Box's M test statistic (MTS) [START_REF] Anderson | Introduction to multivariate statistical analysis[END_REF], that can be re-expressed as

SD = exp        MT S m C i=1 (n i -1)        (5.9)
where C is the number of classes, n i is the number of the instances for i-th class and m is the number of dimensions. The SD is strictly greater than unity if the covariances differ, and is equal to unity if and only if the MTS is zero.

feature efficiency (fe) measures the amount by which each feature dimension contributes to the separation of both classes. This measure is computed for the ith dimension by

FE i = 1 - η i tp (5.10)
where η i represent the number of points inside the overlapping region and tp is the total number of sample points; as seen in Figure 5.6(a). Finally, we define FE = max({FE i }) with i = [1, m] for any given problem with m dimensions.

class distance ratio (cdr) compares the dispersion within the classes to the gap between the classes [START_REF] Ho | Complexity measures of supervised classification problems[END_REF]. For each data sample, compute the Euclidean distance to its nearest neighbor within the class (intraclass distance) and nearest-neighbor from the other class (interclass distance), as shown in Figure 5.6(b). The CDR is the ratio of the averages of all intraclass and interclass distances.

volume of overlap region (vor) provides an estimate of the amount of overlap between both classes in feature dimension space [START_REF] Ho | Complexity measures of supervised classification problems[END_REF]. The VOR is computed by finding, for each dimension, the maximum and minimum value of each class and then calculating the length of the overlap region. The length obtained from each dimension is then multiplied to measure the overlapping region, as depicted in Figure 5.6(c). The VOR is zero when there is at least one dimension in which the two classes do not overlap.

canberra distance (cd) provides a numerical measure of the distance between pairs of points in a vector space. Suppose a problem has m feature dimensions, we take a rank statistic of the samples of each class, call it υ i for class 1 and ν i for class 2, for the i-th dimension. This produces two vectors -→ υ and -→ ν , such that -→ υ = (υ 1 , ..., υ m )

and -→ ν = (ν 1 , ..., ν m ). The CD is given by .11) In this work, we use the CD to describe the distance between both classes using three rank statistics: (1) CD-1 uses the 1st quartile; (2) CD-2 uses the median; and (3) CD-3 uses the 3rd quartile. The set of descriptive measures discussed above helps to minimize the information about each problem. Now, analyzing the algorithmic complexity (big O notation) of the measures, these do not represent a significant computational cost. For instance, the FE, VOR, CD-1, CD-2 and CD-3 features mainly depend on a sorting process, which can have a complexity of O(nlogn) where n is the number of instances of the problem. Moreover, the SD relies on computing the covariance matrix of the data which has a complexity of O(n 2 ). Similarly, to compute the CDR feature we need to do all pairwise comparisons, which also has a complexity of O(n 2 ).

CD( - → υ , - → ν ) = 1 m m i=1 |υ i -ν i | |υ i | + |ν i | . ( 5
Figure 5.7 provides a visual description of the descriptive power of each feature. The figure shows scatter plots where each point corresponds to a single problem p ∈ Q , the x-axis is a particular feature (SD,

Supervised Learning of PEP Models

It is now possible to pose a symbolic regression problem using the set T = {(β i ,CEµ i )} with i = 1, .., |Q |, where the goal is to evolve a model K that can predict each CEµ i using β i as input. Previous works have used several types of linear models [START_REF] Graff | Performance models for evolutionary program induction algorithms based on problem difficulty indicators[END_REF][START_REF] Martínez | A comparison of predictive measures of problem difficulty for classification with genetic programming[END_REF]Trujillo et al., 2011a[START_REF] Trujillo | A comparative study of an evolvability indicator and a predictor of expected performance for genetic programming[END_REF]Trujillo et al., , 2011b,c),c), but (Trujillo et al., 2011a,b,c) showed that non-linear models evolved with GP achieved higher prediction accuracy.

Therefore, in this work we use a tree-based GP, configured with the parameters given in Table 5.2. Three versions of the problem are posed, each with a different terminal set defined as subsets of all extracted features (4F, 5F, 7F) as specified in Table 5.3. Set 4F uses the features with the four highest correlation coefficients (FE, CDR, VOR and CD-1), set 5F uses the features with the five highest correlation coefficients (SD, FE, CDR, VOR and CD-1), and 7F uses all of the seven features. The function set is defined as

F = +, -, * , /, √ ,sin, cos, log, x y , | • |, if .
Finally the fitness function is computed by the root mean squared error (RMSE) between the predicted CE and the true CEµ i , given by

f (K) = n i=1 (K(β i ) -CEµ i ) 2 n .
(5.12)

Testing the PEP models

For each version of the symbolic regression problem defined above (with different feature sets), we performed 100 runs using two different test scenarios: (1) train and test the PEP models using only synthetic problems; and (2) train with synthetic problems and test with realworld problems. In the first scenario, we use 70% of the problems for training and the rest for testing, generating a random partition of the set of problems Q for each run. This is the simplest scenario, since both the training and testing problems are generated in the same manner. The numerical results are encouraging, suggesting that the PEP models can accurately predict PGPC performance. Moreover, there is a very small difference between training and testing performance, suggesting that the PEP models are not overfitted.

Figure 5.8 shows plots in three rows, where in each row we plot each feature set (PEP-4F, PEP-5F and PEP-7F). The plots on the lefthand side column show the PCE of the best PEP model and the true CEµ for all synthetic problems, specifying the RMSE. The plots on the right-hand side column show the CEµ and PCE as scatter plots, specifying the Pearson's correlation coefficient ρ. The evolved PEPs produce accurate predictions with all feature sets.

Testing on Real-World Classification Problems

This section presents the results of testing the best evolved PEPs to predict the testing error of PGPC on real-world problems. To this end, twenty-two real-world datasets are chosen from the University of California Irvine (UCI) machine learning repository [START_REF] Lichman | UCI machine learning repository[END_REF], summarized in Table 5.5. Since our PEPs only consider binary classification, we use these datasets to build 40 binary classification problems. The problems are summarized in Table 5.6, specifying the name of the dataset and the classes used to define each problem, the number of total samples and the imbalance percentage of each problem computed that the synthetic problems used to train the PEPs are completely balanced and relatively small problems in terms of number of samples, while the real-world problems are considerably more varied. In particular, considering class imbalance Figure 5.9 shows an histogram of the number of problems with different amounts of imbalance percentage. Before testing the evolved PEP models, we compute the CEµ achieved by PGPC using 30 independent runs. PGPC performance is pep: predictor of expected performance 5.7 summarizes the performance of the evolved PEPs applied on the real-world problems, showing the median of the RMSE of the best solution found, as well as the RMSE and Pearson's correlation coefficient ρ of the best solution. The table presents three rows of results, one for each feature set (PEP-4F, PEP-5F and PEP-7F). In this case, the best performance is achieved by PEP-4F, which was unexpected. However, if we contrast the results with those achieved on the set of synthetic problems, shown in Table 5.4, a performance drop-off is evident, based on both median and best performance.

Figure 5.12 shows three rows of plots, one for each feature set (PEP-4F, PEP-5F and PEP-7F). The figures on the left-hand side column show the PCE of the best PEP model and the true CEµ for all real-world problems, specifying the RMSE. The figures on the right-hand side column show the CEµ and PCE as scatter plots, specifying the Pearson's correlation coefficient ρ. Again, these figures reveal that the evolved PEP models provide less accurate prediction on real-world problems.

Comparative Study of EI and PEP

FDC is a measure for problem difficulty originally proposed for genetic algorithms (GA's) [START_REF] Jones | Fitness distance correlation as a measure of problem difficulty for genetic algorithms[END_REF] and later extended to GP [START_REF] Kaufmann | A study of fitness distance correlation as a difficulty measure in genetic programming[END_REF]. The logic behind FDC proceeds as follows. Assume that we can compute the genotypic distance between each valid individual and the (global) optimum to a problem. If this distance is pep: predictor of expected performance negatively correlated with the fitness of each individual then the search problem should be characterized as easy, and it should be characterized as difficult if no correlation is detected. Moreover, a problem should be considered to be deceptive if the correlation is positive. While FDC has shown to be reliable in many test cases, its more glaring weakness is that the optimal solution must be known a priori, somewhat not realistic for real-world problems.

Following the same general assumptions of FDC, [START_REF] Vanneschi | Fitness clouds and problem hardness in genetic programming[END_REF] propose the NSC. In the case of NSC, knowledge about the global optimum is not required. Instead, NSC relies on the concept of fitness clouds, a scatter plot where for each genotype υ a point is plotted on a 2-D plane, where the horizontal axis corresponds with the fitness of υ given by f (υ), and the vertical axis represents the fitness f (ν) of a neighbouring genotype ν. The hypothesis behind NSC is that the fitness cloud shape provides a meaningful description of the evolvability of a problem for GP-based search. The NSC is computed by assuming a piecewise linear relationship between f (υ) and f (ν) for a sample of ζ individual genotypes and computing the slope of the scatter points within a set of equally spaced segments of the f (υ) axis. In the original implementation, individuals are sampled using the Metropolis-Hastings algorithm, neighbours are generated using standard sub-tree mutation, and the representative neighbour ν for each genotype υ is chosen using tournament selection. The NSC is given in the range of (-∞, 0], where a value of 0 represents a highly evolvable (assumed to be easy) problem, and a negative NSC indicates a less evolvable (more difficult) problem.

One way to characterize problem difficulty is to attempt to predict the expected performance that a GP search will achieve on a given problem instance, a more direct approach. Following this line of thought, two approaches have been proposed in GP literature. We will use the proposal presented in Trujillo et al. (2011a,b,c), where is predict the performance of a GP-classifier using descriptive features that characterize the geometry of the data distribution in feature space. The PEPs where built using non-linear GP models.

After reviewing the basic methodology of EI's and PEP's, one practical and computational difference stands out. On the one hand, EI's use a very large sampling of the search space to derive an accurate measure.

pep: predictor of expected performance

In effect, this means that for every new problem instance it is necessary to perform this costly computational step. However, executing the actual GP search might in fact be faster. Therefore, the best use of EI's would be to characterize a whole class of problems, where the estimate of search difficulty provided by the EI could generalize to the entire class of problems.

On the other hand, a PEP model is used quite easily and directly for each new problem instance. Practically, the only possible bottleneck would be the computational cost of calculating the set of descriptive features for each problem. However, in order to learn a new PEP a very large number of experimental runs must be carried to derive the training data. Moreover, each PEP is strongly linked to a specific GP system and implementation, and even small deviations from the configuration of the GP system might cause the predictive model to break-down.

The goal of the experimental work is to evaluate and compare the predictive accuracy of a state-of-the-art EI (NSC) and a PEP model for a GP-based classifier PGPC. To this end, is it necessary:

1. Generate and solve with PGPC the set of synthetic classification problems using PGPC.

2. Calculate the NSC over all synthetic classification problems.

3. Build the PEP models following the methodology proposed in Trujillo et al. (2011b,c).

4. Analyze the results.

First, a large set of synthetic classification problems are generated and solved with PGPC, executing 30 independent runs on each problem and computing the average classification error as the estimate of the expected performance of PGPC. To evaluate the performance of PGPC, 300 two-class classification problems are randomly generated using Gaussian mixture models (GMM's), these conform set Q. Then, for every problem p ∈ Q the average test error of PGPC is computed from 30 independent runs. Second, to compute the NSC on each of the classification problems in set Q, the approach is quite straightforward, since it is possible to directly apply the NSC algorithm to every problem. The algorithm described in [START_REF] Vanneschi | Fitness clouds and problem hardness in genetic programming[END_REF] is used here with the same parameters except for the total amount of sampled individuals ζ. Whereas in [START_REF] Vanneschi | Fitness clouds and problem hardness in genetic programming[END_REF] ζ = 40, 000, here ζ = 10, 000, a practical choice to reduce computation time; however, some informal tests showed that the results are consistently similar for both values in the group of experiments reported here. Figure 5.13 presents a scatter plot where the horizontal axis is the average classification error and the vertical axis is the NSC. The results clearly suggest that the NSC does not correlate with PGPC performance, in particular we can see how many problems are characterized as easy (with NSC equal or close to zero) even when the performance achieved by PGPC is quite poor. This suggests that an EI such as the NSC is limited as a predictor of GP performance since it only considers the frame of reference of the search process; i.e., it can only provide an approximate measure of the difficulty of the search but pep: predictor of expected performance tells us very little regarding the difficulty of the underlying problem that the GP is intended to solve.

Third, we show how a PEP estimates the performance of PGPC on the set of classification problems presented above. The PEP is derived following the approach described in [START_REF] Trujillo | Estimating classifier performance with genetic programming[END_REF]. The symbolic regression models are tested derived with GP (GP-PEP), reported to achieve the best results in [START_REF] Trujillo | Estimating classifier performance with genetic programming[END_REF]. In the case of the GP-PEP models, the problem descriptors are used as terminal elements T = {SD, V OR, FE, CDR}

(5.13) while the function set is defined as

F = +, -, * , /, √ ,sin, cos, log, x y , | • |, if (5.14)
Moreover, fitness is computed by the RMSE calculated on a set of n training problems, given by .15) where β i is the vector of descriptive features and i is the performance estimate on a training problem i. Finally, the GP is executed for the set Q of classification problems which is divided into a training set and a testing set and 30 runs are executed with different random partitions.

f (K) = n i=1 (K(β i ) -i ) 2 n . ( 5
In general, the PEP model exhibits a very good predictions, with the median error around 5 and 7 percentage points of classification accuracy. Another look at the predictive accuracy of the PEP models is shown in the scatter plots of Figure 5.14. In these plots the predictive classification error is plotted against the average error of PGPC on each problem, using the best GP-PEP model. It is clear that the prediction of the PEP models is strongly correlated with the average performance of PGPC, and the Pearson's correlation coefficient presented with each plot confirms this observation. Finally, two groups of problem difficulty prediction tools are analyzed, named Evolvability Indicators and Predictors of Expected Performance. The former group of measures attempt to capture how amenable the fitness landscape is to a GP, whereas the latter groups takes as input a set of descriptive features of a problem and produces as output an estimate of the expected performance of the GP search.

The key lessons of this study are the following. Firstly, while EIs (the Negative Slope Coefficient is considered) can give a good estimation of the difficulty of the search problem, they are not necessarily correlated with expected performance; Secondly, the results suggest that PEPs achieve a highly accurate prediction of GP performance.

The above results are encouraging, but for a real-world application even small improvements in the quality of the predictions could have non-negligible effects. Therefore, in this section we propose an ensemble approach using several PEP models, each one referred to as an SPEP. We propose an ensemble approach for two main reasons. First, previous works suggest that ensemble-based modeling can improve performance in a variety of scenarios [START_REF] Folino | An ensemble-based evolutionary framework for coping with distributed intrusion detection[END_REF][START_REF] Zhou | Ensemble Methods: Foundations and Algorithms[END_REF]. Second, an ensemble approach allows us to obtain two types of predictions, a numerical prediction of expected performance and a categorical or fuzzy prediction based on the chosen ensemble component used to compute the final prediction. The proposal is depicted in Figure 6.1, an extension of the basic PEP approach shown in Figure 5.1. However, in the SPEP approach before computing the PCE for a given problem, each problem is classified into a specific group using its corresponding feature vector β. Each group is associated to a particular SPEP in the ensemble, hence if a problem is classified into the i-th group then the i-th SPEP is used to compute the predicted PGPC performance on the test set.

To implement this approach, several design choices must be specified. First, how to define a meaningful grouping of problems. Second, train SPEPs that are specialized for each group in order to build the ensemble. Third, chose the correct SPEP for a particular problem by determining its group membership. Each of these issues are discussed next.

Figure 6.1: Block diagram showing the proposed SPEP approach. The proposed approach is an extension of the basic PEP approach of Figure 5.1, with the additional ensemble approach, where problems are first classified into prespecified groups and based on this a corresponding specialized model (SPEP) is chosen to compute the PCE of PGPC on the test set.

Grouping Problems based on PGPC Performance and Training SPEPs

The proposal is to group problems based on the performance of PGPC given by CEµ. This can be seem as a categorical prediction, where problems are grouped into general groups of different difficulty; e.g. easy and hard problems. In particular, we propose two different groupings based on CEµ, using either two or three groups as shown in Figure 6.2. The groups were chosen in such a way that the number of (synthetic) problems in each group would be approximately the same, in this way posing a balanced classification task for the SPEP approach. Figure 6.2 shows the ranges of PGPC performance for each group and the number of synthetic problems (Figure 6.2(a)) and real-world problems (Figure 6.2(b)) that fall within each group. The plots on the top divide the set of problems into two groups, while the plots on the bottom divide the set of problems into three. Finally, for clarity, since the two group division requires two SPEPs, we refer to a solution for this task as an Ensemble-2, while a solution for the three group task is referred to as an Ensemble-3. For each group an SPEP is trained using the strategy described in the previous section for PEPs. Except that instead of using all of the synthetic problems, each SPEP is trained using the subset of synthetic problems from the corresponding group, as depicted in Figure 6.2. Since we are interested in presenting the best possible prediction of PGPC performance on real-world problems, we must select the best predictive models. Therefore, the testing phase is performed using two subsets of the real-world problems, one for validation and other for testing.

SPEP Selection

As depicted in Figure 6.1, in order to choose an SPEP we must first classify each problem to its corresponding group. This is a straightforward classification task, solved using each problem's feature vector β as the decision variables. Several classification algorithms are tested [START_REF] Duda | Pattern Classification (2Nd Edition)[END_REF], namely:

1. Euclidean distance classifier (EDC).

Mahalanobis distance classifier (MDC).

Naive Bayes classifier (NBC).

spep: specialist predictors of expected performance 4. Support Vector Machine (SVM), with Gaussian radial basis function kernel and a default scaling factor of 1.

5. K-Nearest Neighbor (KNN), using K = 5 neighbors.

6. Treebagger Classifier (TBC), using 3 trees.

7. Probabilistic Genetic Programming Classifier (PGPC), parameters on Table 5.1.

Moreover, the classification task is posed using different subsets of the features in β as previously described in Table 5.3. We apply all classifiers using all subsets of features on both the two-group and threegroup classification tasks.

As done for the SPEP models, in all cases the complete set of synthetic problems Q is used to train the classifiers. The testing phase is performed with two sets, 10% of the real-world problems are used as a validation set while the remaining 90% of real-world problems are used for testing. After performing 100 independent runs, the best solution is chosen based on its validation set performance, and methods are compared based on the performance on the testing set. If several solutions achieve the best validation set performance, than the final solution used in the ensemble is randomly chosen.

Evaluation of SPEP Ensembles

This section presents the performance of the evolved SPEP models, and the performance of the complete ensembles, using both the true problem groups (an oracle approach, where the correct SPEP is always chosen) and the predicted group by the best classifier (a more realistic testing scenario).

Ensemble-2 Solutions

To visualize the underlying difficulty of choosing the correct SPEP for a given problem (i.e., determining the group to which it belongs to) Table 6.1 summarizes the performance of the best SPEP models used to build the Ensemble-2 solution. The first column specifies the spep: specialist predictors of expected performance The results show that the SPEP models are specialized to their groups, achieving error values below 0.1 when tested using problems from their groups, while performing worse when tested on problems from the other group. In general, performance on testing set is good, particularly if we compare with the results achieved by the PEP models from the preceding section. Finally, performance is similar for all feature sets when considering testing performance, with the best performance on Group 1 achieved by using the set 4F and the best performance on Group 2 with set 5F. The results in Table 6.1 represent the best possible performance if the correct problem group is chosen, but also confirm that if the correct group is not chosen than prediction accuracy can decline. Table 6.2 summarizes the performance of all of the tested classifiers for the two-group case, showing the median classification error achieved on the training and testing sets. On these tests, PGPC achieves the best performance based on test error. Table 6.3 shows the performance of the best classifier obtained from each method and chosen based on the validation set. In this table performance is given using all real-world problems. Again, PGPC clearly outperforms all other variants, with the best performance achieved using feature set 7F with a classification error of 0.0250.

spep: specialist predictors of expected performance Table 6.4: Ensemble-2 prediction accuracy using each feature set (4F, 5F and 7F), using the best evolved SPEPs and the best classifiers with each feature set. Performance is given based on the RMSE and Pearson's correlation coefficient when evaluated on the synthetic and real-world problem sets; with bold indicating the best performance on real-world problems. It is now possible to evaluate the performance of the complete Ensemble-2 solutions, using the best evolved SPEPs and the best classifier. These results are summarized in Table 6.4, specifying the RMSE and Pearson's correlation coefficient when evaluated on the synthetic and real-world problem sets. These tests show that the Ensemble-2 solutions can achieve low predictive error and a high correlation with the true PGPC performance, for both synthetic and real-world problems. In particular, using feature set 5F correlation on synthetic problems is close to unity, while performance on the real-world problems show the lowest error and approximately 0.9 correlation.

Feature

Focusing on the real-world problems, Figure 6.4 summarizes the performance of the Ensemble-2 predictors using each feature set (each row of the figure). The column on the left-hand side shows plots of the ground truth CEµ of each problem (triangles) and the Ensemble-2 PCE. These plots show three types of PCE: (1) correctly classified problems for which the appropriate SPEP was selected (CC-PCE); (2) misclassified problems for which an incorrect SPEP was selected (MC-PCE); and (3) for the misclassified problems the oracle SPEP prediction (O-PCE), which is the PCE produced by the correct SPEP. The column on the right-hand side of Figure 6.4 presents scatter plots of the true CEµ and the PCE, using the same notation.

These plots provide a graphical confirmation of the quality of the performance prediction. It is important to highlight the impact of a misclassified problem, shown as a black circle, compared to the prediction on the same problem if the correct SPEP had been chosen (O-PCE). For all problems for which the correct SPEP was chosen the PCE is highly correlated with the ground truth with only marginal differences in most cases. Table 6.5 summarizes the performance of the best SPEP models used to build the Ensemble-3 solution. The first column, specifies the feature subset used from β. The second column specifies the evaluated SPEP. SPEP-1 was trained with synthetic problems from the first group, SPEP-2 with problems from the second group and SPEP-3 with problems from the third group. The third column shows the training RMSE, the fourth column shows the testing group and the final columns shows the testing RMSE.

Ensemble-3 Solutions

Again, the results show that the SPEP models are specialized to their respective groups. Performance on the testing set is better than the simple PEP models, but worse than the Ensemble-2 solution presented before. All feature sets produce similar performance on testing set problems, with the best performance on Group 1 and Group 2 achieved by using set 4F, and the best performance on Group 3 with set 5F.

The results summarized in Table 6.5 represent the best possible performance if the correct problem group is chosen, but also confirm that spep: specialist predictors of expected performance if the correct group is not chosen than prediction accuracy can decline. Table 6.6 summarizes the performance of all of the tested classifiers for the three-group case, showing the median classification error achieved on the training and testing sets. On these tests, TBC achieves the best spep: specialist predictors of expected performance synthetic and real-world problems. In all feature sets the correlation on synthetic problems is above 0.97, while the best performance on the real-world problems is achieved using set 5F based on RMSE and set 7F based on correlation.

spep: specialist predictors of expected performance Focusing on the real-world problems, Figure 6.6 summarizes the performance of the Ensemble-3 predictors using each feature set (each row of the figure). These plots illustrate the performance of the achieved prediction. As in the Ensemble-2 case, it is important to highlight the impact of misclassified problems (shown as a black circle) compared to the prediction on the same problem if the correct SPEP had been chosen (O-PCE). In this case we can see more misclassifications. The reason is evident in Figure 6.5, since Group 2 and Group 3 are not so easily differentiated. However, the impact of the misclassified problems is not as large as it is for the Ensemble-2 solution, given the comparatively similar RMSE of both the Ensemble-3 and the Ensemble-2 solutions. Table 6.8: Ensemble-3 prediction accuracy using each feature set (4F, 5F and 7F), using the best evolved SPEPs and the best classifiers with each feature set. Performance is given based on the RMSE and Pearson's correlation coefficient when evaluated on the synthetic and real-world problem sets; with bold indicating the best performance on real-world problems.

Feature

Discussion

This research presents three approaches towards solving the performance prediction problem using the general PEP approach: a single PEP, an Ensemble-2 solution (2 SPEPs) and an Ensemble-3 solution (3 SPEPs). Table 7.1 presents a comparison of the best results of each solution evaluated on the real-world test cases. While all solutions achieve comparable results, it is clear that the Ensemble-2 solution achieves the lowest RMSE and the highest correlation, particularly when using set 5F. These results provide two important insights. First, that the ensemble approach is justified in this domain, with both ensembles outperforming the single PEP models. Second, that grouping the problem into useful subsets based on performance can be solved using two broad categories, what might be considered as easy and difficult problems. However, differentiating problems further becomes difficult given the underlying distribution of problems within feature space, as shown in Figure 6.5 and confirmed by the lower performance of the Ensemble-3 solution.

Starting with the relative importance of each feature used to predict performance. Since all PEPs and SPEPs where generated using symbolic regression with GP, we use statistics over the GP runs to measure the importance of each feature. Figure 7.1 shows two plots that quantify the frequency of feature use when the models were evolved using the complete feature set (7F) over 100 independent runs. Figure 7.1(a) is a bar plot where the frequency is given by summing the number of times that each feature appeared as a terminal element in the best symbolic regression solutions from each run. Figure 7.1(b) plots discussion the features with higher correlation to PGPC performance are FE, VOR, CDR and CD-1, in that order. However, if we consider all evolved models (Figure 7.1(a)) FE is not the most widely used feature, the evolved models consistently select VOR and CDR at a higher frequency. On the other hand, the less correlated features SD, CD-2 and CD-3 are indeed used less by GP.

If we consider feature frequency in finer detail by comparing the frequency in the PEP models with the frequency in each SPEP, some interesting trends appear, as shown in Figure 6.5(b). In this case it is clear that some features are better predictors of PGPC performance on particular problem groups. For instance, CDR and VOR are the most used by the PEP models. On the other hand, FE is used with a higher frequency when predicting performance on easier problems (Ensemble-2-1, Ensemble-3-1) than for the hardest problems (Ensemble-3-3). This is also the case for CDR and slightly for CD-2. Conversely, while CD-3 is rarely used in PEP models, it appears to be very useful in predicting performance on the most difficult problems (Ensemble-3-3) and the easiest (Ensemble-2-1 and Ensemble-3-1) problems.

It is also instructive to determine if the dimensionality reduction applied as preprocessing has a negative effect with regards to performance prediction. Our proposal is to use the first two principal components of the data, in order to simplify the description of the real-world problems. However, it is not clear if the percentage of the variance described by such few components is enough to properly characterize the problems. To analyze this, Figure 7.2 presents scatter plots of all the real-world problems p ∈ Q , showing the percentage of the total variance of the data explained by the first two principal components (x-axis) and the prediction error (PE) (y-axis) computed as the absolute difference between CEµ and PCE. In particular, Figure 7.2(a) is based on the PEP-4F model while Figure 7.2(b) is based on the SPEP-2-5F model. The legend of each plot specifies the computed Pearson's correlation coefficient ρ between both measures. Notice that there is no significant correlation, suggesting that the accuracy of the models does not suffer from the proposed preprocessing.

8

Conclusions

This work presents three main contributions. First, extensions of the PEP approach originally proposed in Trujillo et al. (2011b,a,c), by adding new descriptive measures and testing the PEP models built with synthetic classification problems over a more challenging scenario, performance prediction on real-world classification problems with different dimensions and class imbalance. To achieve the latter we included a preprocessing step for dimensionally reduction, something that previous proposals lacked. Second, the proposed models predict the performance of the GP classifier when they are evaluated on the test set of fitness cases, while previous works focused on predicting training performance. For real-world scenarios, predicting the test performance of a learning algorithm is more relevant since overfitting can appear on difficult problem instances. Third, this work presents a new proposal using an ensemble of SPEPs, where the problems are separated into groups and specialized models were built for each group, improving the prediction accuracy on unseen real-world problems.

The main conclusions derived from this work are the following. First, the proposed dimensionality reduction was successful, it allowed the system to learn the predictive models using simple 2D synthetic problems and apply them on real-world problems with considerably more dimensions. Second, the evolved PEP and SPEP models were able to accurately predict PGPC performance on imbalanced datasets, without the need of using imbalanced data during the training phase. Third, the new descriptive measures proposed in this work (CD-1, CD-2, CD-3) complemented the problem descriptors used in previous works to conclusions help improve predictive accuracy. Some of the proposed descriptors (CD-1) were among the most correlated with PGPC performance; their usefulness was confirmed when analyzing the feature selection performed by GP. However, it's important to note that all descriptors were used in most evolved PEPs, even if some descriptors exhibited very small amounts of correlation with PGPC performance. Finally, our ensemble proposal provides two general perspectives of the prediction task: categorical and numerical prediction. Where, a categorical prediction is used to select specific SPEPs, while the numerical prediction is given by the chosen SPEP. While not explored in this work, the categorical prediction might be sufficient for some applications, such as in fuzzy inference systems.

Finally, possibles future work derived from this research includes the following. The problem descriptors used in this work produced good results, but defining the optimal set of descriptors is still an open question. We will also use this methodology for many classifiers, deriving one PEP for each classifier, thus allowing us to create an expert system for classifier selection. Another possibility is to use the PEPs within a wrapper approach, where the PEP model could be used as a surrogate fitness function for GP-based classifiers. Moreover, these methodologies could be extended to predict the performance of a GPbased symbolic regression system, building PEP models using a set of descriptive measures that can characterize symbolic regression problems accurately. To do so, a proper dimensionality reduction step must be developed.

  Block diagram of the proposed PEP approach. Given a classification problem, the goal is to predict the performance of a GP classifier on the test data, in this case PGPC. . . . . . . 70 5.2. The methodology used to build the PEP model. Given a set Q of synthetic classification problems: (1) compute the CEµ of PGPC on all problems; (2) apply a preprocessing for dimensionality reduction; (3) extract the feature vector β from the problem data; and (4) learn the predictive model using GP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 5.3. The scatter plots show examples of synthetic classification problems, specifying the CEµ and standard deviation σ achieved by PGPC. These ordered from the lowest CEµ (easiest depict in Fig. 5.3(a)) to the highest CEµ (hardest depict in Fig. 5.3(f)). . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 xiii 5.4. Performance of PGPC over all 500 synthetic problems in Q; where: (a) shows the CEµ for each problem, ordered from the easiest to the hardest; and (b) shows the histogram over CEµ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5. Performance of PGPC over all 300 synthetic problems in Q ⊂ Q; where: (a) shows the CEµ for each problem, ordered from the easiest to the hardest; and (b) shows the histogram over CEµ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6. These figures depict the complexity features used to describe each classification problem as suggested in Ho and Basu (2002), where: (a) Feature Efficiency (FE); (b) Class Distance Ratio (CDR); and (c) Volume of Overlap Region (VOR). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.7. Scatter plots show the relationship between the CEµ (x-axis) and each descriptive feature (y-axis) for all problems p ∈ Q , where ρ specifies Pearson's correlation coefficient. . . . . . . 5.8. Figures show for synthetic problems, the performance prediction of the best PEP models evolved with the different feature set, each row belongs to each feature set: PEP-4F(top), PEP-5F(middle) and PEP-7F(bottom). . . . . . . . . 5.9. Histogram of imbalance percentage for the 40 real-world classification problems. . . . . . . . . . . . . . . . . . . . . . . 5.10. Performance of PGPC on the 40 real-world classification problems; where: (a) shows the CEµ for each problem; and (b) shows the histogram over CEµ. . . . . . . . . . . . . . . . 5.11. Scatter plots show for the real-world problems the relationship between the CEµ (x-axis) and each descriptive feature (y-axis). The legend specifies Pearson's correlation coefficient ρ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.12. Figures show for real-world problems, the performance prediction of the best PEP models evolved with the different feature set, each row belongs to each feature set: PEP-4F(top), PEP-5F(middle) and PEP-7F(bottom). . . . . . . . . xiv 5.13. Scatter plot of the average classification error achieved by PGPC on each problem and the corresponding NSC value. Pearson's correlation coefficient ρ = 0.02. . . . . . . . . . . . 91 5.14. Scatter plots that show the average performance of PGPC (xaxis) and the predicted performance of each PEP model (yaxis). The legend specifies Pearson's correlation coefficient ρ = 0.86. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 6.1. Block diagram showing the proposed SPEP approach. The proposed approach is an extension of the basic PEP approach of Figure 5.1, with the additional ensemble approach, where problems are first classified into prespecified groups and based on this a corresponding specialized model (SPEP) is chosen to compute the PCE of PGPC on the test set. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 6.2. The proposed groupings of classification problems used with the SPEP approach, showing the ranges of PGPC performance and the number of problems in each group. . . . . 97 6.3. Parallel coordinate plots dividing the set of problems into two groups, where each coordinate is given by a feature in β. Plots are shown for synthetic (a) and real-world problems (b). The plots on the left show a single line for each problem, while the plots on the right show the median values for each group. For clarity in the parallel plots, the features SD and CDR were rescaled to values between [0, 1]. . . . . . . . . . . 99 6.4. Performance prediction of the best Ensemble-2 solutions for each feature set: 4F(top), 5F(middle) and 7F (bottom). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 6.5. Parallel coordinate plots dividing the set of problems into three groups, where each coordinate is given by a feature in β. Plots are shown for synthetic (a) and real-world problems (b). The plots on the left show a single line for each problem, while the plots on the right show the median values for each group. For clarity in the parallel plots, the features SD and CDR were rescaled to values between [0, 1].

Figure 2

 2 Figure 2.1: GP syntax tree representing max(x + x, x + 3 * y).

Figure 2

 2 Figure 2.2: Multi-component program representation.

Figure 2

 2 Figure 2.3: Creation of a full tree having maximum depth 2 using the full initialization method (t = time).

Figure 2

 2 Figure 2.5: Example of subtree crossover. Note that the trees on the left are actually copies of the parents. So, their genetic material can freely be used without altering the original individuals.

Figure 2 . 6 :

 26 Figure 2.6: Example of subtree mutation.

  (a) Entire training set T = {I 1 , I 2 ...I n }. (b) Interleave probability δ ∈ [0, 1].

  (a) Generate a real random number rn ∈ [0, 1]. (b) If rn ≤ δ then -Generate an integer random number r, where r ∈ [1, n]. -Evaluate population using I r . (c) Otherwise -Evaluate population using T.

  (a) Entire training set T = {I 1 , I 2 ...I n }. (b) Percentil value error ρ ∈ [1, 100].

Figure 2

 2 Figure 2.7: Box plot comparison about the test performance of the methods, from the best solution found for each benchmark symbolic regression problem over all thirty runs.

  Figure2.9: Box plot comparison about the average size performance of the methods, from the solutions found for each benchmark symbolic regression problem over all thirty runs.

Figure 2

 2 Figure 2.10: Box plot comparison about the test performance of the methods, from the best solution found for each real-world regression problem over all thirty runs.

Figure 2 Figure 2

 22 Figure 2.11: Box plot comparison about the overfitting performance of the methods, from the best solution found for each real-world regression problem over all thirty runs.

  showed in Figure 2.13; which depicts sample points of two different classes (circles and crosses) scattered over the R 2 plane. Problems are generated with unimodal or multimodal classes, with different amounts of class overlap. All class samples lie within the closed 2-D interval υ 1 , υ 2 ∈ [-10, 10], and 200 sample points were randomly generated for each class. The parameters for the GMM of each class were also randomly chosen using the following ranges of values: 1. Number of Gaussian components: {1, 2, 3}. 2. Median of each Gaussian component for each feature dimension: [-3, 3]. 3. Each element of the covariant matrix of each Gaussian component: (0, 2]. 4. The rotation angle of each covariance matrix: [0, 2π]. 5. The proportion of sample points generated with each Gaussian component: [0, 1].

  Figure 2.13: Synthetic binary classification problems randomly generated using Gaussian mixture models with different amounts of class overlap, scattered over 2 dimensional space.

Figure 2

 2 Figure 2.14: Box plot comparison about the test performance of the methods, from the best solution found for each synthetic classification problem over all thirty run.

Figure 2

 2 Figure 2.15: Box plot comparison about the overfitting performance of the methods, from the best solution found for each synthetic classification problem over all thirty run.

Figure 2

 2 Figure 2.16: Box plot comparison about the average size performance of the methods, from the solutions found for each synthetic classification problem over all thirty run.

Figure 2 Figure 2 Figure 2

 222 Figure 2.17: Box plot comparison about the test performance of the methods, from the best solution found for each real-world classification problem over all thirty run.

  [START_REF] Zhang | Using gaussian distribution to construct fitness functions in genetic programming for multiclass object classification[END_REF], Zhang and Smart propose a distance measure between both classes as

  Figure 3.1: Median classification error plotted against day used for training and amount of overlap for the SRS-GPC. Each row corresponds to each subject (top row is S 1 and bottom row S 4 ) and each column corresponds to a different segment duration; leftmost row is 1 sec., middle row 2 and rightmost 3.

  Figure 3.2: Median classification error plotted against day used for training and amount of overlap for the PGPC. Each row corresponds to each subject (top row is S 1 and bottom row S 4 ) and each column corresponds to a different segment duration; leftmost row is 1 sec., middle row 2 and rightmost 3.

  Figure 3.3: Median sensitivity plotted against the day-used for training and the amount of overlap for the SRS-GPC. Each row corresponds to each subject (top row is S 1 and bottom row S 4 ) and each column corresponds to a different segment duration; leftmost row is 1 sec., middle row 2 and rightmost 3.

  Figure3.4: Median specificity plotted against the day used for training and the amount of overlap for the SRS-GPC. Each row corresponds to each subject (top row is S 1 and bottom row S 4 ) and each column corresponds to a different segment duration; leftmost row is 1 sec., middle row 2 and rightmost 3.

Figure 5 . 1 :Figure 5 . 2 :

 5152 Figure 5.1: Block diagram of the proposed PEP approach. Given a classification problem, the goal is to predict the performance of a GP classifier on the test data, in this case PGPC.

2.

  Median of each Gaussian component for each dimension: [-3, 3]. 3. Each element of the covariant matrix of each Gaussian component: (0, 2]. 4. The rotation angle of each covariance matrix: [0, 2π]. 5. Proportion of samples generated with each Gaussian component: [0, 1].

  Figure 5.3: The scatter plots show examples of synthetic classification problems, specifying the CEµ and standard deviation σ achieved by PGPC. These ordered from the lowest CEµ (easiest depict in Fig. 5.3(a)) to the highest CEµ (hardest depict in Fig. 5.3(f)).

  Figure 5.6: These figures depict the complexity features used to describe each classification problem as suggested in Ho and Basu (2002), where: (a) Feature Efficiency (FE); (b) Class Distance Ratio (CDR); and (c) Volume of Overlap Region (VOR).

Figure 5 . 9 :

 59 Figure 5.9: Histogram of imbalance percentage for the 40 real-world classification problems.

  Figure 5.12: Figures show for real-world problems, the performance prediction of the best PEP models evolved with the different feature set, each row belongs to each feature set: PEP-4F(top), PEP-5F(middle) and PEP-7F(bottom).

Figure 5

 5 Figure 5.13: Scatter plot of the average classification error achieved by PGPC on each problem and the corresponding NSC value. Pearson's correlation coefficient ρ = 0.02.

Figure 5

 5 Figure 5.14: Scatter plots that show the average performance of PGPC (x-axis) and the predicted performance of each PEP model (y-axis). The legend specifies Pearson's correlation coefficient ρ = 0.86.

  Figure 6.2: The proposed groupings of classification problems used with the SPEP approach, showing the ranges of PGPC performance and the number of problems in each group.

  Figure 6.3: Parallel coordinate plots dividing the set of problems into two groups, where each coordinate is given by a feature in β. Plots are shown for synthetic (a) and real-world problems (b). The plots on the left show a single line for each problem, while the plots on the right show the median values for each group. For clarity in the parallel plots, the features SD and CDR were rescaled to values between [0, 1].

Figure 6 .

 6 Figure 6.3 presents a parallel coordinate plot dividing the set of problems into two groups, where each coordinate is given by a feature in β. Plots are shown for synthetic (Figure 6.3(a)) and real-world problems (Figure 6.3(b)). The plots on the left show a single line for each problem, while the plots on the right show the median values for each group. For clarity in the parallel plots, the features SD and CDR were rescaled to values between [0, 1].Table6.1 summarizes the performance of the best SPEP models used to build the Ensemble-2 solution. The first column specifies the

Figure 6 .

 6 Figure6.5 presents a parallel coordinate plot dividing the set of problems into three groups, where each coordinate is given by a feature in β. Plots are shown for synthetic (Figure6.5(a)) and real-world problems (Figure6.5(b)). The plots on the left show a single line for each problem, while the plots on the right show the median values for each group. For clarity, features SD and CDR were rescaled to values between [0, 1]. Table6.5 summarizes the performance of the best SPEP models used to build the Ensemble-3 solution. The first column, specifies the feature subset used from β. The second column specifies the evaluated SPEP. SPEP-1 was trained with synthetic problems from the first group, SPEP-2 with problems from the second group and SPEP-3 with problems from the third group. The third column shows the training RMSE, the fourth column shows the testing group and the final columns shows the testing RMSE.

  Figure 6.4: Performance prediction of the best Ensemble-2 solutions for each feature set: 4F(top), 5F(middle) and 7F (bottom).

  Figure 6.6: Performance prediction of the best Ensemble-3 solutions for each feature set: 4F(top), 5F(middle) and 7F (bottom).

  like to thank to the FP7-Marie Curie-IRSES 2013 European Commission program through project ACoBSEC with Contract No. 612689, for the support provided. 2.12. Box plot comparison about the average size performance of the methods, from the solutions found for each real-world regression problem over all thirty runs. . . . . . . . . . . . . 2.13. Synthetic binary classification problems randomly generated using Gaussian mixture models with different amounts of class overlap, scattered over 2 dimensional space. 2.14. Box plot comparison about the test performance of the methods, from the best solution found for each synthetic classification problem over all thirty run. . . . . . . . . . . . 2.15. Box plot comparison about the overfitting performance of the methods, from the best solution found for each synthetic classification problem over all thirty run. . . . . . . . . 2.16. Box plot comparison about the average size performance of the methods, from the solutions found for each synthetic classification problem over all thirty run. . . . . . . . . . . . 2.17. Box plot comparison about the test performance of the methods, from the best solution found for each real-world classification problem over all thirty run. . . . . . . . . . . . 2.18. Box plot comparison about the overfitting performance of the methods, from the best solution found for each realworld classification problem over all thirty run. . . . . . . . . 2.19. Box plot comparison about the average size performance of the methods, from the solutions found for each real-world classification problem over all thirty run. . . . . . . . . . . . 3.1. Median classification error plotted against day used for training and amount of overlap for the SRS-GPC. Each row corresponds to each subject (top row is S 1 and bottom row S 4 ) and each column corresponds to a different segment duration; leftmost row is 1 sec., middle row 2 and rightmost 3. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. Median classification error plotted against day used for

  . . 105 xv 6.6. Performance prediction of the best Ensemble-3 solutions for each feature set: 4F(top), 5F(middle) and 7F (bottom). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7.1. Feature selection by the symbolic regression GP used to evolve all PEP and SPEP models, showing usage frequency over 100 runs: (a) bar plot of the total number of times that each feature appeared as a terminal element in the best models; and (b) median of the number of times that each feature appeared in each tree. . . . . . . . . . . . . . . . . . . 7.2. Scatter plots show the relationship between the percentage of the total variance explained by two principal components (x-axis) and the prediction error (y-axis), for all problems p ∈ Q , where the prediction error is the absolute difference between the CEµ and PCE, figure on the left show the PEP-4F model and figure on the right SPEP-2-5F, where ρ specifies Pearson's correlation coefficient. . . . . . . . . . . Examples of primitives in GP terminal set. . . . . . . . . . . 13 2.2. Examples of primitives in GP function set. . . . . . . . . . . . 14 2.3. Five symbolic regression problems, originally published in Uy et al. (2011), and suggested as benchmark regression problems in McDermott et al. (2012) and Martínez et al. (2013). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.4. Table with the parameters for GP used for the benchmark symbolic regression problems. . . . . . . . . . . . . . . . . . . 25 2.5. Table with the parameters for GP used for symbolic regression real-world problems. . . . . . . . . . . . . . . . . . . . . 29 2.6. Table show the median of 30 executions for testing, overfitting and size; bold indicates best. . . . . . . . . . . . . . . . . 33 2.7. Results of the Friedman test for the classification problems, showing the p-value after the Bonferroni-Holm correction for each pairwise comparison; bold indicates that the test rejects the null hypothesis at the α = 0.05 significance level. 34 2.8. Real-world classification problems from Irvine (UCI) machine learning repository. . . . . . . . . . . . . . . . . . . . . 37 2.9. Table with the parameters for GP used for the classification problems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.10. Table show the median of 30 executions over testing, overfitting and size; bold indicates best. . . . . . . . . . . . . . . . 38 2.11. Results of the Friedman test for the classification problems, showing the p-value after the Bonferroni-Holm correction for each pairwise comparison; bold indicates that the test rejects the null hypothesis at the α = 0.05 significance level. 42 3.1. Parameters for the PGPC system used in the experimental tests. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 5.1. Parameters for the PGPC algorithm. . . . . . . . . . . . . . . 73 xvii 5.2. Parameters for the GP used to derive PEP models for PGPC algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3. Three different features sets used as terminal elements for the symbolic regression GP algorithm. . . . . . . . . . . . . . 5.4. Prediction performance of the evolved PEPs applied on the synthetic problems using each feature set (4F, 5F and 7F, see Table 5.3). Performance is given based on the RMSE and Pearson's correlation coefficient, with bold indicating the best performance. . . . . . . . . . . . . . . . . . . . . . . . 5.5. Real-world datasets from the UCI machine learning repository used in this work. . . . . . . . . . . . . . . . . . . . . . . Performance on the SPEP selection problem for all tested classifiers, showing the median classification error from 100 independent runs. The performance is given on the training and testing sets. Bold text indicates the best performance on each feature set. . . . . . . . . . . . . . . . . . . 101 6.3. Performance on the SPEP selection problem for all tested classifiers, showing the classification error of the best solution found, evaluated over all real-world problems, with bold indicating the best performance on each feature set. . . 101 xviii 6.4. Ensemble-2 prediction accuracy using each feature set (4F, 5F and 7F), using the best evolved SPEPs and the best classifiers with each feature set. Performance is given based on the RMSE and Pearson's correlation coefficient when evaluated on the synthetic and real-world problem sets; with bold indicating the best performance on real-world problems.102 6.5. RMSE of the best evolved SPEP models, using different feature sets (first column). Performance is given based on training and testing set. Moreover, each SPEP-i corresponds to the i -th problem group but is tested on all problem groups, as specified in column 4. Bold text indicates best perfor-

xvi List of Tables 2.1. 5.6. The 40 real-world binary classification problems based on the UCI datasets. . . . . . . . . . . . . . . . . . . . . . . . . . 5.7. Prediction performance of the evolved PEPs applied on the real-world problems using each feature set (4F, 5F and 7F, see

Table 5.3). Performance is given based on the RMSE and Pearson's correlation coefficient, with bold indicating the best performance. . . . . . . . . . . . . . . . . . . . . . . . 6.1. RMSE of the best evolved SPEP models, using different feature sets (first column). Performance is given based on training and testing set. Moreover, each SPEP-i corresponds to the ith problem group but is tested on both problem groups, as specified in the fourth column. Bold indicates the best performance on each group. . . . . . . . . . . . . . . 100 6.2. mance on each group. . . . . . . . . . . . . . . . . . . . . . . 106 6.6. Performance on the SPEP selection problem for all tested classifiers, showing the median classification error from 100 independent runs. The performance is given on the training and testing sets, with bold indicating the best performance on each feature set. . . . . . . . . . . . . . . . . . . 108 6.7. Performance on the SPEP selection problem for all tested classifiers, showing the classification error of the best solution found, evaluated over all real-world problems, with bold indicating the best performance on each feature set. . . 108 6.8. Ensemble-3 prediction accuracy using each feature set (4F, 5F and 7F), using the best evolved SPEPs and the best classifiers with each feature set. Performance is given based on the RMSE and Pearson's correlation coefficient when evaluated on the synthetic and real-world problem sets; with bold indicating the best performance on real-world problems.109 7.1. A comparison of each predictor approach; where bold indicates best performance. . . . . . . . . . . . . . . . . . . . . . . 112 xix xx

Table 2 .

 2 1: Examples of primitives in GP terminal set.

	Terminal Set
	Kind of Primitive Example (s)
	Variables	x, y
	Constant values	3, 0.45
	0-arity functions	rand, go left
	..	...
	ify such a language. That is, together they define the ingredients that
	are available to GP to create computer programs.
	The terminal set may consist of:
	the program's external inputs. These typically take the form of
	named variables (e.g., x, y).

Table 2 .

 2 2: Examples of primitives in GP function set.

	Function Set
	Kind of Primitive	Example (s)
	Arithmetic	+, *, /
	Mathematical	sin, cos, exp
	Boolean	AND, OR, NOT
	Conditional	IF-THEN-ELSE
	Looping	FOR, REPEAT
	..	...
	different random value is generated which is then used for that partic-
	ular terminal, and which will remain fixed for the rest of the run. The
	function set used in GP is typically driven by the nature of the prob-
	lem domain. In a simple numeric problem, for example, the function
	set may consist of merely the arithmetic functions (+, -, * , /). How-
	ever, all sorts of other functions and constructs typically encountered
	in computer programs can be used. Tables 2.1 and 2.2 shows a sample
	of some of the functions one sees in the GP literature. Sometimes the
	primitive set includes specialized functions and terminals which are
	designed to solve problems in a specific problem domain. For example,
	if the goal is to program a robot to mop the floor, then the function set
	might include such actions as move, turn, and swish-the-mop.

Table 2 .

 2 4: Table with the parameters for GP used for the benchmark symbolic regression problems.

	Parameter	Description
	Population size	200 individuals
	Generations	100 generations
	Initialization	Ramped Half-and-Half,
		with 6 levels of maximum depth
	Operator probabilities Crossover p Maximum tree depth 20 levels
	Selection	Tournament selection of size 3
	Elitism	Best individual always survives

c = 0.9, Mutation p µ = 0.05 Function set ( + , -, × , ÷ , sin , cos , exp , log).

Terminal set

υ, 1 for single variable problems and υ, ν for bivariable problem.

Table 2 .

 2 7, shows the p-values with the Bonferroni-Holm correction for the pairwise comparisons on each problem where bold values indicate that Table 2.5: Table with the parameters for GP used for symbolic regression real-world problems.

	Parameter	Description
	Population size	500 individuals
	Generations	200 generations
	Initialization	Ramped Half-and-Half,
		with 6 levels of maximum depth
	Operator probabilities	Crossover p c = 0.9, Mutation p µ = 0.05
	Function set	{ + , -, × , ÷ }
	Terminal set	Input variables,
		constants -1.0, -0.5, 0, 0.5 and 1.0
	Maximum tree depth	17 levels
	Selection	Tournament selection of size 10
	Elitism	Best individual always survives

Table 2 .

 2 6: Table show the median of 30 executions for testing, overfitting and size; bold indicates best.

			Testing
		GP-STD	IS	RIS	LEX	KW-IS
	f1-Benchmark	0.0031	0.0000	0.0000	0.0207	0.0468
	f2-Benchmark	0.0418	0.0000	0.2990	0.0000	0.0286
	f3-Benchmark	0.0079	0.0616	0.0569	0.0166	0.0496
	f4-Benchmark	0.0126	0.1172	0.1733	0.0180	0.0691
	f5-Benchmark	0.0342	0.0695	0.0756	0.0180	0.0455
	Toxicity	4206.99 2217.21 2555.48 2089.20 2267.04
	Plasma Protein Binding	39.47	31.21	45.47	32.00	30.31
	Bioavailability	40.16	42.23	45.15	33.49	37.12
	Concrete	8.56	11.84	30.72	9.87	8.67
	Housing	5.08	5.96	11.26	5.26	4.93
	Yacht	2.31	4.45	14.96	4.21	3.27
		Overfitting
	f1-Benchmark	0.0010	0.0000	0.0000	0.0039	0.0184
	f2-Benchmark	0.0052	0.0000	0.0366	0.0000	0.0023
	f3-Benchmark	0.0013	0.0065	0.0111	0.0044	0.0078
	f4-Benchmark	0.0039	0.0159	0.0362	0.0041	0.0109
	f5-Benchmark	0.0036	0.0025	0.0036	0.0011	0.0036
	Toxicity	2645.66	81.56	65.03	115.32	629.16
	Plasma Protein Binding	21.19	2.08	1.21	4.67	1.25
	Bioavailability	17.40	2.01	0.94	1.50	5.64
	Concrete	0.2541	0.2950	0.3609	0.4100	0.3486
	Housing	0.9882	0.3800	0.2519	0.4918	0.7668
	Yacht	0.7244	0.6957	0.2884	0.6293	0.5997
			Size
	f1-Benchmark	95	89	74	78	63
	f2-Benchmark	90	85	48	72	55
	f3-Benchmark	69	76	71	75	64
	f4-Benchmark	71	63	85	83	78
	f5-Benchmark	65	52	61	50	61
	Toxicity	274	52	1	80	102
	Plasma Protein Binding	212	54	1	100	54
	Bioavailability	308	65	57	87	199
	Concrete	206	172	74	111	198
	Housing	171	145	1	94	159
	Yacht	222	164	5	146	209
	2.6.4.2 Classification Problems
	Synthetic binary classification problems were randomly generated
	using Gaussian mixture models (GMM's). Examples of the classifica-

Table 2 .

 2 7: Results of the Friedman test for the classification problems, showing the p-value after the Bonferroni-Holm correction for each pairwise comparison; bold indicates that the test rejects the null hypothesis at the α = 0.05 significance level.

Table 2 .

 2 .8: Real-world classification problems from Irvine (UCI) machine learning repository. 9: Table with the parameters for GP used for the classification problems. , shows the p-values with the Bonferroni-Holm correction for the pairwise comparisons on each problem where bold values indicate that the null hypothesis is rejected at the α = 0.05 significance level.Based on test performance, three algorithms consistently show the best results, GP-STD, LEX and KW-IS. On the other hand, RIS and IS are clearly the worst methods, in some cases their performance shows twice the error as the best methods (Breast Cancer Wisconsin and P2-

	No.	Problem	Classes Features Instances Description
	1	Breast Cancer Wisconsin	2	8	699	Original Wisconsin Breast
						Cancer Database.
	2	Parkinson's	2	22	195	Oxford Parkinson's Disease
						Detection Dataset
	3	Pima Indians Diabetes	2	8	768	From National Institute of
						Diabetes
	4	Indian Liver Patient	2	10	579	Contains 416 liver patient
						records and 167 non liver pa-
						tient records
	5	Retinopathy	2	19	1151	Contains features extracted
						from the Messidor image set,
						to predict signs of diabetic
						retinopathy or not
	6	Vertebral Column 2C	2	6	310	Biomedical data set built by
						Dr. Henrique da Mota
		Parameter		Description
		Runs		30
		Size of population		200 individuals
		Generations		100 generations
		Initialization		Ramped Half-and-half with mamixum
				depth level of 6
		Operator probabilities	Crossover p c = 0.8, mutation p µ = 0.2
		Function set (+, Terminal set input variables
		Maximum tree depth		20 levels
		Selection		Size 3 tournament
		Elitism		Best individual always survives
	2.11

-, ×, ÷, sin, cos, exp, log, if )

Table 2 .

 2 10: Table show the median of 30 executions over testing, overfitting and size; bold indicates best.

		Testing
		GP-STD	IS	RIS	LEX	KW-IS
	P1-Synthetic	0.0000 0.0000 0.0000 0.0000 0.0000
	P2-Synthetic	0.0938 0.1937 0.1750 0.1000 0.1000
	P3-Synthetic	0.1375 0.2062 0.1875 0.1375 0.1375
	P4-Synthetic	0.2750 0.2500 0.3000 0.2625 0.2750
	P5-Synthetic	0.3875 0.3750 0.3438 0.3688 0.3875
	Breast Cancer Wisconsin 0.1023 0.2045 0.1932 0.0795 0.0909
	Parkinson's	0.1795 0.2564 0.2564 0.1538 0.2308
	Pima Indians Diabetes	0.2727 0.3506 0.3506 0.2630 0.2955
	Indian Liver Patient	0.2832 0.2920 0.2832 0.2832 0.2832
	Retinopathy	0.2860 0.3362 0.4214 0.3166 0.2729
	Vertebral Column 2C	0.1855 0.2258 0.2258 0.2097 0.2258
		Overfitting
	P1-Synthetic	0.0000 0.0000 0.0000 0.0000 0.0000
	P2-Synthetic	0.0359 0.0547 0.0344 0.0328 0.0203
	P3-Synthetic	0.0469 0.0312 0.0312 0.0500 0.0281
	P4-Synthetic	0.0859 0.0344 0.0344 0.0625 0.0375
	P5-Synthetic	0.1063 0.0656 0.0516 0.0859 0.0609
	Breast Cancer Wisconsin 0.0428 0.0360 0.0335 0.0312 0.0454
	Parkinson's	0.0385 0.0128 0.0128 0.0385 0.0321
	Pima Indians Diabetes	0.0398 0.0021 0.0081 0.0291 0.0219
	Indian Liver Patient	0.0536 0.0216 0.0038 0.0082 0.0077
	Retinopathy	0.0401 0.0241 0.0214 0.0245 0.0215
	Vertebral Column 2C	0.0565 0.0645 0.0444 0.0484 0.0504
		Size
	P1-Synthetic	149	147	124	20	143
	P2-Synthetic	91	5	6	102	107
	P3-Synthetic	82	6	5	94	103
	P4-Synthetic	210	168	100	90	71
	P5-Synthetic	215	162	78	128	66
	Breast Cancer Wisconsin	50	3	4	41	59
	Parkinson's	16	2	3	17	48
	Pima Indians Diabetes	70	4	3	66	13
	Indian Liver Patient	165	108	65	79	57
	Retinopathy	153	103	4	61	5
	Vertebral Column 2C	162	118	88	112	51
	38

Table 2 .

 2 11: Results of the Friedman test for the classification problems, showing the p-value after the Bonferroni-Holm correction for each pairwise comparison; bold indicates that the test rejects the null hypothesis at the α = 0.05 significance level.

Table 3 .

 3 1: Parameters for the PGPC system used in the experimental tests.

	Parameter	Description
	Population size	200 individuals.
	Generations	200 generations.
	Initialization	Ramped Half-and-Half,
		with 6 levels of maximum depth.
	Operator probabilities Crossover p c = 0.8; Mutation p µ = 0.2. Function set +, -, * , /, √ ,sin, cos, log, x y , | • |, if
	Terminal set	υ µ , υ m , υ σ , υ max , υ min , υ s and υ k
	Bloat control	Dynamic depth control.
	Initial dynamic depth	6 levels.
	Hard maximum depth	20 levels.
	Selection	Lexicographic
		parsimony tournament
	Survival

Table 5 .

 5 1: Parameters for the PGPC algorithm. Operator probabilities Crossover p c = 0.8; Mutation p µ = 0.2 Function set +, -, * , /, √ ,sin, cos, log, x y , | • |, if Terminal set {υ 1 , ..., υ i , ..., υ P } where each υ i is a dimension of the data patterns υ ∈ R P

	Parameter	Description
	Population size	200 individuals
	Generations	200 generations
	Initialization	Ramped half-and-half,
		with 6 levels of maximum depth
	Bloat control	Dynamic depth control
	Initial dynamic depth	6 levels
	Hard maximum depth	20 levels
	Selection	Tournament, size 3
	Survival	Keep best elitism
	Training Data	70%
	Testing Data	30%
	Runs	30

Table 5 .

 5 4: Prediction performance of the evolved PEPs applied on the synthetic problems using each feature set (4F, 5F and 7F, see Table5.3). Performance is given based on the RMSE and Pearson's correlation coefficient, with bold indicating the best performance.

		median	median
		training RMSE testing RMSE best RMSE best correlation
	PEP-4F	0.0320	0.0375	0.0318	0.9634
	PEP-5F	0.0317	0.0362	0.0295	0.9688
	PEP-7F	0.0326	0.0364	0.0317	0.9636

Table 5 .

 5 5: Real-world datasets from the UCI machine learning repository used in this work.

	No.	Problem	Classes Dimensions Description
	1	Balance scale	3	4	Balance scale weight and distance database.
	2 Breast cancer wisconsin	2	8	Original Wisconsin Breast Cancer Database.
	3	Breast tissue	6	9	Dataset with electrical impedance measurements
					of freshly excised tissue samples from the breast.
	4	Cardiotocography	3	23	Fetal cardiotocograms (CTGs) were
					automatically processed and the respective
					diagnostic features measured.
	5	EEG eye state	2	15	All data is from one continuous EEG measurement
					with the Emotiv EEG Neuroheadset.
	6	Fertility	2	10	100 volunteers provide a semen sample analyzed
					according to the WHO 2010 criteria.
	7	Glass	6	10	From USA Forensic Science Service; 6 types of glass.
	8	Indian liver patient	2	32	This data set contains 416 liver
					patient records and 167 non liver patient records.
	9	Ionosphere	2	32	Classification of radar returns from the ionosphere.
	10	Iris	3	4	The data set contains 3 classes of 50 instances each,
					where each class refers to a type of iris plant.
	11	Parkinsons	2	22	Oxford Parkinson's Disease Detection Dataset.
	12	Pima indians diabetes	2	8	From National Institute of Diabetes
					and Digestive and Kidney Diseases.
	13	Retinopathy	2	19	This dataset contains features extracted from
					the Messidor image set to predict whether an
					image contains signs of diabetic retinopathy or not.
	14	Red wine	6	11	The goal is to model wine quality based on
					physicochemical tests.
	15	Seed	3	7	The examined group comprised kernels belonging
					to three different varieties of wheat.
	16	Sonarall	2	60	The task is to train a network to discriminate
					between sonar signals bounced off a metal cylinder
					and those bounced off a roughly cylindrical rock.
	17	Tae	3	5	The data consist of evaluations of teaching
					performance; scores are "low", "medium", or "high".
	18	Vertebral-column 2C	2	6	Biomedical data set built by Dr. Henrique da Mota.
	19	Vertebral-column 3C	3	6	Biomedical data set built by Dr. Henrique da Mota.
	20	White wine	6	11	The goal is to model wine quality based on
					physicochemical tests.
	21	Wine	3	13	Using chemical analysis determine the origin of wines.
	22	Zoo	7	3	Artificial, 7 classes of animals.

Table 5 .

 5 6: The 40 real-world binary classification problems based on the UCI datasets.

	No.	Problem	Classes Instances Imbalance %
		Balance scale	1-3	576	0
		Breast cancer wisconsin	1-2	699	31
		Breast tissue	1-2	36	17
		Breast tissue	1-3	39	8
		Breast tissue	1-4	37	14
		Breast tissue	2-3	33	9
		Breast tissue	2-4	31	3
		Breast tissue	3-4	34	6
		Cardiotocography	1-2	1950	70
		Cardiotocography	1-3	1831	81
		Cardiotocography	2-3	471	26
		EEG eye state	1-2	8388	17
		Fertility	1-2	100	76
		Glass	1-2	146	4
		Glass	1-6	99	41
		Glass	2-6	105	45
		Indian liver patient	1-2	579	43
		Ionosphere	1-2	351	28
		Iris	1-2	100	0
		Iris	1-3	100	0
		Iris	2-3	100	0
		Parkinsons	1-2	195	51
		Pima indians diabetes	1-2	768	30
		Red wine	5-6	1319	3
		Retinopathy	1-2	1151	6
		Seeds	1-2	140	0
		Seeds	1-3	140	0
		Seeds	2-3	140	0
		Sonarall	1-2	208	7
		Tae	1-2	99	1
		Tae	1-3	101	3
		Tae	2-3	102	2
		Vertebral column 2C	1-2	310	35
		Vertebral column 3C	1-2	210	43
		Vertebral column 3C	1-3	160	25
		Vertebral column 3C	2-3	250	20
		White wine	5-6	3655	20
		Wine	1-2	130	9
		Wine	1-3	107	10
		Zoo	1-2	61	34

Table 5 .

 5 7: Prediction performance of the evolved PEPs applied on the real-world problems using each feature set (4F, 5F and 7F, see Table5.3). Performance is given based on the RMSE and Pearson's correlation coefficient, with bold indicating the best performance.

		median RMSE best RMSE best correlation
	PEP-4F	0.1522	0.0828	0.8634
	PEP-5F	0.1583	0.0929	0.8823
	PEP-7F	0.1676	0.0930	0.8046
	Table

Table 6 .

 6 1: RMSE of the best evolved SPEP models, using different feature sets (first column). Performance is given based on training and testing set. Moreover, each SPEP-i corresponds to the ith problem group but is tested on both problem groups, as specified in the fourth column. Bold indicates the best performance on each group.

		SPEP	training Testing group testing
	4F	SPEP-1 SPEP-2	0.0201 0.0341	1 2 1 2	0.0315 0.2470 0.1445 0.0919
	5F	SPEP-1 SPEP-2	0.0195 0.0380	1 2 1 2	0.0380 0.1819 0.1119 0.0832
	7F	SPEP-1 SPEP-2	0.0212 0.0332	1 2 1 2	0.0469 0.2096 0.1586 0.1014
	feature subset used from β. The second column specifies the evaluated
	SPEP, SPEP-1 was trained with synthetic problems from the first group
	while SPEP-2 was trained with problems from the second group. The
	training RMSE is given in column 3. Every SPEP was tested on real-
	world problems from both groups, to illustrate the performance dif-
	ference and specialization of each model; this is specified in the forth
	column. The final column gives the testing RMSE on each group.

Table 6 .

 6 2: Performance on the SPEP selection problem for all tested classifiers, showing the median classification error from 100 independent runs. The performance is given on the training and testing sets. Bold text indicates the best performance on each feature set. Table6.3: Performance on the SPEP selection problem for all tested classifiers, showing the classification error of the best solution found, evaluated over all real-world problems, with bold indicating the best performance on each feature set.

	Algorithm	EDC	MDC	NBC	SVM	KNN	TBC	PGPC
	4F	training 0.1533 0.0567 0.0200 0.0233 0.0133 0.0067 0.0100 testing 0.2500 0.1389 0.1111 0.1111 0.1389 0.1111 0.0833
	5F	training 0.1533 0.0567 0.0200 0.0200 0.0200 0.0067 0.0100 testing 0.2778 0.1389 0.1389 0.1389 0.1667 0.1389 0.1111
	7F	training 0.1533 0.0467 0.0200 0.0033 0.0200 0.0067 0.0100 testing 0.2778 0.1389 0.1389 0.2500 0.1667 0.1111 0.0972
	Feature Set	EDC	MDC	NBC	SVM	KNN	TBC	PGPC
		4F	0.2500 0.1250 0.1000 0.1000 0.1250 0.1250 0.0500
		5F	0.2750 0.1250 0.1250 0.1250 0.1500 0.1250 0.1000
		7F	0.2750 0.1250 0.1250 0.2500 0.1500 0.1250 0.0250

Table 6 .

 6 5: RMSE of the best evolved SPEP models, using different feature sets (first column). Performance is given based on training and testing set. Moreover, each SPEP-i corresponds to the ith problem group but is tested on all problem groups, as specified in column 4. Bold text indicates best performance on each group.

		SPEP	training Testing group testing
				1	0.0315
		SPEP3-1	0.0201	2	0.1312
				3	0.2767
				1	0.1883
	4F	SPEP3-2	0.0303	2	0.0302
				3	0.1459
				1	0.3955
		SPEP3-3	0.0264	2	0.1349
				3	0.0532
		SPEP3-1	0.0195	1 2	0.0380 0.2076
				3	0.1602
				1	0.0931
	5F	SPEP3-2	0.0313	2	0.0380
				3	0.1245
				1	0.2691
		SPEP3-3	0.0294	2	0.1250
				3	0.0525
		SPEP3-1	0.0212	1 2	0.0469 0.1723
				3	0.2391
				1	0.1096
	7F	SPEP3-2	0.0285	2	0.0352
				3	0.1719
				1	0.1339
		SPEP3-3	0.0277	2	0.1133
				3	0.0531
	and Pearson's correlation coefficient when evaluated on the synthetic
	(training) and real-world (validation and testing) problem sets. These
	tests show that the Ensemble-3 solutions can achieve low predictive er-
	ror and a high correlation with the true PGPC performance, for both
	106

Table 6 .

 6 6: Performance on the SPEP selection problem for all tested classifiers, showing the median classification error from 100 independent runs. The performance is given on the training and testing sets, with bold indicating the best performance on each feature set.

	Algorithm	EDC	MDC	NBC	SVM	KNN	TBC	PGPC
	4F	training 0.2533 0.1967 0.0833 0.1067 0.0467 0.0167 0.0633 testing 0.4722 0.3056 0.3889 0.3611 0.3056 0.2778 0.3611
	5F	training 0.2500 0.1933 0.0833 0.1033 0.0533 0.0200 0.0667 testing 0.5000 0.3056 0.4167 0.3611 0.3333 0.3056 0.3333
	7F	training 0.2467 0.1867 0.0800 0.0533 0.0567 0.0167 0.0667 testing 0.5000 0.3056 0.3889 0.4444 0.3333 0.3333 0.3333

Table 6 .

 6 7: Performance on the SPEP selection problem for all tested classifiers, showing the classification error of the best solution found, evaluated over all real-world problems, with bold indicating the best performance on each feature set.

	Feature Set	EDC	MDC	NBC	SVM	KNN	TBC	PGPC
	4F	0.4750 0.3000 0.4000 0.3500 0.3000 0.2250 0.2500
	5F	0.5000 0.3000 0.4250 0.3500 0.3250 0.1750 0.2500
	7F	0.5000 0.3000 0.3750 0.4500 0.3250 0.2500 0.3000

2.6 training set: fitness-cases

2.6 training set: fitness-cases main. Therefore, a real-world GP-based tool should probably include as a configurable option either LEX, KW-IS or both.

Such a distance measure is a common fitness function for many application domains of GP, particularly for symbolic regression problems.

It is important to state that our PGPC and SPEP implementations were not implemented in any optimal way and that running times might be different.

Acknowledgements

Thanks God for allow me live beautiful moments and experiences with the people who love me.

2011b,c), but accuracy degrades for real-world problems with high dimensional data (Graff et al., 2013a,b). This is due to the fact that feature extraction (the next step in the PEP approach) fails at extracting meaningful information in high dimensional spaces (Graff et al., 2013a,b). To deal with this issue, we apply a dimensionality reduction preprocessing of the problem data using PCA [START_REF] Duda | Pattern Classification (2Nd Edition)[END_REF]. We propose pep: predictor of expected performance FE, CDR, VOR, CD-1, CD-2 and CD-3) and the y-axis is the associated CEµ. The legend of each plot also gives the Pearson's correlation coefficient ρ. It is evident that all of the chosen features are correlated with PGPC performance, in particular FE, VOR, CDR, CD-1 and CD-3 show the highest correlation.

pep: predictor of expected performance SD, FE, CDR, VOR and CD-1 7F SD, FE, CDR, VOR, CD-1, CD-2 and CD-3

In the second scenario, we test the PEP models trained with synthetic problems and evaluate their predictions on many real-world datasets, a more challenging scenario since the real-world problems have high dimensional data, imbalanced classes and different data distributions.

Testing on Synthetic Classification Problems

Table 5.4 summarizes the performance of the evolved PEPs, showing the median of the RMSE of the best solution found in each run for the training and testing sets, as well as the RMSE and Pearson's correlation coefficient ρ of the best solution found. The table presents three rows of results, one for each feature set (PEP-4F, PEP-5F and PEP-7F).

pep: predictor of expected performance These results are different to what was observed on the synthetic problems. While VOR, CDR and CD-3 showed absolute correlation values above 0.6 on synthetic datasets, they were all below 0.44 on the real-world problems. This difference was particularly marked for SD, on synthetic problems the correlation coefficient was -0.42 but on realworld problems it is 0.09. In fact, only FE and CD-1 showed a good correlation on both sets. median performance. Table 6.7 focuses on the performance of the best classifier evaluated over all real-world problems. Again, TBC outperforms all other variants, with the best performance achieved using feature set 5F with a classification error of 0.1750.

It is now possible to evaluate the performance of the complete Ensemble-3 solutions, using the best evolved SPEPs and the best classifier. These results are summarized in Table 6.8, specifying the RMSE discussion the median of the number of times that each feature appears in the best solution from each run. In this plot each line corresponds to either a single PEP or a particular SPEP from each ensemble; for instance, for the Ensemble-2 solutions there are two SPEPs labeled as Ensemble-2-1 and Ensemble-2-2, and similarly for the Ensemble-3 models. Notice that in this plot the lines for SPEP Ensemble-2-1 and SPEP Ensemble-3-1 overlap since they correspond to the same problem group. Finally, an implicit goal of the PEP and SPEP models is to obtain accurate performance predictions in a fraction of the time required to obtain those same estimates by actually performing the GP runs. Pragmatically, one way to validate if this goal is achieved is to calculate the running time for all problems, based on the employed PGPC implementation and the complete SPEP process. These experiments were conducted using MATLAB and the GPLAB toolbox [START_REF] Silva | GPLAB -A Genetic Programming Toolbox for MATLAB[END_REF] running on a PC with Ubuntu 12.04 LTS using an Intel RXeon(R) CPU E3-1270 v3 @ 3.50GHz x 8 processor with 15.6 GB of RAM. In these tests, the minimum amount of time required to compute CEµ (30 runs of PGPC) was 3360.96 seconds, while the maximum amount of time required to compute the PCE (running the SPEP process) was 11.22 seconds. These results clearly show that PEP and SPEP models can be used in real-world scenarios to obtain both accurate and efficient estimations of GP performance 1 .

A

No Free Lunch Theorems (NFL)

Broadly speaking, there are two no free lunch theorems. One for supervised machine learning [START_REF] Wolpert | The lack of a priori distinctions between learning algorithms[END_REF] and one for search/optimization [START_REF] Wolpert | No free lunch theorems for optimization[END_REF]. For an overview of the (no) free lunch and associated theorems, see David Wolpert's What does dinner cost? a.1 No Free Lunch for Supervised Machine Learning Hume (1739-1740) pointed out that even after the observation of the frequent or constant conjunction of objects, we have no reason to draw any inference concerning any object beyond those of which we have had experience. More recently, and with increasing rigour, [START_REF] Mitchell | The need for biases in learning generalizations[END_REF], [START_REF] Schaffer | A conservation law for generalization performance[END_REF] and [START_REF] Wolpert | The lack of a priori distinctions between learning algorithms[END_REF] showed that biasfree learning is futile. [START_REF] Wolpert | The lack of a priori distinctions between learning algorithms[END_REF] shows that in a noise-free scenario where the loss function is the misclassification rate, if one is interested in off-trainingset error, then there are no a priori distinctions between learning algorithms. How well you do is determined by how aligned your learning algorithm P (h | T) is with the actual posterior, P (ν | T).

Wolpert's result, in essence, formalizes Hume, extends him and calls the whole of science into question.

a.2 No Free Lunch for Search/Optimization

The no free lunch theorem for search and optimization [START_REF] Wolpert | No free lunch theorems for optimization[END_REF] applies to finite spaces and algorithms that do not resample points. All algorithms that search for an extremum of a cost function perform exactly the same when averaged over all possible cost functions. So, for any search/optimization algorithm, any elevated performance over one class of problems is exactly paid for in performance over another class.