A Computational Model of Teaching
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.
Cite
Text
Jackson and Tomkins. "A Computational Model of Teaching." Annual Conference on Computational Learning Theory, 1992. doi:10.1145/130385.130421Markdown
[Jackson and Tomkins. "A Computational Model of Teaching." Annual Conference on Computational Learning Theory, 1992.](https://mlanthology.org/colt/1992/jackson1992colt-computational/) doi:10.1145/130385.130421BibTeX
@inproceedings{jackson1992colt-computational,
title = {{A Computational Model of Teaching}},
author = {Jackson, Jeffrey C. and Tomkins, Andrew},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1992},
pages = {319-326},
doi = {10.1145/130385.130421},
url = {https://mlanthology.org/colt/1992/jackson1992colt-computational/}
}