Technical Report CS0550

Title: Tile Passive Student is Really Weaker (A Parametrization Scheme for Classifying Models of Learnability)
Authors: S. Ben-David, G.M. Benedek and Y. Mansour
Abstract: We present a systematic framework: for classifying, comparing and defining models of computadonalleamabilily. Apart from the obvious 'uniformity' parameters we present a novel 'passiveness' notion that captures the difference between 'Guess and Test' learning algorithms and leamability notions for which consistency with the samples guarantees success. We analyze known models in terms of our new parameterization scheme and investigate the relative strength of notions of leamability that correspond to different parameter values. In the last secdon we consider 'proximity' between concept classes. We define notions of 'covering' one class by another and show that with respect to leamability they play a role similar to the role of reductions in computational complexity; If a class is covcrable by a learnable one, then, the farst class too is leamable. We apply the covering technique to resolve some open questions raised in [BI2] and [LMR]. The discussion is carried out in the context of information-theoretic complexity rather than algorithmic complexity. For the sake of concreteness we have also limited the discussion to the setting of learning through randomly drawn samples. Nevertheless, our parameters, and consequently our analysis, are relevant to a much wider variety of learning situations.
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