Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata
Contributor : Rémi Gilleron Connect in order to contact the contributor
Submitted on : Tuesday, November 23, 2010 - 2:48:39 PM
Last modification on : Tuesday, April 28, 2020 - 11:52:08 AM


  • HAL Id : inria-00538883, version 1



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. pp.231--242. ⟨inria-00538883⟩



Record views