Nov, 2012

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

PDF
TL;DR该研究提供了关于线性分隔符的标签高效、多项式时间、被动和主动学习的新结果，并证明了在近乎对数凹的分布下，主动学习提供了超过被动学习的指数级改进。在此基础上，为这种问题提供了一种计算上高效的 PAC 算法，其样本复杂度是最优的 (最多相差一个常数因子)。此外，提供了第一个关于多项式时间 PAC 算法的界限，该算法在通用的数据分布下对一个有趣的无限类假设函数是紧密的，并取得了重大进展。同时，本研究还针对数据可能不是线性可分的情况，提供了被动和主动学习的新限制。
active learningpassive learninglinear separatorssample complexitylog-concave distributions
发现论文，激发创造
  • 利用本地化能力高效学习受到噪声影响的线性分离器

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

    Jul, 2013

  • 关于局部感知机具有优势的半空间对抗噪声最优学习

    本文介绍了一种 Perceptron-like 在线主动学习算法，能够以近乎最优的标签复杂度和样本复杂度下，学习噪声容限在总概率最多为 ν，样本标签误差率 ε 和输入维度 d 给定的 R^d 中同质半空间。该算法的先前版本针对噪声容限存在的情况，不能同时获得标签和样本复杂度多项式级别的优良性能。经过一定的假设前提下，支持 5 罕见的瑕疵。

    Dec, 2020

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

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

    Jun, 2014

  • 高效稀疏半空间的主动学习

    本文提供了一个计算有效的算法，用于解决高维空间中的 PAC 主动学习问题，其中数据遵循某些分布假设，该算法在少量的标记查询下使用稀疏的半空间学习，能够达到 O（t polylog（d，1/ϵ））的标记复杂度。

    May, 2018

  • 基于 S-Concave 分布的样本和计算高效的学习算法

    本文提出了一种新的 $s$-concave 分布类别，基于凸几何工具研究了该分布类别并将其应用于学习算法中，在边缘化算子下提供了有关 $s$-concave 分布的性质和一些学习问题的收敛界限。

    Mar, 2017

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

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

    Mar, 2015

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

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

    Jul, 2013

  • 混合物的高效样本学习

    提出了一种基于混合学习算法的 PAC 学习方法，该算法可用于密度估计中的概率分布，其中包含了学习概率分布，学习混合分布等，其中混合分布包括轴向高斯混合分布，高斯混合分布和对数凹分布。

    Jun, 2017

  • 分布式学习，通信复杂度和隐私

    讨论分布式数据的 PAC 学习问题，分析了涉及的基本通信复杂性问题，包括教学维度和错误绑定。针对特定概念类别，如合取、奇偶函数和决策列表等，给出上下界限。讨论了如何通过增强来在分布式环境下进行一般性通信，以及如何在不确定环境下实现低通信回归。同时，还考虑了隐私性，包括差分隐私和分布式隐私。

    Apr, 2012

  • 具有 Tsybakov 噪声的高效主动学习半空间问题的非凸优化方法

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

    Oct, 2023