Technical Report CS0562

Title: Problems in Computerized Learnability
Authors: Gyora M. Benedek
Abstract: A systematic framework for classifying, comparing and defining models of computational leamability is presented. Three parameters are considered: solidity, uniformity in the target concept and unifonnity in the distribution. Families of learnable classes are defined according to these parameters. Known families are analyzed in tenns of the new parameterization scheme and the relative strength of notions of learnability that correspond to different parameter values are investigated. Some known and some new families are characterized. Notions of 'covering' one class by another are defined and it is shown that with respect to learnability they playa role similar to the role of reductions in computational complexity; If a class is coverable by a learnable one, then, the first class is also learnable. The covering technique is applied to characterize two families of learnable concept classes and to resolve some open questions raised in [BI2] and [LMR]. The discussion is carried out in the setting of learning through randomly drawn samples and concentrates on information-theoretic complexity rather than algorithmic complexity.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1989
To the main CS technical reports page

Computer science department, Technion