On Batch Teaching Without Collusion
Authors: Shaun Fallat, David Kirkpatrick, Hans U. Simon, Abolghasem Soltani, Sandra Zilles; Volume 24, Issue 40, Pages 1-33, 2023.
Abstract
In order to prevent collusion in formal models of learning from teachers, certain criteria must be respected. Goldman and Mathias (1996) proposed the most widely accepted notion of collusion-avoidance, and several teaching models that adhere to their criterion have been studied. For a given model $M$ and concept class $\\mathcal{C}$, the parameter $M$-TD$(\\mathcal{C})$ represents the teaching dimension of the concept class $\\mathcal{C}$ in model $M$. This is defined as the minimum number of examples required to teach a concept, considering the worst-case scenario for all concepts in $\\mathcal{C}$. This paper introduces a new teaching model called no-clash teaching, along with the corresponding parameter NCTD$(\\mathcal{C})$. No-clash teaching is proven to be optimal in the sense that, for any concept class $\\mathcal{C}$ and any model $M$ that adheres to Goldman and Mathias’ collusion-avoidance criterion, NCTD$(\\mathcal{C})\\le M$-TD$(\\mathcal{C})$. We also examine a related notion called NCTD$^+$ for learning from positive data only, establish useful bounds on NCTD and NCTD$^+$, and discuss the relationship between these parameters and other complexity parameters of interest in computational learning theory. Moreover, we argue that Goldman and Mathias’ collusion-avoidance criterion may be too weak in certain settings, as it allows for certain forms of interaction between the teacher and learner that could be considered collusion in practice. Therefore, we introduce a stricter notion of collusion-avoidance and demonstrate that the well-studied notion of Preference-based Teaching is optimal among all teaching schemes that strongly avoid collusion on all finite subsets of a given concept class.
[Abstract]
[PDF][Bibliography]