利用本地化能力高效学习受到噪声影响的线性分离器
研究了线性分离器在 Massart 噪声下的可学习性,提供了第一个在此噪声模型下可以多项式时间学习线性分离器的算法,并证明了传统算法不能达到理想误差。我们的算法是基于活动学习的,并且具有对数标签复杂度。
Mar, 2015
该研究提供了关于线性分隔符的标签高效、多项式时间、被动和主动学习的新结果,并证明了在近乎对数凹的分布下,主动学习提供了超过被动学习的指数级改进。在此基础上,为这种问题提供了一种计算上高效的 PAC 算法,其样本复杂度是最优的 (最多相差一个常数因子)。此外,提供了第一个关于多项式时间 PAC 算法的界限,该算法在通用的数据分布下对一个有趣的无限类假设函数是紧密的,并取得了重大进展。同时,本研究还针对数据可能不是线性可分的情况,提供了被动和主动学习的新限制。
Nov, 2012
本文介绍了一种 Perceptron-like 在线主动学习算法,能够以近乎最优的标签复杂度和样本复杂度下,学习噪声容限在总概率最多为 ν,样本标签误差率 ε 和输入维度 d 给定的 R^d 中同质半空间。该算法的先前版本针对噪声容限存在的情况,不能同时获得标签和样本复杂度多项式级别的优良性能。经过一定的假设前提下,支持 5 罕见的瑕疵。
Dec, 2020
提出了一个简单的噪声 - 鲁棒性基于边缘的主动学习算法来查找同质 (通过原点) 的线性分离器,并分析了标签受噪声干扰时的误差收敛性。我们证明了当所施加的噪声满足 Tsybakov 低噪声条件时,算法能够适应未知的噪声水平,并在多对数因子上实现最优统计速率。同时,我们为基于边缘的主动学习算法在会员查询合成场景下的 Tsybakov 噪音条件 (TNC) 导出了下限。我们的分析可能为其他形式的下限提供了见解。
Jun, 2014
提出一种基于统计学习框架的主动学习算法,能够高效地处理随机分类噪声和差分隐私,且可将其转换为能容忍分类噪声的主动学习算法,同时也实现了用指数级别的误差提高标签节约的差分隐私主动学习算法.
Jul, 2013
研究如何在噪音下进行有效的学习,在保证计算效率的前提下设计了一种主动学习算法,并根据半空间的结构进行加权和风险最小化等方法的技术优化,解决了恶意噪声等问题并且具有良好的属性效率和样本复杂度。
Jun, 2020
通过理论证明及实验证据表明,对数据集加入一些对抗性的噪声可以给原始数据集注入一个分布扰动,并且这些噪声在特定条件下可以很轻易地被分类器分类。
Jun, 2022
本文提出了一种半空间主动学习算法,能够在存在噪声和尽可能少的标签情况下,有效地学习均匀分布在单位球上的均匀半空间,并证明其在两种噪声情况下均达到了近似最优标签复杂度。
Feb, 2017
在存在噪音标签的情况下,我们研究了在线分类问题。通过一般的核来建模噪音机制,为任何特征 - 标签对指定了一个(已知)噪音标签分布集合。每个时间步骤,对手根据实际的特征 - 标签对从核指定的分布集合中选择一个未知分布,并根据所选分布生成噪音标签。学习者根据迄今为止观察到的实际特征和噪音标签进行预测,如果预测与真实情况不同,则遭受损失 1(否则为 0)。预测质量通过计算有限时间视野 T 上的极小化风险来量化。我们证明了对于广泛的自然噪音核、对手选择的特征和有限类别的标记函数,极小化风险可以上界独立于时间视野并以标记函数类别尺寸的对数形式增长。然后,我们通过随机顺序覆盖的概念将这些结果推广到无限类别和随机生成的特征。我们的结果通过对在线条件分布估计的新颖归约提供了直观理解,并且扩展并包含了 Ben-David 等人(2009)的研究结果,具有显著的广泛性。
Sep, 2023
针对模型类如何拟合标记数据的问题,我们提出了一种计算学习能力的方法,可以使用较小的数据量得出精确结果。该方法也适用于二元分类问题,并在多种真实和合成数据集上得到了验证。
May, 2018