Penalty Functions for Genetic Programming Algorithms

Penalty Functions for Genetic Programming Algorithms José L. Montaña,1 César L. Alonso,2 Cruz E. Borges,1 and Javier de la Dehesa.1 [email protected], [email protected], [email protected], [email protected]. Dept. Matemáticas, Estadística y Computación1

Centro de Inteligencia Artificial2

11th ICCSA 2011, 20-23 June 2011, Santander, Spain.

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.

Talk Layout

C.E. Borges

1

The Symbolic Regression Problem

2

Model Selection

3

Experimental Results

Penalty Functions for Genetic Programming Algorithms

2/12

Talk Layout

C.E. Borges

1


2

Model Selection

3



2/12

Talk Layout

C.E. Borges

1


2

Model Selection

3



2/12

Regression Problems. Regressions Problems. Given a set of points and a space of functions, find the best function that fits the set of points. f (x)

f (x)

x x1 x2 x3 4

x0

x5

x7

x8 x x10 9

x6

x C.E. Borges


3/12

Regression Problems. Regressions Problems. Given a set of points and a space of functions, find the best function that fits the set of points. f (x)

g(x)

x C.E. Borges


3/12

How we solve it?

When the Function Set. . . is Known: Interpolation, Least Squares. is Unknown: Symbolic Regression.

C.E. Borges


4/12

How we solve it?


C.E. Borges


4/12

How we solve it?


C.E. Borges


4/12

Symbolic Regression Problems

Symbolic Regression. Looks for a symbolic expression of the regressor. Looks for a computer program that evaluate the regressor. Genetic Programming.

C.E. Borges


5/12



C.E. Borges


5/12



C.E. Borges


5/12

Genetic Programming with Trees.

Figure: Example of a computer program, encoded as a tree, that evaluate the function f := x 4 + x 3 + x 2 + x.

f ≡

+ +

+ ∗ ∗

x x

∗ x

∗

x x

C.E. Borges

∗ x

x

∗ x


x

x

6/12

Model Selection: Vapnik–Chervonenkis Dimension.

Ockham’s Razor. The simplest explanation is most likely the correct one.

Idea. Use a model fitness according to their empirical error plus a penalization based on their complexity.

Classification capacity. Cardinality of the largest set of points that the model can shatter.

C.E. Borges


7/12





C.E. Borges


7/12





C.E. Borges


7/12





C.E. Borges


7/12





C.E. Borges


7/12





Theorem. The Vapnik–Chervonenkis Dimension of a GP-tree is polynomial in the non-scalar height, the number of analytic algebraic nodes and the number of constants and variables. C.E. Borges


7/12

Experimental Results i.

Experimental Setup. Random polynomials of bounded degree. 300 repetitions: 30 learning points with noise. 200 validation points without noise.

Boxplots of the MSE over the validation set of points. Hypothesis Testing.

C.E. Borges


8/12




C.E. Borges


8/12




C.E. Borges


8/12




C.E. Borges


8/12




C.E. Borges


8/12




C.E. Borges


8/12

Experimental Results ii.

Regularization Techniques Used MSE (no regularization). AIC. BIC. SRM.

C.E. Borges


9/12



C.E. Borges


9/12



C.E. Borges


9/12



C.E. Borges


9/12

Experimental Results iii.

0.0

0.1

0.2

0.3

0.4

0.5

PR n [X]

MSE C.E. Borges

AIC

BIC

SRM


10/12

Experimental Results iv.

Hypothesis Testing PR n [X ] MSE AIC BIC SRM

C.E. Borges

MSE 1 8,81 · 10−3 5,82 · 10−3 3,44 · 10−3

AIC 0,94 1 0,91 7,02 · 10−2

BIC 0,93 0,73 1 7,16 · 10−2


SRM 1 0,8 0,94 1

11/12

Penalty Functions for Genetic Programming Algorithms José L. Montaña,1 César L. Alonso,2 Cruz E. Borges,1 and Javier de la Dehesa.1 [email protected], [email protected], [email protected], [email protected]. Dept. Matemáticas, Estadística y Computación1

Centro de Inteligencia Artificial2

11th ICCSA 2011, 20-23 June 2011, Santander, Spain.

This work is licensed under the Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.