TY - GEN
T1 - Learning from a consistently ignorant teacher
AU - Frazier, Michael
AU - Goldman, Sally
AU - Mishra, Nina
AU - Pitt, Leonard
N1 - Funding Information:
*Supported in part by NSF Grant IRI-9014840, NASA grant NAG 1-613. tsupported in part by NSF Grant CCR-91101O8 NSF NYI Grant CCR-93577O7. ‘Supported in part by NSF Grant IRI-9014840.
Publisher Copyright:
© 1994 ACM.
PY - 1994/7/16
Y1 - 1994/7/16
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84872739732&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84872739732&partnerID=8YFLogxK
U2 - 10.1145/180139.181170
DO - 10.1145/180139.181170
M3 - Conference contribution
AN - SCOPUS:84872739732
T3 - Proceedings of the Annual ACM Conference on Computational Learning Theory
SP - 328
EP - 339
BT - Proceedings of the 7th Annual Conference on Computational Learning Theory, COLT 1994
PB - Association for Computing Machinery
T2 - 7th Annual Conference on Computational Learning Theory, COLT 1994
Y2 - 12 July 1994 through 15 July 1994
ER -