On the necessity of Occam algorithms
R. Board, Leonard Pitt · 1990
The distribution-independent model of concept learning from examples ("PAC-learning") due to Valiant [15] is investigated.It has been shown that the existence of an Occarn algorithm for a class of concepts is a sufficient condition for the PAC-learnability of that class [2, 3].(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 that for all concept classes satisfying a natural closure property the converse is also true; the PAC-learnability of the class implies the existence of an Occam algorithm for the class.This results in a complete combinatorial characterization of the PAC-learnability of a wide variety of concept classes.