Aug, 2013

多类学习能力与点最小风险原则

PDF
TL;DR研究多类预测中的样本复杂度，并提出了设计 ERM 学习器的原则以及使用这些原则来证明对称的多类假说类的样本复杂度的紧束缚定理。此外，通过对 Littlestone 维度的新概括，提供了在线背景和强盗问题中多类学习的错误和遗憾界限的描述。
multiclass predictionsample complexityempirical risk minimizers (erm)symmetric multiclass hypothesis classesregret bounds
发现论文，激发创造
  • 多类问题的最优学习器

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

    May, 2014

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

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

    Feb, 2024

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

    在本文中，我们探讨了在二分类的 PAC 学习中，是否有比经验风险最小化（ERM）更弱的预测力量仍然能够实现学习，结果表明只需多项式代价就可以使用我们的更弱预测力量来学习概念类，同时也满足了 Alon 等人提出的对于有效性学习的算法原则的要求。

    Jun, 2024

  • 统计学习的风险界限

    本文提出一个通用的定理给出经验风险最小化器 (ERM) 风险的上界，并且通过采用一些方便的加权经验过程的浓度不等式扩展 Tsybakov 针对 ERM 风险下边缘条件的分析，以便处理一些测量分类器类 “大小” 的方式，特别地，当分类规则属于某个 VC 类且满足边缘条件时，我们推导出 ERM 的新风险上界，并讨论这些上界在极小化意义下的最优性。

    Feb, 2007

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

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

    Nov, 2021

  • 正规化与最优多类学习

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

    Sep, 2023

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

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

    Mar, 2024

  • 从未标注的数据中以最少监督训练任何二元分类器

    该研究通过使用两组未标记的数据和基于经验风险最小化（ERM）的方法，提出了一种可以训练任意（从线性到深度）二分类器的学习方法，并证明了这种方法是一致的；实验证明，该方法可以训练深度模型并优于学习两组未标记数据的现有方法。

    Aug, 2018

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

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

    Jul, 2023

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

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

    Oct, 2017