On May 15, 2013, Prof. Dr. Sandra Zilles will give a talk on "The combinatorial structure of concept classes that can be learned from a small number of examples".
Abstract:
Computational learning theory is concerned with the complexity of machine learning problems, for instance with the question of how many training examples are needed for a machine to identify a concept in a given class of possible target concepts.
This presentation focuses on the combinatorial structure of concept classes that can be learned from a small number of examples. In particular, we reveal a connection between a combinatorial parameter describing the complexity of learning from random examples (the Vapnik-Chervonenkis dimension) and a recently discovered combinatorial parameter describing the complexity of learning from "helpful" examples (the Recursive Teaching Dimension). Our results suggest that the same structural properties that make a concept class easy to learn from randomly chosen examples also make that concept class easy to learn from carefully chosen examples, and often vice versa.
This presentation summarizes joint work with Thorsten Doliwa, Rahim Samei, Pavel Semukhin, Hans Simon, and Boting Yang.