Technical Report CIS9110

TR#:CIS9110
Class:CIS
Title: DOMINATING DISTRIBUTIONS AND LEARNABILITY
Authors: G.Y. Benedek and A. Itai
PDFNot Available
Abstract: We consider the PAC-learning model first introduced by Valiant, but assume that the distribution is known to the student. The problem addressed here is characterizing when learnability with respect to distribution $D_1$ implies learnability with respect to distribution $D_2$. The answer to the above question depends on the learnability model. If the number of examples need not be bounded by a polynomial, it is sufficient to require that all sets which have zero probability with respect to $D_2$ have zero probability with respect to $D_1$. If the number of examples is required to be polynomial, then the probability with respect to $D_2$ must be bounded by a multiplicative constant from that of $D_1$. More stringent conditions must hold if we insist that every hypothesis consistent with the examples be close to the target. Finally, we address the learnability properties of classes of distributions.
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 (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1991/CIS/CIS9110), rather than to the URL of the PDF or PS files directly. The latter URLs may change without notice.

To the list of the CIS technical reports of 1991
To the main CS technical reports page

Computer science department, Technion