Document Type

Technical Report

Publication Date

1991-12-01

Filename

WUCS-91-37.pdf

Technical Report Number

WUCS-91-37

Abstract

This paper studies self-directed learning, a variant of the on-line learning model in which the learner selects the presentation order for the instances. We give tight bounds on the complexity of self-directed learning for the concept classes of monomials, k-term DNF formulas, and orthogonal rectangles in {0, 1, . . ., n-1}d. These results demonstrate that the number of mistakes under self-directed learning can be surprisingly small. We then prove that the model of self-directed learning is more powerful than all other commonly unused on-line and query learning models. Next we explore the relationship between the complexity of self-directed learning and the Vapnik-Chervonenkis dimension. Finally we explore a relationship between Mitchell's version space algorithm and the existence of self-directed learning algorithms that make few mistakes.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7BZ64CV

Download

Share

COinS