TY - GEN
T1 - On the necessity of Occam algorithms
AU - Board, Raymond
AU - Pitt, Leonard
N1 - *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 - https://www.scopus.com/pages/publications/0025111905
UR - https://www.scopus.com/pages/publications/0025111905#tab=citedBy
U2 - 10.1145/100216.100223
DO - 10.1145/100216.100223
M3 - Conference contribution
AN - SCOPUS:0025111905
SN - 0897913612
SN - 9780897913614
T3 - Proceedings of the twenty-second annual ACM symposium on Theory of Computing
SP - 54
EP - 63
BT - Proceedings of the twenty-second annual ACM symposium on Theory of Computing
PB - Publ by ACM
T2 - 22nd Annual ACM Symposium on Theory of Computing, STOC 1990
Y2 - 14 May 1990 through 16 May 1990
ER -