On self-directed learning
We study several issues concerning the selfdmected model of learning [G RS93, GS94). In particular, we show that the mistake bound of the self-directed learner cannot be smaller than the mistake bound of the on-line learner [L88, L89] by more than a factor of log IX], 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 VCdimension of a concept class and its self-directed complexity. We show that for certain concept classes the seIf-directed comp~exity can be arbitrarily high, while their VC-dimension remains a fixed constant. This answers an 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]. *Computer Science Department, Technion, Haifa 32000, Israel. shai@cs.technion .ac.il t Computer Science Department, Tecllnion, Haifa 32000, Israel. t Computer Science Department, Technion, Haifa 32000, Israel. eyalkfdcs.teclmi on.ac.il Permission to m~ke digital/hard copies of all or port of this material without fee is granted provided that the copies are not nmde or distributed for urotit or commercial advantage, the ACM copyright/server not~ce, the title of the publication and its date app-e’ar,-and notice is given that copyright is by permission of the Association for Computing Machinery> Inc. (ACM). To copy otherwise, to republish,to post on servers or to We also prove a lower bound on the product of the number of querves made by a selfdirected algorithm and the number of mistakes it makes. This lower bound indicates that lowering the mistake bound of a self-directed algorithm results in an increase of the number of queries it has to go through.