研究多类预测中的样本复杂度,并提出了设计 ERM 学习器的原则以及使用这些原则来证明对称的多类假说类的样本复杂度的紧束缚定理。此外,通过对 Littlestone 维度的新概括,提供了在线背景和强盗问题中多类学习的错误和遗憾界限的描述。
Aug, 2013
本文证明了多分类问题的效率最优解必须是不正确的,并提出了一种基于 generalized linear classifiers 的效率最优解的算法。
May, 2014
研究一种协作 PAC 学习的变体,旨在学习每个数据分布的准确分类器,同时最小化从这些数据分布中所抽取的样本数总量。给出基于经验风险最小化算法的学习方法,并且分析依赖于增强的假设类的 VC 维度的上界。在计算效率方面,证明了在一般情况下,基于增强的假设类的 ERM 是 NP 难的,为不存在计算效率高的学习器提供了依据,但对于两种特殊情况,给出了既有样本效率又有计算效率的学习器。
Feb, 2024
在本文中,我们探讨了在二分类的 PAC 学习中,是否有比经验风险最小化(ERM)更弱的预测力量仍然能够实现学习,结果表明只需多项式代价就可以使用我们的更弱预测力量来学习概念类,同时也满足了 Alon 等人提出的对于有效性学习的算法原则的要求。
Jun, 2024
这项研究的目的是在多类学习中表征正则化的作用,并使用一种最优学习算法来控制模型容量,该算法与结构风险最小化、最大熵原理和贝叶斯推理相结合。同时引入一种新的学习者,通过在无监督学习阶段学习正则化器,实现结构风险最小化的放松,以及推导学习问题的归纳错误率。最后,引入了对偶误差的泛化和不可知情况的哈明图最优学习算法,通过最大熵程序实现最优学习。
Sep, 2023
提出了一种关于最小二倍经验风险下界的理论证明,并明确了最小二倍经验风险学习算法的特点,其中包括极限对称性和最小随机化 “投票” 程序。
Jun, 2016
本研究提出一种新的框架,超越了传统统一收敛方法的限制,将排列不变预测器的交叉检验误差转化为高概率风险界,并通过 Haussler, Littlestone, 和 Warmuth 的一种算法在二元分类中实现了最优 PAC 界限。在多类分类、部分假设分类和实现有限的回归等三种不同场合中,我们证明了该框架的优越性能。
Apr, 2023
本文提出一种基于 PAC 学习框架的约束学习方法,该方法通过对经验风险最小化规则进行约束来解决分类问题中的偏差、不公平和不稳定性等问题,研究表明该方法能够实现约束学习的泛化。
Jun, 2020
定义可计算的计算度量空间上二元分类的可计算 PAC 学习,提供解决 ERM 学习器可计算性的充分条件,限制 ERM 学习器的 Weihrauch 度,展示一种假设类,尽管底层类具有 PAC 可学性,但它不允许具有可计算采样函数的任何适当的可计算 PAC 学习器。
Nov, 2021
针对多数表决在二元分类中的行为,提出了一种风险界定 ——C-bound,考虑到选民的平均质量和平均分歧,结合具有自我包容性的 PAC-Bayesian 分析可从训练数据中估计 C-bound,最终提出基于 C-bound 最小化的 MinCq 算法,达到与 AdaBoost 和 SVM 相当的效果。
Mar, 2015