On the necessity of Occam algorithms

Raymond Board, Leonard Pitt

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProc 22nd Annu ACM Symp Theory Comput
PublisherPubl by ACM
Pages54-63
Number of pages10
ISBN (Print)0897913612, 9780897913614
DOIs
StatePublished - 1990
EventProceedings of the 22nd Annual ACM Symposium on Theory of Computing - Baltimore, MD, USA
Duration: May 14 1990May 16 1990

Publication series

NameProc 22nd Annu ACM Symp Theory Comput

Other

OtherProceedings of the 22nd Annual ACM Symposium on Theory of Computing
CityBaltimore, MD, USA
Period5/14/905/16/90

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint

Dive into the research topics of 'On the necessity of Occam algorithms'. Together they form a unique fingerprint.

Cite this