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

Sylvain Gelly 1 Olivier Teytaud 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, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR7161
Abstract : 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.
Type de document :
Communication dans un congrès
Conférence d'apprentissage, 2005, Nice, France. 16 p., 2005
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00000546
Contributeur : Olivier Teytaud <>
Soumis le : lundi 24 septembre 2007 - 16:38:49
Dernière modification le : jeudi 12 avril 2018 - 01:49:44
Document(s) archivé(s) le : mardi 21 septembre 2010 - 13:59:32

Fichier

eabloat.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00000546, version 2

Collections

Citation

Sylvain Gelly, Olivier Teytaud, Nicolas Bredeche, Marc Schoenauer. Apprentissage statistique et programmation génétique: la croissance du code est-elle inévitable ?. Conférence d'apprentissage, 2005, Nice, France. 16 p., 2005. 〈inria-00000546v2〉

Partager

Métriques

Consultations de la notice

355

Téléchargements de fichiers

768