Sylvain Gelly

Olivier Teytaud

Nicolas Bredeche

Marc Schoenauer

Apprentissage statistique et programmation génétique: la croissance du code est-elle inévitable ?

programmation genetique : la croissance du code est-elle inevitable ? pp163-178. Proceedings of CAP'2005. Universal Consistency, the convergence to the minimum possible error rate in learning through genetic programming (GP), and Code bloat, the excessive increase of code size, are important issues in GP. This paper proposes a theoretical analysis of universal consistency and code bloat in the framework of symbolic regression in GP, from the viewpoint of Statistical Learning Theory, a well grounded mathematical toolbox for Machine Learning. Two kinds of bloat must be distinguished in that context, depending whether the target function has finite description length or not. Then, the Vapnik-Chervonenkis dimension of programs is computed, and we prove that a parsimonious fitness ensures Universal Consistency (i.e. the fact that the solution minimizing the empirical error does converge to the best possible error when the number of examples goes to infinity). However, it is proved that the standard method consisting in choosing a maximal program size depending on the number of examples might still result in programs of infinitely increasing size with their accuracy; a fitness biased by parsimony pressure is proposed. This fitness avoids unnecessary bloat while nevertheless preserving the Universal Consistency.

Introduction

Universal Consistency denotes the convergence of the error rate, in expectation on the unknown distribution of examples, to the optimal one. Despite it's a fundamental element of learning, it has not been widely studied yet in Genetic Programming (GP). Its restricted version, consistency, i.e. convergence to the optimum when the optimum lies in the search space, has not been more studied. Code bloat (or code growth) denotes the growth of program size during the course of Genetic Programming runs. It has been identified as a key problem in GP from the very beginning [START_REF] Koza | Genetic Programming: On the Programming of Computers by Means of Natural Selection[END_REF], and to any variable length representations based learning algorithm [START_REF] Langdon | The evolution of size in variable length representations[END_REF]. It is today a well studied phenomenon, and empirical solutions have been proposed to address the issues of code bloat (see section 2). However, very few theoretical studies have addressed the issue of bloat. The purpose of this paper is to provide some theoretical insights into the bloat phenomenon and its link with universal consistency, in the context of symbolic regression by GP, from the Statistical Learning Theory viewpoint [START_REF] Vapnik | The nature of statistical learning theory[END_REF]. Statistical Learning Theory is a recent, yet mature, area of Machine Learning that provides efficient theoretical tools to analyse aspects of learning accuracy and algorithm complexity. Our goal is both to perform an in-depth analysis of bloat and to provide appropriate solutions to avoid it. The paper is organized as follows : in the section below, we briefly survey some explanations for code bloat that have been proposed in the literature, and provide an informal description of our results from a GP perspective before discussing their interest for the GP practitioner. Section 2 gives a brief overview of the basic results of Learning Theory that will be used in Section 3 to formally prove all the advertised results. Finally, section 5 discusses the consequences of those theoretical results for GP practitioners and gives some perspectives about this work.

The several theories that intend to explain code bloat are : -the introns theory states that code bloat acts as a protective mechanism in order to avoid the destructive effects of operators once relevant solutions have been found [START_REF] Nordin | Complexity compression and evolution[END_REF][START_REF] Mcphee | Accurate replication in genetic programming[END_REF][START_REF] Blickle | Genetic programming and redundancy[END_REF]. Introns are pieces of code that have no influence on the fitness: either subprograms that are never executed, or sub-programs which have no effect; -the fitness causes bloat theory relies on the assumption that there is a greater probability to find a bigger program with the same behavior (i.e. semantically equivalent) than to find a shorter one. Thus, once a good solution is found, programs naturally tends to grow because of fitness pressure [START_REF] Langdon | Fitness causes bloat: Mutation[END_REF]. This theory states that code bloat is operatorindependent and may happen for any variable length representation-based algorithm. As a consequence, code bloat is not to be limited to population-based stochastic algorithm (such as GP), but may be extended to many algorithms using variable length representation [START_REF] Langdon | The evolution of size in variable length representations[END_REF]; -the removal bias theory states that removing longer sub-programs is more tacky than removing shorter ones (because of possible destructive consequence), so there is a natural bias that benefits to the preservation of longer programs [START_REF] Soule | Exons and code growth in genetic programming[END_REF].

While it is now considered that each of these theories somewhat captures part of the problem [START_REF] Banzhaf | Some considerations on the reason for bloat[END_REF], there has not been any definitive global explanation of the bloat phenomenon. At the same time, no definitive practical solution has been proposed that would avoid the drawbacks of bloat (increasing evaluation time of large trees) while maintaining the good performances of GP on difficult problems. Some common solutions rely either on specific operators (e.g. size-fair crossover [START_REF] Langdon | Size fair and homologous tree genetic programming crossovers[END_REF], or different Fair Mutation [START_REF] Langdon | The evolution of size and shape[END_REF]), on some parsimony-based penalization of the fitness [START_REF] Soule | Effects of code growth and parsimony pressure on populations in genetic programming[END_REF] or on abrupt limitation of the program size such as the one originally used by Koza [START_REF] Koza | Genetic Programming: On the Programming of Computers by Means of Natural Selection[END_REF]. Some other more particular solutions have been proposed but are not widely used yet [START_REF] Ratle | Avoiding the bloat with probabilistic grammar-guided genetic programming[END_REF][START_REF] Silva | Dynamic maximum tree depth : A simple technique for avoiding bloat in tree-based gp[END_REF][START_REF] Luke | Lexicographic parsimony pressure[END_REF].

In this paper, we prove, under some sufficient conditions, that the solution given by GP actually converges, when the number of examples goes to infinity, toward the actual function used to generate the examples. This property is known in Statistical Learning as Universal Consistency. Note that this notion is a slightly different from that of Universal Approximation, that people usually refer to when doing symbolic regression in GP: because polynomial for instance are known to be able to approximate any continuous function, GP search using operators {+, * } is also assumed to be able to approximate any continuous function. However, Universal Consistency is concerned with the behavior of the algorithm when the number of examples goes to infinity: being able to find a polynomial that approximates a given function at any arbitrary precision does not imply that any interpolation polynomial built from an arbitrary set of sample points will converge to that given function when the number of points goes to infinity.

But going back to bloat, and sticking to the polynomial example, it is also clear that the degree of the interpolation polynomial of a set of examples increases linearly with the number of examples. This leads us to start our bloat analysis by defining two kinds of bloat. On the one hand, we define the structural bloat as the code bloat that unavoidably takes place when no optimal solution (i.e. no function that exactly matches all possible examples) is approximated by the search space. In such a situation, optimal solutions of increasing accuracy will also exhibit an increasing complexity, as larger and larger code will be generated in order to better approximate the target function. The extreme case of structural bloat has also been demonstrated in [START_REF] Gustafson | Problem difficulty and code growth in Genetic Programming[END_REF]. The authors use some polynomial functions of increasing difficulty, and demonstrate that a precise fit can only be obtained through an increased bloat (see also [START_REF] Daida | What makes a problem gp-hard? analysis of a tunably difficult problem in genetic programming[END_REF] for related issues about problem complexity in GP). On the other hand, we define the functional bloat as the bloat that takes place when programs length keeps on growing even though an optimal solution (of known complexity) does lie in the search space. In order to clarify this point, let us use a simple symbolic regression problem defined as follow : given a set S of examples, the goal is to find a function f (here, a GP-tree) that minimized the Least Square Error (or LSE). If we intend to approximate a polynomial (ex. : 14 * x 2 ), we may observe code bloat since it is possible to find arbitrarily long polynomials that gives the exact solution (ex. : 14 * x 2 + 0 * x 3 + ...). Most of the works cited in section 1 are in fact concerned with functional bloat which is the simplest, yet already problematic, kind of bloat.

Overview of results.

In section 3, we shall investigate the Universal Consistency of Genetic Programming, and study in detail structural and functional bloat that might take place when searching program spaces using GP. A formal and detailed definition of the program space in GP is given in Lemma 1, section 3, and two types of results will then be derived: i) Universal Consistency results, i.e. does the probability of misclassification of the solution given by GP converges to the optimal probability of misclassification when the number of examples goes to infinity? ii) Bloat-related results, first regarding structural bloat, and second with respect to functional bloat in front of various types of fitness penalization and/or bounds on the complexity of the programs.

Let us now state precisely, yet informally, our main results. First, as already mentioned, we will precisely define the set of programs under examination, and prove that such a search space fulfills the conditions of the standard theorems of Statistical Learning Theory listed in Section 2. Second, applying those theorems will immediately lead to a first Universal Consistency result for GP, provided that some penalization for complexity is added to the fitness (Theorem 3). Third: the first bloat-related result, Proposition 4, unsurprisingly proves that if no optimal function belongs to the search space, then converging to the optimal error implies an infinite increase of bloat. Fourth, theorem 5 is also a negative result about bloat, as it proves that even if the optimal function belongs to the search space, minimizing the LSE alone might lead to bloat (i.e. the com-plexity of the empirical solutions goes to infinity with the sample size). Finally, the last two theorems (5' and 6) are the best positive results one could expect considering the previous findings: it is possible to carefully adjust the parsimony pressure so as to obtain both Universal Consistency and bounds on the complexity of the empirical solution (i.e. no bloat). Section 4 discuss some properties of alternate solutions for complexity penalization : cross-validation or hold out, with various pairing of data sets.

Note that, though all proofs in Section 3 will be stated and proved in the context of classification (i.e. find a function from R d into {0, 1}), their generalization to regression (i.e. find a function from R d into R) is straightforward.

Discussion

The first limit of our work is the fact that all these results consider that GP finds a program which is empirically the best, in the sense that given a set of examples and a fitness function based on the Least Square Error (and possibly including some parsimony penalization), it will be assumed that GP does find one program in that search space that minimizes this fitness -and it is the behavior of this ideal solution, which is a random function of the number of examples, that is theoretically studied. Of course, we all know that GP is not such an ideal search procedure, and hence such results might look rather far away from GP practice, where the user desperately tries to find a program that gives a reasonably low empirical approximation error. Nevertheless, Universal Consistency is vital for the practitioner too: indeed, it would be totally pointless to fight to approximate an empirically optimal function without any guarantee that this empirical optimum is anywhere close to the ideal optimal solution we are in fact looking for. Furthermore, the bloat-related results give some useful hints about the type of parsimony that has a chance to efficiently fight the unwanted bloat, while maintaining the Universal Consistency property -though some actual experiments will have to be run to confirm the usefulness of those theoretical hints.

Elements of Learning theory

In the frameworks of regression and classification, Statistical Learning Theory [START_REF] Vapnik | The nature of statistical learning theory[END_REF] is concerned with giving some bounds on the generalization error (i.e. the error on yet unseen data points) in terms of the actual empirical error (the LSE error above) and some fixed quantity depending only on the search space. More precisely, we will use here the notion of Vapnik-Chervonenkis dimension (in short, VCdim) of a space of functions. Roughly, VC-dim provides bounds on the difference between the empirical error and the generalization error.

Consider a set of s examples (x i , y i ) i∈{1,...,s} . These examples are drawn from a distribution P on the couple (X, Y ). They are independent identically distributed, Y = {0, 1} (classification problem), and typically X = R d for some dimension d. For any function f , define the loss L(f ) to be the expectation of |f (X) -Y |. Similarly, define the empirical loss L(f ) as the loss observed on the examples: L(f ) = Theorem A [5, Th. 12.8, p206] : Consider F a family of functions from a domain X to {0, 1} and V its VC-dimension. Then, for any ǫ > 0 P ( sup

P ∈F |L(P ) -L(P )| ≥ ǫ) ≤ 4 exp(4ǫ + 4ǫ 2 )s 2V exp(-2sǫ 2 )
and for any δ ∈]0, 1]P ( sup

P ∈F |L(P ) -L(P )| ≥ ǫ(s, V, δ)) ≤ δ where ǫ(s, V, δ) = 4-log(δ/(4s 2V )) 2s-4
. Interpretation : In a family of finite VC-dimension, the empirical errors and the generalization errors are probably closely related.

Other forms of this theorem have no log(n) factor ; they are known as Alexander's bound, but the constant is so large that this result is not better than the result above unless s is huge ([5, p207]): if s ≥ 64/ǫ 2 , P ( sup

P ∈F |L(P ) -L(P )| ≥ ǫ) ≤ 16( √ sǫ) 4096V exp(-2sǫ 2 )
We classically derive the following result from theorem A: Theorem A' : Consider F s for s ≥ 0 a family of functions from a domain X to {0, 1} and V s its VC-dimension. Then, sup P ∈Fs |L(P ) -L(P )| → 0 as s → ∞ almost surely whenever V s = o(s/ log(s)).

Interpretation : The maximal difference between the empirical error and the generalization error goes almost surely to 0 if the VC-dimension is finite.

Proof :

We use the classical Borell-Cantelli lemma 1 , for any ǫ ∈ [0, 1] :

s≥64/ǫ 2 P (|L(P ) -L(P )| > ǫ) ≤ 16 s≥64/ǫ 2 ( √ sǫ) 4096Vs exp(-2sǫ 2 ) ≤ 16 s≥64/ǫ 2 exp(4096V s (log( √ s) + log(ǫ)) -2sǫ 2 )
which is finite as soon as V s = o(s/ log(s)). Theorem B in [5, Th. 18.2, p290] :

Let F 1 , . . . , F k . . . with finite VC-dimensions V 1 , . . . , V k , . . . Let F = ∪ n F n . Then, being given s examples, consider P ∈ F s minimizing the empirical risk L among F s . Then, if V s = o(s/log(s)) and V s → ∞, P (L( P ) ≤ L( P ) + ǫ(s, V s , δ)) ≥ 1 -δ P (L( P ) ≤ inf P ∈Fs L(P ) + 2ǫ(s, V s , δ)) ≥ 1 -δ and L( P ) → inf P ∈F L(P ) a.s.
Note that for a well chosen family of functions (typically, programs), inf P ∈F L(P ) = L * for any distribution ; so, theorem B leads to universal consistency (i.e. ∀P ; L( P ) → L * ), for a well-chosen family of functions. 1

If

P n P (Xn > ǫ) is finite for any ǫ > 0 andXn > 0, then Xn → 0 almost surely.

Interpretation : If the VC-dimension increases slowly enough as a function of the number of examples, then the generalization error goes to the optimal one. If the family of functions is well-chosen, this slow increase of VC-dimension leads to universal consistency.

In the following theorem, we use d ′ , t ′ , q ′ instead of d, t, q for the sake of notations in a corollary below.

Theorem C (8.14 and 8.4 in [START_REF] Antony | Neural network learning : Theoretical foundations[END_REF]) : Let H = {x → h(a, x); a ∈ R d ′ } where h can be computed with at most t ′ operations among α → exp(α) ; +, -, ×, / ; jumps conditioned on >, ≥, =, ≤, = ; output 0 ; output 1. Then :

V Cdim(H) ≤ t ′2 d ′ (d ′ + 19 log 2 (9d ′ ))
. Furthermore, if exp(.) is used at most q ′ times, and if there are at most t ′ operations executed among arithmetic operators, conditional jumps, exponentials,

π(H, m) ≤ 2 (d ′ (q ′ +1))2/2 (9d ′ (q ′ + 1)2 t ) 5d ′ (q ′ +1) (em(2 t ′ -2)/d ′ ) d ′
where π(H, m) is the m th shattering coefficient of H, and hence

V Cdim(H) ≤ (d ′ (q ′ + 1)) 2 + 11d ′ (q ′ + 1)(t ′ + log 2 (9d ′ (q ′ + 1))) Finally, if q ′ = 0 then V Cdim(H) ≤ 4d ′ (t ′ + 2
. . . with finite VC-dimensions V 1 , . . . , V k , . . . Let F = ∪ n F n .
Assume that all distribution lead to L F = L * where L * is the optimal possible error (spaces of functions ensuring this exist). Then, given s examples, consider f ∈ F minimizing

L(f ) + 32 s V (f ) log(e × s), where V (f ) is V k with k minimal such that f ∈ F k . Then :
• if additionally one optimal function belongs to F k , then for any s and ǫ such that V k log(e × s) ≤ sǫ 2 /512, the generalization error is lower than ǫ with probability at most ∆ exp(-sǫ 2 /128) + 8s V k × exp(-sǫ 2 /512) where ∆ = ∞ j=1 exp(-V j ) is assumed finite.

• the generalization error, with probability 1, converges to L * .

Interpretation : The optimization of a compromise between empirical accuracy and regularization lead to the same properties as in theorem B, plus a stronger convergence rate property.

Results

This section presents in details results surveyed above. They make an intensive use of the results of Statistical Learning Theory presented in the previous section.

More precisely, Lemma 1 defines precisely the space of programs considered here, and carefully shows that it satisfies the hypotheses of Theorems A-C. This allows us to evaluate the VC-dimension of sets of programs, stated in Theorem 2. Then, announced results are derived. Finally, next we propose a new approach combining an a priori limit on VC-dimension (i.e. size limit) and a complexity penalization (i.e. parsimony pressure) and state in theorem 6 that this leads to both universal consistency and convergence to an optimal complexity of the program (i.e. no bloat).

We first prove the following Lemma 1 : Let F be the set of functions which can be computed with at most t operations among :

• operations α → exp(α) (at most q times); • operations +, -, ×, / ;

• jumps conditioned on >, ≥, =, ≤, = ; and • output 0 ; • output 1 ; • labels for jumps ;

• at most m constants ;

• at most z variables by a program with at most n lines. We note log 2 (x) the integer part (ceil) of log(x)/ log [START_REF] Banzhaf | Some considerations on the reason for bloat[END_REF]. Then F is included in H as defined in theorem C, for a given P with

t ′ = t + t max(3 + log 2 (n) + log 2 (z), 7 + 3 log 2 (z)) + n(11 + max(9log 2 (z), 0) + max(3log 2 (z) -3, 0)), q ′ = q, d ′ = 1 + m.
Interpretation : This lemma states that a family of programs as defined above is included in the parametrizations of one well-chosen program. This replaces a family of programs by one parametric program, and it will be useful for the computation of VC-dimension of a family of programs by theorem C.

Proof : In order to prove this result, we define below a program as in theorem above that can emulate any of these programs, with at most

t ′ = t + t max(3 + log 2 (n) + log 2 (z), 7 + 3 log 2 (z)) + n(11 + max(9log 2 (z), 0) + max(3log 2 (z) -3, 0)), q ′ = q, d ′ = 1 + m.
The program is as follows :

• label "inputs" • initialize variable(1) at value x(1) • label "output 0" • output 0 • label "output 1" • output 1 "operation decode c" can be developed as follows. Indeed, we need m real numbers, for parameters, and 4n integers c(., .), that we will encode as only one real number in [0, 1] as follows :

• initialize variable(2) at value x(2) • . . . • initialize variable(dim(x)) at value x(dim(x)) • label "constants" • initialize variable(dim(x) + 1) at value a 1 • initialize variable(dim(x) + 2) at value a 2 • . . . • initialize variable(dim(x) + m) at value a m • label "Decode the program into c" • operation decode c • label "Line 1" • operation c(1,
1. let y ∈ [0, 1] 2. for each i ∈ [1, . . . n] : • c(i, 1) = 0 • y = y * 2 • if (y > 1) then { c(i, 1) = 1 ; y = y -1 } • y = y * 2 • if (y > 1) then { c(i, 1) = c(i, 1) + 2 ; y = y -1 } • y = y * 2 • if (y > 1) then { c(i, 1) = c(i, 1) + 4 ; y = y -1 } 3. for each j ∈ [2, 4] and i ∈ [1, . . . n] : • c(i, j) = 0 • y = y * 2 • if (y > 1) then { c(i, j) = 1 ; y = y -1 } • y = y * 2 • if (y > 1) then { c(i, j) = c(i, j) + 2 ; y = y -1 } • y = y * 2 • if (y > 1) then { c(i, j) = c(i, j) + 4 ; y = y -1 } • . . . • y = y * 2 • if (y > 1) then { c(i, j) = c(i, j) + 2 log2(z)-1 ; y = y -1 }
The cost of this is n × (3 + max(3 × log 2 (z), 0)) "if then", and n × (3 + max(3 × log 2 (z), 0)) operators ×, and n(2 + max(3(log 2 (z) -1), 0)) operators +, and n × (3 + max(3 × log 2 (z), 0)) operators -. The overall sum is bounded by n(11 + max(9 log 2 (z), 0) + max(3log 2 (z) -3, 0)).

The result then derives from the rewriting of "operation c(i, 1) with variables c(i,2) and c(i,3)". This expression can be developed as follows:

• if c(i, 1) == 0 then goto "output1" • if c(i, 1) == 1 then goto "output 0" • if c(i, 2) == 1 then c = variable(1) • if c(i, 2) == 2 then c = variable(2) • . . . • if c(i, 2) == z then c = variable(z)
• if c(i, 1) == 7 then goto "Line c" (must be encoded by dichotomy with log 2 (n) lines) • if c(i, 1) == 6 then goto "exponential(i)"

• if c(i, 3) == 1 then b = variable(1) • if c(i, 3) == 2 then b = variable(2) • . . . • if c(i, 3) == z then b = variable(z) • if c(i, 1) == 2 then a = c + b • if c(i, 1) == 3 then a = c -b • if c(i, 1) == 4 then a = c × b • if c(i, 1) == 5 then a = c/b • if c(i, 4) == 1 then variable(1) = a • if c(i, 4) == 2 then variable(2) = a • . . . • if c(i, 4) == z then variable(z) = a • label "endOfInstruction(i)"
For each such instruction, at the end of the program, we add three lines of the following form :

• label "exponential(i)" • a = exp(c) • goto "endOfInstruction(i)"
Each sequence of the form "if x=... then" (p times) can be encoded by dichotomy with log 2 (p) tests "if ... then goto". Hence, the expected result.

Theorem 2 : Let F be the set of programs as in lemma 1, where

q ′ ≥ q, t ′ ≥ t + t max(3 + log 2 (n) + log 2 (z), 7 + 3 log 2 (z)) + n(11 + max(9log 2 (z), 0) + max(3log 2 (z) -3, 0)), d ′ ≥ 1 + m. V Cdim(H) ≤ t ′2 d ′ (d ′ + 19 log 2 (9d ′ )) V Cdim(H) ≤ (d ′ (q ′ + 1)) 2 + 11d ′ (q ′ + 1)(t ′ + log 2 (9d ′ (q ′ + 1)))
If q = 0 (no exponential) then V Cdim(H) ≤ 4d ′ (t ′ + 2).

Interpretation : interesting and natural families of programs have finite VCdimension. Effective methods can associate a VC-dimension to these families of programs.

Proof : Just plug Lemma 1 in Theorem C. We now consider how to use such results in order to ensure universal consistency. First, we show why simple empirical minimization (consisting in choosing one function such that L is minimum) does not ensure consistency. Precisely, we state that, for some distribution of examples, and some i.i.d sequence of examples (x 1 , y 1 ), . . . , (x n , y n ), there exists P 1 , . . . , P n , . . . such that

∀i ∈ [[1, n]]P n (x i ) = y i and however ∀n ∈ NP (f (x) = y) = 0.
The proof is as follows. Consider the distribution with x uniformly drawn in [0, 1] and y constant equal to 1. Consider P n the program that compares its entry to x 1 , x 2 , . . . ,

x n , and outputs 1 if the entry is equal to x j for some j ≤ n, and 0 otherwise else. With probability 1, this program output 0, whereas y = 1 with probability 1.

We therefore conclude that minimizing the empirical risk is not enough for ensuring any satisfactory form of consistency. Let's now show that structural risk minimization, i.e. taking into accound a penalization for complex structures, can do the job, i.e. ensure universal consistency, and fast convergence when the solution can be written within finite complexity.

Theorem 3 : Consider q f , t f , m f , n f and z f integer sequences, non-decreasing functions of f . Define V f = V Cdim(H f ), where H f is the set of programs with at most t f lines executed, with z f variables, n f lines, q f exponentials, and m f constants.

Then with

q ′ f = q f , t ′ f = t f + t f max(3 + log 2 (n f ) + log 2 (z f ), 7 + 3 log 2 (z f )) + n f (11 + max(9log 2 (z f ), 0) + max(3log 2 (z f ) -3, 0)), d ′ f = 1 + m f , V f = (d ′ f (q ′ f + 1)) 2 + 11d ′ f (q ′ f + 1)(t ′ f + log 2 (9d ′ f (q ′ f + 1))) or, if ∀f q f = 0 then define V f = 4d ′ f (t ′ f + 2). Then, being given s examples, consider f ∈ F minimizing L(f ) + 32 s V (f ) log(e × s), where V (f ) is the min of all k such that f ∈ F k . Then, if ∆ = ∞ j=1 exp(-V j ) is finite,
-the generalization error, with probability 1, converges to L * .

-if one optimal rule belongs to F k , then for any s and ǫ such that V k log(e × s) ≤ sǫ 2 /512, the generalization error is lower than L * + ǫ with probability at most ∆ exp(-sǫ 2 /128) + 8s

V k × exp(-sǫ 2 /512) where ∆ = ∞ j=1 exp(-V j ) is as- sumed finite.
Interpretation : Genetic programming for bi-class classification, provided that structural risk minimization is performed, is universally consistent and verifies some convergence rate properties.

Proof : Just plug theorem D in theorem 2.

We now prove the non-surprising fact that if it is possible to approximate the optimal function (the Bayesian classifier) without reaching it exactly, then the "complexity" of the program runs to infinity as soon as there is convergence of the generalization error to the optimal one. Proposition 4: Consider P s a sequence of functions such that P s ∈ F V (s) , with F 1 ⊂ F 2 ⊂ F 3 ⊂ . . . , where F V is a set of functions from X to {0, 1} with VC-dimension bounded by V . Define L V = inf P ∈FV L(P ) and V (P ) = inf{V ; P ∈ F V } and suppose that ∀V L V > L * . Then, (L(P s )

s→∞ -→ L * ) =⇒ (V (P s ) s→∞ -→ ∞).
Interpretation : This is structural bloat : if your space of programs approximates but does not contain the optimal function, then bloat occurs.

Proof:

Define ǫ(V ) = L V -L * . Assume that ∀V ǫ(V ) > 0. ǫ is necessarily non-increasing.
Consider V 0 a positive integer ; let us prove that if s is large enough, then

V (P s ) ≥ V 0 .
There exists ǫ 0 such that ǫ(V 0 ) > ǫ 0 > 0.

For s large enough,

L(P s ) ≤ L * + ǫ 0 , hence L Vs ≤ L * + ǫ 0 , hence L * + ǫ(V s ) ≤ L * + ǫ 0 , hence ǫ(V s ) ≤ ǫ 0 , hence V s > V 0 .
We now show that the usual procedure defined below, consisting in defining a maximum VC-dimension depending upon the sample size (as usually done in practice and as recommended by theorem B) and then using a moderate family of functions, leads to bloat. With the same hypotheses as in theorem B, we can state Theorem 5 (bloat theorem for empirical risk minimization with relevant VCdimension): Let F 1 , . . . , F k . . . non-empty sets of functions with finite VC-dimensions V 1 , . . . , V k , . . . Let F = ∪ n F n . Then, given s examples, consider P ∈ F s minimizing the empirical risk L in F s . ¿From Theorem B we already know that if V s = o(s/log(s)) and V s → ∞, then P (L( P ) ≤ L( P ) + ǫ(s, V s , δ)) ≥ 1 -δ, and L( P ) → inf P ∈F L(P ) a.s..

We will now state that if V s → ∞, and noting V (f ) = min{V k ; f ∈ F k }, then ∀V 0 , P 0 > 0, ∃P , distribution of probability on X and Y , such that ∃g ∈ F 1 such that L(g) = L * and for s sufficiently large P (V ( P ) ≤ V 0 ) ≤ P 0 .

Interpretation : The result in particular implies that for any V 0 , there is a distribution of examples such that ∃g; V (g) = V 1 and L(g) = L * , with probability 1, V ( f ) ≥ V 0 infinitely often as s increases. This shows that bloat can occur if we use only an abrupt limit on code size, even if this limit depends upon the number of examples (a fortiori if there's no limit).

Proof (of the part which is not theorem B) : See figure 3 for a figure illustrating the proof. Consider V 0 > 0 and P 0 > 0. Consider α such that (eα/2 α ) V0 ≤ P 0 /2. Consider s such that V s ≥ αV 0 . Let d = αV 0 . Consider x 1 , . . . , x d d points shattered by F d ; such a family of d points exist, by definition of F d . Define the probability measure P by the fact that X and Y are independent and P (Y = 1) = 1 2 and P (X = x i ) = 1 d . Then, the following holds, with Q the empirical distribution (the average of Dirac masses on the x i 's) : 1. no empty x i 's : P (E 1 ) → 0 where E 1 is the fact that ∃i; Q(X = x i ) = 0, as s → ∞. 2. no equality : P (E 2 ) → 0 where E 2 is the fact that E 1 occurs or ∃i; We now only have to use classical results. It is well known in VC-theory that S(a, b) ≤ (ea/b) b (see for example [5, chap.13]), hence S(d, d/α) ≤ (ed/(d/α)) d/α and P (E 3 |E 2 does not hold) ≤ (eα) d/α /2 d ≤ P 0 /2. If n is sufficiently large to ensure that P (E 2 ) ≤ P 0 /2 (we have proved above that P (E 2 ) → 0 as s → ∞) then

Smallest
Q(Y = 1|X = x i ) = 1 2 . 3.
P (E 3 ) ≤ P (E 3 |¬E 2 )×P (¬E 2 )+P (E 2 ) ≤ P (E 3 |¬E 2 )+P (E 2 ) ≤ P 0 /2+P 0 /2 ≤ P 0
We now show that, on the other hand, it is possible to optimize a compromise between optimality and complexity in an explicit manner (e.g., replacing 1 % precision with 10 lines of programs or 10 minutes of CPU) :

Theorem 5' (bloat-control theorem for regularized empirical risk minimization with relevant VC-dimension): Let F 1 , . . . , F k . . . be non-empty sets of functions with finite VC-dimensions V 1 , . . . , V k , . . . Let F = ∪ n F n . Consider W a user-defined complexity penalization term. Then, being given s examples, consider P ∈ F s minimizing the regularized empirical risk L(P ) = L(P ) + W (P ) among F s . If V s = o(s/log(s)) and V s → ∞, then L( P ) → inf P ∈F L(P ) a.s. where L(P ) = L(P ) + W (P ).

Interpretation : Theorem 5' shows that, using a relevant a priori bound on the complexity of the program and adding a user-defined complexity penalization to the fitness, can lead to convergence toward a user-defined compromise ( [START_REF] Zhang | Balancing accuracy and parsimony in genetic programming[END_REF][START_REF] Zhang | Evolutionary induction of sparse neural trees[END_REF]) between classification rate and program complexity (i.e. we ensure almost sure convergence to a compromise of the form "λ 1 CPU time + λ 2 misclassification rate + λ 3 number of lines", where the λ i are user-defined).

Remark : the drawback of this approach is that we have lost universal consistency and consistency (in the general case, the misclassification rate in generalization will not converge to the Bayes error, and whenever an optimal program exists, we will not necessarily converge to its efficiency).

Proof : See figure 3 We now turn our attention to a more complicated case where we want to ensure universal consistency, but we want to avoid a non-necessary bloat ; e.g., we require that if an optimal program exists in our family of functions, then we want to converge to its error rate, without increasing the complexity of the program. We consider a merge between regularization and bounding of the VC-dimension ; we penalize the complexity (e.g., length) of programs by a penalty term R(s, P ) = R(s)R ′ (P ) depending upon the sample size and upon the program ; R(., .) is user-defined and the algorithm will look for a classifier with a small value of both R ′ and L. We study both the universal consistency of this algorithm (i.e. L → L * ) and the no-bloat theorem (i.e. R ′ → R ′ (P * ) when P * exists).

Theorem

6 : Let F 1 , . . . , F k . . . with finite VC-dimensions V 1 , . . . , V k , . . . Let F = ∪ n F n . Define V (P ) = V k with k = inf{t|P ∈ F t }. Define L V = inf P ∈FV L(P ). Consider V s = o(log(s)) and V s → ∞. Consider P minimiz-
ing L(P ) = L(P ) + R(s, P ) in F s and assume that R(s, .) ≥ 0. Then (consistency), whenever sup P ∈FV s R(s, P ) = o(1), L( P ) → inf P ∈F L(P ) almost surely (note that for well chosen family of functions, inf P ∈F L(P ) = L * ). Moreover, assume that ∃P * ∈ F V * L(P * ) = L * . Then with R(s, P ) = R(s)R ′ (P ) and with R ′ (s) = sup P ∈FV s R ′ (P ) :

1. non-asymptotic no-bloat theorem : R ′ ( P ) ≤ R ′ (P * ) + (1/R(s))2ǫ(s, V s , δ)

with probability at least 1 -δ (this result is in particular interesting for ǫ(s, V s , δ)/R(s) → 0, what is possible for usual regularization terms as in theorem D, 2. almost-sure no-bloat theorem : if R(s)s (1-α)/2 = O(1), then almost surely R ′ ( P ) → R ′ (P * ) and if R ′ (P ) has discrete values (such as the number of instructions in P or many complexity measures for programs) then for s sufficiently large, R ′ ( P ) = R ′ (P * ). 3. convergence rate : with probability at least 1 -δ, Interpretation : Combining a code limitation and a penalization leads to universal consistency without bloat.

L( P ) ≤ inf P ∈FV s L(P ) + R(s)R ′ (s)
Remarks : The usual R(s, P ) as used in theorem D or theorem 3 provides consistency and non-asymptotic no-bloat. A stronger regularization leads to the same results, plus almost sure no-bloat. The asymptotic convergence rate depends upon the regularization. The result is not limited to genetic programming and could be used in other areas. As shown in proposition 4, the no-bloat results require the fact that ∃V * ∃P * ∈ F V * L(P * ) = L * . Interestingly, the convergence rate is reduced when the regularization is increased in order to get the almost sure no-bloat theorem.

Proof :

Define ǫ(s, V ) = sup f ∈FV | L(f )-L(f )|.
Let us prove the consistency. For any P , L( P )+R(s, P ) ≤ L(P )+R(s, P ). On the other hand, L( P ) ≤ L( P )+ǫ(s, V s ). So :

L( P ) ≤ ( inf

P ∈FV s ( L(P ) + R(s, P ))) -R(s, P ) + ǫ(s, V s ) ≤ ( inf P ∈FV s (L(P ) + ǫ(s, V s ) + R(s, P ))) -R(s, P ) + ǫ(s, V s ) ≤ ( inf P ∈FV s (L(P ) + R(s, P ))) + 2ǫ(s, V s )
as ǫ(s, V s ) → 0 almost surely2 and (inf P ∈FV s (L(P ) + R(s, P ))) → inf P ∈F L(P ), we conclude that L( P ) → inf P ∈F L(P ) a.s. We now focus on the proof of the "no bloat" result : By definition of the algorithm, for s sufficiently large to ensure P * ∈ F Vs , L( P ) + R(s, P ) ≤ L(P * ) + R(s, P * ) hence with probability at least 1 -δ, R ′ ( P ) ≤ R ′ (P * ) + (1/R(s))(L * + ǫ(s, V s , δ) -L( P ) + ǫ(s, V s , δ)) hence R ′ ( P ) ≤ R ′ (V * ) + (1/R(s))(L * -L( P ) + 2ǫ(s, V s , δ))

As L * ≤ L( P ), this leads to the non-asymptotic version of the no-bloat theorem.

The almost sure no-bloat theorem is derived as follows.

R ′ ( P ) ≤ R ′ (P * ) + 1/R(s)(L * + ǫ(s, V s ) -L( P ) + ǫ(s, V s ))

hence R ′ ( P ) ≤ R ′ (P * ) + 1/R(s)(L * -L( P ) + 2ǫ(s, V s ))

R ′ ( P ) ≤ R ′ (P * ) + 1/R(s)2ǫ(s, V s )

All we need is the fact that ǫ(s, V s )/R(s) → 0 a.s. For any ǫ > 0, we consider the probability of ǫ(s, V s )/R(s) > ǫ, and we sum over s > 0. By the Borell-Cantelli lemma, the finiteness of this sum is sufficient for the almost sure convergence to 0.

The probability of ǫ(s, V s )/R(s) > ǫ is the probability of ǫ(s, V s ) > ǫR(s). By theorem A, this is bounded above by O(exp(2V s log(s) -2sǫ 2 R(s) 2 )). This has finite sum for R(s) = Ω(s -(1-α)/2 ).

Let us now consider the convergence rate. Consider s sufficiently large to ensure L Vs = L * . As shown above during the proof of the consistency, L( P ) ≤ ( inf so with probability at least 1 -δ, ≤ inf P ∈FV s L(P ) + R(s)R ′ (s) + 2ǫ(s, V s , δ)

P

Extensions

We have studied above :

-the method consisting in minimizing the empirical error, i.e. the error observed on examples (leading to bloat (this is an a fortiori consequence of theorem 5) without universal consistency (see remark before theorem 3)) ; -the method consisting in minimizing the empirical error, i.e. the error observed on examples, with a hard bound on the complexity (leading to universal consistency but bloat, see theorem 5) ; -the method, inspired from (but slightly adapted against bloat) structural risk minimization, consisting in minimizing a compromize between the empirical error and a complexity bound including size and computation-time (see theorem 6).

We study the following other cases now :

-the case in which the level of complexity is chosen through resamplings, i.e. crossvalidation or hold out ; -the case in which the complexity penalization does not include any time bound but only size bounds ;

We mainly conclude that penalization is necessary, cannot be replaced by crossvalidation, cannot be replaced by hold-out, and must include time-penalization.

About the use of cross-validation or hold-out for avoiding bloat and choosing the complexity level

Note UC for universal consistency and ERM for empirical risk minimization. We considered above different cases :

-evolutionary programming with only "ERM" fitness ; -evolutionary programming with ERM+bound (leading to UC + bloat) ; -evolutionary programming with ERM+penalization+bound (leading to UC without bloat).

One can now consider some other cases :

1 )

 1 with variables c(1, 2) and c(1, 3) and c(1, 4) • label "Line 2" • operation c(2, 1) with variables c(2, 2) and c(2, 3) and c(2, 4) • . . . • label "Line n" • operation c(n, 1) with variables c(n, 2)and c(n, 3) and c(n, 4)

Fig. 1 .

 1 Fig. 1. Illustration of the proof. With a larger k, F k has a smaller best error.

  for a figure illustrating the proof. sup P ∈Fs | L(P ) -L(P )| ≤ sup P ∈Fs | L(P ) -L(P )| ≤ ǫ(s, V s ) → 0, almost surely, by theorem A'. Hence the expected result.

=o( 1 )

 1 by hypothesis+2ǫ(s, V s , δ) where ǫ(s, V, δ) = 4-log(δ/(4s 2V )) 2s-4is an upper bound on ǫ(s, V ) = sup f ∈FV | L(f ) -L(f )| (given by theorem A), true with probability at least 1 -δ.

  ∈FV s (L(P ) + R(s, P ))) + 2ǫ(s, V s ) ≤ ( infP ∈FV s (L(P ) + R(s)R ′ (P ))) + 2ǫ(s, V s ) ≤ inf P ∈FV s L(P ) + R(s)R ′ (s) + 2ǫ(s, V s )

  the best function is not in F V0 : P (E 3 |E 2 does not hold) ≤ S(d, d/α)/2 d where E 3 is the fact that ∃g ∈ F d/α=V0 ; L(g) = inf F d L, with S(d, d/α) the relevant shattering coefficient, i.e. the cardinal of F d/α restricted to {x 1 , . . . , x d }.

  Illustration of the proof. With a larger k, F k has a smaller best error, but the penalization is stronger than the difference of error.

	Smallest
	Error
	in	Fk
	HatLTilde
	HatL
		LTilde
		L
		Complexity Vk
		of family Fk
	Fig. 2.

s i |f (x i ) -y i |.Finally, define L * , the Bayes error, as the smallest possible generalization error for any mapping from X to {0, 1}.The following 4 theorems are well-known in the Statistical Learning community:

See theorem A'

Acknowledgements This work was supported in part by the PASCAL Network of Excellence. We thank Bill Langdon for very helpful comments.

-hold out in order to choose between different complexity classes (i.e., in the Paretofront corresponding to the compromise between ERM and complexity, choose the function by hold out) ; -idem through cross-validation. This section is devoted to these cases. First, let's consider hold-out for choosing the complexity level. Consider that the function can be chosen in many complexity levels, F 0 ⊂ F 1 ⊂ F 2 ⊂ F 3 ⊂ . . . , where F i = F i+1 . Note L(f, X) the error rate of the function f in the set X of examples:

where l(f, X i ) = 1 if f fails on X i and 0 otherwise. Define f k = arg min F k L(., X k ).

In hold-out, f = f k * where k * = arg min k l k where

In all the sequel, we assume that

We consider that all X k 's and Y k 's have the same size n.

There are different cases : X k = Y k and ∀k, X k = X 0 is the naive case (studied above). The case with hold out leads to different cases also :

-Greedy case: all X k 's and Y k 's are independent.

-Case with pairing:

Case of greedy hold-out.

-consider the case of an output y independent of the input x, and P (y = 1) =

k * is therefore a Poisson law with parameter 1/2 n . Its expectation is TODO and its standard deviation is TODO -therefore, almost surely, k * → ∞ as n → ∞. This is shown with one distribution, which does not depend upon the number of examples. This happens whereas an optimal function lies in F 0 .

Case of hold-out with pairing.

-

with v minimal realizing this condition.

-Consider A = {a 1 , . . . , a V }, a set of points shattered by F v .

-Consider a distribution of examples with x uniform on A and y independent of x with P (y = 1) = P (y = 0) = 1 2 . -Consider PX the empirical distribution associated to X and PY the empirical distribution associated to Y .

-There is at least one function on A which does not belong in F k-1 .

-With probability at least (1 -P (E Y ))/2 V , this function is optimal for L(., Y 0 ).

-With probability at least (1 -P (E X ))/2 V , f k is equal to this function.

-Combining the two probabilities above, as the events are independent, we see that with probability at least p

-this implies the first result : P (k * ≥ v) does not go to 0, whereas a function in F 0 is optimal. -Now, let's consider that we can change the distribution as n moves.

-For n sufficiently large, choose v maximal such that p(v, n) =≥ 1/n and F v has VC-dimension greater than the VC-dimension of F v-1 . Consider the distribution associated to v as above (uniform on A, a set of shattered point).

We have therefore shown, with a distribution dependent on n, that k * → ∞. And for a distribution that does not depend upon n, that P (k * < v) is lower bounded. In both cases, an optimal function lies in F 0 .

We now turn our attention to the case of cross-validation. We formalize N-crossvalidation as follows :

Greedy cross-validation could be considered as in the case of hold out above. This leads to the same result (for some distribution, k * → ∞). We therefore only consider cross-validation with pairing : X i k = X i We only consider cross-validation as a method for computing k * , and not for computing the classifier. We note Pi the empirical law associated to X i . We consider A a set of points shattered by F v , |A| = V , A not shattered by F v-1 . We consider f ∈ F v realizing a dichotomy of A that is not realized by F v-1 . We define E i the event {∀a ∈ A; Pi (y = f (a)|x = a) > 1 2 }. We assume that the distribution of examples is, for x, uniform on A, and for y, independently of x, uniform on {0, 1}. The probability of E i goes to

We therefore have the following result : Theorem : one can not avoid bloat with only hold-out or cross-validation. Consider greedy hold-out, hold out with pairing and cross-validation with pairing. Then, -for some well-chosen distribution of examples, greedy hold-out almost surely leads to k * → ∞ whereas an optimal function lies in F 0 . -whatever may be V = V C -dimension(F v ), for some well-chosen distribution, hold-out with pairing almost surely leads to k * > V infinitely often whereas an optimal function lies in F 0 . -whatever may be V = V C -dimension(F v ), for some well-chosen distribution, cross-validation with pairing almost surely leads to k * > V infinitely often whereas an optimal function lies in F 0 .

Is time-complexity required ?

Consider any learning algorithm working on a sequence of i.i.d examples (x 1 , y 1 ), . . . , (x n , y n ) and outputting a program. We formalize as follows the fact that this algorithm does not take into account any form of time-complexity but only the size of programs : If the learning program outputs P , then there is not program P ′ with the same length as P that has a better empirical error rate.

We show in the sequel that such a learning program can not verify convergence rates as shown in theorem 6, i.e. a guaranteed convergence rate in O(1/ √ n) when an optimal function has bounded complexity. In the sequel, we assume that the reader is familiar with statistical learning theory and shattering properties ; the interested reader is referred to [START_REF] Devroye | A probabilistic theory of pattern recognition[END_REF].

The main element is that theorem C does not hold without bounded time. The following program has bounded length, only one parameter α, but generates as α ∈ R a family of functions which shatters an infinite set :

-consider x the entry in R and α ∈ R a parameter ; -if x ≤ 0 then go to FINISH.

-if α ≥ 0.5, output 1 and stop.

-output 0 and stop.

This program shifts α and x to the left until x > 1 2 . It then replies 1 if and only if α, after shift, has its first digit equal to 1. Therefore, this program can realize any dichotomy of { 1 2 , 1 4 , 1 8 , . . . }. This is exactly the definition of the fact that this set is shattered.

So, we have shown that an family of functions shattering an infinite set was included in the set of programs with bounded length. Now, consider a learning program which has a guaranteed convergence rate in a family of functions including the family of functions computed by the program above. Ie, we assume that Theorem : fitnesses without time-complexity-pressure do not ensure consistency. What ever may be the sequence a 1 , . . . , a n , . . . decreasing to 0, there's no learning program ensuring that for any distribution of examples such that P (y = f (x)) = 1 for some f with bounded length, the expectation of P (P n (x) = y) is O(a n ).

Conclusion

In this paper, we have proposed a theoretical study of two important issues in Genetic Programming known as universal consistency and code bloat. We have shown that GP trees used in symbolic regression (involving the four arithmetic operations, the exponential function, and ephemeral constants, as well as test and jump instructions) could benefit from classical results from Statistical Learning Theory (thanks to Theorem C and Lemma 1). This has led to two kinds of original outcomes : i) some results about Universal Consistency of GP, i.e. almost sure asymptotic convergence to the optimal error rate, ii) results about the bloat. Both the unavoidable structural bloat in case the ideal target function does not have a finite description, and the functional bloat, for which we prove that it can be avoided by simultaneously bounding the length of the programs with some ad hoc bound and using some parsimony pressure in the fitness function. Some negative results have been obtained, too, such as the fact though structural bloat was known to be unavoidable, functional bloat might indeed happen even when the target function does lie in the search space, but no parsimony pressure is used. Interestingly, all those results (both positive and negative) about bloat are also valid in different contexts, such as for instance that of Neural Networks (the number of neurons replaces the complexity of GP programs). Moreover, results presented here are not limited to the scope of regression problems, but may be applied to variable length representation algorithms in different contexts such as control or identification tasks. Finally, going back to the debate about the causes of bloat in practice, it is clear that our results can only partly explain the actual cause of bloat in a real GP run -and tends to give arguments to the "fitness causes bloat" explanation [START_REF] Langdon | Fitness causes bloat: Mutation[END_REF]. It might be possible to study the impact of size-preserving mechanisms (e.g. specific variation operators, like size-fair crossover [START_REF] Langdon | Size fair and homologous tree genetic programming crossovers[END_REF] or fair mutations [START_REF] Langdon | The evolution of size and shape[END_REF]) as somehow contributing to the regularization term in our final result ensuring both Universal Consistency and no-bloat.