...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >General lower bounds on the query complexity within the exact learning model
【24h】

General lower bounds on the query complexity within the exact learning model

机译：精确学习模型中查询复杂度的一般下限

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

In the exact learning model, a learner has to exactly identify a hidden target concept by means of queries. The query complexity of a concept class l is the smallest number of queries which suffices tin the worst case) to exactly identify an unknown target concept C is an element of l. Popular query types are equivalence and membership queries, for instance. In this paper, we prove general lower bounds on the query complexity of a concept class l in terms of combinatorial complexity measures like the capacity function or the VC-dimension of l. These bounds are parameterized by an additional parameter k, and are valid for all collections of query types which include equivalence queries and (arbitrarily many) other types of queries with at most k possible answers. They are tight (up to an asymptotically negligible additive term). Special cases of the most general lower bound lead to improvements of previous bounds. The methods, that we apply to derive the various lower bounds, allows us to compare the power of equivalence queries with the power of queries with at most k answers. It turns out that, for concept classes whose query complexity asymptotically matches the lower bounds, in a first phase, queries with at most k answers provide more information. In a second phase, equivalence queries become more effective. The last two sections of the paper are devoted to a discussion of the "breakpoint", where the learner should switch from Phase 1 to Phase 2. Besides this intuitive insight into the power of different query types, our proof method has a strong combinatorial flavor and the auxiliary results may be interesting in their own right. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 11]
机译：在精确学习模型中，学习者必须通过查询来准确识别隐藏的目标概念。概念类l的查询复杂度是最少的查询数量，足以满足最坏情况的需要，以准确地识别未知目标概念C是l的元素。流行的查询类型例如是等效查询和成员查询。在本文中，我们通过组合复杂性度量（如l的容量函数或VC维）证明了概念类l的查询复杂性的一般下界。这些界限由附加参数k参数化，并且对所有查询类型集合有效，这些集合包括对等查询和（任意多个）其他类型的查询，最多包含k个可能的答案。它们是紧的（直到渐近可忽略的加法项）。最一般的下限的特殊情况导致先前范围的改进。我们用于导出各种下界的方法使我们能够将等价查询的能力与最多有k个答案的查询的能力进行比较。事实证明，对于查询复杂度渐近匹配下限的概念类，在第一阶段中，最多具有k个答案的查询会提供更多信息。在第二阶段，等效查询变得更加有效。本文的最后两节专门讨论“断点”，学习者应从阶段1切换到阶段2。除了对不同查询类型的强大功能的直观了解之外，我们的证明方法还具有很强的组合风味辅助结果本身可能会很有趣。 （C）2000 Elsevier Science B.V.保留所有权利。 [参考：11]

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号