Teaching dimension is a learning theoretic quantity that specifies the minimum training set size to teach a target model to a learner. Previous studies on teaching dimension focused on version-space learners which maintain all hypotheses consistent with the training data, and cannot be applied to modern machine learners which select a specific hypothesis via optimization. This paper presents the first known teaching dimension for ridge regression, support vector machines, and logistic regression. We also exhibit optimal training sets that match these teaching dimensions. Our approach generalizes to other linear learners.
Teaching dimension as a learning-theoretic quantity has attracted a long history of research. It was proposed independently in @cite_1 @cite_17 . Subsequent theoretical developments can be found in e.g. @cite_14 @cite_7 @cite_15 @cite_16 @cite_3 @cite_23 @cite_21 @cite_10 @cite_19 @cite_6 @cite_8 @cite_0 @cite_2 . Most of them assume little extra knowledge on the learner other than that it is consistent with the training data. While such version-space learners are elegant object of theoretical study, they diverge from the practice of modern machine learning. Our present paper is among the first to extend teaching dimension to optimization-based machine learners.
@cite_14 @cite_7 @cite_8 @cite_21 @cite_1 @cite_3 @cite_6 @cite_0 @cite_19 @cite_23 @cite_2 @cite_15 @cite_16 @cite_10 @cite_17
2146938707 1583136812 2027995847 1570266953 2020764470 1996389440 1606414949 59277799 2067905901 2146250995 2071268134 2012508367
While most supervised machine learning models assume that training examples are sampled at random or adversarially, this article is concerned with models of learning from a cooperative teacher that selects "helpful" training examples. The number of training examples a learner needs for identifying a concept in a given class C of possible target concepts (sample complexity of C) is lower in models assuming such teachers, that is, "helpful" examples can speed up the learning process. The problem of how a teacher and a learner can cooperate in order to reduce the sample complexity, yet without using "coding tricks", has been widely addressed. Nevertheless, the resulting teaching and learning protocols do not seem to make the teacher select intuitively "helpful" examples. The two models introduced in this paper are built on what we call subset teaching sets and recursive teaching sets. They extend previous models of teaching by letting both the teacher and the learner exploit knowing that the partner is cooperative. For this purpose, we introduce a new notion of "coding trick" "collusion". We show how both resulting sample complexity measures (the subset teaching dimension and the recursive teaching dimension) can be arbitrarily lower than the classic teaching dimension and known variants thereof, without using coding tricks. For instance, monomials can be taught with only two examples independent of the number of variables. The subset teaching dimension turns out to be nonmonotonic with respect to subclasses of concept classes. We discuss why this nonmonotonicity might be inherent in many interesting cooperative teaching and learning scenarios. The present paper surveys recent developments in algorithmic teaching. First, the traditional teaching dimension model is recalled. Starting from the observation that the teaching dimension model sometimes leads to counterintuitive results, recently developed approaches are presented. Here, main emphasis is put on the following aspects derived from human teaching learning behavior: the order in which examples are presented should matter; teaching should become harder when the memory size of the learners decreases; teaching should become easier if the learners provide feedback; and it should be possible to teach infinite concepts and or finite and infinite concept classes. Recent developments in the algorithmic teaching achieving (some) of these aspects are presented and compared. WF ?X]JIO (’ th? l> wt’r of teaChillg by StUdyiIlg two uu-lille learuing models: teach er-clirecteci learninE and self-dlrectecl learning. In both models, the learner tries to identify an unkuowu concept based on examples of the concept presented one at, a time. The learner predirts wheth r each example is positive or negative with immediate feedback, and the ol)ject,ive is to minimize the uurnl)er of predict,iou mistakes. ThP examples are selected by the teacher in teacher-dlrectecl learning and hy tlhe learner itself in self-directed learning. R,oughly, teacher-directed learning represents the scenario in which a teacher teaches a class of learners, and self-directed learning represents the scenario in which a smart learnerasks questious and learns by itself. For all previolmly studied concept classes, the rnirrimum numl)er of mistalws in teacller-ciirectf ecl learning is always larger than that, in self-directed learning. This raises an mtermting question [.)t’ whrt, hrr teaching is helpful for all learners mrlu(ling the smart learner’. Assuming the existence of clue-way functioms, we construct com cept clahses for which the miuimum nurnher of mislakes is hnear in teacher-directed learning I,ut sllI>rrlJolyllorlllal m self-directed learning, cler lc llst,rt tillg the power of a helpful teacher in a Iearmng process. The present paper introduces a new model for teaching randomized learners. Our new model, though based on the classical teaching dimension model, allows to study the influence of various parameters such as the learner’s memory size, its ability to provide or to not provide feedback, and the influence of the order in which examples are presented. Furthermore, within the new model it is possible to investigate new aspects of teaching like teaching from positive data only or teaching with inconsistent teachers. Furthermore, we provide characterization theorems for teachability from positive data for both ordinary teachers and inconsistent teachers with and without feedback. While most theoretical work in machine learning has focused on the complexity of learning, recently there has been increasing interest in formally studying the complexity of teaching. In this paper we study the complexity of teaching by considering a variant of the on-line learning model in which a helpful teacher selects the instances. We measure the complexity of teaching a concept from a given concept class by a combinatorial measure we call the teaching dimension, Informally, the teaching dimension of a concept class is the minimum number of instances a teacher must reveal to uniquely identify any target concept chosen from the class. We introduce a formal model of teaching in which the teacher is tailored to a particular learner, yet the teaching protocol is designed so that no collusion is possible. Not surprisingly, such a model remedies the nonintuitive aspects of other models in which the teacher must successfully teach any consistent learner. We prove that any class that can be exactly identified by a deterministic polynomial-time algorithm with access to a very rich set of example-based queries is teachable by a computationally unbounded teacher and a polynomial-time learner. In addition, we present other general results relating this model of teaching to various previous results. We also consider the problem of designing teacher learner pairs in which both the teacher and learner are polynomial-time algorithms and describe teacher learner pairs for the classes of 1-decision lists and Horn sentences We study the self-directed (SD) learning model. In this model a learner chooses examples, guesses their classification and receives immediate feedback indicating the correctness of its guesses. We consider several fundamental questions concerning this model: the parameters of a task that determine the cost of learning, the computational complexity of a student, and the relationship between this model and the teacher-directed (TD) learning model. We answer the open problem of relating the cost of self-directed learning to the VC-dimension by showing that no such relation exists. Furthermore, we refute the conjecture that for the intersection-closed case, the cost of self-directed learning is bounded by the VC-dimension. We also show that the cost of SD learning may be arbitrarily higher that that of TD learning. Finally, we discuss the number of queries needed for learning in this model and its relationship to the number of mistakes the student incurs. We prove a trade-off formula showing that an algorithm that makes fewer queries throughout its learning process, necessarily suffers a higher number of mistakes. Teaching is inextricably linked to learning, and there are many studies on the complexity of teaching as well as learning in computational learning theory. In this paper, we study the complexity of teaching in the situation that the number of examples is restricted, especially less than its teaching dimension. We formulate a model of teaching by a restricted number of examples, where the complexity is measured by the maximum error to a target concept. We call a concept class is optimally incrementally teachable if the teacher can optimally teach it to the learner whenever teaching is terminated. We study the complexity of the three concept classes of monotone monomials, monomials without the empty concept, and monomials in our model. We show that the boundary of optimally incremental teachability is different from that of polynomial teachability in the classical model. We also show that inconsistent examples help to reduce the maximum error in our model. Previous teaching models in the learning theory community have been batch models. That is, in these models the teacher has generated a single set of helpful examples to present to the learner. In this paper we present an interactive model in which the learner has the ability to ask queries as in the query learning model of Angluin. We show that this model is at least as powerful as previous teaching models. We also show that anything learnable with queries, even by a randomized learner, is teachable in our model. In all previous teaching models, all classes shown to be teachable are known to be efficiently learnable. An important concept class that is not known to be learnable is DNF formulas. We demonstrate the power of our approach by providing a deterministic teacher and learner for the class of DNF formulas. The learner makes only equivalence queries and all hypotheses are also DNF formulas. This paper is concerned with various combinatorial parameters of classes that can be learned from a small set of examples. We show that the recursive teaching dimension, recently introduced by (2008), is strongly connected to known complexity notions in machine learning, e.g., the self-directed learning complexity and the VC-dimension. To the best of our knowledge these are the first results unveiling such relations between teaching and query learning as well as between teaching and the VC-dimension. It will turn out that for many natural classes the RTD is upper-bounded by the VCD, e.g., classes of VC-dimension 1, intersection-closed classes and finite maximum classes. However, we will also show that there are certain (but rare) classes for which the recursive teaching dimension exceeds the VC-dimension. Moreover, for maximum classes, the combinatorial structure induced by the RTD, called teaching plan, is highly similar to the structure of sample compression schemes. Indeed one can transform any repetition-free teaching plan for a maximum class C into an unlabeled sample compression scheme for C and vice versa, while the latter is produced by (i) the corner-peeling algorithm of Rubinstein and Rubinstein (2012) and (ii) the tail matching algorithm of Kuzmin and Warmuth (2007). This paper considers computational learning from the view-point of teaching. We introduce a notion of teachability with which we establish a relationship between the learnability and teachability. We also discuss the complexity issues of a teacher in relation to learning.