# Technical Report CS0847

 TR#: CS0847 Class: CS Title: ON SELF-DIRECTED LEARNING. Authors: S. Ben-David, N. Eiron and E. Kushilevitz PDF Not Available Abstract: We study several issues concerning the {\em self-directed} model of learning [GRS93, GS94]. In particular, we show that the mistake bound of the self-directed learner cannot be smaller than the mistake bound of the {\em on-line} learner [L88, L89] by more than a factor of $\log|X|$, where $X$ is the instance space. Concept classes which exhibit such a gap are known. In fact, we prove that such a gap exists even between the mistake bound of the self-directed learner and of a learner which is allowed to choose, off-line, the order in which the elements of $X$ will be presented to it (but not adaptively as is the case in the self-directed model); hence, showing the power of adaptiveness. We also study the relations between the VC-dimension of a concept class and its self-directed complexity. We show that for certain concept classes the self-directed complexity can be arbitrarily high, while their VC-dimension remains a fixed constant. This answers a open problem of [GS94]. Moreover, we show that there are intersection-closed'' concept classes for which the self-directed complexity is 3/2 times the VC-dimension. This disproves a conjecture of [GS94]. Copyright The 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/1995/CS/CS0847), rather than to the URL of the PDF files directly. The latter URLs may change without notice.