On Concept Classes With Low No-Clash Teaching Dimension

Abstract

Computational Learning Theory studies the complexity of learning for various formal models of machine learning. Such models use a learning algorithm A fed with a set of labelled data for a target concept belonging to a given class of concepts, and A produces a mapping that is used to accurately predict the correct labels of unseen instances. Machine teaching is concerned with settings in which a teacher provides the learners with helpfully chosen data. Different learning constraints, such as the way a teacher and a learner interact with each other, produce a variety of teaching models for which one task is to answer the question \what is the minimum number of labelled examples required by the learning algorithm A to exactly identify any given concept C belonging to C?". In this thesis, we use combinatorics to study two well-known notions of teaching that avoid unwanted forms of collusion between the teacher and the learner, namely the recursive teaching dimension (RTD) and the no-clash teaching dimension (NCTD). We affirmatively answer the question whether there exists a concept class

for which RTD NCTD > 2 holds. Along these lines, the smallest concept class for which the equality RTD = 3 - NCTD holds is provided. Using design theory, we construct a concept class of size 16 over 8 instances that satisfies RTD = 4 and NCTD = 1. This is the largest multiplicative gap found between RTD and NCTD so far. Furthermore, by implementing a Python toolbox to compute and compare teaching complexity parameters, we succeed to generate numerous concept classes over at most five instances for which our well-known ratio is at least 3. Over 4 instances, it is shown that the smallest concept class which satisfies RTD = 3 - NCTD is unique. Over 5 instances, there are three non-equivalent concept classes of size 8, and also of size 9 for which RTD = 3 and NCTD = 1 hold. Additional concept classes of sizes 10, 12, 14, and 16 are also generated with the property RTD = 3 - NCTD. Finally, by encoding certain teaching information in the one-inclusion graph, we establish a connection between the one-inclusion graph of concept classes and the non-clash teaching complexity. We find that for the so-called shortest-path-closed concept classes with NCTD equal to 1, the corresponding one-inclusion graphs have at most one cycle, and consequently the recursive teaching dimension is at most 2.