On the necessity of Occam algorithms

AbstractThe distribution-independent model of concept learning from examples (“PAC-learning”) due to Valiant (1984) is investigated. It has been shown that the existence of an Occam algorithm for a class of concepts is a sufficient condition for the PAC-learnability of that class (Blumer 1987, 1989). (An Occam algorithm is a randomized polynomial-time algorithm that, when given as input a sample of strings of some unknown concept to be learned, outputs a small description of a concept that is consistent with the sample.) In this paper it is shown for many natural concept classes that the PAC-learnability of the class implies the existence of an Occam algorithm for the class. More generally, the property of closure under exception lists is defined, and it is shown that for any concept class with this property, PAC-learnability of the class is equivalent to the existence of an Occam algorithm for the class. An interpretation of these results is that for many classes, PAC-learnability is equivalent to data compression