A Statistical Learning Theory Approach of Bloat

Olivier Teytaud 1 Sylvain Gelly 1 Nicolas Bredeche 1 Marc Schoenauer 1
1 TANC - Algorithmic number theory for cryptology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], Inria Saclay - Ile de France
Abstract : Code bloat, the excessive increase of code size, is an important is- sue in Genetic Programming (GP). This paper proposes a theoreti- cal analysis of 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 lies in the search space or not. Then, important mathematical results are proved using classical results from Sta- tistical Learning. Namely, the Vapnik-Cervonenkis dimension of programs is computed, and further results from Statistical Learn- ing allow to prove that a parsimonious fitness ensures Universal Consistency (the solution minimizing the empirical error does con- verge to the best possible error when the number of samples goes to infinity). However, it is proved that the standard method consisting in choosing a maximal program size depending on the number of samples might still result in programs of infinitely increasing size whith their accuracy; a more complicated modification of the fit- ness is proposed that theoretically avoids unnecessary bloat while nevertheless preserving the Universal Consistency.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/inria-00000549
Contributor : Sylvain Gelly <>
Submitted on : Wednesday, November 2, 2005 - 11:05:13 AM
Last modification on : Wednesday, March 27, 2019 - 4:41:29 PM
Long-term archiving on: Tuesday, September 11, 2012 - 12:40:44 PM

Identifiers

  • HAL Id : inria-00000549, version 1

Collections

Citation

Olivier Teytaud, Sylvain Gelly, Nicolas Bredeche, Marc Schoenauer. A Statistical Learning Theory Approach of Bloat. Genetic and Evolutionary Computation Conference, Jun 2005, Washington D.C. USA. ⟨inria-00000549⟩

Share

Metrics

Record views

361

Files downloads

870