Help Privacy Policy Disclaimer
  Advanced SearchBrowse




Journal Article

Optimal Collusion-Free Teaching


Simon,  Hans U.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

(Preprint), 739KB

Supplementary Material (public)
There is no public supplementary material available

Kirkpatrick, D., Simon, H. U., & Zilles, S. (in press). Optimal Collusion-Free Teaching. Journal of Machine Learning Research.

Cite as: https://hdl.handle.net/21.11116/0000-000C-332F-7
Formal models of learning from teachers need to respect certain criteria to
avoid collusion. The most commonly accepted notion of collusion-freeness 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
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 no-clash teaching,
together with the corresponding parameter $\mathrm{NCTD}(\mathcal{C})$.
No-clash teaching is provably optimal in the strong sense that, given any
concept class $\mathcal{C}$ and any model $M$ obeying Goldman and Mathias's
collusion-freeness 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 VC-dimension and to sample compression.
In addition to formulating an optimal model of collusion-free 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 NP-hardness results for the latter are of independent interest in the study
of constrained graph matchings.