On Batch Teaching Without Collusion

Formal models of learning from teachers need to respect certain criteria to avoid collusion. The most commonly accepted notion of collusion-avoidance was proposed by Goldman and Mathias (1996), and various teaching models obeying their criterion have been studied. For each model M and each concept class C, a parameter M-TD(C) refers to the teaching dimension of concept class C in model M-defined to be the number of examples required for teaching a concept, in the worst case over all concepts in C. This paper introduces a new model of teaching, called no-clash teaching, together with the corresponding parameter NCTD(C). No-clash teaching is provably optimal in the strong sense that, given any concept class C and any model M obeying Goldman and Mathias's collusion-avoidance criterion, one obtains NCTD(C) <= M-TD(C). We also study a corresponding notion NCTD+ for the case of learning from positive data only, establish useful bounds on NCTD and NCTD+, and discuss relations of these parameters to other complexity parameters of interest in computational learning theory. We further argue that Goldman and Mathias's collusion-avoidance criterion may in some set-tings be too weak in that it admits certain forms of interaction between teacher and learner that could be considered collusion in practice. Therefore, we introduce a strictly stronger notion of collusion-avoidance and demonstrate that the well-studied notion of Preference-based Teaching is optimal among all teaching schemes that are strongly collusion-avoiding on all finite subsets of a given concept class.

Automated summary

This paper introduces a new teaching model called no-clash teaching and proves its optimality in the strong sense. It also studies the corresponding concept for learning from positive data only and discusses the relationship between these parameters and other complexity parameters in computational learning theory. Furthermore, a stricter notion of collusion-avoidance is introduced, and it is demonstrated that preference-based teaching is the optimal choice among all teaching schemes that strongly avoid collusion.