本文介绍了一种 Perceptron-like 在线主动学习算法,能够以近乎最优的标签复杂度和样本复杂度下,学习噪声容限在总概率最多为 ν,样本标签误差率 ε 和输入维度 d 给定的 R^d 中同质半空间。该算法的先前版本针对噪声容限存在的情况,不能同时获得标签和样本复杂度多项式级别的优良性能。经过一定的假设前提下,支持 5 罕见的瑕疵。
Dec, 2020
研究如何在噪音下进行有效的学习,在保证计算效率的前提下设计了一种主动学习算法,并根据半空间的结构进行加权和风险最小化等方法的技术优化,解决了恶意噪声等问题并且具有良好的属性效率和样本复杂度。
Jun, 2020
本文提供了一个计算有效的算法,用于解决高维空间中的 PAC 主动学习问题,其中数据遵循某些分布假设,该算法在少量的标记查询下使用稀疏的半空间学习,能够达到 O(t polylog(d,1/ϵ))的标记复杂度。
May, 2018
研究在独立于分布的情况下学习对抗性鲁棒的半空间问题,在可实现的情况下,给出了对抗性扰动集的必要和充分条件,即半空间可以高效地实现鲁棒性学习,并在存在随机标签噪声时提出了一个简单的、计算效率高的算法。
May, 2020
研究池化主动学习半平面问题,重点挖掘了实现的情况下侵略性方法的可行性及其理论保证,证明在合理假设下其具有实用性;理论和实验结果显示此方法比较温和的方法更具优势,可以更好降低标签复杂度,不仅阐述了实现的情况下其近似保证,还说明了相应启发式策略在其他情况下也可以成功使用。
Aug, 2012
通过设计基于非凸优化的算法,本文研究了具有 Tsybakov 噪声的计算和标签效率 PAC 主动学习上的 d - 维半空间问题,其标签复杂度较先前已知的高效被动或主动算法与该设置下的信息理论下界之间的差距缩小了。
Oct, 2023
研究学习同质半空间的非说服学派问题,证明对于一类结构化分布,包括对数凹分布,在误分类误差 O(opt)+eps 下,非凸 SGD 有效地收敛到解决方案。相比之下,证明优化任何凸代理本质上会导致 ω(opt)的误分类误差,即使在高斯边际分布下。
研究使用高斯分布下随机分类噪声学习半空间的问题,证明算法和统计查询下限,在此基本问题中,存在令人惊讶的信息计算差距,给出了正面的结果和近乎匹配的复杂度,并展示了算法的复杂度下界
Jul, 2023
本文提出了一个以多项式回归和定位技术相结合的算法, 用于在 d - 球上均匀分布的情况下,实现对零时最佳半空间分类器的确定性多项式近似方案(PTAS),误差保证为 opt 的 (1+μ)+ε 倍, 并提供了比以前使用定位技术的算法更加优越的针对全局的误差近似解决方案。
Oct, 2014
学习图上的顶点的二元分类器,特别关注具有特定抽象意义的凸分区类作为分类器,通过多项式时间算法和结构洞见,以及与底层图的关联进行学习,进行了有关监督学习、在线学习和主动学习中的凸分区类的研究和结果验证。
May, 2024