揭示了维塔尔原始学习模型中可学习类的完整条件，发现查询能改变可学习范围。
What is Learnable in Valiant's Theory of the Learnable?
- 通过自适应查询压缩方案认证正样本，定义可学习性新标准。
- 证明d维半空间在该模型中可用多项式样本和查询学习，且下界为Ω(d)。
- 首次给出半空间在该模型下的有效算法，拓展了学习理论边界。
Valiant 1984 年论文常被误认为引入 PAC 学习模型，实则提出不同框架：学习者仅接收正例，可发起成员查询，且输出假设不能有假阳性。本文重访该原始模型，回答：哪些概念类可学习？对任意有限域（包括布尔超立方体），我们证明一个类可学习当且仅当每个可实现的正样本集可通过多项式大小的自适应查询压缩方案被认证。这是一种新型样本压缩，学习者通过与成员预言机短交互来验证样本。该刻画表明，该模型中的可学习性严格介于 PAC 学习与无查询版本之间。这是少数几个引入查询会改变可学习类而非仅复杂度的例子。进一步研究任意域上的扩展，虽未获精确刻画，但技术可推广并保持严格夹逼关系。最后，我们证明：不带查询时不可学的 d 维半空间，在本模型中可学——给出样本复杂度为 $\mathrm{poly}(d) \tilde{O}(1/ε)$、查询复杂度为 $\mathrm{poly}(d) \mathrm{polylog}(1/ε)$ 的算法，并证明至少需要 $Ω(d)$ 样本或查询。据我们所知，这是首个针对半空间在该模型下的算法。这些结果揭示了维塔尔原始学习观背后丰富的理论体系，并引入了可能具独立意义的新思想。
原文摘要 · Abstract (English)
Valiant's 1984 paper is widely credited with introducing the PAC learning model, but it, in fact, introduced a different model: unlike PAC learning, the learner receives only positives, may issue membership queries, and must output a hypothesis with no false positives. Prior work characterized variants, including the case without queries. We revisit Valiant's original model and ask: *Which classes are learnable in it?* For every finite domain, including Valiant's Boolean-hypercube setting, we show that a class is learnable if and only if every realizable positive sample can be certified by a poly-size adaptive query-compression scheme. This is a new variant of sample compression where the learner certifies samples via a short interaction with the membership oracle. Our characterization shows that learnability in Valiant's model is strictly sandwiched between learnability in the PAC model and the variant of Valiant's model without membership queries. This is one of the rare cases where introducing membership queries changes the set of learnable classes, and not just the sample or computational complexity. Next, we study the natural extension of the model to arbitrary domains. While we do not obtain an exact characterization, our techniques readily generalize and show that the same strict sandwiching persists. Finally, we show that $d$-dimensional halfspaces, which are not learnable without queries, are learnable with queries: we give a $\mathrm{poly}(d) \tilde{O}(1/ε)$ sample and $\mathrm{poly}(d) \mathrm{polylog}(1/ε)$ query algorithm, and prove that at least $Ω(d)$ samples or queries are necessary. To our knowledge, this is the first algorithm for halfspaces in Valiant's model. Together, these results uncover a surprisingly rich theory behind Valiant's original notion of learnability and introduce ideas that may be of independent interest in learning theory.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。