arXiv cs.LG@Steve Hanneke, Anay Mehrotra, Grigoris Velegkas, Manolis Zampetakis
精选40
推荐理由：这篇论文澄清了机器学习理论中一个长期被误解的基础问题——Valiant 原始模型与 PAC 学习的区别，做学习理论或计算复杂度研究的学者值得一读，尤其是对成员查询能力感兴趣的人。
全部 AI 动态
AI 相关资讯全量信息流
5月14日
13:26
这篇论文重新审视了 Valiant 1984 年提出的原始学习模型（不同于 PAC 学习），该模型中学习器只能接收正例、可发起成员查询、且必须输出无假正例的假设。作者对有限域（包括布尔超立方体）给出了可学习性的充要条件：每个可实现的样本必须能被一个多项式大小的自适应查询压缩方案认证。这一刻画表明，Valiant 模型的可学习类严格介于 PAC 模型和无查询的 Valiant 模型之间，是少数成员查询能改变可学习类集合而非仅复杂度的情况。对于任意域，同样的严格夹逼关系仍然成立。此外，论文首次给出了 d 维半空间在 Valiant 模型中的学习算法（多项式样本和查询），并证明了 Ω(d) 的样本或查询下界。