PAC Learning with Simple Examples
Résumé
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.