PAC Learning with Simple Examples

Abstract : We define a new PAC learning model. In this model, examples are drawn according to the universal distribution m(. ¦ f) of Solomomoff-Levin, where f is the target concept. The consequence is that the simple examples of the target concept have a high probability to be provided to the learning algorithm. We prove an Occam's Razor theorem. We show that the class of poly-term DNF is learnable, and the class of k-reversible languages is learnable from positive data, in this new model.
Type de document :
Communication dans un congrès
13th Annual Symposium on Theoretical Aspects of Computer Science, STACS'96, 1996, Munich, France. Springer Verlag, 1046, pp.231--242, 1996, Lecture Notes in Computer Science
Liste complète des métadonnées

https://hal.inria.fr/inria-00538883
Contributeur : Rémi Gilleron <>
Soumis le : mardi 23 novembre 2010 - 14:48:39
Dernière modification le : jeudi 11 janvier 2018 - 06:21:19

Identifiants

  • HAL Id : inria-00538883, version 1

Collections

Citation

François Denis, Cyrille Dhalluin, Rémi Gilleron. PAC Learning with Simple Examples. 13th Annual Symposium on Theoretical Aspects of Computer Science, STACS'96, 1996, Munich, France. Springer Verlag, 1046, pp.231--242, 1996, Lecture Notes in Computer Science. 〈inria-00538883〉

Partager

Métriques

Consultations de la notice

145