列表样本压缩与均匀收敛
本文研究了样本压缩方案与统计学习之间的关系,探究了学习能力与可压缩性之间的等价性,并在多类别分类问题中研究了统计学习理论。作者证明了在零 / 一损失分类的情况下,可学习性等价于对数样本大小的压缩,并且一致收敛意味着恒定大小的压缩。作者还探究了在 Vapnik 的一般学习设置下压缩能力与学习能力的等价性,并给出了一些在多类别分类问题中的应用。
Oct, 2016
本文提出采样压缩序列作为一种学习算法的抽象形式,并回答了问题:每个概念类别 C 具有 VC 维度 d 的序列都具有指数大小的采样压缩序列,这得益于对 VC 维下二进制矩阵的逼近极小现象。
Mar, 2015
本研究提出一种新的框架,超越了传统统一收敛方法的限制,将排列不变预测器的交叉检验误差转化为高概率风险界,并通过 Haussler, Littlestone, 和 Warmuth 的一种算法在二元分类中实现了最优 PAC 界限。在多类分类、部分假设分类和实现有限的回归等三种不同场合中,我们证明了该框架的优越性能。
Apr, 2023
每个学习二进制假设类都具有有限的 VC 维度且可采用一个与 VC 维度无关的有限函数大小的样本压缩方案,然而,每个学习多类假设类都具有有限的 DS 维度且不具有一个与 DS 维度无关的有限函数大小的样本压缩方案。
Aug, 2023
研究了具有公共数据访问的私人分布学习问题,通过使用公共和私有样本来输出一个对分布 p 的估计,同时满足纯差分隐私的隐私约束。结果显示,Q 类的公共 - 私有可学习性与 Q 类的样本压缩方案以及中间概念列表学习的存在有关,并且将这种连接利用起来恢复了以前关于 Gaussians 和新的结果,包括关于高斯 $k$ 混合物的样本复杂性上界、关于自适应和分布转移抵抗学习的结果,以及在承担混合和分布乘积时广义公共 - 私有学习的闭合特性。最后,利用与列表学习的联系,结果显示对于 Gaussians 在 R^d 中,至少需要 d 个公共样本进行私人可学习性,这接近已知的 d+1 个公共样本的上界。
Aug, 2023
研究一种协作 PAC 学习的变体,旨在学习每个数据分布的准确分类器,同时最小化从这些数据分布中所抽取的样本数总量。给出基于经验风险最小化算法的学习方法,并且分析依赖于增强的假设类的 VC 维度的上界。在计算效率方面,证明了在一般情况下,基于增强的假设类的 ERM 是 NP 难的,为不存在计算效率高的学习器提供了依据,但对于两种特殊情况,给出了既有样本效率又有计算效率的学习器。
Feb, 2024
本文研究了一种更贴近于实际机器学习应用的学习模型,但仍然在学习可能性方面提供了完整的理论,并通过探索万能学习问题的学习曲线发现,每个概念类的学习曲线都以指数、线性或任意缓慢的速率衰减,并提出了最优学习算法来实现每种情况下最佳的可能速率。
Nov, 2020
讨论分布式数据的 PAC 学习问题,分析了涉及的基本通信复杂性问题,包括教学维度和错误绑定。针对特定概念类别,如合取、奇偶函数和决策列表等,给出上下界限。讨论了如何通过增强来在分布式环境下进行一般性通信,以及如何在不确定环境下实现低通信回归。同时,还考虑了隐私性,包括差分隐私和分布式隐私。
Apr, 2012
本文提出一种基于 PAC 学习框架的约束学习方法,该方法通过对经验风险最小化规则进行约束来解决分类问题中的偏差、不公平和不稳定性等问题,研究表明该方法能够实现约束学习的泛化。
Jun, 2020
提出了一种基于混合学习算法的 PAC 学习方法,该算法可用于密度估计中的概率分布,其中包含了学习概率分布,学习混合分布等,其中混合分布包括轴向高斯混合分布,高斯混合分布和对数凹分布。
Jun, 2017