On a Combinatorial Problem Arising in Machine Teaching
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929238103293952 |
|---|---|
| author | Håvardstun, Brigt Kratochvíl, Jan Sunde, Joakim Telle, Jan Arne |
| author_facet | Håvardstun, Brigt Kratochvíl, Jan Sunde, Joakim Telle, Jan Arne |
| contents | 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 [7] 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 [12], and our proof is based on a lemma of [10]. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_04907 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | On a Combinatorial Problem Arising in Machine Teaching Håvardstun, Brigt Kratochvíl, Jan Sunde, Joakim Telle, Jan Arne Combinatorics Machine Learning G.2.1 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 [7] 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 [12], and our proof is based on a lemma of [10]. |
| title | On a Combinatorial Problem Arising in Machine Teaching |
| topic | Combinatorics Machine Learning G.2.1 |
| url | https://arxiv.org/abs/2402.04907 |