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 -