Abstract
Goldman and Kearns [GK91] recently introduced a notion of the teaching dimension of a concept class. The teaching dimension is intended to capture the combinatorial difficulty of teaching a concept class. We present a computational analog which allows us to make statements about bounded-complexity teachers and learners, and we extend the model by incorporating trusted information. Under this extended model, we modify algorithms for learning several expressive classes in the exact identification model of Angluin [Ang88]. We study the relationships between variants of these models, and also touch on a relationship with distribution-free learning.
Keywords
Dimension (graph theory)Class (philosophy)Computer scienceTheoretical computer scienceBounded functionIdentification (biology)Artificial intelligenceMathematics
Affiliated Institutions
Related Publications
An Introduction to Computational Learning Theory
Emphasizing issues of computational efficiency, Michael Kearns and Umesh Vazirani introduce a number of central topics in computational learning theory for researchers and stude...
Scale-sensitive dimensions, uniform convergence, and learnability
Learnability in Valiant's PAC learning model has been shown to be strongly related to the existence of uniform laws of large numbers. These laws define a distribution-free conve...
Quantum complexity theory
In this dissertation we study quantum computation from a complexity theoretic viewpoint. Our first result is the existence of an efficient universal quantum Turing Machine in De...
Enacting Project-Based Science
Recommendations for reform in science education place a premium on students' understanding of scientific concepts and their ability to identify problems, conduct inquiry, and us...
Distributed Learning, Communication Complexity and Privacy
We consider the problem of PAC-learning from distributed data and analyze fundamental communication complexity questions involved. We provide general upper and lower bounds on t...
Publication Info
- Year
- 1992
- Type
- article
- Pages
- 319-326
- Citations
- 47
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
47
OpenAlex
Cite This
Jeffrey C. Jackson,
Andrew Tomkins
(1992).
A computational model of teaching.
, 319-326.
https://doi.org/10.1145/130385.130421
Identifiers
- DOI
- 10.1145/130385.130421