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

8月7日

12:40

12:40

官方账号arXiv cs.LG@Anay Mehrotra

论文研究单调对抗者（monotone adversary）插入额外正确标注样本后的学习问题，回答 Larsen、Pabbaraju 和 Shetty 提出的开问题。作者证明，VC 维 d=1 时最小最大期望误差为 Θ(1/n)，d≥2 时为 Θ((d/n)log(n/d))，因此额外对数因子是内在代价。同样结论适用于 Littlestone 维 d_L，说明在线学习可达到的 O(d_L/n) 批量速率无法实现。一维上界由简单非恰当学习器配合留一论证达到；下界来自单个显式构造。

论文 Monotone Adversaries VC维 Littlestone维

推荐理由：这篇论文把单调对抗者模型的误差速率定性了：d=1是Θ(1/n)，d≥2多一个log因子，证明很直接。

7月28日

11:58

11:58

官方账号arXiv cs.LG@Jon Kleinberg, Amin Saberi, Xizhi Tan, Grigoris Velegkas

本文研究在有限域[n]上从多个数据提供者学习未知分布p的问题，每个查询返回条件分布p(·|S)的独立样本。可学习性由查询集的共现图决定：当图在目标支撑上连通时可达点态一致性，完全图时可达PAC学习。PAC学习的最优样本复杂度范围从近线性到二次：完全共现图族复杂度为Õ(n²/ε²)，紧界；当[n]本身可查询时复杂度为Θ(n/ε²)，即使所有子集可查询也无法改进。作者识别了层次可比性作为近线性复杂度（Õ(n/ε²)）的充分条件，并展示对于每个α∈(1,2)存在查询族达到最优PAC率Θ(n^α/ε²)。

论文分布学习 PAC学习条件采样

推荐理由：你想知道从多个供应商凑数据学分布有多难吗？这篇论文给出了从线性到二次的完整样本复杂度图谱，还找到了层次可比性这个好用的结构条件。

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进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学习

推荐理由：这篇论文搞清楚了只给正样本时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 学习的区别，做学习理论或计算复杂度研究的学者值得一读，尤其是对成员查询能力感兴趣的人。