本文介绍了一种 Perceptron-like 在线主动学习算法,能够以近乎最优的标签复杂度和样本复杂度下,学习噪声容限在总概率最多为 ν,样本标签误差率 ε 和输入维度 d 给定的 R^d 中同质半空间。该算法的先前版本针对噪声容限存在的情况,不能同时获得标签和样本复杂度多项式级别的优良性能。经过一定的假设前提下,支持 5 罕见的瑕疵。
Dec, 2020
研究如何在噪音下进行有效的学习,在保证计算效率的前提下设计了一种主动学习算法,并根据半空间的结构进行加权和风险最小化等方法的技术优化,解决了恶意噪声等问题并且具有良好的属性效率和样本复杂度。
Jun, 2020
本文提出了一种半空间主动学习算法,能够在存在噪声和尽可能少的标签情况下,有效地学习均匀分布在单位球上的均匀半空间,并证明其在两种噪声情况下均达到了近似最优标签复杂度。
Feb, 2017
本文提出了一个以多项式回归和定位技术相结合的算法, 用于在 d - 球上均匀分布的情况下,实现对零时最佳半空间分类器的确定性多项式近似方案(PTAS),误差保证为 opt 的 (1+μ)+ε 倍, 并提供了比以前使用定位技术的算法更加优越的针对全局的误差近似解决方案。
Oct, 2014
通过设计基于非凸优化的算法,本文研究了具有 Tsybakov 噪声的计算和标签效率 PAC 主动学习上的 d - 维半空间问题,其标签复杂度较先前已知的高效被动或主动算法与该设置下的信息理论下界之间的差距缩小了。
Oct, 2023
本文提出一种能够在存在恶意噪声的条件下有效学习欧氏空间中均匀半空间的 PAC 算法,该算法框架下的样本复杂度接近最优,主要用到了矩阵 Chernoff 型不等式和对错误噪声模型的推广。
Feb, 2021
研究池化主动学习半平面问题,重点挖掘了实现的情况下侵略性方法的可行性及其理论保证,证明在合理假设下其具有实用性;理论和实验结果显示此方法比较温和的方法更具优势,可以更好降低标签复杂度,不仅阐述了实现的情况下其近似保证,还说明了相应启发式策略在其他情况下也可以成功使用。
Aug, 2012
研究分布无关的半空间在 Massart 噪声下的拟准确性学习问题,给出了一个计算复杂度为多项式时间且误分类错误率为 η+ε 的算法。
Jun, 2019
研究使用高斯分布下随机分类噪声学习半空间的问题,证明算法和统计查询下限,在此基本问题中,存在令人惊讶的信息计算差距,给出了正面的结果和近乎匹配的复杂度,并展示了算法的复杂度下界
Jul, 2023
本文首次提出了针对在 Tsybakov 噪声情况下 PAC 学习均匀半空间的可行的多项式时间算法,并且证明了该算法对于如对称型对数凹分布之类的广泛应用的分布成功率显著
Oct, 2020