On the necessity of Occam algorithms

Raymond Board, Leonard Pitt

Research output: Contribution to journalArticle

Abstract

The distribution-independent model of concept learning from examples ("PAC-learning") due to Valiant (1984) 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 (Blumer 1987, 1989). (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 for many natural concept classes that the PAC-learnability of the class implies the existence of an Occam algorithm for the class. More generally, the property of closure under exception lists is defined, and it is shown that for any concept class with this property, PAC-learnability of the class is equivalent to the existence of an Occam algorithm for the class. An interpretation of these results is that for many classes, PAC-learnability is equivalent to data compression.

Original languageEnglish (US)
Pages (from-to)157-184
Number of pages28
JournalTheoretical Computer Science
Volume100
Issue number1
DOIs
StatePublished - Jun 22 1992

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

  • Cite this