Computational learning theory is concerned with the complexityof machine learning problems, for instance with the question ofhow many training examples are needed for a machine toidentify a concept in a given class of possible target concepts.
This presentation focuses on the combinatorial structureof concept classes that can be learned from a small number ofexamples. When learning from randomly chosen examples, theVC-dimension is known to provide bounds on the numberof examples needed for learning. However, for previously studiedmodels of algorithmic teaching (i.e., learning from helpfulexamples), no such combinatorial parameters are known.
Our new results show that the recently introduced notion of recursiveteaching dimension (RTD) produces more natural complexitybounds for teaching. For numerous quite general cases, the RTDis upper-bounded by the VC-dimension, thus creating links betweenteaching complexity and the complexity of learning from randomexamples. The RTD further establishes new lower bounds on thequery complexity for a variety of efficient query learning models.Moreover, some of our results exhibit a remarkable connectionbetween the RTD and the size of sample compression schemes,upper bounds of which are a long-standing target in computationallearning theory. The RTD model can hence be considered as defining acombinatorial structure that characterizes learning from a smallnumber of examples.
(Joint work with Thorsten Doliwa and Hans Simon)
- SMILE in Paris