On the complexity of teaching

By Sally A. Goldman, Michael Kearns. 1991

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Dataset Distillation (2018, methodology): “Our method is also related to the theoretical concept of teaching dimension, which speciﬁes the size of dataset necessary to teach a target model to a learner (Shinohara & Miyano, 1991; Goldman & Kearns, 1995).”
Machine Teaching: An Inverse Problem to Machine Learning and an Approach Toward Optimal Education (2015, background): “The seminal notion of teaching dimension concerns the cardinality of the optimal teaching set (Goldman and Kearns 1995; Shinohara and Miyano 1991).”
Cooperative Inverse Reinforcement Learning (2016, background): “Because CIRL incentivizes the human to teach, as opposed to maximizing reward in isolation, our work is related to optimal teaching: ﬁnding examples that optimally train a learner (Balbach & Zeugmann, 2009; Goldman et al., 1993; Goldman & Kearns, 1995).”
Machine Teaching for Bayesian Learners in the Exponential Family (2013, background): “The first thread is the teaching dimension theory by Goldman and Kearns [10] and its extensions in computer science(e.g., [1, 2, 11, 12, 14, 25]).”
A bibliographical study of grammatical inference (2005, methodology): “Based on teaching models [48,49], de la Higuera proposes the model ofidentification in the limit from polynomial time and data[30].”
Teaching Multiple Concepts to Forgetful Learners (2018, background): “[9] Sally A Goldman and Michael J Kearns.”
The Teaching Dimension of Linear Learners (2015, background): “For a finite hypothesis space H, Goldman and Kearns [13] proved the relation V C(H)/ log(|H|) ≤ TD(H) ≤ V C(H) + |H| − 2 C(H).”
Explicit Defense Actions Against Test-Set Attacks (2017, background): “Adversarially corrupting training sets has been put into the framework of machine teaching (Goldman, Rivest, and Schapire 1993; Goldman and Kearns 1995; Zhu 2015).”
Teacher Improves Learning by Selecting a Training Subset (2018, background): “The theoretical study of machine teaching has focused on the teaching dimension, i.e. the minimum training set size needed to exactly teach a target concept θ ∗ [20, 38, 46, 18, 29, 45, 16, 44, 48, 9, 3, 4, 21, 31, 8, 7, 25, 5, 36, 23, 10].”
Recent Developments in Algorithmic Teaching (2009, methodology): “As it has often been noted [32, 5, 17], the problem of computing the teaching dimension is essentially equivalent to the SET-COVER (or HITTING-SET) problem which is a difficult approximation problem.”
Self-Directed Learning and Its Relation to the VC-Dimension and to Teacher-Directed Learning (1998, background): “Previous work (Goldman, 1990; Goldman & Kearns, 1995; Goldman, Rivest, & Schapire, 1993; Goldman & Sloan, 1994) presented many classes for which self-directed learning is more efficient than teacher-directed learning.”
Optimal Teaching for Limited-Capacity Human Learners (2014, background): “Such a result would establish a conceptual link between idealization manipulations from psychology and optimal teaching procedures from machine learning [7, 6, 8, 2, 9, 10, 11].”
A bound on the label complexity of agnostic active learning (2007, methodology): “To quantify #MQ(C), the worst-case number of membership queries required for Exact learning with concept space C, Hegedüs [3] defines a quantity called the extended teaching dimension of C, based on the teaching dimension of Goldman & Kearns [5].”
Theory of Disagreement-Based Active Learning (2014, methodology): “The exact RobustCAL algorithm stated above is essentially taken from Hanneke [2012] (though that work uses data-dependent bounds in place of U(m, δm), and has a slightly looser label complexity analysis). The label complexity analysis of RobustCAL given above is taken from the recent work of Hanneke”
Learning to Teach with Dynamic Loss Functions (2018, background): “The study of teaching for AI, inspired by human teaching process, has a long history [1, 17].”
Predicting a Correct Program in Programming by Example (2015, background): “The number of representative input-output examples required to learn a desired task is a function of the underlying DSL and has also been referred to as the learning dimension [7] of the DSL.”
New Methods for Competitive Coevolution (1997, background): “A teaching set is a set of individuals that work together by having, for each possible non-optimal opponent, at least one individual in the set capable of defeating that opponent (Goldman & Kearns, 1991; Rosin & Belew, 1996).”
Mixed-Initiative Active Learning (2012, methodology): “An optimal teaching sequence that satisfies the lower bound in Equation 1 is produced by the following algorithm (Goldman & Kearns, 1995): (1) First show one positive example.”