Skip to Main content Skip to Navigation
Reports

Une théorie informative de l'apprentissage

Jérôme Besombes 1 Jean-Yves Marion 1
1 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Résumé : La théorie d'apprentissage à la limite à partir d'exemples positifs introduite par E. M. Gold et développée par D. Angluin détermine des classes de langages apprenables restreintes. Ainsi, l'existence d'un point limite dans une classe implique la non-apprenabilité de celle-ci. Or un tel point limite existe dans la plupart des classes usuelles (langages réguliers, ensembles de langages finis comportant un unique ensemble infini,...). Nous proposons donc une extension de la définition d'apprenabilité, extension basée sur la théorie de l'information de Kolmogorov. Nous nous intéressons à la mesure de la complexité d'un langage connaissant un nombre fini d'éléments de ce langage. Une classe donnée est apprenable si cette complexité, pour tout langage de la classe, est bornée par un entier indépendant du langage.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00100690
Contributor : Publications Loria <>
Submitted on : Tuesday, September 26, 2006 - 2:49:27 PM
Last modification on : Tuesday, May 5, 2020 - 5:02:12 PM

Identifiers

  • HAL Id : inria-00100690, version 1

Collections

Citation

Jérôme Besombes, Jean-Yves Marion. Une théorie informative de l'apprentissage. [Interne] A01-R-014 || besombes01a, 2001, 7 p. ⟨inria-00100690⟩

Share

Metrics

Record views

98