TY - GEN

T1 - On the necessity of Occam algorithms

AU - Board, Raymond

AU - Pitt, Leonard

N1 - Funding Information:
*This research was completed while the first author was at the Department of Computer Science, University of Illinois at Urbana-Champaign, supported in part by NSF grant IRI-8809570. The second author was supported by NSF grant IRI-8809570 and by the Department of Computer Science, University of Illinois at Urbana-Champaign.

PY - 1990

Y1 - 1990

N2 - The distribution-independent model of concept learning from examples ('PAC-learning') due to L.G. Valiant 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. (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.

AB - The distribution-independent model of concept learning from examples ('PAC-learning') due to L.G. Valiant 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. (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.

UR - http://www.scopus.com/inward/record.url?scp=0025111905&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0025111905&partnerID=8YFLogxK

U2 - 10.1145/100216.100223

DO - 10.1145/100216.100223

M3 - Conference contribution

AN - SCOPUS:0025111905

SN - 0897913612

SN - 9780897913614

T3 - Proc 22nd Annu ACM Symp Theory Comput

SP - 54

EP - 63

BT - Proc 22nd Annu ACM Symp Theory Comput

PB - Publ by ACM

T2 - Proceedings of the 22nd Annual ACM Symposium on Theory of Computing

Y2 - 14 May 1990 through 16 May 1990

ER -