Finite Biased Teaching with Infinite Concept Classes
This work addresses the challenge of teaching complex concepts to machines, with implications for machine learning theory, though it is incremental in nature.
The paper tackles the problem of teaching infinite concept classes like Turing machines and finite-state machines by analyzing the effects of learning and sampling biases, deriving bounds for the biased teaching dimension based on complexity measures and identifying conditions for finite expected dimensions.
We investigate the teaching of infinite concept classes through the effect of the learning bias (which is used by the learner to prefer some concepts over others and by the teacher to devise the teaching examples) and the sampling bias (which determines how the concepts are sampled from the class). We analyse two important classes: Turing machines and finite-state machines. We derive bounds for the biased teaching dimension when the learning bias is derived from a complexity measure (Kolmogorov complexity and minimal number of states respectively) and analyse the sampling distributions that lead to finite expected biased teaching dimensions. We highlight the existing trade-off between the bound and the representativeness of the sample, and its implications for the understanding of what teaching rich concepts to machines entails.