## Recursive Teaching Dimension, Learning Complexity, and Maximum Classes

**Abstract. **
This paper is concerned with the combinatorial structure of concept classes
that can be learned from a small number of examples. We show that the recently
introduced notion of recursive teaching dimension (RTD, reflecting the
complexity of teaching a concept class) is a relevant parameter in this context.
Comparing the RTD to self-directed learning, we establish new lower bounds on
the query complexity for a variety of query learning models and thus connect
teaching to query learning.
For many general cases, the RTD is upper-bounded by the
VC-dimension, e.g., classes of VC-dimension 1, (nested
differences of) intersection-closed classes, ``standard''
boolean function classes, and finite maximum classes. The RTD
thus is the first model to connect teaching to the VC-dimension.
The combinatorial structure defined by the RTD has a remarkable
resemblance to the structure exploited by sample compression schemes and hence
connects teaching to sample compression.
Sequences of teaching sets defining the RTD coincide with unlabeled compression
schemes both (i) resulting from Rubinstein and Rubinstein's corner-peeling and
(ii) resulting from Kuzmin and Warmuth's Tail Matching algorithm.