Topics in computational learning theory and graph algorithms

"The distribution-independent model of concept learning from examples (""PAC-learning"") due to Valiant is investigated. It has previously 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.) It is shown here that for any class satisfying the property of closure under exception lists, the PAC-learnability of the class implies the existence of an Occam algorithm for the class. Thus the existence of randomized Occam algorithms exactly characterizes PAC-learnability for all concept classes with this property. This reveals a close relationship between PAC-learning and information compression for a wide range of interesting classes."

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2011

Author dc:creator

• Board, Raymond Acton

Contributors dc:contributor

• Pitt, Leonard

• Mathematics
• Computer Science

Statement dc:rights

• Copyright 1990 Board, Raymond Acton

Language dc:language

eng

Identifier

AAI9114177
(UMI)AAI9114177

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/23171