AAAIJun, 2014

基于 Margin 的噪声自适应主动学习及在 Tsybakov 噪声条件下的下界

PDF
TL;DR提出了一个简单的噪声 - 鲁棒性基于边缘的主动学习算法来查找同质 (通过原点) 的线性分离器，并分析了标签受噪声干扰时的误差收敛性。我们证明了当所施加的噪声满足 Tsybakov 低噪声条件时，算法能够适应未知的噪声水平，并在多对数因子上实现最优统计速率。同时，我们为基于边缘的主动学习算法在会员查询合成场景下的 Tsybakov 噪音条件 (TNC) 导出了下限。我们的分析可能为其他形式的下限提供了见解。
发现论文，激发创造
  • 具有 Tsybakov 噪声的高效主动学习半空间问题的非凸优化方法

    通过设计基于非凸优化的算法，本文研究了具有 Tsybakov 噪声的计算和标签效率 PAC 主动学习上的 d - 维半空间问题，其标签复杂度较先前已知的高效被动或主动算法与该设置下的信息理论下界之间的差距缩小了。

    Oct, 2023

  • 利用本地化能力高效学习受到噪声影响的线性分离器

    本研究提出了一种新的方法来设计计算效率高、能够容忍噪声的学习算法，并通过设计具有改善噪声容忍度的线性分离器学习算法来证明其有效性。在恶意噪声模型和对抗标签噪声模型方面展开讨论，并为这些模型提供了多项式时间算法，以在各自的噪声下学习线性分类器。在主动学习模型下，算法实现标签复杂度对于误差参数的对数对数依赖。

    Jul, 2013

  • 主动学习的极小极大分析

    该研究通过各种噪声模型，建立了关于利用一般假设类进行主动学习的最小极大标签复杂性的无分布上限和下限。结果表明，利用 VC 类进行主动学习的最小极大标签复杂性始终比被动学习的复杂性小。在噪声高的情况下，给定 VC 维数的所有主动学习问题都具有大致相同的最小极大标签复杂度，而在噪声低的情况下，标签复杂性可以用一个称为「星号数」的简单组合复杂度衡量。

    Oct, 2014

  • 噪声容忍和差分隐私的统计主动学习算法

    提出一种基于统计学习框架的主动学习算法，能够高效地处理随机分类噪声和差分隐私，且可将其转换为能容忍分类噪声的主动学习算法，同时也实现了用指数级别的误差提高标签节约的差分隐私主动学习算法.

    Jul, 2013

  • 在对数凹分布下线性分界器的主动学习和被动学习

    该研究提供了关于线性分隔符的标签高效、多项式时间、被动和主动学习的新结果，并证明了在近乎对数凹的分布下，主动学习提供了超过被动学习的指数级改进。在此基础上，为这种问题提供了一种计算上高效的 PAC 算法，其样本复杂度是最优的 (最多相差一个常数因子)。此外，提供了第一个关于多项式时间 PAC 算法的界限，该算法在通用的数据分布下对一个有趣的无限类假设函数是紧密的，并取得了重大进展。同时，本研究还针对数据可能不是线性可分的情况，提供了被动和主动学习的新限制。

    Nov, 2012

  • 学习具有 Tsybakov 噪声的半空间的多项式时间算法

    本文首次提出了针对在 Tsybakov 噪声情况下 PAC 学习均匀半空间的可行的多项式时间算法，并且证明了该算法对于如对称型对数凹分布之类的广泛应用的分布成功率显著

    Oct, 2020

  • 受限噪音下线性分隔器的高效学习

    研究了线性分离器在 Massart 噪声下的可学习性，提供了第一个在此噪声模型下可以多项式时间学习线性分离器的算法，并证明了传统算法不能达到理想误差。我们的算法是基于活动学习的，并且具有对数标签复杂度。

    Mar, 2015

  • 关于损失和基于不确定性的主动学习算法的收敛性

    我们研究了在各种假设下，损失和基于不确定性的主动学习算法的收敛速度。首先，我们给出了一组条件，用于线性分类器和线性可分数据集，以展示对基于损失采样和不同损失函数的收敛速度保证。其次，我们提供了一个框架，通过应用已知的随机梯度下降算法的收敛速度保证，来推导基于损失采样的收敛速度界限。最后，我们提出了一种主动学习算法，它结合了点采样和随机 Polyak 步长。我们展示了对平滑凸损失函数的此算法进行收敛速度保证的采样条件。我们的数值结果证明了我们提出的算法的效率。

    Dec, 2023

  • 非参数主动学习用于成本敏感分类

    设计了一种用于成本敏感分类的通用非参数主动学习算法，通过构建每个标签的预测成本函数的置信区间，该算法选择最具信息量的向量点，通过仅查询可能是最小的预测成本来与其交互，证明了该算法在与向量空间的交互数量方面达到了最优收敛速率，并且在对 Tsybakov 的噪声假设的一般版本中，通过边界决策的概率质量明确表征了相对于相应被动学习方法的收益，并且通过提供匹配的（仅差对数因子的）下界证明了获得上界的接近最优性。

    Sep, 2023

  • 嘈杂贝叶斯主动学习

    本文提出了一种基于最大化外部 Jensen-Shannon 分歧的标签查询采样策略，用于噪声贝叶斯主动学习中的真实标签生成函数的识别，并提供了上下界，表现优于以往的方法。

    Dec, 2013