AITOP

5月14日

13:26

arXiv cs.LG@Steve Hanneke, Anay Mehrotra, Grigoris Velegkas, Manolis Zampetakis

精选40

这篇论文重新审视了 Valiant 1984 年提出的原始学习模型（不同于 PAC 学习），该模型中学习器只能接收正例、可发起成员查询、且必须输出无假正例的假设。作者对有限域（包括布尔超立方体）给出了可学习性的充要条件：每个可实现的样本必须能被一个多项式大小的自适应查询压缩方案认证。这一刻画表明，Valiant 模型的可学习类严格介于 PAC 模型和无查询的 Valiant 模型之间，是少数成员查询能改变可学习类集合而非仅复杂度的情况。对于任意域，同样的严格夹逼关系仍然成立。此外，论文首次给出了 d 维半空间在 Valiant 模型中的学习算法（多项式样本和查询），并证明了 Ω(d) 的样本或查询下界。

论文学习理论 PAC学习成员查询半空间学习样本压缩

推荐理由：这篇论文澄清了机器学习理论中一个长期被误解的基础问题——Valiant 原始模型与 PAC 学习的区别，做学习理论或计算复杂度研究的学者值得一读，尤其是对成员查询能力感兴趣的人。

5月13日

19:12

arXiv cs.LG@Leonardo N. Coregliano, William Opich

精选35

近期一系列研究开始探索乘积空间上学习理论概念的变体，统称为高元学习理论。本文提出高元样本压缩方案的概念，并证明存在非平凡质量的高元样本压缩方案意味着高元PAC可学习性。该工作将经典样本压缩理论扩展到高元场景，为理解复杂数据结构下的学习能力提供了新视角。研究结果建立了高元压缩与可学习性之间的理论桥梁，对机器学习理论有基础性贡献。

论文高元学习理论样本压缩 PAC可学习性乘积空间机器学习理论

推荐理由：理论机器学习研究者会感兴趣——这项研究把样本压缩理论推到了高元空间，证明了压缩方案与PAC可学习性的新联系，做学习理论或高维数据分析的值得关注。