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.
Type de document :
Rapport
[Interne] A01-R-014 || besombes01a, 2001, 7 p
Liste complète des métadonnées

https://hal.inria.fr/inria-00100690
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:49:27
Dernière modification le : jeudi 11 janvier 2018 - 06:19:48

Identifiants

  • 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〉

Partager

Métriques

Consultations de la notice

62