PAC learning under helpful distributions

Abstract : A PAC model under helpful distributions is introduced. A teacher associates a teaching set with each target concept and we only consider distributions such that each example in the teaching set has a non-zero weight. The performance of a learning algorithm depends on the probabilities of the examples in this teaching set. In this model, an Occam's razor theorem and its converse are proved. The class of decision lists is proved PAC learnable under helpful distributions. A PAC learning model with simple teacher (simplicity is based on program-size complexity) is also defined and the model is compared with other models of teaching.
Type de document :
Communication dans un congrès
Proceedings of the 8th International Conference on Algorithmic Learning Theory, ALT'97), 1997, Sendai, Japan. Springer Verlag, 1316, pp.132--145, 1997, Lecture Notes in Artificial Intelligence
Liste complète des métadonnées

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

Identifiants

  • HAL Id : inria-00538884, version 1

Collections

Citation

François Denis, Rémi Gilleron. PAC learning under helpful distributions. Proceedings of the 8th International Conference on Algorithmic Learning Theory, ALT'97), 1997, Sendai, Japan. Springer Verlag, 1316, pp.132--145, 1997, Lecture Notes in Artificial Intelligence. 〈inria-00538884〉

Partager

Métriques

Consultations de la notice

56