On the Complexity of Teaching
Abstract
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.
Cite
Text
Goldman and Kearns. "On the Complexity of Teaching." Annual Conference on Computational Learning Theory, 1991. doi:10.1006/jcss.1995.1003Markdown
[Goldman and Kearns. "On the Complexity of Teaching." Annual Conference on Computational Learning Theory, 1991.](https://mlanthology.org/colt/1991/goldman1991colt-complexity/) doi:10.1006/jcss.1995.1003BibTeX
@inproceedings{goldman1991colt-complexity,
title = {{On the Complexity of Teaching}},
author = {Goldman, Sally A. and Kearns, Michael J.},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1991},
pages = {303-314},
doi = {10.1006/jcss.1995.1003},
url = {https://mlanthology.org/colt/1991/goldman1991colt-complexity/}
}