Jun, 2024

有效的 PAC 学习与回应是 "是" 或者 "否" 的 Oracle 可能吗？

PDF
TL;DR在本文中，我们探讨了在二分类的 PAC 学习中，是否有比经验风险最小化（ERM）更弱的预测力量仍然能够实现学习，结果表明只需多项式代价就可以使用我们的更弱预测力量来学习概念类，同时也满足了 Alon 等人提出的对于有效性学习的算法原则的要求。
empirical risk minimizationerm-based learning algorithmspac learningoraclesample complexity
发现论文，激发创造
  • 多类学习能力与点最小风险原则

    研究多类预测中的样本复杂度，并提出了设计 ERM 学习器的原则以及使用这些原则来证明对称的多类假说类的样本复杂度的紧束缚定理。此外，通过对 Littlestone 维度的新概括，提供了在线背景和强盗问题中多类学习的错误和遗憾界限的描述。

    Aug, 2013

  • 不同标签函数的协同学习

    研究一种协作 PAC 学习的变体，旨在学习每个数据分布的准确分类器，同时最小化从这些数据分布中所抽取的样本数总量。给出基于经验风险最小化算法的学习方法，并且分析依赖于增强的假设类的 VC 维度的上界。在计算效率方面，证明了在一般情况下，基于增强的假设类的 ERM 是 NP 难的，为不存在计算效率高的学习器提供了依据，但对于两种特殊情况，给出了既有样本效率又有计算效率的学习器。

    Feb, 2024

  • 在线学习和使用 ERM 预测子解决无限博弈

    本文提出了一种基于 ERM 孤注一掷算法的在线二元分类方法，证明了它在真实问题上的收益有限，且在迷惑问题上的收益不断增长。同时，本文还探讨了 ERM 算法在非参数博弈中的应用，提出了一种不依赖于最优反应的学习算法，并将其应用到两人和多人博弈中，证明了算法的有效性和可靠性。

    Jul, 2023

  • 关于可计算连续特征学习的研究

    定义可计算的计算度量空间上二元分类的可计算 PAC 学习，提供解决 ERM 学习器可计算性的充分条件，限制 ERM 学习器的 Weihrauch 度，展示一种假设类，尽管底层类具有 PAC 可学性，但它不允许具有可计算采样函数的任何适当的可计算 PAC 学习器。

    Nov, 2021

  • 多类问题的最优学习器

    本文证明了多分类问题的效率最优解必须是不正确的，并提出了一种基于 generalized linear classifiers 的效率最优解的算法。

    May, 2014

  • 使用丰富观察的 Oracle 有效 PAC RL

    本文研究了 PAC 强化学习在富观察力下的计算复杂度，提出了基于确定性隐藏状态动态和随机富观察的可证明的样本有效算法，同时证明了在具有随机隐藏状态动态的情况下，已知样本有效算法 OLIVE 不能在 Oracle 模型中实现，通过几个示例表明了在这样一般的设置中可计算 PAC 强化学习的根本挑战。

    Mar, 2018

  • 三者中的大多数：最简单的最优学习者？

    研究理论以确定最简单的算法，通过选取数据的子集经验风险最小化（ERM）训练而返回多个 ERM 分类器的多数投票，实现高概率区间的最优算法。

    Mar, 2024

  • 基于统一 PAC-Bayesian-Rademacher-Shtarkov-MDL 复杂度的紧致过量风险界

    提出了一种新的学习理论复杂性概念，它在经验风险最小化和贝叶斯估计器的情况下分别以数据无关的 Rademacher 复杂度和数据相关的信息复杂度进行上限绑定，并通过 Rademacher 复杂度将其与 $L_2 (P)$ 熵进行关联。该研究进一步使用 ' 易于理解 ' 和模型复杂性等相互分离的方法，提供适用于 VC 和多项式熵类的最优性差距上限。

    Oct, 2017

  • 关于零知识假设下概率近似正确机器学习模型的最低下界

    提出了一种关于最小二倍经验风险下界的理论证明，并明确了最小二倍经验风险学习算法的特点，其中包括极限对称性和最小随机化 “投票” 程序。

    Jun, 2016

  • 正规化与最优多类学习

    这项研究的目的是在多类学习中表征正则化的作用，并使用一种最优学习算法来控制模型容量，该算法与结构风险最小化、最大熵原理和贝叶斯推理相结合。同时引入一种新的学习者，通过在无监督学习阶段学习正则化器，实现结构风险最小化的放松，以及推导学习问题的归纳错误率。最后，引入了对偶误差的泛化和不可知情况的哈明图最优学习算法，通过最大熵程序实现最优学习。

    Sep, 2023