On Teaching and Learning Intersection-Closed Concept Classes

摘要

We consider the self-directed learning model[7] which is a variant of littlestone's mistake-bound model[9,10]. We will refute the conjecture of [8,2] that for intersection-closed concept classes, the self-directed learning complexity is related to the VC-idmension. We show that, wven under the assumption of intersection-closedness, both parameters are completerly incomparable. We furthermore investigate the structure of intersection-closed concept classes whichare difficult ot learn in the self-directed learning model. We show that such classes must contain mazimum classes.