Optimal CollusionFree Teaching
[edit]
Proceedings of the 30th International Conference on Algorithmic Learning Theory, PMLR 98:506528, 2019.
Abstract
Formal models of learning from teachers need to respect certain criteria to avoid collusion. The most commonly accepted notion of collusionfreeness 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 $\mathcal{C}$, a parameter $M$$\mathrm{TD}(\mathcal{C})$ refers to the \emph{teaching dimension} of concept class $\mathcal{C}$ in model $M$—defined to be the number of examples required for teaching a concept, in the worst case over all concepts in $\mathcal{C}$.
This paper introduces a new model of teaching, called noclash teaching, together with the corresponding parameter $\mathrm{NCTD}(\mathcal{C})$. Noclash teaching is provably optimal in the strong sense that, given \emph{any}\/{concept} class $\mathcal{C}$ and \emph{any}\/{model} $M$ obeying Goldman and Mathias’s collusionfreeness criterion, one obtains $\mathrm{NCTD}(\mathcal{C})\le M$$\mathrm{TD}(\mathcal{C})$. We also study a corresponding notion $\mathrm{NCTD}^+$ for the case of learning from positive data only, establish useful bounds on $\mathrm{NCTD}$ and $\mathrm{NCTD}^+$, and discuss relations of these parameters to the VCdimension and to sample compression.
In addition to formulating an optimal model of collusionfree teaching,
our main results are on the computational complexity of deciding whether $\mathrm{NCTD}^+(\mathcal{C})=k$ (or $\mathrm{NCTD}(\mathcal{C})=k$) for given $\mathcal{C}$ and $k$. We show some such decision problems to be equivalent to
the existence question for certain constrained matchings in bipartite
graphs. Our NPhardness results for the latter are of independent interest in the study of constrained graph matchings.
Related Material


