On a Combinatorial Problem Arising in Machine Teaching

Joakim Sunde, Brigt Håvardstun, Jan Kratochvı́l, Jan Arne Telle
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:47305-47313, 2024.

Abstract

We study a model of machine teaching where the teacher mapping is constructed from a size function on both concepts and examples. The main question in machine teaching is the minimum number of examples needed for any concept, the so-called teaching dimension. A recent paper (Ferri et al., 2024) conjectured that the worst case for this model, as a function of the size of the concept class, occurs when the consistency matrix contains the binary representations of numbers from zero and up. In this paper we prove their conjecture. The result can be seen as a generalization of a theorem resolving the edge isoperimetry problem for hypercubes (Hart, 1976), and our proof is based on a lemma of (Graham, 1970).

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-sunde24a, title = {On a Combinatorial Problem Arising in Machine Teaching}, author = {Sunde, Joakim and H{\aa}vardstun, Brigt and Kratochv\'{\i}l, Jan and Telle, Jan Arne}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {47305--47313}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/sunde24a/sunde24a.pdf}, url = {https://proceedings.mlr.press/v235/sunde24a.html}, abstract = {We study a model of machine teaching where the teacher mapping is constructed from a size function on both concepts and examples. The main question in machine teaching is the minimum number of examples needed for any concept, the so-called teaching dimension. A recent paper (Ferri et al., 2024) conjectured that the worst case for this model, as a function of the size of the concept class, occurs when the consistency matrix contains the binary representations of numbers from zero and up. In this paper we prove their conjecture. The result can be seen as a generalization of a theorem resolving the edge isoperimetry problem for hypercubes (Hart, 1976), and our proof is based on a lemma of (Graham, 1970).} }
Endnote
%0 Conference Paper %T On a Combinatorial Problem Arising in Machine Teaching %A Joakim Sunde %A Brigt Håvardstun %A Jan Kratochvı́l %A Jan Arne Telle %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-sunde24a %I PMLR %P 47305--47313 %U https://proceedings.mlr.press/v235/sunde24a.html %V 235 %X We study a model of machine teaching where the teacher mapping is constructed from a size function on both concepts and examples. The main question in machine teaching is the minimum number of examples needed for any concept, the so-called teaching dimension. A recent paper (Ferri et al., 2024) conjectured that the worst case for this model, as a function of the size of the concept class, occurs when the consistency matrix contains the binary representations of numbers from zero and up. In this paper we prove their conjecture. The result can be seen as a generalization of a theorem resolving the edge isoperimetry problem for hypercubes (Hart, 1976), and our proof is based on a lemma of (Graham, 1970).
APA
Sunde, J., Håvardstun, B., Kratochvı́l, J. & Telle, J.A.. (2024). On a Combinatorial Problem Arising in Machine Teaching. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:47305-47313 Available from https://proceedings.mlr.press/v235/sunde24a.html.

Related Material