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.