首页> 外文期刊>Information and computation >Learning languages from positive data and a finite number of queries
【24h】

Learning languages from positive data and a finite number of queries

机译:从积极的数据和有限的查询中学习语言

获取原文
获取外文期刊封面目录资料

摘要

A computational model for learning languages in the limit from full positive data and a bounded number of queries to the teacher (oracle) is introduced and explored. Equivalence, superset, and subset queries are considered (for the latter one we consider also a variant when the learner tests every conjecture, but the number of negative answers is uniformly bounded). If the answer is negative, the teacher may provide a counterexample. We consider several types of counterexamples: arbitrary, least counterexamples, the ones whose size is bounded by the size of positive data seen so far, and no counterexamples. A number of hierarchies based on the number of queries (answers) and types of answers/ counterexamples is established. Capabilities of learning with different types of queries are compared. In most cases, one or two queries of one type can sometimes do more than any bounded number of queries of another type. Still, surprisingly, a finite number of subset queries is sufficient to simulate the same number of equivalence queries when behaviourally correct learners do not receive counterexamples and may have unbounded number of errors in almost all conjectures.
机译:引入并探索了一种用于从完全正数数据和对教师(oracle)的查询数量有限的语言中学习语言的计算模型。考虑了对等查询,超集查询和子集查询(对于后一种查询,当学习者测试每个猜想时,我们也将其视为变体,但否定答案的数量是有界的)。如果答案是否定的,老师可以提供反例。我们考虑几种类型的反例:任意的,最少的反例,其大小受迄今为止所见的正数据大小限制,没有反例。基于查询(答案)的数量和答案/反例的类型,建立了许多层次结构。比较了使用不同类型查询的学习能力。在大多数情况下,一种类型的一个或两个查询有时可以做的比另一种类型的任意数量的查询要多。仍然令人惊讶的是,当行为正确的学习者没有收到反例并且几乎在所有猜想中都有无限数量的错误时,有限数量的子集查询足以模拟相同数量的等效查询。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号