RTD-Conjecture and Concept Classes Induced by Graphs
Hans Ulrich Simon · 2025
Read RTD-Conjecture and Concept Classes Induced by Graphs by Hans Ulrich Simon (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-09453.txt.
Introduction
Hans Simon presents a 2025 paper in learning theory about how many examples a teacher needs to teach a concept. A well-known guess says the recursive teaching dimension of any finite concept class is at most a fixed multiple of its VC-dimension, a standard measure of class complexity. The guess has resisted proof in general.
Simon confirms it for two rich families of classes built from graphs. In the first, each concept is the set of neighbors of one vertex, a star; in the second, concepts are connected sets of vertices. For both families he shows the teaching dimension either equals the VC-dimension exactly or falls short by one. The clean result strengthens the case for the general conjecture and ties teaching cost tightly to class complexity.
Catalog record
| CREATOR | Hans Ulrich Simon |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 49 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-09453
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
RTD-Conjecture and Concept Classes Induced by Graphs Hans Ulrich Simon Abstract It is conjectured in [ 12 ] that the recursive teaching dimension of any finite concept class is upper-bounded by the VC-dimension of this class times a universal constant. In this paper, we confirm this conjecture for two rich families of concept classes where each class is induced by some graph G G . For each G G , we consider the class whose concepts represent stars in G G as well as the class whose concepts represent connected sets in G G . We show that, for concept classes of this kind, the recursive teaching dimension either equals the VC-dimension or is less by 1 1 . 1 Introduction Teaching models explore the opportunities offered by learning from carefully chosen examples (as opposed to random examples). Let {\mathcal{M}} be a model of teaching and let {\mathcal{C}} be a class of concepts. The {\mathcal{M}} -teaching dimension of {\mathcal{C}} is defined as the smallest number d such that every concept in {\mathcal{C}} can be inferred from d (appropriately chosen) examples in accordance with the rules of the model {\mathcal{M}} . In the original teaching model, as introduced by Shinohara and Miyano [ 11 ] resp. by Goldman and Kearns [ 5 ] , the examples used for teaching a concept C must distinguish C from any other concept in the underlying concept class. This strong requirement, however, leads to intolerably large teaching dimensions even for very simple concept classes. The model of recursive teaching 1 1 1 See Section 2.3 for a definition. had been suggested in [ 15 ] as an alternative (among others) to the original model. The corresponding teaching dimension is called the RT-dimension and denoted by \mathrm{RTD} . As demonstrated in [ 3 ] and [ 8 ] , the RT-dimension of a concept class {\mathcal{C}} is often closely related to the VC-dimension 2 2 2 The VC-dimension, first introduced in the pioneering work of Vapnik and Chervonenkis [ 13 ] , plays a central role in the theory of learning from random examples. of {\mathcal{C}} . The latter will be denoted by \mathrm{VCD}({\mathcal{C}}) in the sequel. The following is among the main open problems in connection with teaching: RTD-Conjecture: Is there a universal constant c>0 such that, for each finite concept class {\mathcal{C}} , we have that \mathrm{RTD}({\mathcal{C}})\leq c\cdot\mathrm{VCD}({\mathcal{C}}) ? It is known [ 6 ] that \mathrm{RTD}({\mathcal{C}})=O\left(\mathrm{VCD}({\mathcal{C}})^{2}\right) . It is furthermore known [ 1 ] that there exists a concept class {\mathcal{C}} such that \mathrm{RTD}({\mathcal{C}})\geq\frac{5}{3}\cdot\mathrm{VCD}({\mathcal{C}}) . We also briefly would like to mention that the RTD-conjecture is related to the well-known Sample-Compression conjecture of Warmuth [ 14 ] : • There is a one-to-one correspondence between so-called repetition-free teaching sets in the RT-model and unlabeled sample compression schemes having the acyclic non-clashing property. See Lemma 27 in [ 3 ] for technical details. • See also [ 2 ] for a connection between recursive teaching and so-called order-compression schemes. The latter are special sample-compression schemes. We cannot go into detail at this point. But it seems to be fair to say that progress with the RTD-conjecture is likely to produce progress with the Sample-Compression conjeture, and vice versa. Up to date, it is not known whether the RTD-conjecture can be confirmed in general. We will show in this paper that it can be confirmed in a very strong sense for two rich families of concept classes where each class is induced by some graph G . We consider classes whose concepts represent stars in G as well as classes whose concepts represent connected sets in G . 3 3 3 The VC-dimension of these classes has been studied before in [ 7 ] . We show that, for concept classes {\mathcal{C}} of this kind, it holds that \mathrm{VCD}({\mathcal{C}})-1\leq\mathrm{RTD}({\mathcal{C}})\leq\mathrm{VCD}({\mathcal{C}})\kern 5.0pt. This paper is structured as follows. In Section 2 , we fix some notation and call to mind some basic definitions (including the definition of various teaching models). The main results on graph-induced concept classes are stated and proved in Section 3 . The paper is closed by mentioning some directions for future research. 2 Definitions, Notations and Facts The powerset of a set M is denoted as 2^{M} . For integers i\leq j , we define [i:j]=\{i,\ldots,j\} , i.e., [i:j] denotes the interval of integers that range from i to j . Moreover, we set [n]=[1:n] . 2.1 Graphs and Subgraphs We first fix some notation for special graphs. The complete graph with n vertices is denoted by K_{n} . Let P_{n} denote a path of length n . Similarly, let C_{n} denote a cycle of length n . Definition 2.1 (Open and Closed Neighborhood) . Let G=(V,E) be a graph and let x\in V be a vertex in G . Then N_{G}^{o}(x)=\{y|\{x,y\}\in E\} denotes the set of vertices that are adjacent to x in G . N_{G}^{o}(x) is said to be the open neighborhood of x in G whereas N_{G}(x)=N_{G}^{o}(x)\cup\{x\} is called the closed neighborhood of x in G . More generally, for X\subseteq V , we define N_{G}(X)=\cup_{x\in X}N_{G}(x) and N_{G}^{o}(X)=N_{G}(X)\setminus X . Remark 2.2 . For all (not necessarily distinct) vertices x,y\in V , we have that N_{G}^{o}(x)\neq N_{G}(y) . Proof. Assume for sake of contradiction that N_{G}^{o}(x)=N_{G}(y) . Since y\in N_{G}(y) , we also have y\in N_{G}^{o}(x) . Thus y is adjacent to x . On the other hand, since x\notin N_{G}^{o}(x) , we have that x\notin N_{G}(y) . Thus x is not adjacent to y . We arrived at a contradiction. ∎ Definition 2.3 (Subgraph-Relation) . Let G=(V,E) be a graph. A graph G^{\prime}=(V^{\prime},E^{\prime}) is a subgraph of G , which is denoted as G^{\prime}\leq G , if V^{\prime}\subseteq V and E^{\prime}\leq E . By \langle V^{\prime}\rangle_{G} we denote the subgraph of G=(V,E) that is spanned by V^{\prime}\subseteq V , i.e., it contains all edges of E whose endpoints are in V^{\prime} . 2.2 Concept Classes and VC-Dimension As usual a concept over domain {\mathcal{X}} is a function of the form C:{\mathcal{X}}\rightarrow\{+,-\} or, equivalently 4 4 4 C can be identified with \{x\in{\mathcal{X}}:C(x)=+\} , a subset of {\mathcal{X}} . The elements of {\mathcal{X}} are called instances . If C(x)=b\in\{+,-\} , then C is said to assign label b to instance x . A set whose elements are concepts over domain {\mathcal{X}} is referred to as a concept class over {\mathcal{X}} . A pair (x,b)\in{\mathcal{X}}\times\{+,-\} is called a (positive resp. negative) example. A collection S\subseteq{\mathcal{X}}\times\{+,-\} of examples is called a sample . A concept is said to be consistent with S if C(x)=b for for all (x,b)\in S . The version space induced by S is defined as the set of all concepts in {\mathcal{C}} that are consistent with S . General Assumption: We will assume throughout the paper that {\mathcal{X}} is finite. For the reader’s convenience, we now call to mind the definition of the VC-dimension: Definition 2.4 (Shattered Sets and VC-dimension [ 13 ] ) . Suppose that {\mathcal{C}} is a concept class over domain {\mathcal{X}} . A set S\subseteq{\mathcal{X}} is said to be shattered by {\mathcal{C}} if, for any S^{\prime}\subseteq S , there exists a concept C\in{\mathcal{C}} such that S\cap C=S^{\prime} . The size of the largest