Technical Report CS0847

Authors: S. Ben-David, N. Eiron and E. Kushilevitz
PDFNot 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].
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 1995
To the main CS technical reports page

Computer science department, Technion