Teaching a smarter learner
Teaching a smarter learner
复制标题
DOI：
10.1006/jcss.1996.0020
复制
发表时间：
1996-04-01
影响因子：
1.1
通讯作者：
Mathias, HD
中科院分区：
文献类型：
--
作者：
Goldman, SA;Mathias, HD
我们引入了一种正式的教学模式，其中教师是针对特定学习者量身定制的，但教学协议的设计是为了避免串通。毫不奇怪，这样的模型弥补了其他模型的非直观方面，在其他模型中，教师必须成功地教授任何一致的学习者。我们证明，任何可以通过确定性多项式时间算法精确识别并访问非常丰富的基于示例的查询的类都可以由计算无限的教师和多项式时间学习者教授。此外，我们还提出了将这种教学模式与以前的各种结果联系起来的其他一般结果。我们还考虑了设计教师/学习者对的问题，其中教师和学习者都是多项式时间算法，并描述 1-决策列表和 Horn 句子类的教师/学习者对。 (C) 1996 学术出版社
We introduce a formal model of teaching in which the teacher is tailored to a particular learner, yet the teaching protocol is designed so that no collusion is possible. Not surprisingly, such a model remedies the nonintuitive aspects of other models in which the teacher must successfully teach any consistent learner. We prove that any class that can be exactly identified by a deterministic polynomial-time algorithm with access to a very rich set of example-based queries is teachable by a computationally unbounded teacher and a polynomial-time learner. In addition, we present other general results relating this model of teaching to various previous results. We also consider the problem of designing teacher/learner pairs in which both the teacher and learner are polynomial-time algorithms and describe teacher/learner pairs for the classes of 1-decision lists and Horn sentences. (C) 1996 Academic Press, Inc.