Occam 算法的等价性
此文介绍了使用多智能体认知逻辑演示 PAC 学习的技术基础,涉及逻辑和弱推理,以提供强大的模型理论框架来回答查询,并研究了该算法的正确性、样本复杂性以及其能够高效的情况,利用表述定理将模态推理纳入命题推理中。
Jun, 2023
讨论分布式数据的 PAC 学习问题,分析了涉及的基本通信复杂性问题,包括教学维度和错误绑定。针对特定概念类别,如合取、奇偶函数和决策列表等,给出上下界限。讨论了如何通过增强来在分布式环境下进行一般性通信,以及如何在不确定环境下实现低通信回归。同时,还考虑了隐私性,包括差分隐私和分布式隐私。
Apr, 2012
本文研究在 PAC 模型下共识查询的学习问题,证明了共识查询类不具有多项式大小匹配的性质,给出了许多限制类共识查询的负 PAC 可学性结果,最后提出了利用成员查询实现共识查询的高效 PAC 学习方法。
Aug, 2022
根据合理的密码学假设,我们展示了一个概念类别,该类别允许在多项式时间内以多项式错误边界运行的在线学习器,但不存在计算效率高的差异隐私 PAC 学习器。
Feb, 2024
本文提出了一种参数化 PAC 学习理论,通过该理论可对 CNF、DNF 和图形学习等问题的可行性边界进行更精细的界定,并发展了机器学习领域的参数化固定参数学习的概念。
Apr, 2023
提出有界拟合作为一种模式学习的方案,该方案可以在本体存在的情况下学习描述逻辑概念,并且称之为 PAC 学习的通用性具有理论保证。同时,我们提供了一种名为 SPELL 的系统,其基于 SAT 求解器高效实施了有界拟合,并将其表现与最先进的学习者进行了比较。
May, 2023
提出了一种新的学习法则,即预测性 PAC 学习,它适用于可交换数据,并使用 de Finetti 定理证明了如果一个具有普遍可分性的函数类在 i.i.d.G 渐进输入下是无偏的,那么在可交换输入下也是无偏的,但样本复杂度略有降低。
Jun, 2010
这篇论文介绍了一种新的证明不适当学习难度的技术,基于难以处理的问题的规约,通过与密码假设相结合,发现了学习 $DNF$,半平面和超平面的交集等问题的困难性。
Nov, 2013
通过向数据集添加少量样本,我们将依靠 PAC 保证的无偏泛化学习转化为依靠转导保证的无偏泛化学习,从而展示了这些问题的等效性。我们还将所得到的结果扩展到了 agnostic 情况,证明了一种 agnostic 转导学习器可以高效转化为 agnostic 无偏泛化学习器。最后,我们对二进制分类的 agnostic one inclusion 图算法进行了性能表征,并且展示了将其和我们的转导转化方法相结合可以得到一个本质上最优的 agnostic 无偏泛化学习器。我们的结果意味着在可实现的环境下,使用伪度量损失函数进行监督学习时,转导学习和 PAC 学习在本质上是等价的;在 agnostic 情况下,对于二进制分类问题,也是如此。我们猜想这个结论在 agnostic 情况下更普遍适用。
May, 2024
本文提出一种基于 PAC 学习框架的约束学习方法,该方法通过对经验风险最小化规则进行约束来解决分类问题中的偏差、不公平和不稳定性等问题,研究表明该方法能够实现约束学习的泛化。
Jun, 2020