PAC学习相关 AI 资讯 · AI 热点

7月8日

11:50

11:50

官方账号arXiv cs.LG@Rahul Bandyopadhyay, Riccardo Molteni, Jens Eisert, Vedran Dunjko, Sofiene Jerbi

该研究从PAC学习角度研究量子多体动力学可学习性。他们设计了一个监督学习任务：训练集包含随机稳定子探针态、均匀采样自[0,T]的演化时间以及特定可观测量期望值。量子算法通过短时训练样本学习未知哈密顿量，并结合哈密顿量模拟与经典阴影协议进行推理。通过将BQP完全计算嵌入Feynman-Kitaev时钟哈密顿量的长时间动力学，他们证明除非BQP⊆P/poly，否则没有经典多项式时间算法能完成该任务。同时经典困难实例仍保持量子可学习性。

论文量子多体系统学习分离 PAC学习 BQP 量子机器学习

推荐理由：这篇论文给量子机器学习找了个硬核任务：预测多体系统时间演化，量子算法能学，经典学不了，除非BQP进P/poly。理论结果很扎实。

6月30日

11:47

11:47

官方账号arXiv cs.LG@Şuayp Talha Kocabay, Talha Rüzgar Akkuş, Kerem Yalçın

精选

论文证明组合函数树的Rademacher复杂度不随符号结构数量指数增长，而是受深度d和基算子Lipschitz常数控制。具体界为ℜ_n(ℋ_comp^d) ≤ (Kb√2L)^{d-1}ℜ_n(ℋ_comp^1)，其中K为算子库大小、b为元数。当K,b=O(1)时，高概率风险界为O(L^d/√n)。实验在合成物理类目标上验证了理论预测。

论文 PAC学习符号回归 Rademacher复杂度组合函数树

推荐理由：论文把PAC学习理论用到符号回归上，证明了组合函数树的样本复杂度不会随深度爆炸，还给了可跑的代码。

6月29日

10:15

10:15

官方账号arXiv cs.LG@Shai Ben-David, Farnam Mansouri, Anay Mehrotra, Manolis Zampetakis

精选

揭示了仅从正样本进行二分类的proper可学习性的完整刻画：一个概念类可proper学习当且仅当其VC维有限且满足新引入的组合条件“均匀外部可分离性”。该研究证明proper与improper学习在此设定下可分离，随机与确定性proper学习间也存在分离。存在概念类无ERM可作为学习器，且有限VC维对非一致学习不足。这些结果通过新组合维度得到，丰富了学习理论。

论文正样本学习 PAC学习 proper学习 VC维均匀外部可分离性

推荐理由：这篇论文搞清楚了只给正样本时proper学习到底能学啥，发现了VC维不够用，还新造了个叫“均匀外部可分离性”的条件，搞理论的人值得看。

5月14日

13:26

13:26

官方账号arXiv cs.LG@Steve Hanneke, Anay Mehrotra, Grigoris Velegkas, Manolis Zampetakis

精选

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

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

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