On Concept Classes With Low No-Clash Teaching Dimension

Soltani, Abolghasem
Journal Title
Journal ISSN
Volume Title
Faculty of Graduate Studies and Research, University of Regina

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.

A Thesis Submitted to the Faculty of Graduate Studies and Research In Partial Fulfillment of the Requirements for the Degree of Master of Science in Computer Science, University of Regina. ix, 73 p.