# Item

ITEM ACTIONSEXPORT

Released

Journal Article

#### Optimal Collusion-Free Teaching

##### External Resource

No external resources are shared

##### Fulltext (restricted access)

There are currently no full texts shared for your IP range.

##### Fulltext (public)

arXiv:1903.04012.pdf

(Preprint), 739KB

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

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

##### Abstract

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.

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.