### 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 language | English (US) |
---|---|

Pages (from-to) | 157-184 |

Number of pages | 28 |

Journal | Theoretical Computer Science |

Volume | 100 |

Issue number | 1 |

DOIs | |

State | Published - 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

*Theoretical Computer Science*,

*100*(1), 157-184. https://doi.org/10.1016/0304-3975(92)90367-O