Learning from a Consistently Ignorant Teacher
Abstract
One view of computational learning theory is that of a learner acquiring the knowledge of a teacher. We introduce a formal model of learning capturing the idea that teachers may have gaps in their knowledge. The goal of the learner is still to acquire the knowledge of the teacher, but now the learner must also identify the gaps. This is the notion of learning from a consistently ignorant teacher. We consider the impact of knowledge gaps on learning, for example, monotone DNF and d-dimensional boxes, and show that learning is still possible. Negatively, we show that knowledge gaps make learning conjunctions of Horn clauses as hard as learning DNF. We also present general results describing when known learning algorithms can be used to obtain learning algorithms using a consistently ignorant teacher.
Cite
Text
Frazier et al. "Learning from a Consistently Ignorant Teacher." Annual Conference on Computational Learning Theory, 1994. doi:10.1145/180139.181170Markdown
[Frazier et al. "Learning from a Consistently Ignorant Teacher." Annual Conference on Computational Learning Theory, 1994.](https://mlanthology.org/colt/1994/frazier1994colt-learning/) doi:10.1145/180139.181170BibTeX
@inproceedings{frazier1994colt-learning,
title = {{Learning from a Consistently Ignorant Teacher}},
author = {Frazier, Michael and Goldman, Sally A. and Mishra, Nina and Pitt, Leonard},
booktitle = {Annual Conference on Computational Learning Theory},
year = {1994},
pages = {328-339},
doi = {10.1145/180139.181170},
url = {https://mlanthology.org/colt/1994/frazier1994colt-learning/}
}