Abstract
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-dimension. We show that, even under the assumption of intersection-closedness, both parameters are completely incomparable.
We furthermore investigate the structure of intersection-closed concept classes which are difficult to learn in the self-directed learning model. We show that such classes must contain maximum classes.
We consider the teacher-directed learning model [5] in the worst, best and average case performance. While the teaching complexity in the worst case is incomparable to the VC-dimension, large concept classes (e.g. balls) are bounded by VC-dimension with respect to the average case. We show that the teaching complexity in the best case is bounded by the self-directed learning complexity. It is also bounded by the VCdimension, if the concept class is intersection-closed. This does not hold for arbitrary concept classes. We find examples which substantiate this gap.
The author likes to thank Hans Ulrich Simon, Norbert Klasner, Michael Schmitt, Andreas Birkendorf and unidentified referees for helpful hints and discussions. The author gratefully acknowledges the support of the German-Israeli Foundation for Scientific Research and Development (grant I-403-001.06/95).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Ben-David and N. Eiron. Self-directed learning and its relation to the vc dimension and to teacher-directed learning. to appear, 1998.
S. Ben-David, N. Eiron, and E. Kushilevitz. On self-directed learning. Proceedings of the Eighth Annual Conference on Computational Learning Theory, 8:136–143, 1995.
S. Floyd. On space-bounded learning and the vapnik-chervonenkis dimension. PhD thesis, International Computer Science Institute Technicak Report TR-89061, Berkeley, California, 1989.
S. Floyd and M. Warmuth. Sample compression, learnability, and the vapnikchervonenkis dimension. Machine Learning, 21:269–304, 1995.
S.A. Goldman and M.J. Kearns. On the complexity of teaching. Journal of Computer and System Sciences, 50:20–31, 1995.
S.A. Goldman and D.H. Mathias. Teaching a smarter learner. Journal of Com-puter and System Sciences, 52(20):255–267, 1996.
S.A. Goldman, R. L. Rivest, and R.E. Schapire. Learning binary relations and total orders. SIAM Journal of Computation, 22(5):1006–1034, 1993.
S.A. Goldman and R.H. Sloan. The power of self-directed learning. Machine Learning, 14:271–294, 1994.
N. Littlestone. Learning with irrelevant attributes abound: A new linear-threshold algorithm. Machine Learning, 2:285–318, 1988.
N. Littlestone. Mistake bound and logarithmic linear-threshold learning algorithms. PhD Thesis, U.C. Santa Cruz, March 1989.
B.K. Natarajan. Probabaly approximate learning of sets and functions. SIAM Journal of Computing, 20(2):328–351, 1991.
R.L. Rivest and Y.L. Yin. Being taught can be faster than asking questions. Proceedings of the Eighth Annual Conference on Computational Learning Theory, 8:144–151, 1995.
N. Sauer. On the density of families of sets. Journal of Combinatorial Theory, 13:145–147, 1972.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kuhlmann, C. (1999). On Teaching and Learning Intersection-Closed Concept Classes. In: Fischer, P., Simon, H.U. (eds) Computational Learning Theory. EuroCOLT 1999. Lecture Notes in Computer Science(), vol 1572. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49097-3_14
Download citation
DOI: https://doi.org/10.1007/3-540-49097-3_14
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65701-9
Online ISBN: 978-3-540-49097-5
eBook Packages: Springer Book Archive