Preference-based Teaching
This work addresses the problem of teaching complexity in machine learning, particularly for infinite concept classes, by providing a more practical framework than existing models.
The paper introduces preference-based teaching (PBTD) as a new model for teaching concepts, showing that it yields finite and reasonably small values for many infinite concept classes, such as Euclidean half-spaces, where the recursive teaching dimension (RTD) becomes infinite.
We introduce a new model of teaching named "preference-based teaching" and a corresponding complexity parameter---the preference-based teaching dimension (PBTD)---representing the worst-case number of examples needed to teach any concept in a given concept class. Although the PBTD coincides with the well-known recursive teaching dimension (RTD) on finite classes, it is radically different on infinite ones: the RTD becomes infinite already for trivial infinite classes (such as half-intervals) whereas the PBTD evaluates to reasonably small values for a wide collection of infinite classes including classes consisting of so-called closed sets w.r.t. a given closure operator, including various classes related to linear sets over $\mathbb{N}_0$ (whose RTD had been studied quite recently) and including the class of Euclidean half-spaces. On top of presenting these concrete results, we provide the reader with a theoretical framework (of a combinatorial flavor) which helps to derive bounds on the PBTD.